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 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].
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
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].
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
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].
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
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].
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.
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].
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.
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].
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])
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
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) ?
2011/6/7 Marc Delisle marc@infomarc.info:
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) ?
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 a écrit :
2011/6/7 Marc Delisle marc@infomarc.info:
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) ?
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.
OK.
Hi
Dne Tue, 7 Jun 2011 20:36:44 +0200 Piotr Przybylski piotr.prz@gmail.com napsal(a):
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.
I don't think having flipped arrays would make it much harder to read
$list = array( 'FOO', 'BAR, );
versus
$list = array( 'FOO' => 1, 'BAR => 1, );
Hi
Dne Tue, 07 Jun 2011 12:22:02 -0400 Marc Delisle marc@infomarc.info napsal(a):
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
I get similar numbers as well:
Binary search: 0.6937 array_search: 3.393 isset: 0.0056 array_key_exists: 0.0228
What is also interesting is worst results achieved during search for all words in the array:
Binary search: 1.3098 array_search: 4.0101 isset: 0.0333 array_key_exists: 0.0868
Both binary search and array_search give pretty inconsistent results.
For the flipped array you expect to call array_flip or change data structure to already contain flipped array? I assume latter, because otherwise overhead for flipping array would probably make results worse.
PS: in_array seems to perform slightly better than array_search.
On Wed, 2011-06-08 at 09:41 +0200, Michal Čihař wrote:
Hi
Dne Tue, 07 Jun 2011 12:22:02 -0400 Marc Delisle marc@infomarc.info napsal(a):
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
I get similar numbers as well:
Binary search: 0.6937 array_search: 3.393 isset: 0.0056 array_key_exists: 0.0228
What is also interesting is worst results achieved during search for all words in the array:
Binary search: 1.3098 array_search: 4.0101 isset: 0.0333 array_key_exists: 0.0868
Both binary search and array_search give pretty inconsistent results.
For the flipped array you expect to call array_flip or change data structure to already contain flipped array? I assume latter, because otherwise overhead for flipping array would probably make results worse.
I think it doesn't matter if one calls array_flip or not as that function is implemented very efficiently in PHP and the time to execute it can be considered negligible.
Rouslan
On Wed, 2011-06-08 at 10:26 +0100, Rouslan Placella wrote:
On Wed, 2011-06-08 at 09:41 +0200, Michal Čihař wrote:
Hi
Dne Tue, 07 Jun 2011 12:22:02 -0400 Marc Delisle marc@infomarc.info napsal(a):
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
I get similar numbers as well:
Binary search: 0.6937 array_search: 3.393 isset: 0.0056 array_key_exists: 0.0228
What is also interesting is worst results achieved during search for all words in the array:
Binary search: 1.3098 array_search: 4.0101 isset: 0.0333 array_key_exists: 0.0868
Both binary search and array_search give pretty inconsistent results.
For the flipped array you expect to call array_flip or change data structure to already contain flipped array? I assume latter, because otherwise overhead for flipping array would probably make results worse.
I think it doesn't matter if one calls array_flip or not as that function is implemented very efficiently in PHP and the time to execute it can be considered negligible.
Rouslan
Actually, I take that back, array_flip really sucks:
Binary search: 0.4924 array_search: 1.5532 isset + array_flip: 4.6791 isset on flipped array: 0.0043
Rouslan
2011/6/8 Rouslan Placella rouslan@placella.com:
On Wed, 2011-06-08 at 10:26 +0100, Rouslan Placella wrote:
On Wed, 2011-06-08 at 09:41 +0200, Michal Čihař wrote:
Hi
Dne Tue, 07 Jun 2011 12:22:02 -0400 Marc Delisle marc@infomarc.info napsal(a):
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
I get similar numbers as well:
Binary search: 0.6937 array_search: 3.393 isset: 0.0056 array_key_exists: 0.0228
What is also interesting is worst results achieved during search for all words in the array:
Binary search: 1.3098 array_search: 4.0101 isset: 0.0333 array_key_exists: 0.0868
Both binary search and array_search give pretty inconsistent results.
For the flipped array you expect to call array_flip or change data structure to already contain flipped array? I assume latter, because otherwise overhead for flipping array would probably make results worse.
I think it doesn't matter if one calls array_flip or not as that function is implemented very efficiently in PHP and the time to execute it can be considered negligible.
Rouslan
Actually, I take that back, array_flip really sucks:
Binary search: 0.4924 array_search: 1.5532 isset + array_flip: 4.6791 isset on flipped array: 0.0043
Yes, it is slow.
For now, I pushed some changes to master: - sqlparser.data.php is unchanged - PMA_backquote uses in_array - PMA_SQP_parse performs array_flip on required arrays and caches results in a static variable (0.00037s for me)
I have still doubts about using flipped arrays in sqlparser.data.php. On one hand, it's a few lines of code less in SQL parser and code is still readable, on the other hand flipped arrays require additional 4 KB of code in sqlparser.data.php
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].
Looking for different strings gives me different results. For example, looking for "BOTH" and array_search() is faster that PMA_STR_binarySearchInArr().
2011/6/7 Marc Delisle marc@infomarc.info:
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].
Looking for different strings gives me different results. For example, looking for "BOTH" and array_search() is faster that PMA_STR_binarySearchInArr().
I searched for 'WRITE' to get an almost-worst case scenario with linear search, but I didn't expect results for array_search on other machines to be that much different.
-
Marc Delisle -
Michal Čihař -
Piotr Przybylski -
Rouslan Placella