[Phpmyadmin-devel] Is PMA_STR_binarySearchInArr needed?

[Marc Delisle]

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) ?

-- 
Marc Delisle
http://infomarc.info