Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:38118
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: unknown (pb1.pair.com: domain php.net does not designate 212.55.154.26 as permitted sender)
Message-ID: <D406487CA14F443B81EAE37236CAD5E6@pc07654>
To: <internals@lists.php.net>,
	"Michal Dziemianko" <michal.dziemianko@gmail.com>
References: <7E62CA6E-83F4-4F9C-86FB-75EBE7D489C9@gmail.com>
In-Reply-To: <7E62CA6E-83F4-4F9C-86FB-75EBE7D489C9@gmail.com>
Date: Mon, 9 Jun 2008 14:49:16 +0100
MIME-Version: 1.0
Content-Type: text/plain;
	format=flowed;
	charset="iso-8859-1";
	reply-type=original
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] Algorithm Optimizations - string search
From: nlopess@php.net ("Nuno Lopes")

Hi,

So some comments:
 - you have some problems with the indentation. We only use tabs, so please 
stick to that. Also, there are some lines that are not indented correctly
 - Have you considered the Boyer-Moore algorithm? I think it's a little 
faster than KMP (take a look at e.g. 
http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/)
 - please remove the //TUTAJ SKONCZYLEM comment
 - revert this change (as well as a few other that are similar):
        - for (r_end = r + Z_STRLEN_P(return_value) - 1; r < r_end; ) {
       + for ( r_end = r + Z_STRLEN_P( return_value ) - 1; r < r_end; ){
(we like small diffs, not long diffs with changes that also break our coding 
standards. e.g. we don't use space after the '(' char. Philip wrote a nice 
article about diffs at http://wiki.php.net/doc/articles/whitespace)
 - in strrpos_reverse_kmp() I think you allocate 4 bytes less that you want
 - I think you've too many comments.. We don't need 1 comment per line :)

After fixing all these points and after running the test suite (with 
valgrind) and make sure there are no regressions, I think it's safe for you 
to commit. Still, I would like to see some performance figures comparing the 
KMP and the Boyer-Moore (or point me some papers about the subject).

Thanks for your work and good luck for the rest of the SoC project :)

Nuno


----- Original Message ----- 
From: "Michal Dziemianko" <michal.dziemianko@gmail.com>
To: <internals@lists.php.net>
Sent: Monday, June 09, 2008 12:39 PM
Subject: [PHP-DEV] Algorithm Optimizations - string search


> Hello,
> Here: http://212.85.117.53/DIFF.txt  is small patch that will speed
> up following functions:
> strpos,
> stripos,
> strrpos
> strripos,
> and probably some others (all that use zend_memnstr/php_memnstr
> function)
>
> The speedup of zend_memnstr is about 8% on average (about 30% in case
> of artificial strings).
> Functions strrpos and strripos are about 25% faster on average.
>
> The only drawback - it needs some additional space (size of the needle).
>
> All functions pass all the tests.
>
> If it looks fine than I will apply for cvs account.
>
> Cheers,
> Michal