Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:98968
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.128.174 as permitted sender)
To: internals@lists.php.net
References: <CAF1yvARPJnxBecX5e-dd4Bb5qQ4MqMxYg0Rv7cNf94Rs+i8m2Q@mail.gmail.com>
 <CAESVnVps7TMViBz6besqAzHcuHHuUy-4DD7vOGf1MCi+qEG=og@mail.gmail.com>
Message-ID: <ca51fdee-b8ea-c152-ef8e-9d1dfa2e9d41@gmail.com>
Date: Thu, 4 May 2017 23:18:08 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <CAESVnVps7TMViBz6besqAzHcuHHuUy-4DD7vOGf1MCi+qEG=og@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] Add is_vectorlike($array) function
From: rowan.collins@gmail.com (Rowan Collins)

On 04/05/2017 16:52, Sara Golemon wrote:
> Just want to underline the "is likely to be" part of this sentence.
> The implementation can't assume an array is not vector-like just
> because those checks fail.  It's possible to manipulate an array into
> being vector-like, but not packed, or having holes.
>
> Not really commenting on the proposal yet, which I'm a big
> shoulder-shruggy about.  Just highlighting the caveat for any eventual
> implementation.  We can short-circuit the O(n) loop if it *is*
> packed/no-holes, but if not then we need to walk it to be certain.
> This is probably fine since this check is likely used in places where
> the array is expected to be vector like and non-vector should be a
> slow path anyway.

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, 
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.

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'

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.

Regards,

-- 
Rowan Collins
[IMSoP]