Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:116965 Return-Path: Delivered-To: mailing list internals@lists.php.net Received: (qmail 64951 invoked from network); 1 Feb 2022 13:32:07 -0000 Received: from unknown (HELO php-smtp4.php.net) (45.112.84.5) by pb1.pair.com with SMTP; 1 Feb 2022 13:32:07 -0000 Received: from php-smtp4.php.net (localhost [127.0.0.1]) by php-smtp4.php.net (Postfix) with ESMTP id B564A180541 for ; Tue, 1 Feb 2022 06:46:21 -0800 (PST) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on php-smtp4.php.net X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FORGED_HOTMAIL_RCVD2, FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS autolearn=no autolearn_force=no version=3.4.2 X-Spam-ASN: AS8075 40.80.0.0/12 X-Spam-Virus: No X-Envelope-From: Received: from NAM12-MW2-obe.outbound.protection.outlook.com (mail-mw2nam12olkn2048.outbound.protection.outlook.com [40.92.23.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by php-smtp4.php.net (Postfix) with ESMTPS for ; Tue, 1 Feb 2022 06:46:21 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=e2YPMZ1cgDcAu0nASo6bE/PhbSP2Irwlu0w2q7kxqzMkeIj9T8uI3FsM8TsmJ9lMWoL29qYeRoPWqLQXEjoON4gJfpQ/InJLjSUmlrLprYfUc8l8z2RmIvXMnL65k5GAYpTuntlg+Tx0Jm3rMr/0QIdOpV+hjEgoR9Bv630lc0kN+boU/M58Aeisj7VIq9E9g1L0qcOftXL0XzQ0IGzyC7LA4x44RzbLHwyd6a+PNXJTMFUmneEL6GWtOh7zXqO96/K/1Q1LPbiQ8sk8J0rng3VNltwnHuuVPdzRxZnKViuBfcAkque+Khp9LBk+CDOa8hJZHv9pRcZsG/aNJqPRQQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=W/akkkK/4nCT4Mxq+uDIyGwIBT9tpMkL2a434Lr79Fw=; b=jSMFJme+qeH4TiL+ruvMInTgyPHEUt9dNhSoNiXs6Wv/dTWr1/1LE4yOtu0U3HmceOXaSGhbHch7yViUk38ENUApuSvT7o3co95SpD27YYHYztYNyKO4dEIqPGHJJn+m+70dRyzEDYVlJwS9JdnJ8MwCNRqUE3fmOrFMGUcs21I9vLwQlFUeXXeRHFUM3mMYgd6w7qG1+J92yGlwHOe8F9rbAugaoh9MkCw8wFXrZTz5pCUCzfIqttP+M/y9EMGX5P3aikIqg3vjLnNINfsfQXy5WmA9W8+AiUJP/1WYClcMQV+jleeZLiicccmoAn9AsW9nD+GvHyWTxLJYL8onXg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=W/akkkK/4nCT4Mxq+uDIyGwIBT9tpMkL2a434Lr79Fw=; b=cilfoDXOrgp5T6JS5vsb12VnR/94nGd1yX1pl7DweoEo1N6zOV05no3M9bHAK54y9aSB9hRw7+rhh4LZ0kWu3nDJ9yvkV6+8A1GUQzgBa2JnzW5SdnqEvd7MGZW5pBX+Hi88eZIky+o3VPNckt4u7v332htcPQ0agDRcTbSTCj7ubo+CxTCJnrkdEJBSYYLFGQO+gblCEp+V6DjQcNrVfXcnwFRNGt6uulmHfT9jJH07nGps3VWZszCx8e2/HNQrFWh04EcUIkZCvCFdZcka00fG3sHcYtgk9YMPTvSSkSMsrk+fjP8PC4v0KEdgtl+qCUzxlrmtjNIha+W+yFcDtw== Received: from DM6PR14MB4155.namprd14.prod.outlook.com (2603:10b6:5:21e::11) by BYAPR14MB2118.namprd14.prod.outlook.com (2603:10b6:a02:b6::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4930.17; Tue, 1 Feb 2022 14:46:19 +0000 Received: from DM6PR14MB4155.namprd14.prod.outlook.com ([fe80::1ddb:6eeb:a96d:9846]) by DM6PR14MB4155.namprd14.prod.outlook.com ([fe80::1ddb:6eeb:a96d:9846%4]) with mapi id 15.20.4930.022; Tue, 1 Feb 2022 14:46:19 +0000 To: "internals@lists.php.net" Thread-Topic: Adding `final class Deque` to PHP Thread-Index: AQHXraUxaK1dZ0niuECOJlLUpHNcpax/lZKy Date: Tue, 1 Feb 2022 14:46:19 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-CA, en-US Content-Language: en-CA X-MS-Has-Attach: X-MS-TNEF-Correlator: suggested_attachment_session_id: 8e6d4b44-3a32-79e1-3a88-93a65b7043b6 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [qrp1pf3C0FMpLtzgL0jkwMkdvBBIyDc9poC66l0yWf8KTfyfc8WHrLuKp5H9cwdF22Ex77Nw4xk=] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 89cd010b-1c70-49f7-b6f1-08d9e5919b8d x-ms-traffictypediagnostic: BYAPR14MB2118:EE_ x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: +RHr/l9V1A7ZQEnqaiuK3tWO7VRifIBzsbLsNx6Qi71Rf8bG0yHtRm7yFBcyvdDEWtomeMzE3MCztU2oicLXkmI52eG8Bib0AJUfvdZw4TwFv5npuqxPnjY8Cyh1j55vvN7AL6k6LW8J64igxoQswJ9uHS+8ecUYKsUcV4EThJHRjTJn3R0Zf2ATO0BdGrpZnip2SLO2yigqpWjESQ2DWcdZZRft529lHAdn67NtxdEfFdp5zAWOcm3z36+nINVPZkn5FPenFuD5aSfUakX8fHqZeOdPjYJ3Vh1e2F7LoFUrxYlxEUKsSDu/iv/hMtH+RJUxRUyspf28I6aCsJYuBMIsMSiF09UMKYfiTA5oOHQTvSwjUZpPK95E0P24CTpmBHZ4WH24qEj264xibKb3swirn5HGmc6gLUId0iTgXU4oPGfosPg7+KU8mx1nKfTd/45wV6MMWV2xlJLLJ68P3P/AtnAvftjQ2kM0nqFRDP77fz5yGe6BxOe3QJPVr1QtcIc801cJpvwrZz00zxNn/FWBqdPcjFIguPfL+hIHiJGwcl807dqDIkjzbc7movkCQ4Rhm/QIEZTgylHKPEp0g6iqypvVepHEJOhn1CB6bAErhxGtEi5GhR6l1qN1YPgySBMEhvDAjbKTq5qpw4he1vIFyMAOSKaFXoZ3WsKH2b4= x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?TEY1yfLOyUCSOWzcwajS4INFapAdk0wbzZwqBj7If/qqu5xCO+p7lOwB6N?= =?iso-8859-1?Q?KN8AQRnWrBVa8Q0ZrIyZQ2lJWhZgcpnC11m8GA/bd4t5HN1rYJv1ktniuc?= =?iso-8859-1?Q?hrlh0gK6hCBVQzwhSFahHweEYWPJ4sqeBZqjuCedjh6wYryfXOZeHWuhRs?= =?iso-8859-1?Q?xIc0zoJ7FeTBtegWeveZxH3pDMi+u1fA7qGtuDQT/H6tylXI38Gk/Zze7T?= =?iso-8859-1?Q?GO7uzafyexrzKc2/u2m+dlWjG2WcIyoJjNw9Jc//8xjpRWa+a5pZUNdZ3H?= =?iso-8859-1?Q?Ggu6XNqhgWlj5z8iUkPIBQJBsEjMLFiQ0G824S8hCzFKj43DWoK7PhDfAd?= =?iso-8859-1?Q?no6aSzvZnVinQB5XahQMRou6w7RB8ScbX/ExMsjauDSnq6zR+cEwVesXBe?= =?iso-8859-1?Q?UU9DC4wI5KZ9za75fp3dzTsBsZXtzd6UUURsqfBrQcTeMfs14h+HaKP/uh?= =?iso-8859-1?Q?lWT2WdAdUn45tfEeYwIEaJMxAdktZuGfJ2GS/1pgQ6aY59KGikuXjZsbZV?= =?iso-8859-1?Q?OsMnw54Kt1ys2xe/VkJ05HUXr+kkmlRkXrtqJsiDfub+CNDgOJyVYreoee?= =?iso-8859-1?Q?Y7BgEh1+51UHBnpmT5x+rNGevp9zg29NpBUpx3LyyCyH3ZmHa6n18YuuRb?= =?iso-8859-1?Q?8ZlI0zD7ByoMa56qa4DuJSisIlCoQ/CMJsH+Bb1pUaOlfOcC28S6mxAMuK?= =?iso-8859-1?Q?RZl9AG6zIBSIKSGdlmChvncHk0Ykv2NsJYhx9v+WckRE6Y6QH6DAPFqMTf?= =?iso-8859-1?Q?t/Zded/WXcxa2Vk0y4tNSoGdCn1Q+FnHUc3lDoU65pXubOTFMVFrqHWB7+?= =?iso-8859-1?Q?Hr2RDZhYPKyjrw8ra72H1sYKrPPByfVuSwq9vhkpIL5ir7xZI5/wqkv3Ag?= =?iso-8859-1?Q?zKf1Q68nPZgSancuW8SPk4qZdz64zooD6BmIyfEAhFb/nIN/YPMlhykOli?= =?iso-8859-1?Q?1qgF5d0GuHe4gKByh/Stfa09GIA4ePE7+Z9oAChKEKbia5txUOg0iDll33?= =?iso-8859-1?Q?7IGJG+W+aMVPi2e1E3ioQ6zrCKNV/4JXcMGYQ2o9Zt19zJ2N4mosK2u8uP?= =?iso-8859-1?Q?Tg=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: 89cd010b-1c70-49f7-b6f1-08d9e5919b8d X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Feb 2022 14:46:19.1629 (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: BYAPR14MB2118 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 cla= ss 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 = those):=0A= > =0A= > 1. `SplDoublyLinkedList` is internally represented by a doubly linked lis= t,=0A= > =A0=A0 making it use roughly twice as much memory as the proposed `Deque`= =0A= > 2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower d= ue to=0A= > =A0=A0 needing to allocate or free the linked list nodes.=0A= > 3. Reading values in the middle of the `SplDoublyLinkedList` is proportio= nal 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 standard= 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 man= y lists of values or run for long periods of time.=0A= > =A0=A0 Notably, PHP's `array` type will never release allocated capacity.= =0A= > =A0=A0 See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implement= ation.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 re= adable, 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 `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 w= ay (and be slower).=0A= > =0A= > There are also several pitfalls to using an array as a queue for larger q= ueue 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 `S= plDoublyLinkedList`=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 number = of elements `unset` from the start of an array,=0A= > =A0=A0 causing it to unexpectedly be extremely slow (quadratic time) afte= r unsetting many elements at the start of the queue.=0A= > =A0=A0 (when the array infrequently runs out of capacity, buckets are mov= ed 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 usi= ng references.=0A= > 3. More obviously, `array_unshift` and `array_shift` will take time propo= rtional 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, Februar= y 4th.=0A= =0A= Several changes have been made to https://wiki.php.net/rfc/deque#changelog= =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 expa= nded for methods.=0A= - Benchmarks were updated.=0A= - Like other standard datastructures, iteration over the deque is now over = the original object (instead of creating a copy), =0A= and mutating the deque will be reflected in `$iterator->current()` (and m= oving 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= the offsets will be corrected and values won't be skipped or iterated ove= r multiple times.=0A= (no matter how many iterators were created by `Deque->getIterator()`)=0A= See https://wiki.php.net/rfc/deque#iteration_behavior=0A= - The get()/set() methods were removed, after feedback in https://externals= .io/message/116100#116214=0A= =0A= A WebAssembly demo is available at https://tysonandre.github.io/php-rfc-dem= o/deque/=0A= =0A= Thanks,=0A= Tyson=0A=