# strtr() performance degradation - Thread: https://externals.io/message/67610 - Original archive: https://news-web.php.net/php.internals/67610 - Started by Dmitry Stogov on 2013-06-03T08:55:16+00:00 - Messages: 23 - Reply by email to internals@lists.php.net - More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt --- ## #67610 — Dmitry Stogov — 2013-06-03T08:55:16+00:00 URL: https://externals.io/message/67610#67610 Hi Gustavo, 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 "11", "g"=>"22")); } } foo(); $ time sapi/cli/php.5.4.11 strtr.php real 0m0.082s user 0m0.071s sys 0m0.010s $ time sapi/cli/php.5.4.15 strtr.php real 0m0.594s user 0m0.584s sys 0m0.007s 7 times slower :( Could you place take a look. Thanks. Dmitry. --- ## #67629 — Gustavo Lopes — 2013-06-04T18:53:08+00:00 URL: https://externals.io/message/67610#67629 · In reply to: #67610 > 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 > 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 --- ## #67630 — Dmitry Stogov — 2013-06-04T20:12:41+00:00 URL: https://externals.io/message/67610#67630 · In reply to: #67629 Hi Gustavo, This "good" algorithm that doesn't work well for "worse" cases makes about 15% slowdown of ZF2 based applications. It also slowdowns wordpress and other apps, but not so significantly. It's definitely doesn't work well for real-life applications :( Something must be dome (e.g. usage of old or new algorithms depending on different argument patterns). Thanks. Dmitry. On Tue, Jun 4, 2013 at 10:53 PM, Gustavo Lopes wrote: > > > I didn't look into the code yet (and really don't like to do it), but we > > […] > 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 --- ## #67631 — Gustavo Lopes — 2013-06-04T23:37:53+00:00 URL: https://externals.io/message/67610#67631 · In reply to: #67630 > This "good" algorithm that doesn't work well for "worse" cases makes > about 15% slowdown of ZF2 based applications. > It also slowdowns wordpress and other apps, but not so significantly. > > It's definitely doesn't work well for real-life applications :( > Something must be dome (e.g. usage of old or new algorithms depending on > different argument patterns). > All right, I'll take a look at what can be done. It's quite possible we can even do better than the old algorithm for short texts, but falling back to it in those cases is always an option. -- Gustavo Lopes --- ## #70461 — Laruence — 2013-12-02T07:02:09+00:00 URL: https://externals.io/message/67610#70461 · In reply to: #67631 > > > > […] > > All right, I'll take a look at what can be done. It's quite possible we can > even do better than the old algorithm for short texts, but falling back to > it in those cases is always an option. Hey: is there any new progress of this ? :) thanks > > > -- > Gustavo Lopes > > -- > > > -- Laruence Xinchen Hui http://www.laruence.com/ --- ## #70474 — Gustavo Lopes — 2013-12-02T23:02:47+00:00 URL: https://externals.io/message/67610#70474 · In reply to: #70461 > > > […] > Hey: > > is there any new progress of this ? :) > The progress consists of writing of scripts to test the point where to switch algorithms and trying some improvements on the old one without as expensive preprocessing steps. Now, this was in the summer... I'll have some time in the holidays to pick up this and some other PHP-related backlog; that said, if there's some impatience (which would be perfectly understandable...), I wouldn't mind if someone reverted to the previous state in the meantime. -- Gustavo Lopes --- ## #70475 — Andi Gutmans — 2013-12-03T06:54:18+00:00 URL: https://externals.io/message/67610#70475 · In reply to: #70474 > > […] > > The progress consists of writing of scripts to test the point where to switch algorithms and trying some improvements on the old one without as expensive preprocessing steps. > > Now, this was in the summer... I'll have some time in the holidays to pick up this and some other PHP-related backlog; that said, if there's some impatience (which would be perfectly understandable...), I wouldn't mind if someone reverted to the previous state in the meantime. Sounds like this may take some time to figure out. So if there is absolutely no difference in semantics between the two I would suggest we revert until you are able to dig into this. Andi --- ## #70477 — Hannes Magnusson — 2013-12-03T07:33:44+00:00 URL: https://externals.io/message/67610#70477 · In reply to: #70475 > > > > […] > > Sounds like this may take some time to figure out. So if there is absolutely no difference in semantics between the two I would suggest we revert until you are able to dig into this. > This change was included in 5.4.12 and 5.4.22 has been released. Now you want to revert and maybe release 5.4.23 and then apply again in 5.4.24? That doesn't seem worth it. What done is done. Had it been reverted right away then it would have make sense, but not 10 releases later? -Hannes --- ## #70478 — Dmitry Stogov — 2013-12-03T07:59:16+00:00 URL: https://externals.io/message/67610#70478 · In reply to: #70477 At least it must be fixed in PHP-5.6 and measured what kind of performance degradation we got in 5.4. Then we may think if it makes sense to apply it to 5.4 and 5.5. It's always dangerous, but significant speed difference on real life applications matters. Thanks. Dmitry. On Tue, Dec 3, 2013 at 11:33 AM, Hannes Magnusson < hannes.magnusson@gmail.com> wrote: > > > […] > wrote: > > […] > switch algorithms and trying some improvements on the old one without as > expensive preprocessing steps. > > […] > pick up this and some other PHP-related backlog; that said, if there's some > impatience (which would be perfectly understandable...), I wouldn't mind if > someone reverted to the previous state in the meantime. > > […] > absolutely no difference in semantics between the two I would suggest we > revert until you are able to dig into this. > > […] > > > This change was included in 5.4.12 and 5.4.22 has been released. > Now you want to revert and maybe release 5.4.23 and then apply again in > 5.4.24? > > That doesn't seem worth it. What done is done. Had it been reverted > right away then it would have make sense, but not 10 releases later? > > -Hannes --- ## #70480 — Zeev Suraski — 2013-12-03T08:29:49+00:00 URL: https://externals.io/message/67610#70480 · In reply to: #70477 > -----Original Message----- > From: Hannes Magnusson [mailto:hannes.magnusson@gmail.com] > Sent: Tuesday, December 03, 2013 9:34 AM > To: Andi Gutmans > Cc: Gustavo Lopes; Laruence; Dmitry Stogov; PHP Internals; Zeev Suraski; > Gadi Goldbarg > Subject: Re: [PHP-DEV] `strtr()` performance degradation > > > > […] > wrote: > > […] > algorithms and trying some improvements on the old one without as > expensive preprocessing steps. > > […] > up this and some other PHP-related backlog; that said, if there's some > impatience (which would be perfectly understandable...), I wouldn't mind > if > someone reverted to the previous state in the meantime. > > […] > no difference in semantics between the two I would suggest we revert until > you are able to dig into this. > > […] > > > This change was included in 5.4.12 and 5.4.22 has been released. > Now you want to revert and maybe release 5.4.23 and then apply again in > 5.4.24? > > That doesn't seem worth it. What done is done. Had it been reverted right > away then it would have make sense, but not 10 releases later? Hannes, To put things in perspective, the work that goes into improving PHP's performance by 10% is measured in months, sometimes more (from inception to production). Here, we have a patch that slowed real world apps (not synthetic benchmarks) by over 10%, and despite the fact it was reported 6 months ago, we've done absolutely nothing about it. If anything in that story doesn't make sense, that would be it. As to when we reintroduce it - I think it's absolutely fine that we don't reintroduce it in the 5.4.x series, or even the 5.5.x series, but slate it to 5.6.0 - and that too only if it's fully-baked by the time 5.6.0 is ready. We've all experienced first-hand what a complete rewrite of a very popular piece of code can do, and the fact that compatibility can be broken not just by changing behavior, but also by radically changing the algorithm in a way that produces very negative performance side effects. Performance should be one of the measures by which we weigh compatibility - a major regression in performance shouldn't be acceptable any more than a major regression in functionality. We should revert this patch ASAP; It's unfortunate we haven't done it back when it was found but better late than never. Zeev --- ## #70481 — Stas Malyshev — 2013-12-03T08:37:37+00:00 URL: https://externals.io/message/67610#70481 · In reply to: #70480 Hi! > As to when we reintroduce it - I think it's absolutely fine that we don't > reintroduce it in the 5.4.x series, or even the 5.5.x series, but slate it > to 5.6.0 - and that too only if it's fully-baked by the time 5.6.0 is ready. I agree, if it is slowing things down for RL apps - we should remove it from stable versions and re-introduce it in 5.6 when ready. It shouldn't matter for how many versions it was slow, since code changes are not required so once people upgrade to next stable, they get their performance back. -- Stanislav Malyshev, Software Architect SugarCRM: http://www.sugarcrm.com/ (408)454-6900 ext. 227 --- ## #70482 — Laruence — 2013-12-03T08:48:04+00:00 URL: https://externals.io/message/67610#70482 · In reply to: #70481 > Hi! > > > […] > > I agree, if it is slowing things down for RL apps - we should remove it > from stable versions and re-introduce it in 5.6 when ready. It shouldn't > matter for how many versions it was slow, since code changes are not > required so once people upgrade to next stable, they get their > performance back. I agree too, since revet it won't break any things.. thanks > -- > Stanislav Malyshev, Software Architect > SugarCRM: http://www.sugarcrm.com/ > (408)454-6900 ext. 227 -- Laruence Xinchen Hui http://www.laruence.com/ --- ## #70484 — Pierre Joye — 2013-12-03T09:15:26+00:00 URL: https://externals.io/message/67610#70484 · In reply to: #70480 > To put things in perspective, the work that goes into improving PHP's > performance by 10% is measured in months, sometimes more (from inception to > production). Here, we have a patch that slowed real world apps (not > synthetic benchmarks) by over 10%, and despite the fact it was reported 6 > months ago, we've done absolutely nothing about it. If anything in that > story doesn't make sense, that would be it. I cannot agree more than performance is part of the CI/QA process and should be taken as blocker on release time (if any regressions are noticed). We do that on a daily basis for every commit and alerts are sent if there is a performance impact superior to 1-3%. However I have hard time to imagine than strstr alone can reduce real apps performance by 10%, unless we are talking about one single module using it intensively. Do you have numbers and the way you tested it pls? > We should revert this patch ASAP; It's unfortunate we haven't done it back > when it was found but better late than never. I'm not too fund to revert in stable series. But I'm fine to revert it for 5.6.0 if the performance impact has not been solved by the time we will release the final release. Once it is out (optimized back or reverted), we can always consider it for 5.5 or eventually 5.4. Cheers, -- Pierre @pierrejoye | http://www.libgd.org --- ## #70485 — Dmitry Stogov — 2013-12-03T09:16:40+00:00 URL: https://externals.io/message/67610#70485 · In reply to: #70482 It'll break performance improvement for a particular case described in the bug report. Thanks. Dmitry. > On Tue, Dec 3, 2013 at 4:37 PM, Stas Malyshev > wrote: > > […] > don't > > […] > it > > […] > ready. > > […] > I agree too, since revet it won't break any things.. > > thanks > > […] > > > > -- > Laruence Xinchen Hui > http://www.laruence.com/ --- ## #70486 — Zeev Suraski — 2013-12-03T09:50:00+00:00 URL: https://externals.io/message/67610#70486 · In reply to: #70485 True, but you still agree that's the right thing to do. Breaking the common case for the rare case wasn't a good trade... Sent from my mobile > It'll break performance improvement for a particular case described in the > bug report. > > Thanks. Dmitry. > > > > > > […] --- ## #70487 — Mike — 2013-12-03T09:58:57+00:00 URL: https://externals.io/message/67610#70487 · In reply to: #70480 Hi! > We've all experienced first-hand what a complete rewrite of a very popular > piece of code can do, and the fact that compatibility can be broken not just > by changing behavior, but also by radically changing the algorithm in a way > that produces very negative performance side effects. What popular piece of code are you referring to? -- Regards, Mike --- ## #70489 — Zeev Suraski — 2013-12-03T10:28:24+00:00 URL: https://externals.io/message/67610#70489 · In reply to: #70487 > > > Hi! > > > […] > > What popular piece of code are you referring to? `strtr()`. The algorithm change resulted in a ~10x slowdown for short simple cases, and given its popularity in PHP apps - that translated to a ~12% slowdown in real life performance. Zeev --- ## #70490 — Pierre Joye — 2013-12-03T10:42:38+00:00 URL: https://externals.io/message/67610#70490 · In reply to: #70489 > > > > > […] popular > > […] not just > > […] a way > > […] > > `strtr()`. The algorithm change resulted in a ~10x slowdown for short > simple cases, and given its popularity in PHP apps - that translated > to a ~12% slowdown in real life performance. As I agree on the issue, I would really like to see which apps you use to test and how, as well as the numbers. Cheers, --- ## #70492 — Pierre Joye — 2013-12-03T13:30:17+00:00 URL: https://externals.io/message/67610#70492 hi Dmitry! > > ZF2 :) > Screen-short explains it. > > Thanks. Dmitry. > > > Thanks for the shot :) However what is used to produced this call stack? I can imagine that a zf2 specific method could suffer from this regression, but I still have hard time to see a full app suffering from it (12%). The only reason I insist is that we already had "simply revert" in the past, which ended being incomplete or with mistakes, leading to much more critical problems. That's what I would like to prevent in stable releases. Cheers, -- Pierre @pierrejoye | http://www.libgd.org --- ## #70493 — Hannes Magnusson — 2013-12-03T16:18:45+00:00 URL: https://externals.io/message/67610#70493 · In reply to: #70480 > > […] > > Hannes, > > To put things in perspective, the work that goes into improving PHP's > performance by 10% is measured in months, sometimes more (from inception to > production). Here, we have a patch that slowed real world apps (not > synthetic benchmarks) by over 10%, and despite the fact it was reported 6 > months ago, we've done absolutely nothing about it. If anything in that > story doesn't make sense, that would be it. Agreed. The release manager messed up. He should have been paying attention and never shipped the release. And oddly enough, the 5.5.0 release (released just couple of weeks after the initial mail in this thread) also included this wrong-fix without anyone caring. And to this date, I am unable to find a bug report complaining about a slowdown. > As to when we reintroduce it - I think it's absolutely fine that we don't > reintroduce it in the 5.4.x series, or even the 5.5.x series, but slate it > to 5.6.0 - and that too only if it's fully-baked by the time 5.6.0 is ready. I think optimizations of this kind shouldn't be committed into bugfix releases anyway. We are rolling out bugfix releases these days like we are trying to catch up with browser versions, and minor releases so frequently that kids use to to learn how to count. Optimizations should be considered a major feature and only added to .0 releases so this doesn't happen. > We've all experienced first-hand what a complete rewrite of a very popular > piece of code can do, and the fact that compatibility can be broken not just > by changing behavior, but also by radically changing the algorithm in a way > that produces very negative performance side effects. Performance should be > one of the measures by which we weigh compatibility - a major regression in > performance shouldn't be acceptable any more than a major regression in > functionality. Completely agree, further strengthening my argument that bugfix releases should be left out of this. > > We should revert this patch ASAP; It's unfortunate we haven't done it back > when it was found but better late than never. I don't know... Noone cared when it was released, noone has reported a ticket, can't we leave stable branches stable and fix this in the upcoming minor release? -Hannes --- ## #70494 — Matthew Leverton — 2013-12-03T16:32:24+00:00 URL: https://externals.io/message/67610#70494 · In reply to: #70486 > True, but you still agree that's the right thing to do. Breaking the > common case for the rare case wasn't a good trade... > In addition, this generates a new `E_NOTICE` in 5.4.12, which IMO constitutes an unacceptable incompatibility for a minor release: echo strtr('.', ['a' => []]); -- Matthew Leverton --- ## #70504 — Laruence — 2013-12-06T08:06:57+00:00 URL: https://externals.io/message/67610#70504 · In reply to: #70492 > hi Dmitry! > > > > > […] > > > Thanks for the shot :) > > However what is used to produced this call stack? I can imagine that a > zf2 specific method could suffer from this regression, but I still > have hard time to see a full app suffering from it (12%). > > The only reason I insist is that we already had "simply revert" in the > past, which ended being incomplete or with mistakes, leading to much > more critical problems. That's what I would like to prevent in stable > releases. Hey: There are two options 1. fixed the regression based on current implementation, which will be a little ugly.. 2. revert it and try to make a optimization based on the previous implementation... which obviously won't have BC break. and more safe than 1.. I propose revert it in the next release, (5.4, 5.5, 5.6, and master).. please, lets' make it simple... the previous implementation worked well... thanks > > > Cheers, > -- > Pierre > > @pierrejoye | http://www.libgd.org -- Laruence Xinchen Hui http://www.laruence.com/ --- ## #70527 — Laruence — 2013-12-08T05:17:00+00:00 URL: https://externals.io/message/67610#70527 · In reply to: #70504 > > > […] > Hey: > There are two options > > 1. fixed the regression based on current implementation, which > will be a little ugly.. > 2. revert it and try to make a optimization based on the previous > implementation... which obviously won't have BC break. and more safe > than 1.. > > I propose revert it in the next release, (5.4, 5.5, 5.6, and master).. > > please, lets' make it simple... the previous implementation worked well... > > > thanks > > […] > > > > -- > Laruence Xinchen Hui > http://www.laruence.com/ Hey: if no strongly objections,, I will revert it in next week first... thanks -- Laruence Xinchen Hui http://www.laruence.com/