Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116986
To: "internals@lists.php.net" <internals@lists.php.net>
Thread-Topic: Adding `final class Deque` to PHP
Thread-Index: AQHXraUxaK1dZ0niuECOJlLUpHNcpax/lZKygATD6ZWAAkBvMQ==
Date: Sun, 6 Feb 2022 02:39:06 +0000
Message-ID:
 <DM6PR14MB41556846B922C79DC5E430FFF92B9@DM6PR14MB4155.namprd14.prod.outlook.com>
References:
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
 <DM6PR14MB41556131E6A9D7812854AA75F9269@DM6PR14MB4155.namprd14.prod.outlook.com>
 <DM6PR14MB4155EECD794A874CB9A0AAA8F9299@DM6PR14MB4155.namprd14.prod.outlook.com>
In-Reply-To:
 <DM6PR14MB4155EECD794A874CB9A0AAA8F9299@DM6PR14MB4155.namprd14.prod.outlook.com>
Accept-Language: en-CA, en-US
Content-Language: en-CA
suggested_attachment_session_id: 8fa2a664-b184-c6c7-ec63-7dcbee6cd8d8
x-ms-exchange-messagesentrepresentingtype: 1
x-tmn: [fDnRrpc85bK0bW11T/U1scXVQvaN0vxl8IdwodyH/yv9a80aak38MY0Bb2sPIyYg]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: c1eddef9-ab69-4849-9955-08d9e919d88c
x-ms-traffictypediagnostic: CH2PR14MB4119:EE_
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info:
 Kb51i9WJ16XAkHtYGwWFrpNqwwnnciJhSEnNACUMemd+e/8M4z/Rv5Y7nn1d1YBMet/KSqRxrbGbD7Fpj9b50vkQhQ8X9G1vAx4b8FR5zw2jPj2pfg2A5Zi6lLrNfPFv+UrmK/6xybQQXldCUkuDMvR4ytvYpCUEeWZDY73SgE7XB5rBp2cTwUouALJSulK5mUIuFrYGOtNaMRsYpikOfeaF/Ne66WPW/Zf/VTt8LUS5h96I2UV71h/dLsTm+jcUlkwigs7s3pgA7/H1Gpasc7UyZ5HWJtYvJ857qiSbvfIX5Q4Xp7zZ6zl8IjAmfVMN4IZ5fgNrEgxpbMfuKtKtgLSLktX+AtKrjR60AmEVmorESxIIOrolq1glJm66xgbXMiuNjnjcVcL1jm154D1z//rYZrS8+RPYaw2xzvbyyqr/NWJ/drkNF8gAcVgkHwh3qbkWwe0geVAJVHBJgbrrs4X/FY9yLzAs4by4F/LtYHzTK0rA5VXb4UpmuMwO9UiBdNpInLeWDWy54rPdXBxI+K/p/YAPqtyM7UsYXCXpyThTTUwrsOq/dXJVc2p9GnxvrE4S6setvOvtZce3FeITtbNcTeNVmV9cPMXwkXCMjZ3FxPV7pfAukUknbqjLaWMXG1ROF8R+hsKmdmlpykj5bJm9Mk2/2cWAuncI6AzcfQM=
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0:
 =?iso-8859-1?Q?9J4AYIeRbNgdYE5u3HinVxNifcX8YOV7q3bRs/BN+8mKxB5qCOWu79d8nk?=
 =?iso-8859-1?Q?ZGeKCzXWDkZt2dSOI6BOrw4RP9Daz9os4Icnx0ekF0njEfgpaRMSLHxNRE?=
 =?iso-8859-1?Q?To9lSZUqg+OIFNfor+cHqzDyxED1IxI6dLVU21YYCS4LbAuX5IkV5vRUSC?=
 =?iso-8859-1?Q?KqLnB9ThE76+P8T+siuDBE43Lp7Oaf0AvXzHyoKeKZuNXJN5EXvawLGYJg?=
 =?iso-8859-1?Q?zt5zeXyCloQ0xUWS8GxmN5mg5A7iAbVjZXuf31r9GM9DliIcOXwymJpLId?=
 =?iso-8859-1?Q?wiwoevNXgCJGOGs+k0h3C1agqECMwRrcAbrnHV7BNJH1eU5ds4k8+3cMd+?=
 =?iso-8859-1?Q?6/U1rhb972Im4GIZirS/smUqRILL8MIIEcXd7JOE2COKXgUm3iNYyIV868?=
 =?iso-8859-1?Q?bxlcLiJ5aP/i2qM6/CnStzZu+cu1enO1VFLL6PG8YZuT+0ymGzihxKUL18?=
 =?iso-8859-1?Q?MzJCqT4UWWpahV6wfGaozhOPGgXNlOzIKqlGIW4APaSWhc5giODdRjBEdk?=
 =?iso-8859-1?Q?hyVrzBxLlA8uqRiVNB7aCJch0EkmTfK7p7QQ1X1cZ5sXZ+1WmKGMZiH7H1?=
 =?iso-8859-1?Q?MWmVVWuN6Yd+KmXpWlvv3y/st6KN7ZgTczGo+jBa0EsWT3TZ9xMbk3uH43?=
 =?iso-8859-1?Q?uHzOY0NApec0QtGL2pqB8k4YT8Sk483pLA2EIQFlhYiDrqKtsYQlltxKVu?=
 =?iso-8859-1?Q?d4u4WDpfiodthPRdkQ/yNWKo8/IfsmT8MqZXX3diHjmgomz0ufenOJ+2bJ?=
 =?iso-8859-1?Q?/vW+3ccfdcMXpB/8BEtB399QnIVyKgJ17uKqiX13ZK69RZ/HiG9+S50cdP?=
 =?iso-8859-1?Q?XYZsBx/AsEcjAlKvaOtKMd5Dr5dtF21MR2byoD6jkcQnmRdC1OTFoJkLGg?=
 =?iso-8859-1?Q?/YUZXO69IfudY1iRZqMfqsCk2RKOuPLjVexBr46zWnotLL60pRxLtUBzg7?=
 =?iso-8859-1?Q?OS/FKdfnhf5+VzPtn0xRseGKhTP3ESnAedqACxF8aVUaCYBSffKWeXiacP?=
 =?iso-8859-1?Q?3Z10UW7gpCD1s3Z2yOTwGS022KXSZCCuQxQHDM?=
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: sct-15-20-4755-11-msonline-outlook-cd57b.templateTenant
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: DM6PR14MB4155.namprd14.prod.outlook.com
X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000
X-MS-Exchange-CrossTenant-Network-Message-Id: c1eddef9-ab69-4849-9955-08d9e919d88c
X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Feb 2022 02:39:06.5245
 (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: CH2PR14MB4119
Subject: Re: 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` ex=
ist in the SPL, they have several drawbacks=0A=
> > > that are addressed by this RFC to add a `Deque` class (to use instead=
 of those):=0A=
> > >=0A=
> > > 1. `SplDoublyLinkedList` is internally represented by a doubly linked=
 list,=0A=
> > > =A0=A0 making it use roughly twice as much memory as the proposed `De=
que`=0A=
> > > 2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slow=
er due to=0A=
> > > =A0=A0 needing to allocate or free the linked list nodes.=0A=
> > > 3. Reading values in the middle of the `SplDoublyLinkedList` is propo=
rtional to the length of the list,=0A=
> > > =A0=A0 due to needing to traverse the linked list nodes.=0A=
> > > 4. `foreach` Iteration behavior cannot be understood without knowing =
what constructed the=0A=
> > > =A0=A0 `SplDoublyLinkedList` instance or set the flags.=0A=
> > >=0A=
> > > It would be useful to have an efficient `Deque` container in the stan=
dard library=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=
> > > =A0=A0 Notably, PHP's `array` type will never release allocated capac=
ity.=0A=
> > > =A0=A0 See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-imple=
mentation.html=0A=
> > > 2. To provide a better alternative to `SplDoublyLinkedList`, `SplStac=
k`, and `SplQueue`=0A=
> > > =A0=A0 for use cases that require stacks or queues.=0A=
> > > 3. As a more efficient option than `array` and `SplDoublyLinkedList`=
=0A=
> > > =A0=A0 as a queue or `Deque`, especially for `unshift`.=0A=
> > >=0A=
> > > A `Deque` is more efficient than an `array` when used as a queue, mor=
e readable, and easier to use correctly.=0A=
> > > 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),=0A=
> > > it is very inefficient to prepend elements to the start of a large `a=
rray` 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 th=
at way (and be slower).=0A=
> > >=0A=
> > > There are also several pitfalls to using an array as a queue for larg=
er queue sizes,=0A=
> > > some of which are not obvious and discovered while writing the benchm=
arks.=0A=
> > > (Having a better (double-ended) queue datastructure (`Deque`) than th=
e `SplDoublyLinkedList`=0A=
> > > would save users from needing to write code with these pitfalls):=0A=
> > >=0A=
> > > 1. `array_key_first()` and reset()`takes time proportional to the num=
ber of elements `unset` from the start of an array,=0A=
> > > =A0=A0 causing it to unexpectedly be extremely slow (quadratic time) =
after unsetting many elements at the start of the queue.=0A=
> > > =A0=A0 (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=
> > > =A0=A0 and php is less efficient at reading or writing to reference.=
=0A=
> > > =A0=A0 Opcache is also less efficient at optimizing uses of variables=
 using references.=0A=
> > > 3. More obviously, `array_unshift` and `array_shift` will take time p=
roportional to the number of elements in the array=0A=
> > > =A0=A0 (to reindex and move existing/remaining elements).=0A=
> >=0A=
> > I plan to start voting on https://wiki.php.net/rfc/deque on Friday, Feb=
ruary 4th.=0A=
> >=0A=
> > Several changes have been made to https://wiki.php.net/rfc/deque#change=
log=0A=
> > after the feedback in https://externals.io/message/116100=0A=
> >=0A=
> > - The class is now named `Collections\Deque`=0A=
> > - The api documentation in https://wiki.php.net/rfc/deque#proposal was =
expanded for methods.=0A=
> > - Benchmarks were updated.=0A=
> > - Like other standard datastructures, iteration over the deque is now o=
ver the original object (instead of creating a copy),=0A=
> > =A0 and mutating the deque will be reflected in `$iterator->current()` =
(and moving the end with push()/pop() will affect where iteration ends).=0A=
> > - Iteration will account for calls to shift/unshift moving the start of=
 the deque.=0A=
> > =A0 the offsets will be corrected and values won't be skipped or iterat=
ed over multiple times.=0A=
> > =A0 (no matter how many iterators were created by `Deque->getIterator()=
`)=0A=
> > =A0 See https://wiki.php.net/rfc/deque#iteration_behavior=0A=
> > - The get()/set() methods were removed, after feedback in https://exter=
nals.io/message/116100#116214=0A=
> >=0A=
> > A WebAssembly demo is available at https://tysonandre.github.io/php-rfc=
-demo/deque/=0A=
> =0A=
> I've updated the RFC https://wiki.php.net/rfc/deque yet again (no impleme=
ntation changes). I now plan to start voting on Saturday, February 5th.=0A=
> =0A=
> I've also updated the WebAssembly demo at https://tysonandre.github.io/ph=
p-rfc-demo/deque/ to include a benchmark to illustrate the differences in p=
erformance of shift/unshift at various deque/array sizes.=0A=
> A more detailed section on the performance of unshift/shift compared to a=
rray and existing data structures was added to the RFC.=0A=
> =0A=
> I've also added a discussion section for the request to `return $this` (h=
ttps://externals.io/message/116100#116967), removed duplicated quotes, and =
clarified some parts of the RFC.=0A=
=0A=
There's more changes I found this morning while working on test cases for u=
nrelated datastructures, so I'll be postponing the vote.=0A=
=0A=
1. The maximum `Collections\Deque` size is probably going to be reduced to =
be the same as the maximum array size.=0A=
   For 64-bit php builds, that's roughly 2 billion (2147483648 elements, us=
ing at least 32 gigabytes of memory for array or Deque),=0A=
   which was more memory than I'd assumed (16 bytes per `zval`), and needin=
g that much is expected to be a rare use case that can be revisited, e.g. i=
f array size limits are raised.=0A=
=0A=
   Collections would need to be converted to/from arrays for serialization,=
 unserialization, debug output (var_export, json_encode, etc.), etc.,=0A=
   so having a much larger maximum size didn't seem to have a compelling us=
e case.=0A=
=0A=
2. I found and proposed potential improvements for detection of infinite re=
cursion in var_export/debug_zval_dump/json_encode affecting userland classe=
s, existing spl classes, etc.,=0A=
   which seemed worth finishing discussing before starting the vote.=0A=
=0A=
3. Miscellaneous refactorings=0A=
=0A=
Thanks,=0A=
Tyson=0A=