Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:64822
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 74.125.82.46 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <op.wqn1hdywidpuyk@damnation.nl.lo.geleia.net>
References: <CAOg_pRTSGouOVYzorTH1WDYvKqtKdJkJVHxVddO4u=TGNkSs8A@mail.gmail.com>
	<ce9075c17cad65fcdd350a1f243e6ea1@nebm.ist.utl.pt>
	<op.wqn1hdywidpuyk@damnation.nl.lo.geleia.net>
Date: Thu, 10 Jan 2013 20:47:44 +0100
Message-ID: <CAOg_pRQ2ACwxJ-WVpqF=-WaCJSkKz3h1gLTQ6wVB-venmyzDKg@mail.gmail.com>
To: Gustavo Lopes <glopes@nebm.ist.utl.pt>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary=089e010d8afee2986504d2f47309
Subject: Re: [PHP-DEV] strtr vs. str_replace runtime
From: nicolai.scheer@gmail.com (Nicolai Scheer)

--089e010d8afee2986504d2f47309
Content-Type: text/plain; charset=UTF-8

Hi!


On 9 January 2013 23:45, Gustavo Lopes <glopes@nebm.ist.utl.pt> wrote:

> 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
>

Nice :)


>
> 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
>

Even that is way better than before :)


>
> 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<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.2927>
> [2] https://github.com/cataphract/php-src/compare/strtr_wu94


Does "merging to 5.4" mean I can grab the head of the 5.4 branch afterwards
and try it myself?

Thanks!

Greetings

Nico

--089e010d8afee2986504d2f47309--