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-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 -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: https://www.php.net/unsub.php
