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]
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
