Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Stephen,

> As a userland dev & library author it’s nice to see some progression on basic 
> data structures, so thank you for your efforts on this!
> 
> 
> Two little things in the RFC:
> 
> The proposed API switches between terms `front`, `back`, `start` and `end` in 
> comments - is there meant to be a conceptual difference between front/start 
> and end/back ?
 
Good point. I've changed the method names to first()/last() and also made the 
wording in https://wiki.php.net/rfc/deque more consistently use first/last to 
avoid confusion.

No, They're the same. front=start=bottom=first. Bottom was from 
SplDoublyLinkedList/SplStack, e.g. the bottom of the stack, top is where 
`push()` acts, etc.
Front was how I was referring to iteration order.
 
> In the "Why use this instead of array?” Section, the 3rd point seems cut off:
> > Note that starting in php 8.2, array

That should say "Note that starting in php 8.2, arrays that are lists (with 
no/few gaps) are represented in a more memory efficient way than associative 
arrays.".

I've updated the RFC.

Thanks,
Tyson

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Mel Dafert,

> >The proposed API switches between terms `front`, `back`, `start` and `end` 
> >in comments - is there meant to be a conceptual difference between 
> >front/start and end/back ?
> 
> On a similar note, why are the methods for getting the first/last value called
> `top()`/`bottom()`? Off the top of my head, it is hard for me to imagine 
> which side is
> the top and which side is the bottom.
> I would prefer if it was called something more intuitive, possibly 
> `first()`/`last()` in
> accordance with `array_key_first()`/`array_key_last()`.

I've changed it to first/last in https://wiki.php.net/rfc/deque

I'd forgotten about first/last when looking for existing names php used for 
methods/global functions.
The closest I'd seen was in SplDoublyLinkedList, I'd forgotten about 
https://php.net/array_key_last getting added in php 7.3
(due to it existing for keys but not values)


Thanks,
Tyson
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mel Dafert]

On 1 February 2022 17:06:59 CET, Stephen Reay  wrote:
>
>The proposed API switches between terms `front`, `back`, `start` and `end` in 
>comments - is there meant to be a conceptual difference between front/start 
>and end/back ?

On a similar note, why are the methods for getting the first/last value called
`top()`/`bottom()`? Off the top of my head, it is hard for me to imagine which 
side is
the top and which side is the bottom.
I would prefer if it was called something more intuitive, possibly 
`first()`/`last()` in
accordance with `array_key_first()`/`array_key_last()`.

Regards,
Mel

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Stephen Reay]

> On 1 Feb 2022, at 21:46, tyson andre  wrote:
> 
> Hi internals,
> 
>> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class 
>> Deque`
>> 
>> This is based on the `Teds\Deque` implementation I've worked on
>> for the https://github.com/TysonAndre/pecl-teds PECL.
>> 
>> While `SplDoublyLinkedList` and its subclass `SplQueue`/`SplStack` exist in 
>> the SPL, they have several drawbacks
>> that are addressed by this RFC to add a `Deque` class (to use instead of 
>> those):
>> 
>> 1. `SplDoublyLinkedList` is internally represented by a doubly linked list,
>>making it use roughly twice as much memory as the proposed `Deque`
>> 2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower due 
>> to
>>needing to allocate or free the linked list nodes.
>> 3. Reading values in the middle of the `SplDoublyLinkedList` is proportional 
>> to the length of the list,
>>due to needing to traverse the linked list nodes.
>> 4. `foreach` Iteration behavior cannot be understood without knowing what 
>> constructed the
>>`SplDoublyLinkedList` instance or set the flags.
>> 
>> It would be useful to have an efficient `Deque` container in the standard 
>> library
>> to provide an alternative without those drawbacks,
>> as well as for the following reasons:
>> 
>> 1. To save memory in applications or libraries that may need to store many 
>> lists of values or run for long periods of time.
>>Notably, PHP's `array` type will never release allocated capacity.
>>See 
>> https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html
>> 2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`, and 
>> `SplQueue`
>>for use cases that require stacks or queues.
>> 3. As a more efficient option than `array` and `SplDoublyLinkedList`
>>as a queue or `Deque`, especially for `unshift`.
>> 
>> A `Deque` is more efficient than an `array` when used as a queue, more 
>> readable, and easier to use correctly.
>> While it is possible to efficiently remove elements from the start of an 
>> `array` (in terms of insertion order) (though this makes 
>> reset()/array_key_first() inefficient),
>> it is very inefficient to prepend elements to the start of a large `array` 
>> due to needing to either copy the array
>> or move all elements in the internal array representation,
>> and an `array` would use much more memory than a `Deque` when used that way 
>> (and be slower).
>> 
>> There are also several pitfalls to using an array as a queue for larger 
>> queue sizes,
>> some of which are not obvious and discovered while writing the benchmarks.
>> (Having a better (double-ended) queue datastructure (`Deque`) than the 
>> `SplDoublyLinkedList`
>> would save users from needing to write code with these pitfalls):
>> 
>> 1. `array_key_first()` and reset()`takes time proportional to the number of 
>> elements `unset` from the start of an array,
>>causing it to unexpectedly be extremely slow (quadratic time) after 
>> unsetting many elements at the start of the queue.
>>(when the array infrequently runs out of capacity, buckets are moved to 
>> the front)
>> 2. `reset()` or `end()` will convert a variable to a reference,
>>and php is less efficient at reading or writing to reference.
>>Opcache is also less efficient at optimizing uses of variables using 
>> references.
>> 3. More obviously, `array_unshift` and `array_shift` will take time 
>> proportional to the number of elements in the array
>>(to reindex and move existing/remaining elements).
> 
> I plan to start voting on https://wiki.php.net/rfc/deque on Friday, February 
> 4th.
> 
> Several changes have been made to https://wiki.php.net/rfc/deque#changelog
> after the feedback in https://externals.io/message/116100
> 
> - The class is now named `Collections\Deque`
> - The api documentation in https://wiki.php.net/rfc/deque#proposal was 
> expanded for methods.
> - Benchmarks were updated.
> - Like other standard datastructures, iteration over the deque is now over 
> the original object (instead of creating a copy), 
>  and mutating the deque will be reflected in `$iterator->current()` (and 
> moving the end with push()/pop() will affect where iteration ends).
> - Iteration will account for calls to shift/unshift moving the start of the 
> deque.
>  the offsets will be corrected and values won't be skipped or iterated over 
> multiple times.
>  (no matter how many iterators were created by `Deque->getIterator()`)
>  See https://wiki.php.net/rfc/deque#iteration_behavior
> - The get()/set() methods were removed, after feedback in 
> https://externals.io/message/116100#116214
> 
> A WebAssembly demo is available at 
> https://tysonandre.github.io/php-rfc-demo/deque/
> 
> Thanks,
> Tyson
> 
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: https://www.php.net/unsub.php
> 

Hi Tyson,

As a userland dev & library author it’s nice to see some progression on basic 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Levi Morrison,

> I think this RFC is in much better shape now.
> 
> The last thing I'll personally push for is dropping `get` and `set`.
> I'm not sure about those names, and the functionality is already
> provided by `offsetGet` and `offsetSet`, albeit through `mixed`
> instead of `int`, but I think this sort of cleanup should be done en
> masse at some point, rather than having this one type doing something
> different from the others.

The get/set methods have been removed. I've updated the RFC and implementation.

Thanks,
Tyson
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Levi Morrison via internals]

I think this RFC is in much better shape now.

The last thing I'll personally push for is dropping `get` and `set`.
I'm not sure about those names, and the functionality is already
provided by `offsetGet` and `offsetSet`, albeit through `mixed`
instead of `int`, but I think this sort of cleanup should be done en
masse at some point, rather than having this one type doing something
different from the others.

-- 
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

> > The name "deque" is used in the standard library of these languages:
> >
> >  - C++: std::deque
> >  - Java: java.util.Deque (interface)
> >  - Python: collections.deque
> >  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> > official? Don't know Swift)
> >  - Rust: std::collections::VecDeque
> >
> > And these don't have it in the standard library:
> >  - Go
> >  - C#
> >  - C
> >  - JavaScript
> >
> > Anyway, it's pretty decent evidence that:
> >  1. This functionality is pretty widely used across languages.
> >  2. This functionality should have "deque" be in the name, or be the
> > complete name.
> >
> > Discussion naming for "vector" I can understand, as it's less widely
> > used or sometimes means something specific to numbers, but there's
> > little point in discussing the name "deque." It's well established in
> > programming, whether PHP programmers are aware of it or not.
> >
> > As I see it, the discussion should be centered around:
> >  1. The API Deque provides.
> >  2. The package that provides it.
> >  3. Whether Deque's API is consistent with other structures in the same
> > package.
> >  4. Whether this should be included in php-src or left to extensions.
> >
> > I suggest that we try to make PHP as homogenous in each bullet as we
> > can with other languages:
> >  1. Name it "Deque."
> >  2. Put it in the namespace "Collections" (and if included in core,
> > then "ext/collections").
> >  3. Support common operations on Deque (pushing and popping items to
> > both front and back, subscript operator works, iteration, size, etc)
> > and add little else (don't be novel here). To me, the biggest thing
> > left to discuss is a notion of a maximum size, which in my own
> > experience is common for circular buffers (the implementation chosen
> > for Deque) but not all languages have this.
> >  4. This is less clear, but I'm in favor as long as we can provide a
> > few other data structures at the same time. Obviously, this a voter
> > judgement call on the yes/no.
> >
> > Given that I've suggested the most common options for these across
> > many languages, it shouldn't be very controversial. The worst bit
> > seems like picking the namespace "Collections" as this will break at
> > least one package: https://github.com/danielgsims/php-collections. We
> > should suggest that they vendor it anyway, as "collections" is common
> > e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> > a good alternative here to "Collections", as we haven't agreed on very
> > much on past namespace proposals.
> >
> > Anyway, that's what I suggest.
> >
> 
> I generally agree with everything Levi has said here. I think that adding a
> deque structure generally makes sense, and that putting it into a new
> ext/collections extension under the corresponding namespace would be
> appropriate. I wouldn't insist on introducing it together with other
> structures (I'm a lot more sceptical about your Vector proposal), but do
> think there should be at least some overarching plan here, even if we only
> realize a small part of it in this version.
 
https://wiki.php.net/rfc/deque has been updated after 
https://wiki.php.net/rfc/deque_straw_poll.
It's now going in the namespace `Collections\`, and a new always-enabled 
extension `collections` 
is added in `php-src/ext/collections` in that RFC (for end users, that would 
mainly affect php.net manual organization).

I plan to start voting in a few days.

Also, iteration behavior has changed to 
https://wiki.php.net/rfc/deque#iteration_behavior

I also set up a WebAssembly demo to make it easier to look up how it currently 
behaves:
https://tysonandre.github.io/php-rfc-demo/deque/

> A few questions for the particular API proposed here:
> 
> 1. There would be the possibility of having an interface Deque that is
> backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
> would actually make sense, but I wanted to throw it out there, given that
> the class is final (which is without any doubt the correct decision).

Would `ArrayDeque` be referring to something with a hardcoded maximum size?
I can't think of a strong use case for that, and it's possible in userland by 
wrapping `Collections\Deque` (with composition) and checking size on add 
operations.

> 2. How do set() / offsetSet() work with an out of range index? Is it
> possible to push an element with $deque[count($deque)] = x? I would assume
> that throws, but want to make sure. On a related note, why do we need both
> get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

They throw for out of range indexes. Offsets between 0 and count-1 are in range.

offsetSet/offsetGet attempt to coerce values to integers to act as a drop-in 
replacement 
for arrays and Spl datastructures (e.g. for applications that deal with string 
inputs).
They throw TypeError if coercion fails, OutOfBoundsException for invalid 
offsets.

> 3. I believe it's pretty standard for Deque 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Nikita Popov]

t be multiple iterators at
the same time, so I don't think the suggestion from the last sentence would
work. Though I think the general idea does work, as long as we're working
with a delta between the offset in the iterator and the deque.


> 3. Behave as if the entire Deque was copied when iteration starts (either
> by actually copying everything or by copy on write).
>
>That was the **planned** implementation documented in the RFC, but
> would be inefficient for iterations that end early and use a lot of memory
> for large Deques.
>
> 4. Throw if attempting to change the size of the `Deque` while a foreach
> is in progress.
>
>The semantics of that would be annoying, e.g. handling `clear()` or
> `shift()`, and the exception getting thrown would be unexpected.
>
> > 5. The shift/unshift terminology is already used by our array API, but
> I'm
> > not sure it's the most intuitive choice in the context of a deque.
> SplQueue
> > has enqueue() and dequeue(). Another popular option from other languages
> > (which I would personally favor) is pushFront() and popFront().
>
> My original name idea was pushBack/popBack/pushFront/popFront but I had
> decided against proposing brand new terms
> for functionality that already had terms in php-src.
> It would also be inconsistent with proposed names for `Vector` if that was
> also added.
>
> https://www.php.net/manual/en/class.ds-deque.php and SplDoublyLinkedList
> had done the same thing
>
> enqueue and dequeue don't have a good term for enqueueing on the opposite
> side.
>
> - It would make it easier to learn the language to have fewer terms and
> migrate code using SplDoublyLinkedList or arrays
> - push()/shift() are also shorter names than pushBack/popFront()
>
> Thanks,
> Tyson
>
>
> From: Nikita Popov 
> Sent: October 4, 2021 8:04 AM
> To: Levi Morrison 
> Cc: PHP internals 
> Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP
>
> On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
> internals@lists.php.net> wrote:
>
> > The name "deque" is used in the standard library of these languages:
> >
> >  - C++: std::deque
> >  - Java: java.util.Deque (interface)
> >  - Python: collections.deque
> >  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> > official? Don't know Swift)
> >  - Rust: std::collections::VecDeque
> >
> > And these don't have it in the standard library:
> >  - Go
> >  - C#
> >  - C
> >  - JavaScript
> >
> > Anyway, it's pretty decent evidence that:
> >  1. This functionality is pretty widely used across languages.
> >  2. This functionality should have "deque" be in the name, or be the
> > complete name.
> >
> > Discussion naming for "vector" I can understand, as it's less widely
> > used or sometimes means something specific to numbers, but there's
> > little point in discussing the name "deque." It's well established in
> > programming, whether PHP programmers are aware of it or not.
> >
> > As I see it, the discussion should be centered around:
> >  1. The API Deque provides.
> >  2. The package that provides it.
> >  3. Whether Deque's API is consistent with other structures in the same
> > package.
> >  4. Whether this should be included in php-src or left to extensions.
> >
> > I suggest that we try to make PHP as homogenous in each bullet as we
> > can with other languages:
> >  1. Name it "Deque."
> >  2. Put it in the namespace "Collections" (and if included in core,
> > then "ext/collections").
> >  3. Support common operations on Deque (pushing and popping items to
> > both front and back, subscript operator works, iteration, size, etc)
> > and add little else (don't be novel here). To me, the biggest thing
> > left to discuss is a notion of a maximum size, which in my own
> > experience is common for circular buffers (the implementation chosen
> > for Deque) but not all languages have this.
> >  4. This is less clear, but I'm in favor as long as we can provide a
> > few other data structures at the same time. Obviously, this a voter
> > judgement call on the yes/no.
> >
> > Given that I've suggested the most common options for these across
> > many languages, it shouldn't be very controversial. The worst bit
> > seems like picking the namespace "Collections" as this will break at
> > least one package: https://github.com/danielgsims/php-collections. We
> > should suggest that they vendor it anyway, as "collections" is common
> > 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

 make it easier to learn the language to have fewer terms and migrate 
code using SplDoublyLinkedList or arrays
- push()/shift() are also shorter names than pushBack/popFront()

Thanks,
Tyson


From: Nikita Popov 
Sent: October 4, 2021 8:04 AM
To: Levi Morrison 
Cc: PHP internals 
Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP 
 
On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
internals@lists.php.net> wrote:

> The name "deque" is used in the standard library of these languages:
>
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
>
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.
>
> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.
>
> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same
> package.
>  4. Whether this should be included in php-src or left to extensions.
>
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
> few other data structures at the same time. Obviously, this a voter
> judgement call on the yes/no.
>
> Given that I've suggested the most common options for these across
> many languages, it shouldn't be very controversial. The worst bit
> seems like picking the namespace "Collections" as this will break at
> least one package: https://github.com/danielgsims/php-collections. We
> should suggest that they vendor it anyway, as "collections" is common
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> a good alternative here to "Collections", as we haven't agreed on very
> much on past namespace proposals.
>
> Anyway, that's what I suggest.
>

I generally agree with everything Levi has said here. I think that adding a
deque structure generally makes sense, and that putting it into a new
ext/collections extension under the corresponding namespace would be
appropriate. I wouldn't insist on introducing it together with other
structures (I'm a lot more sceptical about your Vector proposal), but do
think there should be at least some overarching plan here, even if we only
realize a small part of it in this version.

A few questions for the particular API proposed here:

1. There would be the possibility of having an interface Deque that is
backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
would actually make sense, but I wanted to throw it out there, given that
the class is final (which is without any doubt the correct decision).

2. How do set() / offsetSet() work with an out of range index? Is it
possible to push an element with $deque[count($deque)] = x? I would assume
that throws, but want to make sure. On a related note, why do we need both
get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

3. I believe it's pretty standard for Deque implementations to provide
insert() / remove() methods to insert at any position (these would be O(n)).

4. The design of getIterator() here is rather unusual, and deserves some
additional justification. Normally, we let getIterator() see concurrent
modifications to the structure, though the precise behavior is unspecified.
I would also like to know how this will look like on a technical level (it
doesn't seem to be implemented yet?) This seems like something that will
require a check on every write operation, to potentially separate the
structure in some form.

5. The shift/unshift

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Nikita Popov]

On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
internals@lists.php.net> wrote:

> The name "deque" is used in the standard library of these languages:
>
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
>
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.
>
> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.
>
> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same
> package.
>  4. Whether this should be included in php-src or left to extensions.
>
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
> few other data structures at the same time. Obviously, this a voter
> judgement call on the yes/no.
>
> Given that I've suggested the most common options for these across
> many languages, it shouldn't be very controversial. The worst bit
> seems like picking the namespace "Collections" as this will break at
> least one package: https://github.com/danielgsims/php-collections. We
> should suggest that they vendor it anyway, as "collections" is common
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> a good alternative here to "Collections", as we haven't agreed on very
> much on past namespace proposals.
>
> Anyway, that's what I suggest.
>

I generally agree with everything Levi has said here. I think that adding a
deque structure generally makes sense, and that putting it into a new
ext/collections extension under the corresponding namespace would be
appropriate. I wouldn't insist on introducing it together with other
structures (I'm a lot more sceptical about your Vector proposal), but do
think there should be at least some overarching plan here, even if we only
realize a small part of it in this version.

A few questions for the particular API proposed here:

1. There would be the possibility of having an interface Deque that is
backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
would actually make sense, but I wanted to throw it out there, given that
the class is final (which is without any doubt the correct decision).

2. How do set() / offsetSet() work with an out of range index? Is it
possible to push an element with $deque[count($deque)] = x? I would assume
that throws, but want to make sure. On a related note, why do we need both
get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

3. I believe it's pretty standard for Deque implementations to provide
insert() / remove() methods to insert at any position (these would be O(n)).

4. The design of getIterator() here is rather unusual, and deserves some
additional justification. Normally, we let getIterator() see concurrent
modifications to the structure, though the precise behavior is unspecified.
I would also like to know how this will look like on a technical level (it
doesn't seem to be implemented yet?) This seems like something that will
require a check on every write operation, to potentially separate the
structure in some form.

5. The shift/unshift terminology is already used by our array API, but I'm
not sure it's the most intuitive choice in the context of a deque. SplQueue
has enqueue() and dequeue(). Another popular option from other languages
(which I would personally favor) is pushFront() and popFront().

Regards,
Nikita

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Levi Morrison,

> > "Maximum size" shouldn't be an issue for `Deque` specifically, it's a 
> > `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
> > (or for
> > PHP would just encounter a fatal error due to either
> 
> You wrote a lot, but unfortunately it was based on a misunderstanding.
> In some languages you can set the maximum allowed number of items a
> specific Deque can hold. For example (pseudo-code):
> 
>     let deque = new Deque(max_capacity: 3)
>     deque.push_back(1)
>     deque.push_back(2)
>     deque.push_back(3) # okay, it's now full
> 
>     deque.push_back(4) # !
> 
> In this condition, they either error or remove the earliest.
> 
> It's okay if the proposed Deque doesn't add this capability, but it's
> the only remaining major functionality which some languages have but
> not the others; it should at least be discussed, I think.

Oh, I hadn't remembered seeing that before. That makes sense.
All of the implementations I'd remembered were unlimited.
(https://cplusplus.com/reference/deque/deque/max_size/ was a system limit, for 
example)

I can't think of a common use case for that in php.
If there was one, though, I strongly believe it shouldn't be the same class 
(and shouldn't be a subclass),
in order to ensure the behavior of push or other operations remains easy to 
reason about.
This can be done in userland as a userland class.

- (e.g. with a Deque instance property and runtime `count() < 
$this->maxCapacity` checks,
  to choose their own desired return value or Throwable subclass (or manual 
array and circular buffer in PHP)

Thanks,
Tyson

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Levi Morrison via internals]

> "Maximum size" shouldn't be an issue for `Deque` specifically, it's a 
> `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
> (or for
> PHP would just encounter a fatal error due to either

You wrote a lot, but unfortunately it was based on a misunderstanding.
In some languages you can set the maximum allowed number of items a
specific Deque can hold. For example (pseudo-code):

let deque = new Deque(max_capacity: 3)
deque.push_back(1)
deque.push_back(2)
deque.push_back(3) # okay, it's now full

deque.push_back(4) # !

In this condition, they either error or remove the earliest.

It's okay if the proposed Deque doesn't add this capability, but it's
the only remaining major functionality which some languages have but
not the others; it should at least be discussed, I think.

-- 
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Levi Morrison,

> The name "deque" is used in the standard library of these languages:
> 
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
> 
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.

Thanks for putting that together.

For anyone wondering about the languages that don't have it:
The first 3 are compiled languages so there's the same performance for a 
standard library 
and third-party library code written in those libraries. 
For C and Go, the standard libraries of C and Go are written in C and Go.
C and Go also have a very minimal standard library as a design goal.
Everything in C and Go is a "native library", so a third-party library and a 
standard library would have the same performance.
(The standard library of C and Go use or allow embedding assembly for 
platform-dependent functionality or optimizations. 
Third party libraries in C or Go can also use inline assembly 
https://stackoverflow.com/a/23796420)
(Not familiar with C#'s standard library, I assume it's similar?)

And browser vendors have put immense amounts of effort on optimizing JavaScript
and the JIT compilers for JavaScript for low memory usage,
supporting inlining, working efficiently on various platforms, etc.

> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.

Yes, I'd agree.

It's a well established term in programming, and using a non-standard or more 
verbose term
would make it harder to find/remember this functionality for users moving to 
php from 
other programming languages, 
or for users moving from php to other programming languages.

Learning programming inevitably has unfamiliar terms such as `array`, `printf`, 
etc.
that are not commonly used in mathematics or daily life.

> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same 
> package.
>  4. Whether this should be included in php-src or left to extensions.
> 
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

I had planned on a minimal API for Deque.

"Maximum size" shouldn't be an issue for `Deque` specifically, it's a `size_t`. 
It isn't an issue for SplFixedArray and ArrayObject.
(or for 
PHP would just encounter a fatal error due to either

1. Hitting the `memory_limit` or available memory limit
while constructing or appending to the `Deque`
2. Seeing a fatal error due to integer overflow, which would only matter on 
32-bit php.
   (The `Deque` API doesn't have a setSize)
   The `safe_erealloc` macros allow you to do that.

For additions such as `Vector` and `Deque`, because we **can** choose a 
`size_t` (type large enough to store any size of memory) (and because 32-bit 
systems are increasingly rare),
I currently think always emitting an uncatchable fatal error (and exiting 
immediately) for impossibly large values
would be the most consistent (e.g. applications wouldn't reach `catch 
(Throwable $t)` 
blocks meant for a different purpose in an unexpected way, if they failed to 
validate inputs).
This is already done in array and SPL types.

```
php > var_dump(new SplFixedArray(PHP_INT_MAX));
Fatal error: Possible integer overflow in memory allocation 
(9223372036854775807 * 16 + 0) in php shell code on line 1

php > var_dump(array_fill(0, 2**31 - 2, null));

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to 
allocate 68719476744 bytes) in php shell code on line 1
php > var_dump(array_fill(0, 2**31, null));

Warning: Uncaught ValueError: array_fill(): Argument #2 ($count) is too large 
in php shell code:1
...

// Without memory_limit
php > 

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Levi Morrison via internals]

The name "deque" is used in the standard library of these languages:

 - C++: std::deque
 - Java: java.util.Deque (interface)
 - Python: collections.deque
 - Swift: Collections.Deque (not standard lib, apparently, but Apple
official? Don't know Swift)
 - Rust: std::collections::VecDeque

And these don't have it in the standard library:
 - Go
 - C#
 - C
 - JavaScript

Anyway, it's pretty decent evidence that:
 1. This functionality is pretty widely used across languages.
 2. This functionality should have "deque" be in the name, or be the
complete name.

Discussion naming for "vector" I can understand, as it's less widely
used or sometimes means something specific to numbers, but there's
little point in discussing the name "deque." It's well established in
programming, whether PHP programmers are aware of it or not.

As I see it, the discussion should be centered around:
 1. The API Deque provides.
 2. The package that provides it.
 3. Whether Deque's API is consistent with other structures in the same package.
 4. Whether this should be included in php-src or left to extensions.

I suggest that we try to make PHP as homogenous in each bullet as we
can with other languages:
 1. Name it "Deque."
 2. Put it in the namespace "Collections" (and if included in core,
then "ext/collections").
 3. Support common operations on Deque (pushing and popping items to
both front and back, subscript operator works, iteration, size, etc)
and add little else (don't be novel here). To me, the biggest thing
left to discuss is a notion of a maximum size, which in my own
experience is common for circular buffers (the implementation chosen
for Deque) but not all languages have this.
 4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

Given that I've suggested the most common options for these across
many languages, it shouldn't be very controversial. The worst bit
seems like picking the namespace "Collections" as this will break at
least one package: https://github.com/danielgsims/php-collections. We
should suggest that they vendor it anyway, as "collections" is common
e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
a good alternative here to "Collections", as we haven't agreed on very
much on past namespace proposals.

Anyway, that's what I suggest.

-- 
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mike Schinkel]

> On Sep 21, 2021, at 1:12 PM, Pierre Joye  wrote:
> On Tue, Sep 21, 2021, 11:56 PM Mike Schinkel  > wrote:
> > On Sep 21, 2021, at 3:45 AM, Pierre Joye  > > wrote:
> > 
> > On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  > > wrote:
> > 
> >> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why 
> >> we would name a class with a verb?  It wasn't until Rowan's comment that I 
> >> realized `Deque` is an abbreviation.
> >> 
> >> Which begs the question: how many other PHP developers will know computer 
> >> science terms like this well enough to know `Deque` is a noun when they 
> >> see it, and more importantly how many PHP developers will think to search 
> >> for `Deque` when they need a queue?
> > 
> > Unlike the Vector name which is really confusing as it is not a
> > vector, Deque is actually relatively known for anyone needing a double
> > ended queue. It even comes first in google search, wikipedia or java
> > implementations, which matches this implementation.
> 
> Being able to google what Deque means is one thing, but thinking to search 
> for it when you don't know it exists *and* you don't know that Deque is the 
> term you would need to be searching for.
> 
> > We expect our
> > users to know all weird names of different patterns, I trust them to
> > be able to learn what a Deque is. :)
> 
> So we expect PHP developers to have a computer science background? Maybe you 
> are assuming everyone minimally has your expertise?  Have we as a group 
> decided to forsake beginners? 
> 
> 
> It is not what I was trying to explain.
> 
> However if one looks at the php documentation looking for specific things 
> like these, the Deque will be there. 
> 
> So I am not expecting anyone to have a CS background (btw, I don't), however 
> I do have a minimal trust in users reading the docs and doing a minimum of 
> research. 

And what I was trying to explain is that given my past experience working with 
other PHP developers, I believe that trust is misplaced for many.  

And why make it harder than it needs to be? For PHP, jargon is Bad(tm), IMHO 
anyway.

-Mike

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre Joye]

On Tue, Sep 21, 2021, 11:56 PM Mike Schinkel  wrote:

> > On Sep 21, 2021, at 3:45 AM, Pierre Joye  wrote:
> >
> > On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel 
> wrote:
> >
> >> Honestly, at first I confused `Deque` with `Dequeue` and was wondering
> why we would name a class with a verb?  It wasn't until Rowan's comment
> that I realized `Deque` is an abbreviation.
> >>
> >> Which begs the question: how many other PHP developers will know
> computer science terms like this well enough to know `Deque` is a noun when
> they see it, and more importantly how many PHP developers will think to
> search for `Deque` when they need a queue?
> >
> > Unlike the Vector name which is really confusing as it is not a
> > vector, Deque is actually relatively known for anyone needing a double
> > ended queue. It even comes first in google search, wikipedia or java
> > implementations, which matches this implementation.
>
> Being able to google what Deque means is one thing, but thinking to search
> for it when you don't know it exists *and* you don't know that Deque is the
> term you would need to be searching for.
>
> > We expect our
> > users to know all weird names of different patterns, I trust them to
> > be able to learn what a Deque is. :)
>
> So we expect PHP developers to have a computer science background? Maybe
> you are assuming everyone minimally has your expertise?  Have we as a group
> decided to forsake beginners?



It is not what I was trying to explain.

However if one looks at the php documentation looking for specific things
like these, the Deque will be there.

So I am not expecting anyone to have a CS background (btw, I don't),
however I do have a minimal trust in users reading the docs and doing a
minimum of research.

best,

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mike Schinkel]

> On Sep 21, 2021, at 3:45 AM, Pierre Joye  wrote:
> 
> On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  wrote:
> 
>> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why 
>> we would name a class with a verb?  It wasn't until Rowan's comment that I 
>> realized `Deque` is an abbreviation.
>> 
>> Which begs the question: how many other PHP developers will know computer 
>> science terms like this well enough to know `Deque` is a noun when they see 
>> it, and more importantly how many PHP developers will think to search for 
>> `Deque` when they need a queue?
> 
> Unlike the Vector name which is really confusing as it is not a
> vector, Deque is actually relatively known for anyone needing a double
> ended queue. It even comes first in google search, wikipedia or java
> implementations, which matches this implementation.

Being able to google what Deque means is one thing, but thinking to search for 
it when you don't know it exists *and* you don't know that Deque is the term 
you would need to be searching for.

> We expect our
> users to know all weird names of different patterns, I trust them to
> be able to learn what a Deque is. :)

So we expect PHP developers to have a computer science background? Maybe you 
are assuming everyone minimally has your expertise?  Have we as a group decided 
to forsake beginners?  

-Mike
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre Joye]

On Tue, Sep 21, 2021 at 11:21 AM Mike Schinkel  wrote:

> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why we 
> would name a class with a verb?  It wasn't until Rowan's comment that I 
> realized `Deque` is an abbreviation.
>
> Which begs the question: how many other PHP developers will know computer 
> science terms like this well enough to know `Deque` is a noun when they see 
> it, and more importantly how many PHP developers will think to search for 
> `Deque` when they need a queue?

Unlike the Vector name which is really confusing as it is not a
vector, Deque is actually relatively known for anyone needing a double
ended queue. It even comes first in google search, wikipedia or java
implementations, which matches this implementation. We expect our
users to know all weird names of different patterns, I trust them to
be able to learn what a Deque is. :)

best,
-- 
Pierre

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

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Mike Schinkel]

> On Sep 19, 2021, at 8:03 PM, tyson andre  wrote:
> 
> Hi internals,
> 
> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class 
> Deque`
> 
> This is based on the `Teds\Deque` implementation I've worked on
> for the https://github.com/TysonAndre/pecl-teds PECL.

With one caveat, this is a much stronger RFC than the Vector one.  Good job!

However...

> On Sep 20, 2021, at 4:25 PM, Rowan Tommins  wrote:
> 
> On 20/09/2021 14:46, tyson andre wrote:
>> The choice of global namespace maintains consistency with the namespace used 
>> for general-purpose collections already in the SPL
> 
> I find this argument unconvincing. If the intention is for this to fit with 
> existing classes in the SPL, it should be called "SplDeque", or more 
> consistently "SplDoubleEndedQueue", and the RFC should talk about how the 
> design aligns with those existing classes.
> 
> If it is intended to be the first of a new set of data structures which are 
> *not* aligned with the existing SPL types, then putting it in a new namespace 
> would make most sense.
> 
> In the RFC and the list you've mentioned a few comparisons, but I don't think 
> any of them hold:
> 
> * ArrayObject, WeakReference, and WeakMap are all classes for binding to 
> specific engine behaviour, not generic data structures
> * Iterators all have an "Iterator" suffix (leading to some quite awkward 
> names)
> * Reflection classes all have a "Reflection" prefix
> * Having both "Queue" and "SplQueue", or both "Stack" and "SplStack" would be 
> a terrible idea, and is a pretty strong argument *not* to add data structures 
> with such plain names

I am in complete agreement with Rowan.  

Honestly, at first I confused `Deque` with `Dequeue` and was wondering why we 
would name a class with a verb?  It wasn't until Rowan's comment that I 
realized `Deque` is an abbreviation.  

Which begs the question: how many other PHP developers will know computer 
science terms like this well enough to know `Deque` is a noun when they see it, 
and more importantly how many PHP developers will think to search for `Deque` 
when they need a queue?

So here is a straw man argument; name the class one of:

- DataStruct\DoubleEndedQueue, or
- DataStruct\DE_Queue

Let the bike-shedding begin! 

(Or is that "Let it continue?")

-Mike

P.S. BTW re: https://github.com/TysonAndre/pecl-teds 
, who is Ted? (pun intended)

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Rowan Tommins]

On 20/09/2021 14:46, tyson andre wrote:

The choice of global namespace maintains consistency with the namespace used 
for general-purpose collections already in the SPL



I find this argument unconvincing. If the intention is for this to fit 
with existing classes in the SPL, it should be called "SplDeque", or 
more consistently "SplDoubleEndedQueue", and the RFC should talk about 
how the design aligns with those existing classes.


If it is intended to be the first of a new set of data structures which 
are *not* aligned with the existing SPL types, then putting it in a new 
namespace would make most sense.


In the RFC and the list you've mentioned a few comparisons, but I don't 
think any of them hold:


* ArrayObject, WeakReference, and WeakMap are all classes for binding to 
specific engine behaviour, not generic data structures
* Iterators all have an "Iterator" suffix (leading to some quite awkward 
names)

* Reflection classes all have a "Reflection" prefix
* Having both "Queue" and "SplQueue", or both "Stack" and "SplStack" 
would be a terrible idea, and is a pretty strong argument *not* to add 
data structures with such plain names



Regards,

--
Rowan Tommins
[IMSoP]

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre]

Le 20/09/2021 à 15:46, tyson andre a écrit :

Hi Pierre,
I'm not certain what you mean by "normalize".
https://www.merriam-webster.com/dictionary/normalize mentions


At least please try to make it serious, I think you understood what I 
meant. I'm in no place in arguing about technical details about how it 
should be implemented because the C language is not a place where I 
shine and I trust people like you for doing it best.


Nevertheless, my only point was, please put all data structures 
altogether, and please, just don't throw them in global namespace. 
Otherwise, as we said in french "ça va être un sacré bordel là dedans" 
(actually, it already is "un sacré bordel").


I'll let someone better in english than me translate, I'm not a native 
english speaker I could get it wrong.



If you also mean all datastructure RFCs should be combined into a single RFC,
I'd considered combining the Vector RFC with https://wiki.php.net/rfc/deque,
but decided against combining the RFCs in this instance, because of:


No, not necessarily, they don't need to be in the same RFC, having one 
per data structure is probably the way to go you'll maximize chances 
that each one pass vote. Nevertheless, many RFC's exist and if there's 
many other to come, no matter in which order they'll happen and no 
matter at which pace, they still can be seen as a "whole", and a 
namespace is a in my opinion still a good idea.


I won't debate on the rest, because you are much more both involved and 
technically competent than I am, and as being someone stupid, I need 
things to be well-organized to find them easily, that's the only 
constructive argument I have to bring to this discussion.


Regards,

--

Pierre

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi Pierre,

> It seems that you are writing more than one RFC to add many data 
> structures. I love that you're doing that, but I suggest that you'd 
> normalize them all

I'm not certain what you mean by "normalize".
https://www.merriam-webster.com/dictionary/normalize mentions

1. "to make conform to or reduce to a norm or standard"
2. 
https://www.freetext.org/Introduction_to_Linear_Algebra/Basic_Vector_Operations/Normalization/
   (no pun intended)
3. "to bring or restore to a normal condition"

If you mean to make Vector and Queue's APIs consistent with each other,
I plan to make changes to Vector (e.g. remove $preserveKeys, add isEmpty), but 
the Vector RFC is currently on hold.

If you also mean all datastructure RFCs should be combined into a single RFC,
I'd considered combining the Vector RFC with https://wiki.php.net/rfc/deque,
but decided against combining the RFCs in this instance, because of:

1. Current discussion about whether or not to choose an alternate name for a 
`Vector`
2. The fact that `Deque` has much better performance for various queue workloads
   on both time and memory usage than `array`
   (and significantly better performance than `SplDoublyLinkedList`).

Still, I may consider the approach for future RFCs, given that

1. Many developers in internals have expressed a desire for having a 
significantly 
   larger data structure library in core along the lines of what php-ds 
provides,
   but may be uninterested in some of the individual datastructures or design 
choices.

   E.g. if 60% of developers were in favor of a sorted set and its proposed 
API/name 
   (along the lines of https://cplusplus.com/reference/set/set/),
   60% were in favor of an immutable sequence and its proposed API/name (of 
values) (similar to 
https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences),
   then with the 2/3 voting threshold,
   neither of those RFCs would pass but a proposal combining those two would 
pass,
   despite ~95% of developers wanting some type of improved datastructures 
added to core in general (I would guess).
2. This would allow seeing how datastructures compare to each other.

Combining RFCs has the drawback of significantly increasing the implementation, 
discussion, review,
delays, and time involvement for the volunteer RFC authors and voters,
and may lead to a larger number of last-minute concerns raised after voting has 
started when more time 
is spent trying out the new code and looking at the RFC.

> and place all new classes in a single new dedicated 
> namespace.

My rationale for deciding against a dedicated namespace is in 
https://wiki.php.net/rfc/deque#global_namespace
which I've recently expanded on.

The `Deque` proposal is normalized with respect to the namespace choice of data 
structures that already exist.

The choice of global namespace maintains consistency with the namespace used 
for general-purpose collections already in the SPL 
(as well as relatively recent additions such as ''WeakReference'' (PHP 7.4) and 
''WeakMap'' (PHP 8.0)).
Other recent additions to PHP such as ''ReflectionIntersectionType'' in PHP 8.1 
have 
also continued to use the global namespace when adding classes with 
functionality related to other classes.

Additionally, prior polls for namespacing choices of other datastructure 
functionality showed preferences 
for namespacing and not namespacing were evenly split in a straw poll for a new 
iterable type
(https://wiki.php.net/rfc/cachediterable_straw_poll#namespace_choices)

Introducing a new namespace for data structures would also raise the question 
of whether existing datastructures 
should be moved to that new namespace (for consistency), and that process would:

1. Raise the amount of work needed for end users or 
library/framework/application authors to migrate to new PHP versions.
2. Cause confusion and inconvenience for years about which namespace can or 
should be used in an application 
   (''SplObjectStorage'' vs ''Xyz\SplObjectStorage''), especially for 
developers working on projects supporting different php version ranges.
3. Prevent applications/libraries from easily supporting as wide of a range of 
php versions as they otherwise could.
4. Cause serialization/unserialization issues when migrating to different php 
versions,
   if the old or new class name in the serialized data did not exist in the 
other php version and was not aliased.
   For example, if the older PHP version could not ''unserialize()'' 
''Xyz\SplObjectStorage'' 
   and would silently create a `__PHP_Incomplete_Class_Name` 
   (see 
https://www.php.net/manual/en/language.oop5.serialization.php#language.oop5.serialization)
   without any warnings or notices.

Thanks,
Tyson

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Christian Schneider]

Am 20.09.2021 um 10:36 schrieb Pierre :
> Le 20/09/2021 à 02:03, tyson andre a écrit :
>> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class 
>> Deque`
> 
> It seems that you are writing more than one RFC to add many data structures. 
> I love that you're doing that, but I suggest that you'd normalize them all 
> and place all new classes in a single new dedicated namespace.

+1

- Chris

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

Re: [PHP-DEV] Adding `final class Deque` to PHP

[Pierre]

Le 20/09/2021 à 02:03, tyson andre a écrit :

Hi internals,

I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class 
Deque`


Hello,

It seems that you are writing more than one RFC to add many data 
structures. I love that you're doing that, but I suggest that you'd 
normalize them all and place all new classes in a single new dedicated 
namespace.


Regards,

--

Pierre

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php

[PHP-DEV] Adding `final class Deque` to PHP

[tyson andre]

Hi internals,

I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class 
Deque`

This is based on the `Teds\Deque` implementation I've worked on
for the https://github.com/TysonAndre/pecl-teds PECL.

While `SplDoublyLinkedList` and its subclass `SplQueue`/`SplStack` exist in the 
SPL, they have several drawbacks
that are addressed by this RFC to add a `Deque` class (to use instead of those):

1. `SplDoublyLinkedList` is internally represented by a doubly linked list,
   making it use roughly twice as much memory as the proposed `Deque`
2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower due to
   needing to allocate or free the linked list nodes.
3. Reading values in the middle of the `SplDoublyLinkedList` is proportional to 
the length of the list,
   due to needing to traverse the linked list nodes.
4. `foreach` Iteration behavior cannot be understood without knowing what 
constructed the
   `SplDoublyLinkedList` instance or set the flags.

It would be useful to have an efficient `Deque` container in the standard 
library
to provide an alternative without those drawbacks,
as well as for the following reasons:

1. To save memory in applications or libraries that may need to store many 
lists of values or run for long periods of time.
   Notably, PHP's `array` type will never release allocated capacity.
   See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html
2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`, and 
`SplQueue`
   for use cases that require stacks or queues.
3. As a more efficient option than `array` and `SplDoublyLinkedList`
   as a queue or `Deque`, especially for `unshift`.

A `Deque` is more efficient than an `array` when used as a queue, more 
readable, and easier to use correctly.
While it is possible to efficiently remove elements from the start of an 
`array` (in terms of insertion order),
it is very inefficient to prepend elements to the start of a large `array` due 
to needing to either copy the array
or move all elements in the internal array representation,
and an `array` would use much more memory than a `Deque` when used that way 
(and be slower).

There are also several pitfalls to using an array as a queue for larger queue 
sizes,
some of which are not obvious and discovered while writing the benchmarks.
(Having a better (double-ended) queue datastructure (`Deque`) than the 
`SplDoublyLinkedList`
would save users from needing to write code with these pitfalls):

1. `array_key_first()` takes time proportional to the number of elements 
`unset` from the start of an array,
   causing it to unexpectedly be extremely slow (quadratic time) after 
unsetting many elements at the start of the queue.
   (when the array infrequently runs out of capacity, buckets are moved to the 
front)
2. `reset()` or `end()` will convert a variable to a reference,
   and php is significantly less efficient at reading or writing to reference.
   Opcache is also less efficient at optimizing uses of variables using 
references.
3. More obviously, `array_unshift` and `array_shift` will take time 
proportional to the number of elements in the array
   (to reindex and move existing/remaining elements).

After the discussion period ends, I currently plan to start voting on the 
`Deque` RFC and await the results
to determine next steps for the `Vector` RFC.



The thread for my other open proposal `final class Vector` 
(https://externals.io/message/116048) has prior discussion on implementation 
choices,
naming choices, and motivation for adding datastructures to php-src.

- E.g. the question of why we should add general-purpose datastructures
  to php-src itself rather than have users rely on PECLs,
  and why this proposal doesn't and can't use `php-ds`/`ext-ds`.

Thanks,
Tyson

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: https://www.php.net/unsub.php