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 > > > 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 ´RÇ/&¶ > > > ¡¶Øt@íV±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 U¤‰\•m > > ·ÞZ‘uhttps://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. There's more changes I found this morning while working on test cases for unrelated datastructures, so I'll be postponing the vote. 1. The maximum Collections\Deque size is probably going to be reduced to be the same as the maximum array size. For 64-bit php builds, that's roughly 2 billion (2147483648 elements, using at least 32 gigabytes of memory for array or Deque), which was more memory than I'd assumed (16 bytes per zval), and needing that much is expected to be a rare use case that can be revisited, e.g. if array size limits are raised. Collections would need to be converted to/from arrays for serialization, unserialization, debug output (var_export, json_encode, etc.), etc., so having a much larger maximum size didn't seem to have a compelling use case. 2. I found and proposed potential improvements for detection of infinite recursion in var_export/debug_zval_dump/json_encode affecting userland classes, existing spl classes, etc., which seemed worth finishing discussing before starting the vote. 3. Miscellaneous refactorings Thanks, Tyson