[Phpmyadmin-devel] Is PMA_STR_binarySearchInArr needed?

[Piotr Przybylski]

2011/6/7 Marc Delisle <marc at infomarc.info>:
> Piotr Przybylski a écrit :
>> 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
>>
>
> Ok for me.
>
> Did you find evidence that these arrays in their non-flipped form would
> still be needed (apart from their usage in ./test) ?
>

No, but I think it's better to leave their definitions as they are now
- even though sorting would not be needed, they are currently easy to
read and modify.

-- 
Piotr Przybylski