Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:98970
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.223.182 as permitted sender)
MIME-Version: 1.0
Sender: jesseschalken@gmail.com
In-Reply-To: <ca51fdee-b8ea-c152-ef8e-9d1dfa2e9d41@gmail.com>
References: <CAF1yvARPJnxBecX5e-dd4Bb5qQ4MqMxYg0Rv7cNf94Rs+i8m2Q@mail.gmail.com>
 <CAESVnVps7TMViBz6besqAzHcuHHuUy-4DD7vOGf1MCi+qEG=og@mail.gmail.com> <ca51fdee-b8ea-c152-ef8e-9d1dfa2e9d41@gmail.com>
Date: Fri, 5 May 2017 13:44:09 +1000
Message-ID: <CAF1yvATiPB32p2E+6ex_GQhRDw=Y93=bWE0ckQW2siAP_drjDA@mail.gmail.com>
To: Rowan Collins <rowan.collins@gmail.com>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=001a113ddda4c3c32a054ebeb3ff
Subject: Re: [PHP-DEV] Add is_vectorlike($array) function
From: me@jesseschalken.com (Jesse Schalken)

--001a113ddda4c3c32a054ebeb3ff
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Fri, May 5, 2017 at 8:18 AM, Rowan Collins <rowan.collins@gmail.com>
wrote:

> Maybe I'm misunderstanding what "with holes" means in this case, but I
> would have expected any array with holes to trivially return false, here,
> because we're looking for arrays with a complete set of consecutive keys.
>
> That aside, there are 3 cases here:
>
> A) arrays that are not vector / list like
> B) arrays that have been constructed and manipulated in various ways, suc=
h
> that they are *now* vector / list like, but aren't packed in memory
> C) arrays that have been consistently constructed and handled as a "list"
> / "vector", and will be packed and hole-less in memory
>
> - A can be determined (in userland or internally) by walking the array,
> and short-cutting to false when you find the first non-integer or
> non-sequential key.
> - B can only be determined by walking the whole array, right to the end.
> - In userland, C is indistinguishable from B, so you have to walk right t=
o
> the end. This is where the big win comes in for an internal function,
> because we can go from examining *all* the keys to examining *none* of th=
em.
>
> I don't know the exact caveats of when the engine packs arrays, but I
> would expect C to be a common case, because as you say the function will
> often be called when *expecting* vector-like arrays, and those vector-lik=
e
> arrays will often have been constructed using only basic operations like
> ['a', 'b', 'c'] or $foo[] =3D 'd'
>
> So the worst case behaviour of an internal function is exactly the same a=
s
> an optimised userland implementation; but a fairly common best case goes
> from a guaranteed O(n) to constant.
>
>
Exactly, and I would add that in the case of a truly associative array (A)
it will return false on the first key that doesn't match 0,1,2=E2=80=A6N, w=
hich is
likely to be the first one, so even that is likely to be fast.

Putting it in a table:

                   keys checked   keys checked
keys               (PHP version)  (C version)
______________________________________________
0,1,2=E2=80=A6N (packed)   N              0
0,1,2=E2=80=A6N            N              N
=E2=8B=AE                  =E2=8B=AE             =E2=8B=AE
0,1,?=E2=80=A6             3              3
0,?,?=E2=80=A6             2              2
?,?,?=E2=80=A6             1              1

The top and bottom rows are the common cases.

--001a113ddda4c3c32a054ebeb3ff--