Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:67629
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.22 cause and error)
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: "Dmitry Stogov" <dmitry@zend.com>
Cc: "PHP Internals" <internals@lists.php.net>, "Zeev Suraski" <zeev@zend.com>,
 "Gadi Goldbarg" <gadi@zend.com>
References: <CA+9eiLuSBF9NVqnGV8Oe1Dn-tBQ_86h2PGsFuJhr0_Wv9jYoZg@mail.gmail.com>
Date: Tue, 04 Jun 2013 20:53:08 +0200
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.wx532ugqidpuyk@damnation.nl.lo.geleia.net>
In-Reply-To: <CA+9eiLuSBF9NVqnGV8Oe1Dn-tBQ_86h2PGsFuJhr0_Wv9jYoZg@mail.gmail.com>
User-Agent: Opera Mail/12.15 (Linux)
Subject: Re: strtr() performance degradation
From: glopes@nebm.ist.utl.pt ("Gustavo Lopes")

On Mon, 03 Jun 2013 10:55:16 +0200, Dmitry Stogov <dmitry@zend.com> wrote:

> I didn't look into the code yet (and really don't like to do it), but we
> just noticed terrible performance degradation of strtr() function between
> 5.4.11 and 5.4.15 coming probably after your changes.
>
> $ cat strtr.php
> <?php
> function foo() {
>     for ($i = 0; $i < 100000; $i++) {
>         strtr("abcdefgh", array("a"=>"11", "g"=>"22"));
>     }
> }
> foo();
>

Your example is basically a worst-case scenario of the new algorithm and a  
best-case scenario of the old one. The new algorithm has a more costly  
preprocessing step and its gains are the smallest when the minimum pattern  
size is 1. That combined with a very short text makes the cost of the  
preprocessing step dominate.

For strtr(str_repeat("abcdefgh", 50), ...) the results are very close and  
for 100 repeats the new algorithm is already faster. It also does not have  
cases of multi-second runs in relatively small inputs like the old  
algorithm (see https://bugs.php.net/bug.php?id=63893 ); you're talking  
about function calls that still execute in around 7 microseconds.

That said, there certainly is an argument for using the old algorithm for  
short inputs, as its preprocessing step is much cheaper. It will require  
some experimentation in order to determine the cutoff, but if you think  
it's important I can do it (you're welcome to do it as well).

Regards

-- 
Gustavo Lopes