Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:98929
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 74.125.82.51 as permitted sender)
To: internals@lists.php.net
References: <CAF1yvARPJnxBecX5e-dd4Bb5qQ4MqMxYg0Rv7cNf94Rs+i8m2Q@mail.gmail.com>
Message-ID: <0b4f249f-f574-2dcc-4485-1d765bc4cb18@gmail.com>
Date: Tue, 2 May 2017 10:55:22 +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: <CAF1yvARPJnxBecX5e-dd4Bb5qQ4MqMxYg0Rv7cNf94Rs+i8m2Q@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 02/05/2017 10:13, Jesse Schalken wrote:
> Related to the optimisation made by Sara Golemon here:
> https://github.com/php/php-src/commit/c74bc87c74f48bc55541b3bf2fc67d595f58a3b5
>
> I often define a function like this, which checks if an array is "vector
> like" i.e. has keys 0,1,2..N:
>
> function is_vectorlike(array $a): bool {
>    $i = 0;
>    foreach ($a as $k => $v) {
>      if ($k !== $i++) {
>        return false;
>      }
>    }
>    return true;
> }
>
> The problem is that this function is O(n), but in PHP7 an array that is
> vector-like is likely to be packed and without holes (HT_IS_PACKED(x) &&
> HT_IS_WITHOUT_HOLES(x)), in which case it is known to be vector-like
> without needing to iterate over it, but PHP code can't check for this (nor
> should it be able to, since it's really an implementation detail).
>
> Would it be a good idea to define this is_vectorlike() function in the PHP
> runtime, so it can short circuit to return true on packed arrays without
> holes? The above code would be a suitable polyfill.
>

+1, I've been thinking of making a similar suggestion. We can bikeshed 
the name (it should certainly start with "array_"), but I think there's 
a very good case for having an optimised implementation built in, given 
the opportunities for short-cutting based on representation details.

As an example use case, serialization formats often dynamically switch 
between an "array"/"vector"/"list", and a "hash"/"dictionary"/"table". I 
came upon this example recently: 
https://github.com/php-amqplib/php-amqplib/blob/master/PhpAmqpLib/Wire/AMQPAbstractCollection.php#L218

Regards,

-- 
Rowan Collins
[IMSoP]