Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:85809
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.218.54 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
References: <CAJCMAP7kZqNcrN-KdRPk=bUQqM4_jNpbd=D4NV9zeuRjpAoSUA@mail.gmail.com>
Date: Tue, 14 Apr 2015 11:23:53 -0700
Message-ID: <CAJCMAP71C5kr5CNrprAkTc+7_y6WQ521pXdTGyk-=GgaFaEusA@mail.gmail.com>
To: internals@lists.php.net
Content-Type: multipart/alternative; boundary=001a113dd2543cf9af0513b35598
Subject: Re: Potential binary search optimization or feature
From: medinsky94@gmail.com (Danylo Medinsky)

--001a113dd2543cf9af0513b35598
Content-Type: text/plain; charset=UTF-8

Thanks for the feedback and apologies for the late response.

Since my posting and your responses, I began implementing the binary search
into array.c. After a couple days of coding and research, I managed to
produce this code.

    HashTable *arr_hash;
    arr_hash = Z_ARRVAL_P(array);
    int low=0;
    int high=zend_hash_num_elements(arr_hash);
    int mid;
    zval res;
    while(low&lt;=high){
            mid=(low+high)/2;
            ZVAL_DEREF(entry);
            entry = zend_hash_index_find(arr_hash, mid);
            compare_function(&amp;res,entry,value);
            //php_printf("%ld\n", Z_LVAL(res));
         if(Z_LVAL(res) &gt; 0){
            high=mid-1;
         }else if(Z_LVAL(res) &lt; 0){
            low=mid+1;
         }else{
            RETURN_TRUE;
         }
    }
    RETURN_FALSE;


After benchmarking this code, I managed to conclude that this binary search
algorithm preforms vastly quicker then the php_search_array function. Based
on these results I believe that this algorithm would be a good optimization
or feature to add to PHP. Based on the feedback I have received from you
guys, I am holding off the sort flag in the binary search function
parameters until I can determine how much performance will be compromised
from the sorting.

At the moment I am trying to figure out if my function would be considered
a minor or major chance since if it is a major/large change, I will require
a RFC in order to submit a pull request.

If anybody has any additional feedback or recommendations, feel free to
reply to this post.

On 29 March 2015 at 23:24, Danylo Medinsky <medinsky94@gmail.com> wrote:

> Recently, as part of school course on optimization, I have identified a
> potential optimization or feature for PHP. After looking through the
> array.c file(located in etc/standard in the PHP source code), I noticed
> that both the in_array and array_search are using the linear search C
> function php_search_array. The potential issue I see is that even though
> the linear search algorithm does not drastically effect performance when
> searching a relatively small array, it may slow performance down when
> iterating through a very large array(couple of million indexes).
>
> To back this fact up I preformed some benchmarks using a PHP script that
> measures the time it takes to preform a linear search and binary search.
> The benchmark was in favor of the binary search as it found its target many
> times quicker compared to the linear search.
>
> After researching more about different PHP search functions, I was not
> able to find one that uses a binary search algorithm. Based on these
> factors I believe that a binary search implementation into PHP will prove
> useful in certain situations and would like to implement that feature.
>
> At the moment I am debating between adding a separate binary search based
> function into array.c or modifying the current array_search_array function
> to utilize a binary search algorithm. Since the requirement for a binary
> search is that the array being searched is sorted, I thought is would be a
> good idea to have a Boolean parameter in the binary search function to
> specify if the input array should be sorted or not. something among the
> lines of "function binary_search(string target, array arrayToSearch, bool
> sort)". Doing this, the function can preform a sort if required to, thus
> not needing to sort a array that is already sorted.
>
> Before I can begin the implementation and create a pull request, I would
> like to know the PHP's community feedback on my potential contribution and
> if this is a wise feature to change or implement.
>
>
>

--001a113dd2543cf9af0513b35598--