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/
I've updated the RFC https://wiki.php.net/rfc/deque yet again (no
implementation changes). I now plan to start voting on Saturday, February 5th.
I've also updated the WebAssembly demo at
https://tysonandre.github.io/php-rfc-d
