Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:64962
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain oracle.com designates 156.151.31.81 as permitted sender)
Message-ID: <50F49F34.4040204@oracle.com>
Date: Mon, 14 Jan 2013 16:13:40 -0800
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:17.0) Gecko/20130107 Thunderbird/17.0.2
MIME-Version: 1.0
To: Gustavo Lopes <glopes@nebm.ist.utl.pt>
CC: internals@lists.php.net
References: <CAOg_pRTSGouOVYzorTH1WDYvKqtKdJkJVHxVddO4u=TGNkSs8A@mail.gmail.com> <ce9075c17cad65fcdd350a1f243e6ea1@nebm.ist.utl.pt> <op.wqn1hdywidpuyk@damnation.nl.lo.geleia.net> <op.wqw8ivcxidpuyk@damnation.nl.lo.geleia.net>
In-Reply-To: <op.wqw8ivcxidpuyk@damnation.nl.lo.geleia.net>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] strtr vs. str_replace runtime
From: christopher.jones@oracle.com (Christopher Jones)



On 01/14/2013 01:55 PM, Gustavo Lopes wrote:
> On Wed, 09 Jan 2013 23:45:03 +0100, 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.
>
> OK, so now the plan is to merge this onto 5.4:
>
> https://github.com/cataphract/php-src/compare/php:PHP-5.4...cataphract:strtr_wu94_54
>
> And this to 5.5:
>
> https://github.com/cataphract/php-src/compare/php:PHP-5.5...cataphract:strtr_wu94_55
>
> The difference is that the 5.4 version does not introduce zend_qsort_r() and instead has dedicated simple heap sort.
>
> Any thoughts on this?
>

Despite temptation, I'm still erring on the side of merging to 5.5+
only.  My argument is based on the potential for regressions (behavior
and performance), added code maintenance issues, merge effort etc.
The ability to differentiate the benefits of PHP 5.5 over 5.4, and
promote migration to 5.5 will also be improved.

Chris

-- 
christopher.jones@oracle.com  http://twitter.com/ghrd
Newly updated, free PHP & Oracle book:
http://www.oracle.com/technetwork/topics/php/underground-php-oracle-manual-098250.html