Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116981
To: "internals@lists.php.net" <internals@lists.php.net>
Thread-Topic: Adding `final class Deque` to PHP
Thread-Index: AQHXraUxaK1dZ0niuECOJlLUpHNcpax/lZKygATD6ZU=
Date: Fri, 4 Feb 2022 15:24:13 +0000
Message-ID:
 <DM6PR14MB4155EECD794A874CB9A0AAA8F9299@DM6PR14MB4155.namprd14.prod.outlook.com>
References:
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
 <DM6PR14MB41556131E6A9D7812854AA75F9269@DM6PR14MB4155.namprd14.prod.outlook.com>
In-Reply-To:
 <DM6PR14MB41556131E6A9D7812854AA75F9269@DM6PR14MB4155.namprd14.prod.outlook.com>
Accept-Language: en-CA, en-US
Content-Language: en-CA
suggested_attachment_session_id: 7c786e75-190b-ec75-aef4-67ab36d64dd5
x-ms-exchange-messagesentrepresentingtype: 1
x-tmn:
 [qz178fL/d00ZpGs2Wg5KBIlDxaqAExSu7cqpPL4ECU0I0kXkbWAw8KFHaTnBeW3YreT5uHGS3tI=]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 938ff056-cff4-4813-d16b-08d9e7f26625
x-ms-traffictypediagnostic: BYAPR14MB2487:EE_
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info:
 iXkSS1WmQavrgQR1Hm+zL3ZyE148XXwQMx5Ryz6mVojrlJNWjMdKsPA9ONoaz1OESKoS7xBwwo9BXHFze9fR7SbKErL4mig3AKO0+HhIXwBGAlCtYLVvPtQ/mqb2ZaA/BZwwmnHn1P87Abv3dXdE3KTqwEMBe5vGpZ+5JUQZ4ATr6UmjD6dhyQE3vfxNB8EizX3qgu38jL7fCptEcfsg1dHkNOy+7mcifLfxQ7MW6/92dPejdVajfbmR1bnbyJO4Voa/7Jvf07gzjo3vDng0zTlZcaWL19vziogCJC8Oj5HYS2R0Wx0Go68w1lBX6UAgTfedP3HnI66HI3tsfmVXxDVvn8tzw1MBNzDvH2RCvtLaIvMgfTWVEuFUCBQZAys2AvuWpQJQG4LiAJ4relaAIGx2J8HEfwa5OxUAMWeYctDWdI2bIMqBj3KZbqaqxhxfS0c+eEHhzK5UbgtRHcahf9hbGl0I1wFsWBPEDFhHn9lp34f/mSw2t8H6y0aTOdSSUstl1ASU69nN4RZO7kX0+4eyIRzJZgoDnRY1z6KZA6sbaBgl1s2NAzVevU5i2bt9SgJl1JNVFiQOP1z3n+Y8lBEuDaATlTxQmZCKh/6M9npFKaz1X1EUU8wJne9bMBpkhiG1UGAjvLnc7NcJK8A7ifC9aRH2i61dPpfq9MAks8c=
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0:
 =?iso-8859-1?Q?D8Gb9wvOYI4X0O+NohQK3KwHosJDPp0yNhOmT5Zqb846qVZ4tflVF1a88b?=
 =?iso-8859-1?Q?8GKN1J9q7in9iFGhb1T4ohQ9jyebiyw9zSgosI9Ipmeevd/jCVHipXyAI4?=
 =?iso-8859-1?Q?NB9tqBvbIW3nnySdT8ITEH3yfdzih2J3vdt0IgyStrzaNQ8Gj5z9D/bO8r?=
 =?iso-8859-1?Q?6iK0cC2IIO2/Vyl6Xs5yPWzYlsOC2n1BPXPVa83MXq0OQxGWSAoIWMCoUl?=
 =?iso-8859-1?Q?3jeSsTeGCDMotuGIRzuesKuLv4j8yrt5j0sWv7zAD4TvPzgfHEui0yHM1N?=
 =?iso-8859-1?Q?v/BWO96I9caQJE7WoKulNjDoqWYiN1vlkcO1WD5OFLKybItbtDB8hqxP4j?=
 =?iso-8859-1?Q?ls/EOp5NFqria1/OprxilPWsS36f10mR27YTGa3aotUbR+6d/9kH7JVRqf?=
 =?iso-8859-1?Q?VgVeINvHH+o2YM+6VqHGyjr6t/f3tc/WJPaIfBmKtzGj9VoUT1zN1nm0zC?=
 =?iso-8859-1?Q?6eKGClpGx/ZuEwDgXr2sGSQk4g/radU7wZ5mBHxYO/tOuegBzs6ZE7ed+u?=
 =?iso-8859-1?Q?soS9WTFT1UNXjsXNjdh5ZxtT+wj5CFwBkMXeORB5lK2tgeBNbnKfb/kr+G?=
 =?iso-8859-1?Q?ZrM5zpL+WKbyVClHoTZ5ZQjqHldXJFDs6ZDGLjzvQeK1MsUbzdFw2cyjYz?=
 =?iso-8859-1?Q?HlKT6J+u9itOWfML48BvH6lY1yAkmRzOYSUpkUpWUL/n1C6Ro8vl51LHb5?=
 =?iso-8859-1?Q?vtf4cSlNsBkL3FVRLSR3RYwBDGkA4VvyHah6zpXw2A4o3XiiQX+crFIAhZ?=
 =?iso-8859-1?Q?TQpzfScz5k/OvKO/4xECl71lBCD79vLjkzgCU8OP+tpq06PiU5xlqAtHlV?=
 =?iso-8859-1?Q?PzNunWLu6WrFS8D6LL/9tDuwP4DzO8bu2dDksnDFa43EcI1+VUAJdNLIrU?=
 =?iso-8859-1?Q?fK1vKuLWK0ah1zlYAA4hTpTowEHQ67tluWZ1pJxMpwBMZLBD9DbxkbUEku?=
 =?iso-8859-1?Q?Gwpd6sYLeOOcS0D0a38FpvHXo5WHzaxeeVYdq2Pt/mP7tfKx25nQomb2hA?=
 =?iso-8859-1?Q?HgM1sqCpOczYXUqtJtOiu4hhkYebmdIHIHhm2Tr0bQs23EKz2LbULNjdTq?=
 =?iso-8859-1?Q?XA=3D=3D?=
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: 938ff056-cff4-4813-d16b-08d9e7f26625
X-MS-Exchange-CrossTenant-originalarrivaltime: 04 Feb 2022 15:24:13.0554
 (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: BYAPR14MB2487
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 c=
lass 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` exis=
t in the SPL, they have several drawbacks=0A=
> > that are addressed by this RFC to add a `Deque` class (to use instead o=
f those):=0A=
> >=0A=
> > 1. `SplDoublyLinkedList` is internally represented by a doubly linked l=
ist,=0A=
> > =A0=A0 making it use roughly twice as much memory as the proposed `Dequ=
e`=0A=
> > 2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower=
 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 proport=
ional 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 wh=
at 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 standa=
rd 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 m=
any lists of values or run for long periods of time.=0A=
> > =A0=A0 Notably, PHP's `array` type will never release allocated capacit=
y.=0A=
> > =A0=A0 See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme=
ntation.html=0A=
> > 2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`=
, 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, more =
readable, and easier to use correctly.=0A=
> > While it is possible to efficiently remove elements from the start of a=
n `array` (in terms of insertion order) (though this makes reset()/array_ke=
y_first() inefficient),=0A=
> > it is very inefficient to prepend elements to the start of a large `arr=
ay` 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=
 queue sizes,=0A=
> > some of which are not obvious and discovered while writing the benchmar=
ks.=0A=
> > (Having a better (double-ended) queue datastructure (`Deque`) than the =
`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 numbe=
r of elements `unset` from the start of an array,=0A=
> > =A0=A0 causing it to unexpectedly be extremely slow (quadratic time) af=
ter unsetting many elements at the start of the queue.=0A=
> > =A0=A0 (when the array infrequently runs out of capacity, buckets are m=
oved 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 u=
sing references.=0A=
> > 3. More obviously, `array_unshift` and `array_shift` will take time pro=
portional 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, Febru=
ary 4th.=0A=
>=0A=
> Several changes have been made to https://wiki.php.net/rfc/deque#changelo=
g=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 ex=
panded for methods.=0A=
> - Benchmarks were updated.=0A=
> - Like other standard datastructures, iteration over the deque is now ove=
r the original object (instead of creating a copy),=0A=
> =A0 and mutating the deque will be reflected in `$iterator->current()` (a=
nd moving the end with push()/pop() will affect where iteration ends).=0A=
> - Iteration will account for calls to shift/unshift moving the start of t=
he deque.=0A=
> =A0 the offsets will be corrected and values won't be skipped or iterated=
 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://externa=
ls.io/message/116100#116214=0A=
>=0A=
> A WebAssembly demo is available at https://tysonandre.github.io/php-rfc-d=
emo/deque/=0A=
=0A=
I've updated the RFC https://wiki.php.net/rfc/deque yet again (no implement=
ation 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/php-=
rfc-demo/deque/ to include a benchmark to illustrate the differences in per=
formance of shift/unshift at various deque/array sizes.=0A=
A more detailed section on the performance of unshift/shift compared to arr=
ay and existing data structures was added to the RFC.=0A=
=0A=
I've also added a discussion section for the request to `return $this` (htt=
ps://externals.io/message/116100#116967), removed duplicated quotes, and cl=
arified some parts of the RFC.=0A=
=0A=
Thanks,=0A=
Tyson=0A=