[Phpmyadmin-devel] Is PMA_STR_binarySearchInArr needed?

Marc Delisle marc at infomarc.info
Tue Jun 7 19:03:56 CEST 2011


Piotr Przybylski a écrit :
> 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.
> 
IMO the new form would be more readable.

Current:
  PMA_STR_binarySearchInArr($d_cur_upper, $PMA_SQPdata_function_name, 
$PMA_SQPdata_function_name_cnt)

New:
isset($PMA_SQPdata_function_name_flipped[$d_cur_upper])


-- 
Marc Delisle
http://infomarc.info




More information about the Developers mailing list