Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:38434
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: unknown (pb1.pair.com: domain gmail.com does not designate 82.132.130.150 as permitted sender)
In-Reply-To: <D22A07AC73A84BF2BABDC8295B6A9098@pc07654>
References: <7E62CA6E-83F4-4F9C-86FB-75EBE7D489C9@gmail.com>	 <D406487CA14F443B81EAE37236CAD5E6@pc07654>	 <484D36EB.9080202@macvicar.net> <31fe29920806110114i263a47b4sd66d4849ceb22980@mail.gmail.com> <484F910A.3080208@zend.com> <33FE7D54-B113-4C5F-9315-659F8550397E@gmail.com> <D22A07AC73A84BF2BABDC8295B6A9098@pc07654>
Mime-Version: 1.0 (Apple Message framework v753.1)
Content-Type: multipart/alternative; boundary=Apple-Mail-2--623312344
Message-ID: <C8A3A2A3-E78B-4277-9E26-6E3DF3B27F0B@gmail.com>
Date: Thu, 19 Jun 2008 21:24:48 +0100
To: internals@lists.php.net
Subject: Re: [PHP-DEV] Algorithm Optimizations - string search
From: michal.dziemianko@gmail.com (Michal Dziemianko)

--Apple-Mail-2--623312344
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

Hi,
I am also sorry for delay - got ill recently and spend a day in bed  
after night at emergency. I am working on other things now, and hope  
to post some patches soon. I will create patch for zend_memnstr as  
you suggest and post it here probably tomorrow. I have some ideas/ 
implementations/data already prepared for other functions (not only  
string related) but haven't got time to publish it neither here, nor  
on the page (http://212.85.117.53/gsoc/), but will try to do it till  
Monday.
Michal

On 2008-06-17, at 23:57, Nuno Lopes wrote:

> Hi,
>
> Sorry for taking so long to answer, but I'm trying to catch up last  
> stuff.
> It's known that usually to optimize things for longer inputs you  
> usually end up making things for short inputs worst. So IMHO, I  
> think you should have the len==1 optimization and then use the KMP  
> algorithm. Your implementation can be further optimized (at least  
> on 32 bits machines), but seems ok for now.
> I suggest you to produce a final patch, send it here, and then move  
> on to optimize other things (like strtr() that I'm sure wikipedia  
> guys will appreciate).
>
> Nuno
>
>
> ----- Original Message -----
>> 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
>


--Apple-Mail-2--623312344--