Adding `final class Deque` to PHP View as Markdown

Am 20.09.2021 um 10:36 schrieb Pierre pierre-php@processus.org:

Le 20/09/2021 à 02:03, tyson andre a écrit :

I've created a new RFC https://wiki.php.net/rfc/deque to add a final class Deque

It seems that you are writing more than one RFC to add many data structures. I love that you're doing that, but I suggest that you'd normalize them all and place all new classes in a single new dedicated namespace.

+1

• Chris

Hi Pierre,

It seems that you are writing more than one RFC to add many data
structures. I love that you're doing that, but I suggest that you'd
normalize them all

I'm not certain what you mean by "normalize".
https://www.merriam-webster.com/dictionary/normalize mentions

1. "to make conform to or reduce to a norm or standard"
2. https://www.freetext.org/Introduction_to_Linear_Algebra/Basic_Vector_Operations/Normalization/
   (no pun intended)
3. "to bring or restore to a normal condition"

If you mean to make Vector and Queue's APIs consistent with each other,
I plan to make changes to Vector (e.g. remove $preserveKeys, add isEmpty), but the Vector RFC is currently on hold.

If you also mean all datastructure RFCs should be combined into a single RFC,
I'd considered combining the Vector RFC with https://wiki.php.net/rfc/deque,
but decided against combining the RFCs in this instance, because of:

1. Current discussion about whether or not to choose an alternate name for a Vector
2. The fact that Deque has much better performance for various queue workloads
   on both time and memory usage than array
   (and significantly better performance than SplDoublyLinkedList).

Still, I may consider the approach for future RFCs, given that

1. Many developers in internals have expressed a desire for having a significantly
   larger data structure library in core along the lines of what php-ds provides,
   but may be uninterested in some of the individual datastructures or design choices.

   E.g. if 60% of developers were in favor of a sorted set and its proposed API/name
   (along the lines of https://cplusplus.com/reference/set/set/),
   60% were in favor of an immutable sequence and its proposed API/name (of values) (similar to https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences),
   then with the 2/3 voting threshold,
   neither of those RFCs would pass but a proposal combining those two would pass,
   despite ~95% of developers wanting some type of improved datastructures added to core in general (I would guess).

2. This would allow seeing how datastructures compare to each other.

Combining RFCs has the drawback of significantly increasing the implementation, discussion, review,
delays, and time involvement for the volunteer RFC authors and voters,
and may lead to a larger number of last-minute concerns raised after voting has started when more time
is spent trying out the new code and looking at the RFC.

and place all new classes in a single new dedicated
namespace.

My rationale for deciding against a dedicated namespace is in https://wiki.php.net/rfc/deque#global_namespace
which I've recently expanded on.

The Deque proposal is normalized with respect to the namespace choice of data structures that already exist.

The choice of global namespace maintains consistency with the namespace used for general-purpose collections already in the SPL
(as well as relatively recent additions such as ''WeakReference'' (PHP 7.4) and ''WeakMap'' (PHP 8.0)).
Other recent additions to PHP such as ''ReflectionIntersectionType'' in PHP 8.1 have
also continued to use the global namespace when adding classes with functionality related to other classes.

Additionally, prior polls for namespacing choices of other datastructure functionality showed preferences
for namespacing and not namespacing were evenly split in a straw poll for a new iterable type
(https://wiki.php.net/rfc/cachediterable_straw_poll#namespace_choices)

Introducing a new namespace for data structures would also raise the question of whether existing datastructures
should be moved to that new namespace (for consistency), and that process would:

1. Raise the amount of work needed for end users or library/framework/application authors to migrate to new PHP versions.
2. Cause confusion and inconvenience for years about which namespace can or should be used in an application
   (''SplObjectStorage'' vs ''Xyz\SplObjectStorage''), especially for developers working on projects supporting different php version ranges.
3. Prevent applications/libraries from easily supporting as wide of a range of php versions as they otherwise could.
4. Cause serialization/unserialization issues when migrating to different php versions,
   if the old or new class name in the serialized data did not exist in the other php version and was not aliased.
   For example, if the older PHP version could not ''unserialize()'' ''Xyz\SplObjectStorage''
   and would silently create a __PHP_Incomplete_Class_Name
   (see https://www.php.net/manual/en/language.oop5.serialization.php#language.oop5.serialization)
   without any warnings or notices.

Thanks,
Tyson

Honestly, at first I confused Deque with Dequeue and was wondering why we would name a class with a verb? It wasn't until Rowan's comment that I realized Deque is an abbreviation.

Which begs the question: how many other PHP developers will know computer science terms like this well enough to know Deque is a noun when they see it, and more importantly how many PHP developers will think to search for Deque when they need a queue?

Unlike the Vector name which is really confusing as it is not a
vector, Deque is actually relatively known for anyone needing a double
ended queue. It even comes first in google search, wikipedia or java
implementations, which matches this implementation. We expect our
users to know all weird names of different patterns, I trust them to
be able to learn what a Deque is. :)

best,

Pierre

@pierrejoye | http://www.libgd.org

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/

Thanks,
Tyson

--

To unsubscribe, visit: https://www.php.net/unsub.php

Hi Tyson,

As a userland dev & library author it’s nice to see some progression on basic data structures, so thank you for your efforts on this!

Two little things in the RFC:

The proposed API switches between terms front, back, start and end in comments - is there meant to be a conceptual difference between front/start and end/back ?

In the "Why use this instead of array?” Section, the 3rd point seems cut off:

Note that starting in php 8.2, array

Cheers

Stephen

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/

Request:

push() and unshift() currently return void. That's not helpful. It would be vastly more useful if they both returned $this. Not as much for chaining, but more so that you can add a value to a queue and pass it as an argument to another call (often recursive, but not necessarily) in a single operation.

Example: I was doing last year's Advent of Code in functional PHP, and had a stack walker that looked like this:

function parse(string $line, $pos = 0, array $stack = []): Result|string
{
$next = $line[$pos] ?? null;
$head = $stack[0] ?? null;

return match ($next) {
    // Opening brace, push an "expected" onto the stack.
    '{' => parse($line, $pos + 1, ['}', ...$stack]),
    '<' => parse($line, $pos + 1, ['>', ...$stack]),
    '(' => parse($line, $pos + 1, [')', ...$stack]),
    '[' => parse($line, $pos + 1, [']', ...$stack]),
    '}', '>', ')', ']' => $next === $head ? parse($line, $pos + 1, array_slice($stack, 1)) : $next,
    null => count($stack) ? Result::Incomplete : Result::OK,
};

}

The interesting part is the ['<', ...$stack], to pass on a modified version of an array-as-stack. That's of course annoyingly slow with arrays right now, and a Deque would be better, but only if it could be "modified and passed" like that. If not, it would be incompatible with single-expression usages (match statements, short lambdas, etc.)

Returning $this would resolve that, I think. (Making it return a new, immutable copy of the Deque would be even nicer, but I realize that's probably not an argument I'm going to win at this point on this RFC.)

Also, typo:

"By introducing a data structure (Deque) that's even faster and more memory usage than an array for use as a double-ended queue, even more applications would benefit from it. "

I think you mean "less memory usage", or possibly "more memory efficient", or something like that.

--Larry Garfield

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