Hello again On Wed, Jun 11, 2008 at 9:47 AM, Stanislav Malyshev <[EMAIL PROTECTED]> wrote:
> I'm not sure very big haystacks really worth the trouble - how many of them > are used? It may be interesting to see medians instead of averages for that. > But len=1 I think worth having special case. > -- > Here are some charts showing haystack and needle length distribution. Haystack: http://212.85.117.53/haystack.png (shows only lengths up to 2000 -> haystacks longer are only 0.7%) Needle: http://212.85.117.53/needle.png For haystack median is 19, for needle..1. As both haystack and needle are in most cases short the optimization should go in this direction. Now lets forget about the first patch I made (if I did this profiling before I wouldn't have came up with this idea). And consider for now only the patch for better execution in case of needle_len = 1 Here are some results of a comparison (10 000 000 iterations, first row is original zend_memnstr implementation, second with patch) time in seconds. match at 11: 0.72 0.43 match at 773 12.61 12.43 Here is diff for the patch: -------------------------------- --- Zend/zend_operators.h 19 Mar 2008 12:44:13 -0000 1.94.2.4.2.10.2.7 +++ Zend/zend_operators.h 11 Jun 2008 21:35:58 -0000 @@ -220,6 +220,10 @@ char *p = haystack; char ne = needle[needle_len-1]; + if (needle_len == 1){ + return (char *)memchr(p, *needle, (end-p+1)); + } + end -= needle_len; while (p <= end) { -------------------------------- To avoid any discussion about UNICODE etc: this is patch for PHP_5_3 - function memchr is used in original implementation of zend_memnstr (followed by memcmp) I will take a look into HEAD later today. Nathan Nobbe has shown me this: http://marc.info/?t=121254018200001&r=1&w=2 <http://marc.info/?t=121254018200001&r=1&w=2>(thx Nathan). I did a small comparison of different implementations of stripos - the original one, and with lowering each caracter separately just before comparing (2 different versions). Here are some results (1st row is original implementation, 2nd with separate lowering), time in seconds, each stripos executed 1000000 times: string length 31, match at 15 0.63 0.53 str len 31, match at 28 0.72 0.93 str len 18 match at 15 0.44 0.50 str len 18 match at 5 0.42 0.32 string len 575 match at 296 9.03 6.07 len 575 match at 570 10.59 11.92 len 1220 match at 400 19.06 10.76 len 1220 match at 1206 22.190000 24.680000 It shows that in case of short haystacks (assuming that there is a match, and it is in first half of the haystack) implementation that does not lower the whole haystack at the beginning is better. Even in case of match closely to the end of string the difference is not that big (2 seconds in last test shown). As said before - the median is 19...so maybe it is worth considering. All comments are highly appreciated, regards Michal
