# RFC: Add `final class Vector` to PHP

- Thread: https://externals.io/message/116048
- Original archive: https://news-web.php.net/php.internals/116048
- Started by tyson andre on 2021-09-17T02:09:55+00:00
- Messages: 42
- RFC: final class Deque (Inactive) — https://externals.io/rfc/deque.md
- RFC: final class Vector (Inactive) — https://externals.io/rfc/vector.md
- Page 1 of 2: messages 1 to 25 (25 per page, add `?page=N` to the URL)
- Next page: https://externals.io/message/116048.md?page=2
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · RFCs at https://externals.io/rfc.md · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #116048 — tyson andre — 2021-09-17T02:09:55+00:00

URL: https://externals.io/message/116048#116048

Hi internals,

I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP.

PHP's native `array` type is rare among programming language in that it is used as an associative map of values, but also needs to support lists of values.
In order to support both use cases while also providing a consistent internal array HashTable API to the PHP's internals and PECLs, additional memory is needed to track keys (https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html - around twice as much as is needed to just store the values due to needing space both for the string pointer and int key in a Bucket, for non-reference counted values)).
Additionally, creating non-constant arrays will allocate space for at least 8 elements to make the initial resizing more efficient, potentially wasting memory.

It would be useful to have an efficient variable-length container in the standard library for the following reasons: 

1. To save memory in applications or libraries that may need to store many lists of values and/or run as a CLI or embedded process for long periods of time 
   (in modules identified as using the most memory or potentially exceeding memory limits in the worst case)
   (both in userland and in native code written in php-src/PECLs)
2. To provide a better alternative to `ArrayObject` and `SplFixedArray` for use cases 
   where objects are easier to use than arrays - e.g. variable sized collections (For lists of values) that can be passed by value to be read and modified.
3. To give users the option of stronger runtime guarantees that property, parameter, or return values really contain a list of values without gaps, that array modifications don't introduce gaps or unexpected indexes, etc.

Thoughts on Vector?

P.S. The functionality in this proposal can be tested/tried out at https://pecl.php.net/teds (under the class name `\Teds\Vector` instead of `\Vector`).
(That is a PECL I created earlier this year for future versions of iterable proposals, common data structures such as Vector/Deque, and less commonly used data structures that may be of use in future work on implementing other data structures)

Thanks,
Tyson

---

## #116049 — Marco Pivetta — 2021-09-17T02:19:03+00:00

URL: https://externals.io/message/116048#116049 · In reply to: #116048

Hey Tyson,

Would it perhaps make sense to drag in php-ds, which has matured quite a
bit over the years? I'm referring to:
https://www.php.net/manual/en/class.ds-sequence.php

Is what you are suggesting with `Vector` different from it?

Note: For some reason, I can't quote your post and then reply, so it will
be a top-post 🤷‍♀️



> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add
> `final class Vector` to PHP.
>
> PHP's native `array` type is rare among programming language in that it is
> used as an associative map of values, but also needs to support lists of
> values.
> In order to support both use cases while also providing a consistent
> internal array HashTable API to the PHP's internals and PECLs, additional
> memory is needed to track keys (
> https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html
> - around twice as much as is needed to just store the values due to needing
> space both for the string pointer and int key in a Bucket, for
> non-reference counted values)).
> Additionally, creating non-constant arrays will allocate space for at
> least 8 elements to make the initial resizing more efficient, potentially
> wasting memory.
>
> It would be useful to have an efficient variable-length container in the
> standard library for the following reasons:
>
> 1. To save memory in applications or libraries that may need to store many
> lists of values and/or run as a CLI or embedded process for long periods of
> time
>    (in modules identified as using the most memory or potentially
> exceeding memory limits in the worst case)
>    (both in userland and in native code written in php-src/PECLs)
> 2. To provide a better alternative to `ArrayObject` and `SplFixedArray`
> for use cases
>    where objects are easier to use than arrays - e.g. variable sized
> collections (For lists of values) that can be passed by value to be read
> and modified.
> 3. To give users the option of stronger runtime guarantees that property,
> parameter, or return values really contain a list of values without gaps,
> that array modifications don't introduce gaps or unexpected indexes, etc.
>
> Thoughts on Vector?
>
> P.S. The functionality in this proposal can be tested/tried out at
> https://pecl.php.net/teds (under the class name `\Teds\Vector` instead of
> `\Vector`).
> (That is a PECL I created earlier this year for future versions of
> iterable proposals, common data structures such as Vector/Deque, and less
> commonly used data structures that may be of use in future work on
> implementing other data structures)
>
> Thanks,
> Tyson

---

## #116050 — Levi Morrison via internals — 2021-09-17T02:50:09+00:00

URL: https://externals.io/message/116048#116050 · In reply to: #116048

>
> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP.
>
> PHP's native `array` type is rare among programming language in that it is used as an associative map of values, but also needs to support lists of values.
> In order to support both use cases while also providing a consistent internal array HashTable API to the PHP's internals and PECLs, additional memory is needed to track keys (https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html - around twice as much as is needed to just store the values due to needing space both for the string pointer and int key in a Bucket, for non-reference counted values)).
> Additionally, creating non-constant arrays will allocate space for at least 8 elements to make the initial resizing more efficient, potentially wasting memory.
>
> It would be useful to have an efficient variable-length container in the standard library for the following reasons:
>
> 1. To save memory in applications or libraries that may need to store many lists of values and/or run as a CLI or embedded process for long periods of time
>    (in modules identified as using the most memory or potentially exceeding memory limits in the worst case)
>    (both in userland and in native code written in php-src/PECLs)
> 2. To provide a better alternative to `ArrayObject` and `SplFixedArray` for use cases
>    where objects are easier to use than arrays - e.g. variable sized collections (For lists of values) that can be passed by value to be read and modified.
> 3. To give users the option of stronger runtime guarantees that property, parameter, or return values really contain a list of values without gaps, that array modifications don't introduce gaps or unexpected indexes, etc.
>
> Thoughts on Vector?
>
> P.S. The functionality in this proposal can be tested/tried out at https://pecl.php.net/teds (under the class name `\Teds\Vector` instead of `\Vector`).
> (That is a PECL I created earlier this year for future versions of iterable proposals, common data structures such as Vector/Deque, and less commonly used data structures that may be of use in future work on implementing other data structures)
>
> Thanks,
> Tyson
> --
> 
> To unsubscribe, visit: https://www.php.net/unsub.php
>

I'm okay with a final Vector class in general. I don't love the
proposed API but don't hate it either. Feedback on that at the end.

What I would _love_ is a `vec` type from hacklang, which is similar to
this but pass-by-value, copy-on-write like an array. Of course, this
would require engine work and I understand it isn't as simple to add.

Feedback on API:

-  `indexOf` returning `false` instead of `null` when it cannot be
found. If we are keeping this method (which I don't like, because
there's no comparator), please return `null` instead of false. The
language has facilities for working with null like `??`, so please
prefer that when it isn't needed for BC (like this, this is a new
API).
- `contains` also doesn't have a comparator.
-  Similarly but less strongly, I don't like the filter callable
returning `mixed` -- please just make it `bool`.
- I don't know what `setSize(int $size)` does. What does it do if the
current size is less than `$size`? What about if its current size is
greater? I suspect this is about capacity, not size, but without docs
I am just guessing.

---

## #116053 — tyson andre — 2021-09-17T03:33:34+00:00

URL: https://externals.io/message/116048#116053 · In reply to: #116050

Hi Levi Morrison,

> I'm okay with a final Vector class in general. I don't love the
> proposed API but don't hate it either. Feedback on that at the end.
> 
> What I would _love_ is a `vec` type from hacklang, which is similar to
> this but pass-by-value, copy-on-write like an array. Of course, this
> would require engine work and I understand it isn't as simple to add.

Yeah, as mentioned in https://wiki.php.net/rfc/vector#adding_a_native_type_instead_is_vec , it would require a massive amount of work.

- A standard library for dealing with `vec`, filtering it, etc
- Userland libraries and PECLs would need to deal with a third complex type different from array/object that probably couldn't be implicitly 
- Extensive familiarity with opcache and the JIT for x86 and other platforms beyond what I have
- Willingness to do that with the uncertainty the final implementation would get 2/3 votes with backwards compatibility objections, etc.

> Feedback on API:
> 
> -  `indexOf` returning `false` instead of `null` when it cannot be
> found. If we are keeping this method (which I don't like, because
> there's no comparator), please return `null` instead of false. The
> language has facilities for working with null like `??`, so please
> prefer that when it isn't needed for BC (like this, this is a new
> API).

I hadn't thought about that - that seems reasonable since I don't remember anything else adding indexOf as a method name.

> - `contains` also doesn't have a comparator.

I was considering proposing `->any(callable)` and `->all(callable)` extensions if this passed.
I'm not quite sure what you mean by a comparator for contains. There'd have to be a way to check if a raw closure is contained.

> -  Similarly but less strongly, I don't like the filter callable
> returning `mixed` -- please just make it `bool`.

The filter callable is something that would be passed into the filter function. The return value would be checked for truthiness.
The phpdoc in the documentation could be changed, but that wouldn't change the implementation.

> - I don't know what `setSize(int $size)` does. What does it do if the
> current size is less than `$size`? What about if its current size is
> greater? I suspect this is about capacity, not size, but without docs
 > I am just guessing.

It's the same behavior as https://www.php.net/manual/en/splfixedarray.setsize.php . It's about size, not capacity.

> Change the size of an array to the new size of size.
> If size is less than the current array size, any values after the new size will be discarded.
> If size is greater than the current array size, the array will be padded with null values.

I'd planned to add phpdoc documentation and examples before starting a vote to document the behavior and thrown exceptions of the proposed methods.

Thanks,
Tyson

---

## #116054 — tyson andre — 2021-09-17T04:18:45+00:00

URL: https://externals.io/message/116048#116054 · In reply to: #116049

Hey Marco Pivetta,

> Would it perhaps make sense to drag in php-ds, which has matured quite a bit over the years? I'm referring to: https://www.php.net/manual/en/class.ds-sequence.php
> 
> Is what you are suggesting with `Vector` different from it?
> 
> Note: For some reason, I can't quote your post and then reply, so it will be a top-post 🤷‍♀️

This was outlined in the section https://wiki.php.net/rfc/vector#why_not_use_php-ds_instead before I sent out the announcement. To expand on that,

This has been asked about multiple times in threads on unrelated proposals (https://externals.io/message/112639#112641 and https://externals.io/message/93301#93301 years ago) throughout the years,
but the maintainer of php-ds had a long term goal of developing the separately from php's release cycle (and was still focusing on the PECL when I'd asked on the GitHub issue in the link almost a year ago).

- There have been no proposals from the maintainer to do that so far, that was what the maintainer mentioned as a long term plan.
- I personally doubt having it developed separately from php's release cycle would be accepted by voters (e.g. if unpopular decisions couldn't be voted against), or how backwards compatibility would be handled in that model, and had other concerns. (e.g. API debates such as https://externals.io/message/93301#93301)
- With php-ds itself getting merged anytime soon seeming unlikely to me, I decided to start independently working on efficient data structure implementations.

I don't see dragging it in (against the maintainer's wishes) as a viable option for many, many, many reasons.
But having efficient datastructures in PHP's core is still useful.

- While PECL development outside of php has its benefits for development and ability to make new features available in older php releases,
  it's less likely that application and 
  library authors will start making use of those data structures because many users won't have any given PECL already installed. 
  (though php-ds also publishes a polyfill, it would not have the cpu and memory savings, and add its own overhead)

- Additionally, users (and organizations using PHP) can often make stronger assumptions on
  backwards compatibility and long-term availability of functionality that is merged into PHP's core.

So the choice of feature set, some names, signatures, and internal implementation details are different, because this is reimplementing a common datastructure found in different forms in many languages.
It's definitely a mature project, but I personally feel like reimplementing this (without referring to the php-ds source code and without copying the entire api as-is) is the best choice to add efficient data structures to core while respecting the maintainer's work on the php-ds project and their wish to maintain control over the php-ds project.

As a result, I've been working on implementing data structures such as Vector based on php-src's data structure implementations (mostly SplFixedArray and ArraayObject) instead (and based on my past PECL/RFC experience, e.g. with runkit7/igbinary)

Regards,
Tyson

---

## #116055 — Levi Morrison via internals — 2021-09-17T04:46:59+00:00

URL: https://externals.io/message/116048#116055 · In reply to: #116053

> > […]
>
> I was considering proposing `->any(callable)` and `->all(callable)` extensions if this passed.
> I'm not quite sure what you mean by a comparator for contains. There'd have to be a way to check if a raw closure is contained.

I mean that there isn't a way to provide a custom way to compare for
equality. One way to accomplish this is to have a signature like:
    function contains(T $value, ?callable(T, T):bool $comparator = null): bool

The same goes for `indexOf`.

> > […]
>
> It's the same behavior as https://www.php.net/manual/en/splfixedarray.setsize.php . It's about size, not capacity.
>
> > […]
>
> I'd planned to add phpdoc documentation and examples before starting a vote to document the behavior and thrown exceptions of the proposed methods.

I would rather see multiple methods like:
    function truncateTo(int $size)
    function padEnd(int $length, $value) // allows more than just null
    function padBeginning(int $length, $value)
And one or more for increasing/ensuring capacity without changing size.

---

## #116056 — Matthew Brown — 2021-09-17T04:48:38+00:00

URL: https://externals.io/message/116048#116056 · In reply to: #116053

On Thu, 16 Sept 2021 at 23:33, tyson andre <tysonandre775@hotmail.com>
wrote:

> Yeah, as mentioned in
> https://wiki.php.net/rfc/vector#adding_a_native_type_instead_is_vec , it
> would require a massive amount of work.
>
> - A standard library for dealing with `vec`, filtering it, etc
> - Userland libraries and PECLs would need to deal with a third complex
> type different from array/object that probably couldn't be implicitly
> - Extensive familiarity with opcache and the JIT for x86 and other
> platforms beyond what I have
> - Willingness to do that with the uncertainty the final implementation
> would get 2/3 votes with backwards compatibility objections, etc.
>

I feel like the standard library could be added in userland first, and then
corresponding faster implementations could arrive in the std lib.

But the last point is a really important one, and feels like a weakness in
the RFC process.

I know RFCs without implementations are generally frowned upon, but if
2/3rds of the community agreed that they wanted some sort of vec[] support
in theory, it might then free up the implementer(s) to take a more granular
approach to supporting vec. It could, for example, be an experimental
feature for a minor version.

Best wishes,

Matt

On Thu, 16 Sept 2021 at 23:33, tyson andre <tysonandre775@hotmail.com>
wrote:

> Hi Levi Morrison,
>
> > […]
>
> Yeah, as mentioned in
> https://wiki.php.net/rfc/vector#adding_a_native_type_instead_is_vec , it
> would require a massive amount of work.
>
> - A standard library for dealing with `vec`, filtering it, etc
> - Userland libraries and PECLs would need to deal with a third complex
> type different from array/object that probably couldn't be implicitly
> - Extensive familiarity with opcache and the JIT for x86 and other
> platforms beyond what I have
> - Willingness to do that with the uncertainty the final implementation
> would get 2/3 votes with backwards compatibility objections, etc.
>
> > […]
>
> I hadn't thought about that - that seems reasonable since I don't remember
> anything else adding indexOf as a method name.
>
> > […]
>
> I was considering proposing `->any(callable)` and `->all(callable)`
> extensions if this passed.
> I'm not quite sure what you mean by a comparator for contains. There'd
> have to be a way to check if a raw closure is contained.
>
> > […]
>
> The filter callable is something that would be passed into the filter
> function. The return value would be checked for truthiness.
> The phpdoc in the documentation could be changed, but that wouldn't change
> the implementation.
>
> > […]
>
> It's the same behavior as
> https://www.php.net/manual/en/splfixedarray.setsize.php . It's about
> size, not capacity.
>
> > […]
> size will be discarded.
> > […]
> with null values.
>
> I'd planned to add phpdoc documentation and examples before starting a
> vote to document the behavior and thrown exceptions of the proposed methods.
>
> Thanks,
> Tyson
> --
> 
> To unsubscribe, visit: https://www.php.net/unsub.php

---

## #116057 — Matthew Brown — 2021-09-17T05:13:20+00:00

URL: https://externals.io/message/116048#116057 · In reply to: #116056

I can also give some in-the-trenches perspective of vec's utility, having
spent the last month and a half writing Hack. vec is a really useful data
structure to be able to use explicitly in code. It makes code that uses it
easier to understand.

The main benefit over Vector is that it could be used as a straightforward
replacement for array in many cases, with the same copy-on-write semantics
helping developers avoid spooky action-at-a-distance. I'm confident that by
the time that such a feature would be ready for primetime, there would be
tools in place to assist migrations. We could also presumably allow for
casts between vec and array.

And once opcache is sorted out, I'm also confident that the advice "using
vec will make your code a bit faster" would be a successful recruitment
tool.

Best wishes,

Matt

---

## #116058 — Pierre Joye — 2021-09-17T05:43:32+00:00

URL: https://externals.io/message/116048#116058 · In reply to: #116048

Hello Tyson,

Vector support would be very good. JIT can do a lot with them if we
have a clean Vector implementation, or even without JIT.

What is your base inspiration for Vector? I do like the pretty
standard C++ Vector implementation:

https://www.cplusplus.com/reference/vector/vector/

Where a Vector is initalizied with:

$myIntVector = vector<Integer>;

What is key for performance is also the alloc/realloc/free strategy.
In C++ (or most C or other languages custom) gives control to the
creators to define max size, capacity, etc.

If a non typed Vector is the goal, then I am less in need of it, still
good to have but not as good as a clear pure Vector support :).

Also I think it will be very good to have more details about what this
RFC proposes in the RFC. It is kind of hard to follow right now, with
all external links. RFCs are better if they act as a real
specification :)

Best,
Pierre


>
> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP.
>
> PHP's native `array` type is rare among programming language in that it is used as an associative map of values, but also needs to support lists of values.
> In order to support both use cases while also providing a consistent internal array HashTable API to the PHP's internals and PECLs, additional memory is needed to track keys (https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html - around twice as much as is needed to just store the values due to needing space both for the string pointer and int key in a Bucket, for non-reference counted values)).
> Additionally, creating non-constant arrays will allocate space for at least 8 elements to make the initial resizing more efficient, potentially wasting memory.
>
> It would be useful to have an efficient variable-length container in the standard library for the following reasons:
>
> 1. To save memory in applications or libraries that may need to store many lists of values and/or run as a CLI or embedded process for long periods of time
>    (in modules identified as using the most memory or potentially exceeding memory limits in the worst case)
>    (both in userland and in native code written in php-src/PECLs)
> 2. To provide a better alternative to `ArrayObject` and `SplFixedArray` for use cases
>    where objects are easier to use than arrays - e.g. variable sized collections (For lists of values) that can be passed by value to be read and modified.
> 3. To give users the option of stronger runtime guarantees that property, parameter, or return values really contain a list of values without gaps, that array modifications don't introduce gaps or unexpected indexes, etc.
>
> Thoughts on Vector?
>
> P.S. The functionality in this proposal can be tested/tried out at https://pecl.php.net/teds (under the class name `\Teds\Vector` instead of `\Vector`).
> (That is a PECL I created earlier this year for future versions of iterable proposals, common data structures such as Vector/Deque, and less commonly used data structures that may be of use in future work on implementing other data structures)
>
> Thanks,
> Tyson
> --
> 
> To unsubscribe, visit: https://www.php.net/unsub.php
>


-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #116059 — Christian Schneider — 2021-09-17T08:06:47+00:00

URL: https://externals.io/message/116048#116059 · In reply to: #116048

Am 17.09.2021 um 04:09 schrieb tyson andre <tysonandre775@hotmail.com>:
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP.


First of all: I don't have a strong opinion on a Vector class being useful or necessary.

But I have two comments about this RFC:
1) Using the very generic name Vector without any prefix/namespace seems dangerous and asking for BC breaks.
2) I don't like that this class is final. The reasons given in https://wiki.php.net/rfc/vector#final_class <https://wiki.php.net/rfc/vector#final_class> seem unconvincing to me and restrict the usage of Vector in a way which makes me question the usefulness to a big enough part of the PHP community.

These two reasons combined would make me reject the RFC at the current stage.

- Chris

---

## #116060 — Pierre Joye — 2021-09-17T08:32:37+00:00

URL: https://externals.io/message/116048#116060 · In reply to: #116059

Good afternoon Christian,

On Fri, Sep 17, 2021 at 3:07 PM Christian Schneider
<cschneid@cschneid.com> wrote:
>
> Am 17.09.2021 um 04:09 schrieb tyson andre <tysonandre775@hotmail.com>:
> > […]
>
>
> First of all: I don't have a strong opinion on a Vector class being useful or necessary.
>
> But I have two comments about this RFC:
> 1) Using the very generic name Vector without any prefix/namespace seems dangerous and asking for BC breaks.
> 2) I don't like that this class is final. The reasons given in https://wiki.php.net/rfc/vector#final_class <https://wiki.php.net/rfc/vector#final_class> seem unconvincing to me and restrict the usage of Vector in a way which makes me question the usefulness to a big enough part of the PHP community.
>
> These two reasons combined would make me reject the RFC at the current stage.

I think it is more in a draft stage for discussions.

To be more precise with my earlier reply, I only see such additions as
useful if it is an actual Vector as known in other languages and
widely used the last years in ML and other similar areas like data or
image processing.

To me a vector is useful if it allows vectorized operations, as in
SIMD, AltVec, CUBA etc. Some refs:

https://users.ece.cmu.edu/~franzf/teaching/slides-18-645-simd.pdf
https://indico.cern.ch/event/238763/attachments/401939/558861/HP-intel_mic_optimization.pdf

These two refer to Intel architecture but ARM (especiall v9 with Neon,
MIPS, ppc and maybe soon riscV does support such operations as well.
It is amazingly well suited for raw performance increase. I can
imagine having annotations and/or specific optimization for vectors of
scalar processing. It requires a bit of (re)thinking, but it is
totally worth it.

Generic multiple data types vectors are less useful for such things
and SplFixedArray does it already, if I understand the RFC, as it
stands now, correctly.

best,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #116061 — olle.haerstedt@limesurvey.org — 2021-09-17T08:36:05+00:00

URL: https://externals.io/message/116048#116061 · In reply to: #116050

On Thu, Sep 16, 2021 at 8:10 PM tyson andre <mailto:tysonandre775@hotmail.com> wrote: 
> > […]
> 
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP. 
> 
> PHP's native `array` type is rare among programming language in that it is used as an associative map of values, but also needs to support lists of values. 
> In order to support both use cases while also providing a consistent internal array HashTable API to the PHP's internals and PECLs, additional memory is needed to track keys (https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html - around twice as much as is needed to just store the values due to needing space both for the string pointer and int key in a Bucket, for non-reference counted values)). 
> Additionally, creating non-constant arrays will allocate space for at least 8 elements to make the initial resizing more efficient, potentially wasting memory. 
> 
> It would be useful to have an efficient variable-length container in the standard library for the following reasons: 
> 
> 1. To save memory in applications or libraries that may need to store many lists of values and/or run as a CLI or embedded process for long periods of time 
>    (in modules identified as using the most memory or potentially exceeding memory limits in the worst case) 
>    (both in userland and in native code written in php-src/PECLs) 
> 2. To provide a better alternative to `ArrayObject` and `SplFixedArray` for use cases 
>    where objects are easier to use than arrays - e.g. variable sized collections (For lists of values) that can be passed by value to be read and modified. 
> 3. To give users the option of stronger runtime guarantees that property, parameter, or return values really contain a list of values without gaps, that array modifications don't introduce gaps or unexpected indexes, etc. 
> 
> Thoughts on Vector? 
> 
> P.S. The functionality in this proposal can be tested/tried out at https://pecl.php.net/teds (under the class name `\Teds\Vector` instead of `\Vector`). 
> (That is a PECL I created earlier this year for future versions of iterable proposals, common data structures such as Vector/Deque, and less commonly used data structures that may be of use in future work on implementing other data structures) 
> 
> Thanks, 
> Tyson 
> -- 
>  
> To unsubscribe, visit: https://www.php.net/unsub.php 
> 
 
I'm okay with a final Vector class in general. I don't love the 
proposed API but don't hate it either. Feedback on that at the end. 
 
What I would _love_ is a `vec` type from hacklang, which is similar to 
this but pass-by-value, copy-on-write like an array. Of course, this 
would require engine work and I understand it isn't as simple to add. 
 
Feedback on API: 
 
-  `indexOf` returning `false` instead of `null` when it cannot be 
found. If we are keeping this method (which I don't like, because 
there's no comparator), please return `null` instead of false. The 
language has facilities for working with null like `??`, so please 
prefer that when it isn't needed for BC (like this, this is a new 
API). 
- `contains` also doesn't have a comparator. 
-  Similarly but less strongly, I don't like the filter callable 
returning `mixed` -- please just make it `bool`. 
- I don't know what `setSize(int $size)` does. What does it do if the 
current size is less than `$size`? What about if its current size is 
greater? I suspect this is about capacity, not size, but without docs 
I am just guessing. 
 
-- 
 
To unsubscribe, visit: https://www.php.net/unsub.php 
 





use SplFixedArray as vec;



Done. ;)



Olle

---

## #116063 — Pierre — 2021-09-17T09:14:21+00:00

URL: https://externals.io/message/116048#116063 · In reply to: #116048

Le 17/09/2021 à 04:09, tyson andre a écrit :
> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add `final class Vector` to PHP.

Hello,

That's nice, and I like it, but like many people I will argue about the 
API itself.

One thing is that there's many methods in there that would totally fit 
generic collection common interfaces, and in that regard, I'd be very 
sad that it would be merged as is.

I think it's taking the problem backwards, I would personally prefer that:

  - This RFC introduces the vector into a new Collection namespace, or 
any other collection/iterable/enumerable related namespace, that'd 
probably become the birth of a later to be standard collection API.

  - Start thinking about a common API even if it's for one or two 
methods, and propose something that later would give the impulsion for 
adding new collection types and extending this in order to be become 
something that looks like a really coherent collection API.

If this goes in without regarding the greater plan, it will induce 
inconsistencies in the future, when people will try to make something 
greater. I'd love having something like DS and nikic/iter fused 
altogether into PHP core, as a whole, in a consistent, performant, with 
a nice and comprehensive API (and that doesn't require to install 
userland dependencies).

I know this vector proposal is not about that, but nevertheless, in my 
opinion, it must start preparing the terrain for this, or all other RFC 
in the future will only create new isolated data structures and make the 
SPL even more inconsistent.

Regards,

--

Pierre

---

## #116068 — tyson andre — 2021-09-17T12:54:33+00:00

URL: https://externals.io/message/116048#116068 · In reply to: #116063

Hi Pierre,

> That's nice, and I like it, but like many people I will argue about the
> API itself.
> 
> One thing is that there's many methods in there that would totally fit
> generic collection common interfaces, and in that regard, I'd be very
> sad that it would be merged as is.

It isn't an interface, but my previous attempts at introducing common functionality for working with iterables have failed,
e.g. with preferring userland reasons or being too small in scope among the reasons.
https://wiki.php.net/rfc/any_all_on_iterable#straw_poll

Until there's a Set type or a Map type, adding generic functionality such as contains()
to all spl data structures is harder.

I haven't seen any recent additions of utility methods to existing spl datastructures in years other than when filling an urgent need,
(e.g. SplHeap->isCorrupted())
and have been pessimistic about that succeeding, but may be mistaken.

> I think it's taking the problem backwards, I would personally prefer that:
> 
>  - This RFC introduces the vector into a new Collection namespace, or
> any other collection/iterable/enumerable related namespace, that'd
> probably become the birth of a later to be standard collection API.
> 
>  - Start thinking about a common API even if it's for one or two
> methods, and propose something that later would give the impulsion for
> adding new collection types and extending this in order to be become
> something that looks like a really coherent collection API.
> 
> If this goes in without regarding the greater plan, it will induce
> inconsistencies in the future, when people will try to make something
> greater. I'd love having something like DS and nikic/iter fused
> altogether into PHP core, as a whole, in a consistent, performant, with
> a nice and comprehensive API (and that doesn't require to install
> userland dependencies).

Aside: https://github.com/TysonAndre/pecl-teds#iterable-functions
starts doing that, but evaluating eagerly instead of using generators.
I still don't think there's enough functionality yet to re-propose that.

> I know this vector proposal is not about that, but nevertheless, in my
> opinion, it must start preparing the terrain for this, or all other RFC
> in the future will only create new isolated data structures and make the
> SPL even more inconsistent.

It's possible, but I don't know what others think.

1. https://www.php.net/manual/en/class.ds-collection.php actually seems fairly universal, but out of scope, and I don't know if people would json encode a SplMaxHeap. Right now that isn't implemented and the value is always `{}`
2. `add($value)/remove($value)/contains[Value]($value)` is limited to some structures - Only containsValue() would apply to ArrayObject/SplObjectStorage. The others wouldn't work since you'd need to know the keys as well.

Also,

- Union type/intersection type support exists, so allowing any generic collection interface is less urgent.
- equals() may work, though infinite recursion (or the way it is or isn't detected) in circular data structures is a potential objection, especially with lack of stack overflow detection - php just crashes/segfaults without a useful method when it runs out of stack space.

For the ones that are universal, Countable/ArrayAccess/IteratorAggregate/Traversable already exist.

Also, as you said, this RFC is not about that.
Requiring that anyone systematically overhaul existing data structures before adding any new data structures
seems like it would significantly delay or discourage any future additions of data structures.

In the immediate future, an RFC only doing that would not have much short-term benefit to users - it would also have short-term drawbacks for what I consider not enough benefit,
if adopting that interface made libraries drop support for older php versions.

Thanks,
Tyson

---

## #116070 — Pierre — 2021-09-17T13:15:11+00:00

URL: https://externals.io/message/116048#116070 · In reply to: #116068

Le 17/09/2021 à 14:54, tyson andre a écrit :
> Aside: https://github.com/TysonAndre/pecl-teds#iterable-functions
> starts doing that, but evaluating eagerly instead of using generators.
> I still don't think there's enough functionality yet to re-propose that.
Nice to know this, I wasn't aware it even existed, I'll have a look.
> > […]
> It's possible, but I don't know what others think.
>
> 1. https://www.php.net/manual/en/class.ds-collection.php actually seems fairly universal, but out of scope, and I don't know if people would json encode a SplMaxHeap. Right now that isn't implemented and the value is always `{}`
> 2. `add($value)/remove($value)/contains[Value]($value)` is limited to some structures - Only containsValue() would apply to ArrayObject/SplObjectStorage. The others wouldn't work since you'd need to know the keys as well.
That's true, vector is a bit aside of what we'd expect from a full blown 
collection API, it's a very basic structure in the end so it can 
probably live on its own.
> Also,
>
> - Union type/intersection type support exists, so allowing any generic collection interface is less urgent.
That's right, but I don't think that union/intersection types solve the 
generic collection problem, you'd still have to match for specific class 
names or interfaces if methods are not rationalised in a single API.
> - equals() may work, though infinite recursion (or the way it is or isn't detected) in circular data structures is a potential objection, especially with lack of stack overflow detection - php just crashes/segfaults without a useful method when it runs out of stack space.
>
> For the ones that are universal, Countable/ArrayAccess/IteratorAggregate/Traversable already exist.
Yes, they exist, but I wouldn't place IteratorAggregate as being part of 
the interface, it's about implementation, but right. Anyway altogether 
they form a very poor API covering a very small surface and I'd imagine 
those becoming a legacy thing if a new API was introduced.
> Also, as you said, this RFC is not about that.
> Requiring that anyone systematically overhaul existing data structures before adding any new data structures
> seems like it would significantly delay or discourage any future additions of data structures.
>
> In the immediate future, an RFC only doing that would not have much short-term benefit to users - it would also have short-term drawbacks for what I consider not enough benefit,
> if adopting that interface made libraries drop support for older php versions.

I think your point is legit, and a part of me agrees with you, probably 
having some data structure before thinking about rationalisation is 
something that would make people move forward. Nevertheless it's always 
very difficult to change things once they're here, and the whole problem.

I crave so deeply for a complete, easy to use, well documented and 
standard collection API that I always jump on such RFC's to tell people 
"stop using DS, stop using Doctrine Collections, stop using "[name it 
here] collection", please everyone, let's design, implement and use the 
single and same one, so that we will never have to support them all 
(them being the 1,000 existing duplicated library in userland) in our 
framework or business code.

Thanks a lot for your answer and you time, despite the fact I still 
think that designing a collection first can still be done, having the 
vector type/class in core is a great idea.

Regards,

--

Pierre

---

## #116071 — tyson andre — 2021-09-17T13:16:23+00:00

URL: https://externals.io/message/116048#116071 · In reply to: #116055

Hi Levi Morrison,

> I mean that there isn't a way to provide a custom way to compare for
> equality. One way to accomplish this is to have a signature like:
> 
>    function contains(T $value, ?callable(T, T):bool $comparator = null): bool
> 
> The same goes for `indexOf`.

It'd make much more sense to have `->any(static fn($other): bool => $comparator($value, $other)): ?:int`
Overloading contains to do two different things (identity check or test the result of a callable)
seems like it's unintuitive to users.

Since there is plenty of time to add more functionality,
and I still haven't created the extended iterable library proposal,
this currently only adds operations that are significantly more efficient inside the Vector
(or have a return type of Vector) rather than going through the generic Iterator methods.

> > […]
> 
> I would rather see multiple methods like:
>     function truncateTo(int $size)
>     function padEnd(int $length, $value) // allows more than just null
>     function padBeginning(int $length, $value)

I'd consider this unfriendly to users (and personally consider it a poor design) if we start with 3 or 4 different ways to change the size of the Vector.
(Especially if English is a second language)

A wide variety of programming languages such as Java, Rust, C++, etc. all use resize rather than truncateTo/padEnd,
after what I assume is considerable discussion among language design experts in those languages.
In the vast majority of cases, users know the exact size they want and don't care about the mechanism to set that.
(And if the size is set larger or smaller in an `if{...}else{...}`, the existence of setSize is still needed.
Or if the user intends to reuse the allocated memory while overwriting all values.)

- Diverging from what end users are familiar with (without a strong reason to) would also make it harder to start using `Vector`.

I'd considered using a signature of `setSize(int $size, mixed $value = null)` to allow using something other than null
but decided to leave that to a followup proposal if it passed.

For now, I'd omitted ways to add to the start of the array because the linear time taken would be potentially objectionable,
if people didn't imagine using it themselves or thought it'd be more appropriate for end users to use a Deque.

> And one or more for increasing/ensuring capacity without changing size.

setCapacity seems useful to me for reserving exactly the amount of memory needed when the final size was known (e.g. setCapacity(2) to avoid over-allocating) but I was waiting to see if anyone else wanted that.

Thanks,
Tyson

---

## #116073 — tyson andre — 2021-09-17T13:54:53+00:00

URL: https://externals.io/message/116048#116073 · In reply to: #116059

Hi Christian Schenider,

> First of all: I don't have a strong opinion on a Vector class being useful or necessary.
> 
> But I have two comments about this RFC:
> 
> 1. Using the very generic name Vector without any prefix/namespace seems dangerous and asking for BC breaks.

I downloaded the top 400 composer packages with https://github.com/nikic/popular-package-analysis/ and didn't find any classes named Vector.

- Only php-cs-fixer extends SplFixedArray in one class. It can continue do so.
- I don't see other classes called Vector. Just stubs for `\Ds\Vector`.

There are tradeoffs and objections to any possible choice of name I could make, including this or alternates.

- Too likely to have conflicts
- Excessively long
- Open to adopting namespace but objecting to migrating existing classes (or not doing so)
- Objecting to a specific choice 

> 2. I don't like that this class is final. The reasons given in https://wiki.php.net/rfc/vector#final_class https://wiki.php.net/rfc/vector#final_class seem unconvincing to me and restrict the usage of Vector in a way which makes me question the usefulness to a big enough part of the PHP community.
> These two reasons combined would make me reject the RFC at the current stage.

There are alternatives such as making all/almost all of the methods final(especially for reading and modifying array elements or basic properties of the vector), but allowing extending the class.

- Still, I don't think that'd be very useful, and would make future final method additions to Vector backwards incompatible.
- Trying to do everything (e.g. be extensible and handle all edge cases of extension) has often resulted in many spl data structures doing not anything very well(efficiently, correctly, or possible to make universal assumptions about or optimize in the future with opcache/the jit).

While it is possible to extend ArrayObject and SplFixedArray, very few things do that, and it'd generally lead to worse API design except in a few cases.
(E.g. `UserList extends \Vector` wouldn't be able to enforce that inserted values are actually users with final methods)

Thanks,
Tyson

---

## #116074 — Levi Morrison via internals — 2021-09-17T13:55:30+00:00

URL: https://externals.io/message/116048#116074 · In reply to: #116071

> I'd considered using a signature of `setSize(int $size, mixed $value = null)` to allow using something other than null
> but decided to leave that to a followup proposal if it passed.

Rust and C++ both accept a value to pad, there's no reason to restrict
this to only null. Go ahead and make the change now.

---

## #116075 — Pierre Joye — 2021-09-17T14:18:01+00:00

URL: https://externals.io/message/116048#116075 · In reply to: #116058

Hi Tyson,

Back on my laptop so I will answer my question myself as I read the
source code. Please, really, that should be part of the RFC content.
Half of the questions here are about APIs, goals, etc. RFC should be
specifications as much as possible.


>
> Hello Tyson,
>
> Vector support would be very good. JIT can do a lot with them if we
> have a clean Vector implementation, or even without JIT.

Teds\Vector is named as Vector however I am afraid it is not, it is a
fixed array implementation. A vector, as in all other languages are,
for the definition, , fixed or variable sizes, of element of the same
type, The same type is absolutely key here.The reason to require the
same type is the core principle of vector (and vectorization),
structure of arrays rather than array of structs. The latter are hard
(or pointless) to parallelize and hard to optimize. An easy way to
play with Vector would be to try out numpy's Vector, which is by far
one of the best (and fastest) scripting language implementations of
Vector.

I did not spend enough time on the code, but I would by deconstructing:

typedef struct _teds_vector_entries {
size_t size;
size_t capacity;
zval *entries;
} teds_vector_entries;

to  different types (or using multiple entries with a zval_type entry.
ie. for a zval float Vector:

typedef struct _teds_vector_entries {
size_t size;
size_t capacity;
double float;
} teds_vector_entries;

Alternatively, common C port of C++ Vector do something along this line:

typedef struct _cVector{
unsigned int size;
unsigned int cnt_elements;
unsigned int element_size;
void *elements;
} cVector;

where the initialization is:

void cVectorInit (cVector *array, unsigned int element_size); where
element_size is sizeof(double) f.e.

so any append, truncate, etc. are aware of the size to be
(re)allocated, if needed.

The only addition to handle zval would be:

typedef struct _cVector{
unsigned int size;
unsigned int cnt_elements;
zval_enum type zval_type;
unsigned int element_size;
void *elements;
} cVector;

Doing so will drastically help to finally have a simple, by usage and
implementation/api, way to implement vectorization using PHP.

I would also like to suggest having it in the engine somehow, if it is
not possible to have JIT jump in here if it is not an actual type in
the engine. While it is possible to have intrinsics implementations in
any extension, it won't be as good or efficient as an engine type with
JIT support.

Also, as it stands, I do not think it can be called a Vector. So I am
not too keen for it as I don't think we need another SplFixed*Array
implementation, as simple as it could be. The RFC needs some work
anyway before any vote can be taken.

In any case, if the above would be something you may consider (to
implement an actual vector), I can help and would be happy too if you
need/like to.

Best,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #116077 — Max Semenik — 2021-09-17T19:36:59+00:00

URL: https://externals.io/message/116048#116077 · In reply to: #116048

On Fri, Sep 17, 2021 at 5:10 AM tyson andre <tysonandre775@hotmail.com>
wrote:

> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add
> `final class Vector` to PHP.


Thank you so much, Tyson - I love your proposal. Since Ds was mentioned,
I've added it to your benchmark (code and complete results at
https://gist.github.com/MaxSem/d0ea0755d6deabaf88c9ef26039b2f27):

Appending to array:         n= 1048576 iterations=      20 memory=33558608
bytes, create+destroy time=0.369 read time = 0.210 result=10995105792000
Appending to Vector:        n= 1048576 iterations=      20 memory=16777304
bytes, create+destroy time=0.270 read time = 0.270 result=10995105792000
Appending to SplStack:      n= 1048576 iterations=      20 memory=33554584
bytes, create+destroy time=0.893 read time = 0.397 result=10995105792000
Appending to SplFixedArray: n= 1048576 iterations=      20 memory=16777304
bytes, create+destroy time=2.475 read time = 0.340 result=10995105792000
Appending to Ds\Vector:     n= 1048576 iterations=      20 memory=24129632
bytes, create+destroy time=0.389 read time = 0.305 result=10995105792000

Another comparison with Ds, I wonder if an interface akin to Ds\Sequence[1]
could be added, to have something in common with other future containers.

-----
[1] http://docs.php.net/manual/en/class.ds-sequence.php

-- 
Best regards,
Max Semenik

---

## #116078 — Larry Garfield — 2021-09-17T20:38:57+00:00

URL: https://externals.io/message/116048#116078 · In reply to: #116048

> Hi internals,
> 
> I've created a new RFC https://wiki.php.net/rfc/vector proposing to add 
> `final class Vector` to PHP.
> 
> PHP's native `array` type is rare among programming language in that it 
> is used as an associative map of values, but also needs to support 
> lists of values.
> In order to support both use cases while also providing a consistent 
> internal array HashTable API to the PHP's internals and PECLs, 
> additional memory is needed to track keys 
> (https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html - around twice as much as is needed to just store the values due to needing space both for the string pointer and int key in a Bucket, for non-reference counted values)).
> Additionally, creating non-constant arrays will allocate space for at 
> least 8 elements to make the initial resizing more efficient, 
> potentially wasting memory.
> 
> It would be useful to have an efficient variable-length container in 
> the standard library for the following reasons: 
> 
> 1. To save memory in applications or libraries that may need to store 
> many lists of values and/or run as a CLI or embedded process for long 
> periods of time 
>    (in modules identified as using the most memory or potentially 
> exceeding memory limits in the worst case)
>    (both in userland and in native code written in php-src/PECLs)
> 2. To provide a better alternative to `ArrayObject` and `SplFixedArray` 
> for use cases 
>    where objects are easier to use than arrays - e.g. variable sized 
> collections (For lists of values) that can be passed by value to be 
> read and modified.
> 3. To give users the option of stronger runtime guarantees that 
> property, parameter, or return values really contain a list of values 
> without gaps, that array modifications don't introduce gaps or 
> unexpected indexes, etc.
> 
> Thoughts on Vector?
> 
> P.S. The functionality in this proposal can be tested/tried out at 
> https://pecl.php.net/teds (under the class name `\Teds\Vector` instead 
> of `\Vector`).
> (That is a PECL I created earlier this year for future versions of 
> iterable proposals, common data structures such as Vector/Deque, and 
> less commonly used data structures that may be of use in future work on 
> implementing other data structures)

Improving collection/set operations in PHP is something near and dear to my heart, so I'm in favor of adding a Vector class or similar to the stdlib.

However, I am not a fan of this particular design.

* As Levi noted, this being a mutable object that passes by handle is asking for trouble.  It should either be some by-value internal type, or an immutable object with evolver methods on it.  (Eg, add($val): Vector).  Making it a mutable object is creating spooky action at a distance problems.  An immutable object seems likely easier to implement than a new type, but both are beyond my capabilities so I defer to those who could do so.

* The methods around size control are seemingly pointless from a user POV.  I understand the memory optimization value they have, but that's not something PHP developers are at all used to dealing with.  That makes it less of a convenient drop-in replacement for array and more just another user-space collection object, but in C with internals endorsement.  If such logic needs to be included, it should be kept as minimalist as possible for usability, even at the cost of a little memory usage in some cases.

* There is no reason to preserve keys.  A Vector or list type should not have user-defined keys.  It should just be a linear list.  If you populate it from an existing array/iterable, the keys should be entirely ignored.  If you care about keys you want a HasMap or Dictionary or similar (which we also desperately need in the stdlib, but that's a separate thing).

* Whether or not contains() needs a comparison callback in my mind depends mainly on whether or not the operator overloading RFC passes.  If it does, then contains() can/should use the __compareTo() method on objects.  If it doesn't, then there needs to be some other way to compare non-identical objects or else that method becomes mostly useless.

* To echo Pierre, a Vector needs to be of a single guaranteed type.  Yes, this gets us back to the generics conversation again, but I presume (perhaps naively?) there are ways to address this question without getting into full-blown generics.  But really, a non-type-guaranteed Vector/List construct is of fairly little use to me in practice, and that's before we even get into the potential performance optimizations for map() and filter() from type guarantees.  I can write a type-guaranteed user-space class that does what I need in under 10 minutes, and for most low cardinality sets that's adequately performant.  A built-in needs to be better than that.

I very much appreciate the chicken-and-egg challenge of wanting to get something useful in despite the absence of a larger plan, and also the challenge of getting buy-in on a larger plan.  Really. :-)  This is an area where PHP's current dev process is very lacking.  Still, I also agree with others that we need to be thinking holistically about this problem space, which will inform what the steps are.  The approach we took for enums could be a model to consider (multiple RFCs clustered together under an RFC "epic".)  That would allow for a long-term design, and the influence that offers, while still having milestones along the way that offer value unto themselves.  (I'm happy to help with that, since that's about all I'm good for around here. :-) )

So big +1 to improving the in-C collection story; -1 to the current proposal.

--Larry Garfield

---

## #116079 — Levi Morrison via internals — 2021-09-17T20:56:22+00:00

URL: https://externals.io/message/116048#116079 · In reply to: #116078

> * Whether or not contains() needs a comparison callback in my mind depends mainly on whether or not the operator overloading RFC passes.  If it does, then contains() can/should use the __compareTo() method on objects.  If it doesn't, then there needs to be some other way to compare non-identical objects or else that method becomes mostly useless.

This is only partly true. Let's say we have a vector of some complex
type A. There are legitimate reasons for using different ways of
comparing As, such as when projecting sub-fields (for example, sorting
by each member's name this time, but next time sorting by each
member's location).

Of course, if it passes, then using a type's built-in comparison
overloading is a sensible default, but it doesn't remove the need of
having a custom comparator.

-----

I was tired when I originally pointed it out the comparator/equatable
stuff, but Tyson was rightly saying that `any` solves this need, e.g.

    <?php
    if ($vec->contains($value, $eq)) {/**/}
    // translates to
    if ($vec->any(fn ($x) => $eq($x, $value))) {/**/}
    ?>

However, it's not as clear what to do for `indexOf` where you care
about the index it was found at.

---

## #116080 — tyson andre — 2021-09-18T00:00:45+00:00

URL: https://externals.io/message/116048#116080 · In reply to: #116077

Hi Max Semenik,

> Since Ds was mentioned, I've added it to your benchmark (code and complete results at https://gist.github.com/MaxSem/d0ea0755d6deabaf88c9ef26039b2f27):
> 
> Appending to array:         n= 1048576 iterations=      20 memory=33558608 bytes, create+destroy time=0.369 read time = 0.210 result=10995105792000
> Appending to Vector:        n= 1048576 iterations=      20 memory=16777304 bytes, create+destroy time=0.270 read time = 0.270 result=10995105792000
> Appending to SplStack:      n= 1048576 iterations=      20 memory=33554584 bytes, create+destroy time=0.893 read time = 0.397 result=10995105792000
> Appending to SplFixedArray: n= 1048576 iterations=      20 memory=16777304 bytes, create+destroy time=2.475 read time = 0.340 result=10995105792000
> Appending to Ds\Vector:     n= 1048576 iterations=      20 memory=24129632 bytes, create+destroy time=0.389 read time = 0.305 result=10995105792000
> 
> Another comparison with Ds, I wonder if an interface akin to Ds\Sequence[1] could be added, to have something in common with other future containers.

It's worth noting that the first 4 data structures all start with initial sizes that are powers of 2 and continue doubling (and not mattering for SplStack, a doubly linked list),
but according to Ds\Vector's documentation,
it starts with a minimum size of 10. So it's an unfair comparison. http://docs.php.net/manual/en/class.ds-vector.php#ds-vector.constants.min-capacity
So there are probably larger copies done in Ds\Vector - Ds\Vector might do better for other sizes or use less memory under other circumstances.

(for reasons mentioned in https://externals.io/message/116048#116054 , I haven't checked the resizing strategy used by Ds\Vector - doubling is a common choice in vector implementations in other languages, others use other multiples of old capacity, etc)

Regards,
- Tyson

---

## #116081 — tyson andre — 2021-09-18T01:49:16+00:00

URL: https://externals.io/message/116048#116081 · In reply to: #116078

> Improving collection/set operations in PHP is something near and dear to my heart,
> so I'm in favor of adding a Vector class or similar to the stdlib.
> 
> However, I am not a fan of this particular design.
> 
> As Levi noted, this being a mutable object that passes by handle is asking for trouble.
> It should either be some by-value internal type, or an immutable object with evolver methods on it.
> (E.g., add($val): Vector). Making it a mutable object is creating spooky action at a distance problems.
> An immutable object seems likely easier to implement than a new type,
> but both are beyond my capabilities so I defer to those who could do so.

https://wiki.php.net/rfc/vector#adding_a_native_type_instead_is_vec discusses why I'm doubtful of `is_vec` getting implemented or passing.
Especially with `add()` taking linear time to copy all elements of the existing value if you mean an array rather than a linked list-like structure, and any referenced copies taking a lot more memory than an imperative version would.


PHP's end users and internals members come from a wide variety of backgrounds,
and I assume most beginning or experienced PHP programmers would tend towards imperative&mutable programming rather than functional&immutable programming.

PHP provides tools such as `clone`, private visibility, etc to deal with that.

The lack of any immutable object datastructures in core and the lack of immutable focused extensions in PECL https://pecl.php.net/package-search.php?pkg_name=immutable
https://www.php.net/manual-lookup.php?pattern=immutable&scope=quickref
(other than DateTimeImmutable)
heavily discourage me from proposing anything immutable.

(Technically, https://github.com/TysonAndre/pecl-teds has minimal implementations of immutable data structures, but the api is still being revised and Vector is the primary focus, followed by iterable functions. e.g. there's no `ImmutableSequence::add($value): ImmutableSequence` method.)


> The methods around size control are seemingly pointless from a user POV.

setSize is useful in allocating exactly the variable amount of memory needed while using less memory than a PHP array.
`setSize($newSize, 0)` would be much more efficient and concise in initializing the value.

- Or in quickly reducing the size of the array rather than repeatedly calling pop in a loop.

And while methods around capacity control exist in many other programming languages, they aren't used by most users and most users are fine with functionality they don't use existing.
The applications or libraries that do have a good use case to reduce memory will take advantage of them and end users of those applications/libraries would benefit from the memory usage reduction.

> I understand the memory optimization value they have, but that's not something PHP developers are at all used to dealing with.
> That makes it less of a convenient drop-in replacement for array and more just another user-space collection object, but in C with internals endorsement.
> If such logic needs to be included, it should be kept as minimalist as possible for usability,
> even at the cost of a little memory usage in some cases.

If the functionality was just a drop-in replacement for array, others may say "why not just use array and the array libraries?" (or Vector).
With the strategy of doubling capacity, it can be up to 99% more memory than needed in some cases (Even more wastage after shrinking from the maximum size).

> There is no reason to preserve keys.
> A Vector or list type should not have user-defined keys.
> It should just be a linear list. If you populate it from an existing array/iterable, the keys should be entirely ignored.
> If you care about keys you want a HashMap or Dictionary or similar (which we also desperately need in the stdlib, but that's a separate thing).

The behavior is similar to https://www.php.net/manual/en/splfixedarray.fromarray.php 
It tries to preserve the keys, and fills in gaps with null.

1. There's the consistency with existing functionality such as SplFixedArray::fromArray, or existing constructors preserving keys.
2. And I'd imagined that a last minute objection of "Wait, `new SplFixedArray([1 => 'second', 0 => 'first'])` does what by default? Isn't this using the keys 0 and 1?", and the same for gaps

   I was considering only having the no-param constructor, and adding the static method fromValues(iterable $it) to make it clearer keys are ignored.

> Whether or not contains() needs a comparison callback in my mind depends mainly on whether or not the operator overloading RFC passes. 
> If it does, then contains() can/should use the __compareTo() method on objects.
> If it doesn't, then there needs to be some other way to compare non-identical objects or else that method becomes mostly useless.

There's a distinction between needs and very nice to have - a contains check for some predicate on a Vector can be done with a userland helper method and a foreach.

Also, you're requesting functionality that I don't believe is currently available for arrays, either.
 
> To echo Pierre, a Vector needs to be of a single guaranteed type.
> Yes, this gets us back to the generics conversation again, but I presume (perhaps naively?) there are ways to address this question without getting into full-blown generics.

Yep, as you said, this type is mixed, just like the SplFixedArray, ArrayObject, values of SplObjectStorage/WeakMap, etc.
Generic support is something that's been brought up before, investigated, then abandoned.

My concerns with adding StringVector, MixedVector, IntVector, FloatVector, BoolVector, ArrayVector (confusing), ObjectVector, etc is that

- I doubt many people would agree that there's a wide use case for any 
  specific one of them compared to a vector of any type.

  This would be even harder to argue for than just a single Vector type.
- Mixes of null and type `T` might make sense in many cases (e.g. optional objects, statistics that failed to get computed, etc) but would be forbidden by that
- It would be a bad choice if generic support did get added in the future.

I'm not sure if we're thinking of the same thing.
Could you provide more details on how that would be implemented? Have other PECLs done something similar?

> But really, a non-type-guaranteed Vector/List construct is of fairly little use to me in practice, and that's before we even get into the potential performance optimizations for map() and filter() from type guarantees.

See earlier comments on `vec`/Generics not being actively worked on right now and probably being a far way away from an implementation that would pass a vote.

As for optimizations, opcache currently doesn't optimize individual global functions (let alone methods), it optimizes opcodes.
Even `array_map()`/array_filter() aren't optimized, they call callbacks in an ordinary way.
E.g. https://github.com/php/php-src/pull/5588 or https://externals.io/message/109847 regarding ordinary methods.

Aside: In the long term, I think the opcache core team had a long-term plan of changing the intermediate representation to make these types of optimizations feasible without workarounds like the one I proposed in 5588

> I can write a type-guaranteed user-space class that does what I need in under 10 minutes, and for most low cardinality sets that's adequately performant. A built-in needs to be better than that.
> 
> I very much appreciate the chicken-and-egg challenge of wanting to get something useful in despite the absence of a larger plan, and also the challenge of getting buy-in on a larger plan.
> Really. :-) This is an area where PHP's current dev process is very lacking.
> Still, I also agree with others that we need to be thinking holistically about this problem space, which will inform what the steps are.
> The approach we took for enums could be a model to consider (multiple RFCs clustered together under an RFC "epic".)
> That would allow for a long-term design, and the influence that offers, while still having milestones along the way that offer value unto themselves. (I'm happy to help with that, since that's about all I'm good for around here. :-) )

Enums were extensions of existing class types (is_object(Suit::Hearts) is true) rather than adding a whole separate type to the type system and don't need to support generics or contain anything other than an int/string.
I don't think the choice of "epic" widely influenced the vote.

Regards,
Tyson

---

## #116082 — Pierre Joye — 2021-09-18T02:30:57+00:00

URL: https://externals.io/message/116048#116082 · In reply to: #116081

Good morning,

Not sure you care or read my reply but I had to jump in one more time here :)



> setSize is useful in allocating exactly the variable amount of memory needed while using less memory than a PHP array.
> `setSize($newSize, 0)` would be much more efficient and concise in initializing the value.
>
> - Or in quickly reducing the size of the array rather than repeatedly calling pop in a loop.

I would rather not reduce it at all, but use the vector_size and keep
it. User land set its max size but a realloc/free should not be
necessary and counter productive from a perf point of view. If one
uses it in a daemon, it can always be destroyed as needed.

> > […]
>
> Yep, as you said, this type is mixed, just like the SplFixedArray, ArrayObject, values of SplObjectStorage/WeakMap, etc.
> Generic support is something that's been brought up before, investigated, then abandoned.
>
> My concerns with adding StringVector, MixedVector, IntVector, FloatVector, BoolVector, ArrayVector (confusing), ObjectVector, etc is that
>
> - I doubt many people would agree that there's a wide use case for any
>   specific one of them compared to a vector of any type.

I am lost here. This is the main usage of Vector. For linear
arithmetic like dot product, masking, add/sub/mul/div of vector etc. I
do not see any other usage per see for all the things I have
implemented or saw out there. Additionally, f.e., a string is a vector
already on its own, I am not sure a vector of vectors makes sense ;).

>   This would be even harder to argue for than just a single Vector type.
> - Mixes of null and type `T` might make sense in many cases (e.g. optional objects, statistics that failed to get computed, etc) but would be forbidden by that
> - It would be a bad choice if generic support did get added in the future.

These are special cases for general purposes of vectors. Implementing
vectors focusing on these special cases rather than the general
purpose (vectorization) would be a strategic mistake. I mentioned it
before, but please take a look at the numpy's Vector f.e., with
python's operator overload, what has been done there is simply
amazing, bringing vector processing/arithmetic a huge boost in
performance, even with millions of entries (14 to 400x speed boost
compared to classic array, even fixed).

> > […]
>
> See earlier comments on `vec`/Generics not being actively worked on right now and probably being a far way away from an implementation that would pass a vote.

Generics!=Vector. But I hope that's not the way we are heading here :)

> As for optimizations, opcache currently doesn't optimize individual global functions (let alone methods), it optimizes opcodes.
> Even `array_map()`/array_filter() aren't optimized, they call callbacks in an ordinary way.
> E.g. https://github.com/php/php-src/pull/5588 or https://externals.io/message/109847 regarding ordinary methods.
>
> Aside: In the long term, I think the opcache core team had a long-term plan of changing the intermediate representation to make these types of optimizations feasible without workarounds like the one I proposed in 5588

You are fully correct here, I see a lack of the engine devs
involvement (not complaining, just a state of the affairs :) in such
RFC where this kind of feature could greatly benefit PHP. Well
planned, this is a huge addition to PHP.

It is also why I am convinced that doing it right for Vectors (as a
start) and thinking forwards to JIT and ops overloading (internally or
userland) to allow smooth and nice vectorization (as some parts use
them already internally f.e.) will bring PHP up to speed with the
competition. If we don't, we just have something that would be similar
to what anyone could do in userland with more flexibility.

Best,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

Next page: https://externals.io/message/116048.md?page=2