Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116100
To: "internals@lists.php.net" <internals@lists.php.net>
Thread-Topic: Adding `final class Deque` to PHP
Thread-Index: AQHXraUxaK1dZ0niuECOJlLUpHNcpQ==
Date: Mon, 20 Sep 2021 00:03:33 +0000
Message-ID:
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
Accept-Language: en-CA, en-US
Content-Language: en-CA
suggested_attachment_session_id: 073262ea-caf5-1206-2c9a-2ef6c7532526
x-tmn:
 [fBYrlmwtnEmXAKgK6K4V0ZMD8BwRelYRMvmvv2CRcdSSZGM0K5F8n8FcLhEgHLReQOJ4KE6J9+U=]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: faacd2dc-6f7f-4180-0a7c-08d97bca1625
x-ms-traffictypediagnostic: DM6PR07MB7913:
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info:
 22l8vL7UhWQ9udV8dMqlSf6QEV3mvFvXKqJo/CiqNiUI3oPUz0D84vwMP7OrU2OfHninOz5LkYecRpe5KxzecFC41s5xJPxzAce8h7nmTbnqR/07wH4IGN/gk8EdMuMmKButJ1JvKk4Mi1rb2xQyjSC6vCUkA66WEWt0M2mAv/dWSyKsasl+TvFrmPltVm5MVRVHPeYVkzGOsGq1eCsccElXO2eVidUiHNVW1NKanxlldfNSaiYOHWM2l/o0HtSKz3vRFu0asioXJEnTBueXSb/E130v3txxRDLLwXXLOu2ftG8QqbEUAZ5pUg+F6Bvt/TEuJ8AnC/QD2AJpiY/wnEKx1hwGupTv3fSVmyN4gJTITU8NCtBpkLkxBOMZOtzm/9FAxt1AicRHXBCHIQk91WV2im6UG+KB0hMCSXUYQgZHc/3UelbU5exktHK6jE/ALRC4xWwNlamMmBH+B+JrRsTCirUboYLWiAqVO+oxryc=
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0:
 Xk+96ATnVyC9JNY1li9U65QnaAnUy0PuIHmqkACqJKh7fl0sKGaVoqmwwic8JbV3IbXMM6OedFCOts2VMkBXXUzhUBMRkEoaIxNo0q9iPlP1/XvDckuRyDg878TQHc17jOl3Sea0ZwSChDwlPrLHzTKCaselyYcuWWbq4g/Ni0AAK0fW+SGD22RsI2ftG7qMrCtDEQzHt2ruuCQQZqwY4A==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: sct-15-20-3174-20-msonline-outlook-35401.templateTenant
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: DM6PR07MB6618.namprd07.prod.outlook.com
X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000
X-MS-Exchange-CrossTenant-Network-Message-Id: faacd2dc-6f7f-4180-0a7c-08d97bca1625
X-MS-Exchange-CrossTenant-originalarrivaltime: 20 Sep 2021 00:03:33.3862
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa
X-MS-Exchange-CrossTenant-rms-persistedconsumerorg: 00000000-0000-0000-0000-000000000000
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR07MB7913
Subject: Adding `final class Deque` to PHP
From: tysonandre775@hotmail.com (tyson andre)

Hi internals,=0A=
=0A=
I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class=
 Deque`=0A=
=0A=
This is based on the `Teds\Deque` implementation I've worked on=0A=
for the https://github.com/TysonAndre/pecl-teds PECL.=0A=
=0A=
While `SplDoublyLinkedList` and its subclass `SplQueue`/`SplStack` exist in=
 the SPL, they have several drawbacks=0A=
that are addressed by this RFC to add a `Deque` class (to use instead of th=
ose):=0A=
=0A=
1. `SplDoublyLinkedList` is internally represented by a doubly linked list,=
=0A=
   making it use roughly twice as much memory as the proposed `Deque`=0A=
2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower due=
 to=0A=
   needing to allocate or free the linked list nodes.=0A=
3. Reading values in the middle of the `SplDoublyLinkedList` is proportiona=
l to the length of the list,=0A=
   due to needing to traverse the linked list nodes.=0A=
4. `foreach` Iteration behavior cannot be understood without knowing what c=
onstructed the=0A=
   `SplDoublyLinkedList` instance or set the flags.=0A=
=0A=
It would be useful to have an efficient `Deque` container in the standard l=
ibrary=0A=
to provide an alternative without those drawbacks,=0A=
as well as for the following reasons:=0A=
=0A=
1. To save memory in applications or libraries that may need to store many =
lists of values or run for long periods of time.=0A=
   Notably, PHP's `array` type will never release allocated capacity.=0A=
   See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.=
html=0A=
2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`, an=
d `SplQueue`=0A=
   for use cases that require stacks or queues.=0A=
3. As a more efficient option than `array` and `SplDoublyLinkedList`=0A=
   as a queue or `Deque`, especially for `unshift`.=0A=
=0A=
A `Deque` is more efficient than an `array` when used as a queue, more read=
able, and easier to use correctly.=0A=
While it is possible to efficiently remove elements from the start of an `a=
rray` (in terms of insertion order),=0A=
it is very inefficient to prepend elements to the start of a large `array` =
due to needing to either copy the array=0A=
or move all elements in the internal array representation,=0A=
and an `array` would use much more memory than a `Deque` when used that way=
 (and be slower).=0A=
=0A=
There are also several pitfalls to using an array as a queue for larger que=
ue sizes,=0A=
some of which are not obvious and discovered while writing the benchmarks.=
=0A=
(Having a better (double-ended) queue datastructure (`Deque`) than the `Spl=
DoublyLinkedList`=0A=
would save users from needing to write code with these pitfalls):=0A=
=0A=
1. `array_key_first()` takes time proportional to the number of elements `u=
nset` from the start of an array,=0A=
   causing it to unexpectedly be extremely slow (quadratic time) after unse=
tting many elements at the start of the queue.=0A=
   (when the array infrequently runs out of capacity, buckets are moved to =
the front)=0A=
2. `reset()` or `end()` will convert a variable to a reference,=0A=
   and php is significantly less efficient at reading or writing to referen=
ce.=0A=
   Opcache is also less efficient at optimizing uses of variables using ref=
erences.=0A=
3. More obviously, `array_unshift` and `array_shift` will take time proport=
ional to the number of elements in the array=0A=
   (to reindex and move existing/remaining elements).=0A=
=0A=
After the discussion period ends, I currently plan to start voting on the `=
Deque` RFC and await the results=0A=
to determine next steps for the `Vector` RFC.=0A=
=0A=
----=0A=
=0A=
The thread for my other open proposal `final class Vector` (https://externa=
ls.io/message/116048) has prior discussion on implementation choices,=0A=
naming choices, and motivation for adding datastructures to php-src.=0A=
=0A=
- E.g. the question of why we should add general-purpose datastructures=0A=
  to php-src itself rather than have users rely on PECLs,=0A=
  and why this proposal doesn't and can't use `php-ds`/`ext-ds`.=0A=
=0A=
Thanks,=0A=
Tyson=0A=