On Fri, May 5, 2017 at 8:18 AM, Rowan Collins <rowan.coll...@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, 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.
>
>
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…N, which 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…N (packed) N 0
0,1,2…N N N
⋮ ⋮ ⋮
0,1,?… 3 3
0,?,?… 2 2
?,?,?… 1 1
The top and bottom rows are the common cases.
