Re: Adding `final class Deque` to PHP
| From: | tyson andre | Date: | Tue, 01 Feb 2022 14:46:19 +0000 |
| Subject: | Re: Adding `final class Deque` to PHP | ||
| References: | 1 | Groups: | php.internals |
| Request: | Send a blank email to internals+get-116965@lists.php.net to get a copy of this message | ||
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¼+((…ý
> ÓÀZÇ
> 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