[Phpmyadmin-devel] Is PMA_STR_binarySearchInArr needed?

Piotr Przybylski piotr.prz at gmail.com
Tue Jun 7 18:52:20 CEST 2011


2011/6/7 Marc Delisle <marc at infomarc.info>:
> Rouslan Placella a écrit :
>> On Tue, 2011-06-07 at 12:25 -0400, Marc Delisle wrote:
>>> Marc Delisle a écrit :
>>>> Piotr Przybylski a écrit :
>>>>> Hi,
>>>>>
>>>>> For some time I was curious whether PMA_STR_binarySearchInArr is
>>>>> needed at all, and my test showed that there are faster (sometimes
>>>>> much faster) alternatives. Test for 100 000 iterations on PHP 5.3.4
>>>>> (Windows, i5 2,53 GHz core):
>>>>>
>>>>> PMA_STR_binarySearchInArr:    2.6606s
>>>>> array_search:     1.8936s
>>>>> isset:            0.0102s
>>>>> array_key_exists: 0.0934s
>>>>>
>>>>> Isset and array_key_exists require flipped array, but array_search is
>>>>> a drop-in replacement that works faster, even though it does a linear
>>>>> search. Code used to perform this test is at [1].
>>>>>
>>>>> [1] http://pastebin.com/cJmpmCPh
>>>>>
>>>> Piotr,
>>>> I tested on a 64-bit Linux machine (running as a VM under ESX 4.1) under
>>>> PHP 5.3.6-RC3 and got different results (for current master):
>>>>
>>>> Binary search:    0.6088
>>>> array_search:     2.0246
>>>> isset:            0.0068
>>>> array_key_exists: 0.0176
>>>>
>>>>
>>>>
>>> And on a similar VM running PHP 5.2.17:
>>>
>>> Binary search:    0.7197
>>> array_search:     2.7731
>>> isset:            0.0075
>>> array_key_exists: 0.0178
>>>
>>
>> My results look a lot like Marc's, too:
>>
>> PHP: 5.3.5
>> PMA: Latest GIT
>> OS:  Ubuntu Linux 11.04 - 64bit
>> CPU: AMD Phenom II @ 3.95GHz
>> RAM: DDR2 @ 1066MHz
>>
>> Binary search:    0.4967
>> array_search:     1.5545
>> isset:            0.0041
>> array_key_exists: 0.0162
>>
>> Rouslan
>
> isset() on a flipped array is the winner, but would require a logic
> verification everywhere to be sure we flip a minimum of times.
>
> I also like the fact that we would no longer need to maintain a long
> list of keywords in proper alpha order.
>

I was really counting on array_search results, but in this case I
believe binary search is justified by code readability.

-- 
Piotr Przybylski




More information about the Developers mailing list