Re: Adding `final class Deque` to PHP

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 wp[Ëž. > > wØ™@‚1Chttps://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-demo/deque/ to include a benchmark to illustrate the differences in performance of shift/unshift at various deque/array sizes. A more detailed section on the performance of unshift/shift compared to array and existing data structures was added to the RFC. I've also added a discussion section for the request to return $this (https://externals.io/message/116100#116967), removed duplicated quotes, and clarified some parts of the RFC. Thanks, Tyson