Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:64954 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 58313 invoked from network); 14 Jan 2013 21:55:44 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 14 Jan 2013 21:55:44 -0000 Authentication-Results: pb1.pair.com header.from=glopes@nebm.ist.utl.pt; sender-id=unknown Authentication-Results: pb1.pair.com smtp.mail=glopes@nebm.ist.utl.pt; spf=permerror; sender-id=unknown Received-SPF: error (pb1.pair.com: domain nebm.ist.utl.pt from 193.136.128.22 cause and error) X-PHP-List-Original-Sender: glopes@nebm.ist.utl.pt X-Host-Fingerprint: 193.136.128.22 smtp2.ist.utl.pt Linux 2.6 Received: from [193.136.128.22] ([193.136.128.22:55684] helo=smtp2.ist.utl.pt) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id B8/DB-22727-DDE74F05 for ; Mon, 14 Jan 2013 16:55:42 -0500 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp2.ist.utl.pt (Postfix) with ESMTP id BDD9270003F0; Mon, 14 Jan 2013 21:55:38 +0000 (WET) X-Virus-Scanned: by amavisd-new-2.6.4 (20090625) (Debian) at ist.utl.pt Received: from smtp2.ist.utl.pt ([127.0.0.1]) by localhost (smtp2.ist.utl.pt [127.0.0.1]) (amavisd-new, port 10025) with LMTP id N1skI7PgI10D; Mon, 14 Jan 2013 21:55:38 +0000 (WET) Received: from mail2.ist.utl.pt (mail.ist.utl.pt [IPv6:2001:690:2100:1::8]) by smtp2.ist.utl.pt (Postfix) with ESMTP id 75C2D70003D7; Mon, 14 Jan 2013 21:55:38 +0000 (WET) Received: from damnation.nl.lo.geleia.net (unknown [IPv6:2001:470:94a2:4:21d:baff:feee:cc0b]) (Authenticated sender: ist155741) by mail2.ist.utl.pt (Postfix) with ESMTPSA id 5CD5B2008493; Mon, 14 Jan 2013 21:55:37 +0000 (WET) Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes To: internals@lists.php.net, "Stanislav Malyshev" , =?utf-8?Q?Johannes_Schl=C3=BCter?= References: Date: Mon, 14 Jan 2013 22:55:33 +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: In-Reply-To: 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 Wed, 09 Jan 2013 23:45:03 +0100, Gustavo Lopes wrote: > On Thu, 03 Jan 2013 11:40:31 +0100, Gustavo Lopes > 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? -- Gustavo Lopes