Re: Algorithm Optimizations - string search

Hello again I have setup small page where I am publishing all the profiling and evaluation results. It is here: http://83.168.205.202/~michal/standard15/ So far I have put there function usage profile, zend_memnstr analysis, stripos and strrpos analysis including some charts etc. CVS diffs where applicable are also posted along with comparison of original and patched code. Michal On 2008-06-11, at 09:47, Stanislav Malyshev wrote:

Hi!

Here are some statistics: - average haystack length: 624.2 - average needle length: 1.9 ! -> 63% of needles of length 1 - avg length of haystacks shorter than avg: 41.0 -> 85% of all haystacks - avg length of haystacks longer than avg: 5685.11

I think it would be interesting to see same excluding 1-char needles since in this case it should do one-char lookup (btw, if we don't do it on C level, it might be a good idea to).

Although strpos implements fix for that, some other functions don't. My idea is than to implement ZEND_MEMNSTR once again in shape: if (needle_len = 1)

    here just linear sweep
else if haystack_len < 5000 (5000 is arbitrary - maybe some more tests

needed to choose good value)

    original implementation (as it is the best one in this case)

else

    BM/KMP (i think BM will be better in this case, as some people

suggested)

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. --Stanislav Malyshev, Zend Software Architect stas@zend.com http://www.zend.com/ (408)253-8829 MSN: stas@zend.com