Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116120
To: PHP internals <internals@lists.php.net>
Thread-Topic: [PHP-DEV] Adding `final class Deque` to PHP
Thread-Index:
 AQHXraUxaK1dZ0niuECOJlLUpHNcpaut5O0AgAA5JgCAAJnxgIAABFYAgAAl9YCAABrsgIAATpeh
Date: Wed, 22 Sep 2021 02:02:51 +0000
Message-ID:
 <DM6PR07MB66183D86AA74441DB07D7700F9A29@DM6PR07MB6618.namprd07.prod.outlook.com>
References:
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
 <A59125BE-AF91-44D1-9B47-82046B51EE8F@newclarity.net>
 <CAEZPtU7+hgcHwRfaa7-CR9SVv2=HfH46kDVu0pDYm5M=WeFPVg@mail.gmail.com>
 <67BFE5C6-3C3F-4309-97A2-14CA0D8C3B3B@newclarity.net>
 <CAEZPtU62gfKb-xODqm_yk-BE_ycLshuD2_ps733_ReFgksLqaQ@mail.gmail.com>
 <7BEE0406-3CAE-4E83-A196-F9F608BE8D17@newclarity.net>
 <CAAKU0uk6Wvd5aPQ4qzJTQiHpuLCM999Wsm7qrjWMonF7q+SuDw@mail.gmail.com>
In-Reply-To:
 <CAAKU0uk6Wvd5aPQ4qzJTQiHpuLCM999Wsm7qrjWMonF7q+SuDw@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-CA
suggested_attachment_session_id: 1aa411e4-c0e0-9d2e-5359-9a5aa6da53b7
x-ms-exchange-messagesentrepresentingtype: 1
x-tmn:
 [nAaWsxU34mjLvD2eyC9H7iQzzj5V+NV/qzy2UWoOKeOVseESsHITsbJct+y+1TwM0+Nk4aKnv4E=]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: d3f7e593-e847-441b-9b98-08d97d6d15ce
x-ms-traffictypediagnostic: DM5PR07MB3866:
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info:
 P2CEoc6Wz6rFENaXlSGTB5JhT8sIK9xvy3N8ZNdcsv3Oo84ubKAvL+mDDEC95vPuxeLKNrNoMydATktlEmvtA9JBqy16UQBrD4+W/4WHDBwvozuIka0BQ9jB0oGuSw7IKHtq11+YEU7iEvvPTMkG9dSVli7BBAzO7Kz3O6Pqj/zpj19MtyjAkWUDayw0fZlfXu3liHodb+AyF3f0On1JIUtMliHlkQN/wRiZFv6x4q2wUdAq1qne0NXYAFDbMULuRMxJ7AW7nEqBtdKuRlh2PXSCCdcpoC6iKrRG7lZdGAk7lRKaLpEtRIVp4cZhJY1vxPr4sLsK89X/JYV3UxCktW6A32cLpFSGOivah1k/fRcxoCYFnxQAXsckB5i3on4dJsA6dO9QEa6FQp2LB3N54Bz/WV010FO6fMIVLu9yDNuH005OwUFW4jqgjmH7KJYvoXSN7N2cGJnKoTu0KsCZoNb6Gmuf3x7f5nozKjSWjFQtgjXFVHMHfVx+HVcFmO04k1bSFb28qhS2cZMxnElD9w==
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0:
 i+Cz2zRTgBdQc/2SQvgHZVHeKdi5M3WDT6YQ7ZvFeKAPKxPOg0egr76d/HX7t2j4BYL+joSmRFxutL7FkXiGjweKbV23bEcbf8ZjYB8Rh6QgA0xh1Vdah9aNkrlE/vPCo2/5Evb94dFEgoJAbRiRianFPxhlqpjYL14d/Be0+Rw8csR5kci2Tt2SylMELmU7j8MKfDZVTy7zLP1aFGqeiQ==
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: d3f7e593-e847-441b-9b98-08d97d6d15ce
X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Sep 2021 02:02:51.9275
 (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: DM5PR07MB3866
Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP
From: tysonandre775@hotmail.com (tyson andre)

Hi Levi Morrison,=0A=
=0A=
> The name "deque" is used in the standard library of these languages:=0A=
> =0A=
>  - C++: std::deque=0A=
>  - Java: java.util.Deque (interface)=0A=
>  - Python: collections.deque=0A=
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple=0A=
> official? Don't know Swift)=0A=
>  - Rust: std::collections::VecDeque=0A=
> =0A=
> And these don't have it in the standard library:=0A=
>  - Go=0A=
>  - C#=0A=
>  - C=0A=
>  - JavaScript=0A=
>=0A=
> Anyway, it's pretty decent evidence that:=0A=
>  1. This functionality is pretty widely used across languages.=0A=
>  2. This functionality should have "deque" be in the name, or be the=0A=
> complete name.=0A=
=0A=
Thanks for putting that together.=0A=
=0A=
For anyone wondering about the languages that don't have it:=0A=
The first 3 are compiled languages so there's the same performance for a st=
andard library =0A=
and third-party library code written in those libraries. =0A=
For C and Go, the standard libraries of C and Go are written in C and Go.=
=0A=
C and Go also have a very minimal standard library as a design goal.=0A=
Everything in C and Go is a "native library", so a third-party library and =
a standard library would have the same performance.=0A=
(The standard library of C and Go use or allow embedding assembly for platf=
orm-dependent functionality or optimizations. =0A=
Third party libraries in C or Go can also use inline assembly https://stack=
overflow.com/a/23796420)=0A=
(Not familiar with C#'s standard library, I assume it's similar?)=0A=
=0A=
And browser vendors have put immense amounts of effort on optimizing JavaSc=
ript=0A=
and the JIT compilers for JavaScript for low memory usage,=0A=
supporting inlining, working efficiently on various platforms, etc.=0A=
=0A=
> Discussion naming for "vector" I can understand, as it's less widely=0A=
> used or sometimes means something specific to numbers, but there's=0A=
> little point in discussing the name "deque." It's well established in=0A=
> programming, whether PHP programmers are aware of it or not.=0A=
=0A=
Yes, I'd agree.=0A=
=0A=
It's a well established term in programming, and using a non-standard or mo=
re verbose term=0A=
would make it harder to find/remember this functionality for users moving t=
o php from =0A=
other programming languages, =0A=
or for users moving from php to other programming languages.=0A=
=0A=
Learning programming inevitably has unfamiliar terms such as `array`, `prin=
tf`, etc.=0A=
that are not commonly used in mathematics or daily life.=0A=
=0A=
> As I see it, the discussion should be centered around:=0A=
>  1. The API Deque provides.=0A=
>  2. The package that provides it.=0A=
>  3. Whether Deque's API is consistent with other structures in the same p=
ackage.=0A=
>  4. Whether this should be included in php-src or left to extensions.=0A=
> =0A=
> I suggest that we try to make PHP as homogenous in each bullet as we=0A=
> can with other languages:=0A=
>  1. Name it "Deque."=0A=
>  2. Put it in the namespace "Collections" (and if included in core,=0A=
> then "ext/collections").=0A=
>  3. Support common operations on Deque (pushing and popping items to=0A=
> both front and back, subscript operator works, iteration, size, etc)=0A=
> and add little else (don't be novel here). To me, the biggest thing=0A=
> left to discuss is a notion of a maximum size, which in my own=0A=
> experience is common for circular buffers (the implementation chosen=0A=
> for Deque) but not all languages have this.=0A=
>  4. This is less clear, but I'm in favor as long as we can provide a=0A=
few other data structures at the same time. Obviously, this a voter=0A=
judgement call on the yes/no.=0A=
=0A=
I had planned on a minimal API for Deque.=0A=
=0A=
"Maximum size" shouldn't be an issue for `Deque` specifically, it's a `size=
_t`. It isn't an issue for SplFixedArray and ArrayObject.=0A=
(or for =0A=
PHP would just encounter a fatal error due to either=0A=
=0A=
1. Hitting the `memory_limit` or available memory limit=0A=
while constructing or appending to the `Deque`=0A=
2. Seeing a fatal error due to integer overflow, which would only matter on=
 32-bit php.=0A=
   (The `Deque` API doesn't have a setSize)=0A=
   The `safe_erealloc` macros allow you to do that.=0A=
=0A=
For additions such as `Vector` and `Deque`, because we **can** choose a `si=
ze_t` (type large enough to store any size of memory) (and because 32-bit s=
ystems are increasingly rare),=0A=
I currently think always emitting an uncatchable fatal error (and exiting i=
mmediately) for impossibly large values=0A=
would be the most consistent (e.g. applications wouldn't reach `catch (Thro=
wable $t)` =0A=
blocks meant for a different purpose in an unexpected way, if they failed t=
o validate inputs).=0A=
This is already done in array and SPL types.=0A=
=0A=
```=0A=
php > var_dump(new SplFixedArray(PHP_INT_MAX));=0A=
Fatal error: Possible integer overflow in memory allocation (92233720368547=
75807 * 16 + 0) in php shell code on line 1=0A=
=0A=
php > var_dump(array_fill(0, 2**31 - 2, null));=0A=
=0A=
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to all=
ocate 68719476744 bytes) in php shell code on line 1=0A=
php > var_dump(array_fill(0, 2**31, null));=0A=
=0A=
Warning: Uncaught ValueError: array_fill(): Argument #2 ($count) is too lar=
ge in php shell code:1=0A=
...=0A=
=0A=
// Without memory_limit=0A=
php > ini_set('memory_limit', -1);=0A=
php > $x =3D array_fill(0, 2**31 - 1, null);=0A=
=0A=
mmap() failed: [12] Cannot allocate memory=0A=
=0A=
mmap() failed: [12] Cannot allocate memory=0A=
=0A=
Fatal error: Out of memory (allocated 2097152) (tried to allocate 687194767=
44 bytes) in php shell code on line 1=0A=
```=0A=
=0A=
(If anyone's wondering about the error handling, php arrays have a size of =
signed `int32_t` (i.e. at most ~2 billion elements)=0A=
to support common use cases and many array instances, in a memory efficient=
 way, while still being efficient in the engine's internals)=0A=
=0A=
- If someone's application or library unexpectedly has users that end up ne=
eding to process more than 2 billion values=0A=
  (64GB of RAM in php 7.0-8.1), e.g. in reading/computing statistics from l=
arge binary files,=0A=
  the addition of `Deque` and `Vector` which don't have arbitrary size limi=
ts would be useful to them,=0A=
  and would reduce complaints or feature requests related to the ValueError=
.=0A=
=0A=
> Given that I've suggested the most common options for these across=0A=
> many languages, it shouldn't be very controversial. The worst bit=0A=
> seems like picking the namespace "Collections" as this will break at=0A=
> least one package: https://github.com/danielgsims/php-collections. We=0A=
> should suggest that they vendor it anyway, as "collections" is common=0A=
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see=0A=
> a good alternative here to "Collections", as we haven't agreed on very=0A=
> much on past namespace proposals.=0A=
=0A=
I don't plan to use any of the class names currently found in https://githu=
b.com/danielgsims/php-collections/tree/2.X/src=0A=
for future proposals, so that's less of an issue.=0A=
=0A=
I also don't see good alternatives to "Collections". On a side note, other =
programming languages linked keep referring to collections packages as the =
plural `Collections\`,=0A=
and I also keep using the name `Collections` when thinking about it and fin=
d `use Collection\Deque;` unnatural for a reason I'm not sure about,=0A=
so the plural `Collections\` makes more sense.=0A=
=0A=
I'd announced https://externals.io/message/116112 in case anyone had any id=
eas=0A=
=0A=
- `DataStructures` was mentioned but I consider it too broad.=0A=
  https://en.m.wikipedia.org/wiki/List_of_data_structures is a massive list=
 of which collections of objects is just a small part.=0A=
  It'd make more sense if everything was distributed as a single package su=
ch as a PECL, though=0A=
=0A=
I also misread https://wiki.php.net/rfc/namespaces_in_bundled_extensions#pr=
oposal .=0A=
Sub-namespaces are allowed and could be used for functions/classlikes that =
were not=0A=
collections or ancestor types of collections in the future, if needed (`Col=
lections\Xyz\function_dealing_with_collections()`).=0A=
=0A=
Thanks,=0A=
Tyson=