Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:123755
Precedence: bulk
MIME-Version: 1.0
References: <2a6b92eb-d5e9-4a1a-9548-a068ac42ebd2@app.fastmail.com>
 <02ee8831-43a0-4857-886e-7f54fb42a99d@varteg.nz> <CAB-Buja2B0_idnmjZFDNiQrGSRck-z-G7M1v8dNQ6ZyCf482OQ@mail.gmail.com>
 <CAPzBOBNLFmGESU-OEfp+ZVXdzKQ_H+yBT2Ak-hcrm1ZK25kUQA@mail.gmail.com>
 <7d825b1d-e584-4916-9435-3561b9c54c26@gmail.com> <CAPzBOBNLfccuXNzcsgf-2-JpJeGNXu2jVGsA-+Fkhbu0+sGBdA@mail.gmail.com>
In-Reply-To: <CAPzBOBNLfccuXNzcsgf-2-JpJeGNXu2jVGsA-+Fkhbu0+sGBdA@mail.gmail.com>
Date: Sat, 22 Jun 2024 20:58:48 +0200
Message-ID: <CAP1Jc10RBiSY_bosS90LBxBjccj6_rNsr_f68yo8Rhos=axQJg@mail.gmail.com>
Subject: Re: [PHP-DEV] [Early Feedback] Pattern matching
To: Robert Landers <landers.robert@gmail.com>
Cc: Niels Dossche <dossche.niels@gmail.com>, internals@lists.php.net
Content-Type: multipart/alternative; boundary="0000000000000818ff061b7f247e"
From: arnaud.lb@gmail.com (Arnaud Le Blanc)

--0000000000000818ff061b7f247e
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Fri, Jun 21, 2024 at 7:20=E2=80=AFPM Robert Landers <landers.robert@gmai=
l.com>
wrote:
> > > I'm always surprised why arrays can't keep track of their internal
> > > types. Every time an item is added to the map, just chuck in the type
> > > and a count, then if it is removed, decrement the counter, and if
> > > zero, remove the type. Thus checking if an array is `array<int>`
> > > should be a near O(1) operation. Memory usage might be an issue (a
> > > couple bytes per type in the array), but not terrible.... but then
> > > again, I've been digging into the type system quite a bit over the
> > > last few months.
> >
> > And every time a modification happens, directly or indirectly, you'll
> > have to modify the counts too. Given how much arrays / hash tables are
> > used within the PHP codebase, this will eventually add up to a lot of
> > overhead. A lot of internal functions that work with arrays will need
> > to be audited and updated too. Lots of potential for introducing bugs.
> > It's (unfortunately) not a matter of "just" adding some counts.
>
> Well, of course, nothing in software is "just" anything.

Counters are not cheap as we need one slot for each type in the array so we
need a dynamic buffer and an indirection, plus absolutely every mutation
needs to update a counter, including writes to references. It is possible
to remove the counters and to maintain an optimistic upper bound of the
type (computing the type more precisely when type checking fails), but I
feel this would not work well with pattern matching.

Also, a few things complicate this:
- Nested writes like $a[0][0][0]=3D1 need to backtrack to update the type o=
f
all parent arrays after the element is added/updated
- Supporting references to properties whose type is a typed array, or
dimensions of these properties, is very hard

Fixed-type arrays may be easier to support but there are important
drawbacks in usability IMHO. This does not play well with CoW semantics.

Best Regards,
Arnaud

--0000000000000818ff061b7f247e
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>On Fri, Jun 21, 2024 at 7:20=E2=80=AFPM Robert Landers &lt;<a href=3D"=
mailto:landers.robert@gmail.com" target=3D"_blank">landers.robert@gmail.com=
</a>&gt; wrote:<br>
&gt; &gt; &gt; I&#39;m always surprised why arrays can&#39;t keep track of =
their internal<br>
&gt; &gt; &gt; types. Every time an item is added to the map, just chuck in=
 the type<br>
&gt; &gt; &gt; and a count, then if it is removed, decrement the counter, a=
nd if<br>
&gt; &gt; &gt; zero, remove the type. Thus checking if an array is `array&l=
t;int&gt;`<br>
&gt; &gt; &gt; should be a near O(1) operation. Memory usage might be an is=
sue (a<br>
&gt; &gt; &gt; couple bytes per type in the array), but not terrible.... bu=
t then<br>
&gt; &gt; &gt; again, I&#39;ve been digging into the type system quite a bi=
t over the<br>
&gt; &gt; &gt; last few months.<br>
&gt; &gt;<br>
&gt; &gt; And every time a modification happens, directly or indirectly, yo=
u&#39;ll<br>
&gt; &gt; have to modify the counts too. Given how much arrays / hash table=
s are<br>
&gt; &gt; used within the PHP codebase, this will eventually add up to a lo=
t of<br>
&gt; &gt; overhead. A lot of internal functions that work with arrays will =
need<br>
&gt; &gt; to be audited and updated too. Lots of potential for introducing =
bugs.<br>
&gt; &gt; It&#39;s (unfortunately) not a matter of &quot;just&quot; adding =
some counts.<br>
&gt;<br>
&gt; Well, of course, nothing in software is &quot;just&quot; anything.</di=
v><div dir=3D"auto"><br></div><div dir=3D"auto">Counters are not cheap as w=
e need one slot for each type in the array so we need a dynamic buffer and =
an indirection, plus absolutely every mutation needs to update a counter, i=
ncluding writes to references. It is possible to remove the counters and to=
 maintain an optimistic upper bound of the type (computing the type more pr=
ecisely when type checking fails), but I feel this would not work well with=
 pattern matching.<br></div><div dir=3D"auto">
<br>
Also, a few things complicate this:<br>
- Nested writes like $a[0][0][0]=3D1 need to backtrack to update the type o=
f all parent arrays after the element is added/updated<br>
- Supporting references to properties whose type is a typed array, or dimen=
sions of these properties, is very hard<br>
<br>
Fixed-type arrays may be easier to support but there are important drawback=
s in usability IMHO. This does not play well with CoW semantics.<br>
<br>
Best Regards,<br>
Arnaud<br>
</div>

--0000000000000818ff061b7f247e--