Piotr Przybylski a écrit :
2011/6/7 Marc Delisle marc@infomarc.info:
Piotr Przybylski a écrit :
2011/6/7 Marc Delisle marc@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) ?