Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:64789
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain nebm.ist.utl.pt from 193.136.128.21 cause and error)
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: internals@lists.php.net
References: <CAOg_pRTSGouOVYzorTH1WDYvKqtKdJkJVHxVddO4u=TGNkSs8A@mail.gmail.com> <ce9075c17cad65fcdd350a1f243e6ea1@nebm.ist.utl.pt>
Date: Wed, 09 Jan 2013 23:45:03 +0100
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Organization: =?utf-8?Q?N=C3=BAcleo_de_Eng=2E_Biom=C3=A9di?=
 =?utf-8?Q?ca_do_I=2ES=2ET=2E?=
Message-ID: <op.wqn1hdywidpuyk@damnation.nl.lo.geleia.net>
In-Reply-To: <ce9075c17cad65fcdd350a1f243e6ea1@nebm.ist.utl.pt>
User-Agent: Opera Mail/12.11 (Linux)
Subject: Re: [PHP-DEV] strtr vs. str_replace runtime
From: glopes@nebm.ist.utl.pt ("Gustavo Lopes")

On Thu, 03 Jan 2013 11:40:31 +0100, Gustavo Lopes <glopes@nebm.ist.utl.pt>  
wrote:

> The algorithm behaves very poorly in this case because at each position  
> of the text, all the substrings starting there and with size between m  
> and n (where m is the size of the smallest pattern and n is the largest)  
> are checked, even if there are only two patterns with size m and n. We  
> could fix this easily by building a set of the pattern sizes found and  
> try only with those. The hashing of the substrings could also be  
> improved; we don't have to recalculate everything when we advance in the  
> text.
>

Both optimizations (the hash rolling and limiting the substrings hashed on  
each iteration) worked quite well.

But I got much better results with another algorithm [1], so I'm going to  
merge the branch with it [2] instead. I get these results with a 1.7 MB  
string and 13 replacement strings, the smallest with 6 characters and 30  
iterations (x86-64, gcc -O3):

strtr: 0.1387
str_replace: 0.4471

The algorithm doesn't perform as well when the replacement strings are  
small. Adding a replacement for the pattern '_' (1 character) yields:

strtr: 0.6157
str_replace: 0.6230

But even in this case, it works better than my optimized version of the  
current algorithm.

I plan on merging to 5.4 and 5.5; you may want to review it as introducing  
completely new code carries some risk.

[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.2927
[2] https://github.com/cataphract/php-src/compare/strtr_wu94

-- 
Gustavo Lopes