Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:98971
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: softfail (pb1.pair.com: domain golemon.com does not designate 74.125.82.52 as permitted sender)
MIME-Version: 1.0
Sender: php@golemon.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: Thu, 4 May 2017 22:58:45 -0500
Message-ID: <CAESVnVoxgyBTDQx6MmTo5qMiZ8S9DWbxDRo-xmq_f_iYhDLGBg@mail.gmail.com>
To: Rowan Collins <rowan.collins@gmail.com>
Cc: PHP internals <internals@lists.php.net>
Content-Type: text/plain; charset=UTF-8
Subject: Re: [PHP-DEV] Add is_vectorlike($array) function
From: pollita@php.net (Sara Golemon)

On Thu, May 4, 2017 at 5:18 PM, Rowan Collins <rowan.collins@gmail.com> wrote:
> A) arrays that are not vector / list like
> B) arrays that have been constructed and manipulated in various ways, such
> 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 to
> 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 them.
>
Correct.  The "B" class is the primary case I was referencing.  I was
thinking there might be another class: Array manipulated such that it
is now vector like even without holes, but that the flag hadn't been
reset. Looking into zend_hash, I can now see that my assumption about
that was wrong, so nevermind. :)

> 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-like arrays
> will often have been constructed using only basic operations like ['a', 'b',
> 'c'] or $foo[] = 'd'
>
Absolutely.  Were calls to this written in C, they would be wrapped in
an EXPECTED() macro.  I'm not super worried about the perf (which is
certainly no worse than doing it in userland), I just wanted to point
out that not *all* invocations of is_vectorlike() would be O(1).
That's really all.

> So the worst case behaviour of an internal function is exactly the same as
> an optimised userland implementation; but a fairly common best case goes
> from a guaranteed O(n) to constant.
>
Yes, which is why at worst, this is just a tiny no-harm
micro-optimization API.  And thus my unemotional shrug later in the
message. :)

-Sara