[Phpmyadmin-devel] Is PMA_STR_binarySearchInArr needed?

Piotr Przybylski piotr.prz at gmail.com
Tue Jun 7 19:45:07 CEST 2011


2011/6/7 Marc Delisle <marc at infomarc.info>:
> 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])
>

If we want to change this, I opt for:
- isset in PMA_SQP_parse and do array_flip there
- array_search in PMA_backquote - sometimes faster, worst case a few
times slower, but much better that additional 43 KB of memory and
array_flip in sqlparser.data.php

-- 
Piotr Przybylski




More information about the Developers mailing list