58533[BUGFIX] Avoid scanning entire haystack in begins/ends-with
Commit message
Review
-
Code review CR 0
-
Verified V 0
Issues 1
Files 1
Review log 3955
Show 2030 earlier messages
-
Claus Due uploaded patch set 1 10/01/18, 14:48
-
Claus Due uploaded patch set 2 10/01/18, 14:56
-
Claus Due uploaded patch set 3 10/01/18, 14:57
-
Claus Due uploaded patch set 4 10/01/18, 14:58
-
Claus Due uploaded patch set 5 10/01/18, 15:01
-
TYPO3com voted on patch set 1 V -1 10/01/18, 15:04 Completed build in 13m 16s on Mon, 1 Oct, 05:04 PM Test Summary: 30 of 37273 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29184
-
TYPO3com voted on patch set 5 V -1 10/01/18, 15:10 Completed build in 11s on Mon, 1 Oct, 05:10 PM Test Summary: No tests found Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29189
-
TYPO3com voted on patch set 2 V -1 10/01/18, 15:10 Completed build in 11m 19s on Mon, 1 Oct, 05:10 PM Test Summary: 132 of 36287 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29186
-
TYPO3com voted on patch set 3 V -1 10/01/18, 15:10 Completed build in 11m 19s on Mon, 1 Oct, 05:10 PM Test Summary: 135 of 31338 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29187
-
TYPO3com commented on patch set 5 10/01/18, 15:25 Completed build in 15m 37s on Mon, 1 Oct, 05:25 PM Test Summary: 105 of 37273 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29189
-
Claus Due uploaded patch set 6 10/01/18, 15:26
-
TYPO3com voted on patch set 6 V +1 10/01/18, 15:36 Completed build in 09m 34s on Mon, 1 Oct, 05:36 PM Test Summary: 36913 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-29191
-
Markus Klein commented on patch set 6 CR -1 10/01/18, 17:00
strlen is always very dangerousStringUtility.php:48mb_strlen -
Claus Due commented on patch set 6 10/01/18, 17:15
StringUtility.php:48ReplyIt doesn't matter because if your $needle contains multibyte characters then that exact same number of bytes will be matched. When the use case does not need to care about multibyte, the faster string measuring/comparing functions should be used. Though there is no unit test with unicode characters it is quite safe to keep this function naive about multibyte. -
Markus Klein commented on patch set 6 10/01/18, 17:37
StringUtility.php:48ReplyNot if the needle is by chance a byte subset of the haystack. example: needle: 0x10 haystack: 0x10B30 This would yield a true, but is actually false, since haystack is a 3-byte unicode character -
Claus Due commented on patch set 6 10/02/18, 09:36
StringUtility.php:48ReplyThat's quite a theoretical use case. If there even is a use case for passing 0x10 as needle, I fail to see it. I personally think that if the potential errors (false positives) are all caused by needles that have to be carefully crafted to be invalid, we might want to opt for keeping the more efficient code that serves 99.999999% of executions fast, instead of implementing a slower solution to prevent the intentionally miscrafted needles from causing wrong responses... Be that as it may, it could still be argued that this patch is not intended to make a method that was not previously byte-safe (strpos vs. mb_strpos) into one that is. I would say we can do this which 100% preserves the original behavior but optimises it - then open another where we argue about the likelihood of byte-safeness causing any problems in real world examples. -
Benni Mack updated the commit message in patch set 7 12/14/18, 09:57
-
TYPO3com voted on patch set 7 V +1 12/14/18, 10:37 Completed build in 35m 28s on Fri, 14 Dec, 11:37 AM Test Summary: 48757 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-30689
-
Andreas Kienast rebased onto patch set 8 12/06/19, 11:59
-
Andreas Kienast commented on patch set 8 12/06/19, 11:59
StringUtility.php:49Output of PhpStorm: > [EA] 'strpos($haystack, $needle) === 0' can be used instead (improves maintainability). Do you think the remark is legit in this case? -
TYPO3com voted on patch set 8 V +1 12/06/19, 12:08 Completed build in 08m 56s on Fri, 6 Dec, 12:08 PM Test Summary: 68763 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39147
-
Markus Klein commented on patch set 8 12/06/19, 12:16
StringUtility.php:49ReplyIMO this would be even more efficient: return $needleLength <= strlen($haystack) && $needle[0] === $haystack[0] && strpos($haystack, $needle) === 0; This is optimized for "fail fast" and does not require any mem-copies (which substr needs) -
Claus Due commented on patch set 8 12/06/19, 12:33
StringUtility.php:49Reply Unresolved@Andi: the EA remark about strpos is NOT legit, especially not in this case. I've had some debate with the EA maintainers about improper suggestions - and this is one of them. I don't mean to sound categorical but in this case there really is zero debate possible as to which of these performs better. You can confirm this yourself (note that the bigger the haystack is, the more improvement these changes will bring). @Markus: conditions are actually more costly than methods like `strncmp` and if we can avoid those, that gives us even more bang for our buck. Reconsidering this I'd probably remove the calls to `strlen` and the condition that is supposed to "fail fast" since in reality, it makes things slower in all other use cases than if $needle is longer than $haystack. `strncmp` would serve both purposes.StringUtility.php:79UnresolvedSmall note: `strncmp` would not apply to this particular use case, hence the dual condition and string length checks are (sadly) still required. -
Claus Due uploaded patch set 9 12/06/19, 12:53
-
TYPO3com voted on patch set 9 V -1 12/06/19, 13:01 Completed build in 08m 03s on Fri, 6 Dec, 01:01 PM Test Summary: 60 of 69213 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39154
-
Claus Due uploaded patch set 10 12/06/19, 13:11
-
TYPO3com voted on patch set 10 V -1 12/06/19, 13:11 Completed build in 16s on Fri, 6 Dec, 01:11 PM Test Summary: No tests found Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39159
-
Claus Due uploaded patch set 11 12/06/19, 13:30
-
Oliver Klee voted on patch set 11 CR +1 12/06/19, 13:33
-
Claus Due commented on patch set 11 12/06/19, 13:35
Landed on solution with substr_compare which seems to cover both use cases without memory copy, without additional conditions and without first determining the length of strings.
-
TYPO3com voted on patch set 11 V -1 12/06/19, 13:42 Completed build in 09m 43s on Fri, 6 Dec, 01:42 PM Test Summary: 60 of 69213 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39164
-
Claus Due uploaded patch set 12 12/06/19, 14:00
-
TYPO3com voted on patch set 12 V +1 12/06/19, 14:08 Completed build in 07m 25s on Fri, 6 Dec, 02:08 PM Test Summary: 68763 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39168
-
Claus Due commented on patch set 12 12/06/19, 14:09
Couldn't get around using strlen as substr_compare will choose *the larger of the lengths of needle and haystack* if we don't specify that it must use only needle. -
Alexander Schnitzler rebased onto patch set 13 12/13/19, 14:31
-
Oliver Klee commented on patch set 13 12/13/19, 14:34
StringUtility.php:46If I read this correctly, we still need the string casts to avoid strict PHP warnings here. -
Alexander Schnitzler commented on patch set 13 V +1 CR +1 12/13/19, 14:35
Unresolved
You mean substr_compare here. -
TYPO3com voted on patch set 13 V +1 12/13/19, 14:41 Completed build in 09m 42s on Fri, 13 Dec, 02:41 PM Test Summary: 68714 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39395
-
Oliver Klee voted on patch set 13 CR -1 12/13/19, 16:03
-
Alexander Schnitzler commented on patch set 13 12/13/19, 16:06
StringUtility.php:46Reply UnresolvedGood catch! -
Alexander Schnitzler uploaded patch set 14 12/13/19, 16:47
-
Alexander Schnitzler voted on patch set 14 V +1 CR +1 12/13/19, 16:48
-
TYPO3com voted on patch set 14 V +1 12/13/19, 16:55 Completed build in 07m 29s on Fri, 13 Dec, 04:55 PM Test Summary: 68714 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39405
-
Markus Klein voted on patch set 14 CR +1 12/13/19, 18:40
-
Oliver Klee voted on patch set 14 CR +1 12/13/19, 20:42
-
Markus Klein updated the commit message in patch set 15 01/12/20, 10:54
-
Markus Klein voted on patch set 15 V +1 CR +1 01/12/20, 10:55
-
TYPO3com voted on patch set 15 V -1 01/12/20, 11:13 Completed build in 10m 59s on Sun, 12 Jan, 11:13 AM Test Summary: 329 of 67923 failed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39803
-
TYPO3com voted on patch set 15 V +1 01/12/20, 12:04 Completed build in 1h 13m 13s on Sun, 12 Jan, 12:04 PM Test Summary: 69198 passed Find logs and detail information at https://bamboo.typo3.com/browse/CORE-GTC-39803
-
Jörg Bösche voted on patch set 15 V +1 CR +1 01/13/20, 11:53
-
Susi Moog commented on patch set 15 V -1 01/14/20, 18:18
can we see some numbers please? my local performance tests result in faster execution every time for _the old way_ (with short and long strings, returning false / true) - when should this be faster? -
Claus Due commented on patch set 15 01/15/20, 10:36
> Patch Set 15: Verified-1 > > can we see some numbers please? my local performance tests result in faster execution every time for _the old way_ (with short and long strings, returning false / true) - when should this be faster? Please note that this patch has been open since Oct 2018, and was written at a time when PHP 7.2 was the most recent version. The performance of strpos() has been improved since (primarily due to opcode optimisations) but the following still holds generally true: * The longer the string is and the further back/forward the needle sits, the more strpos() will be outperformed by other functions. * Negative matches (needle not found) are generally faster without strpos() and more so with longer strings. * strncmp() tends to be faster than substr_compare() but requires an additional strlen(). * In CLI environments, opcode is disabled by default and requires php.ini setting to enable, making strpos() perform worse by default. Basic profile for the "begins with" use case. "Ends with" is similar, but only for functions which allow negative offsets. https://3v4l.org/RpBM9 Free from my liver: the longer we keep micro-optimisation patches alive, and because methods like strpos() are so frequently mis-used for this purpose, the greater the chance is that PHP opcode makes a workaround/optimisation which makes the "bad" usage run faster. In other words, because of the time it took to process this merge request, the smaller the difference has become (difference between PHP 7.2 and 7.4). The longer we wait, the less we actually need the patch - but the usage of strpos() is still technically "bad" as it only avoids scanning the entire haystack because of opcode transparently changing the behavior to something more like strncmp/substr_compare. -
Markus Klein commented on patch set 15 V 0 CR 0 01/15/20, 11:24
I was sitting next to Susi and saw her performance tests. Yes, not CLI, but that's probably not the 90% case for using this function. Actually all tests she conducted - haystack with only few chars, and one with 40k chars, needle in string and not in string - were slower with the new implementation. I'm not sure about the PHP version she used, but I guess this patch somehow lost its validity, as you described. -
Susi Moog commented on patch set 15 01/15/20, 11:25
> Patch Set 15: > Free from my liver: the longer we keep micro-optimisation patches alive, and because methods like strpos() are so frequently mis-used for this purpose, the greater the chance is that PHP opcode makes a workaround/optimisation which makes the "bad" usage run faster. In other words, because of the time it took to process this merge request, the smaller the difference has become (difference between PHP 7.2 and 7.4). The longer we wait, the less we actually need the patch - but the usage of strpos() is still technically "bad" as it only avoids scanning the entire haystack because of opcode transparently changing the behavior to something more like strncmp/substr_compare. Ok, I agree that the theory is on your side, but looking at the numbers merging the patch now would mean that we make it worse performance wise for newer versions for the sake of minor improvements on CLI and PHP versions running out of support soon. Taking that into account, I'd actually opt for abandoning the patch. As for the argument of long-living patches and micro-optimizations: Imho we could also interpret this as a sign that these kinds of optimizations are tedious and in comparison to other improvements that could happen on our side getting more and more superfluous as PHP itself is optimized more. This does not mean that we should never spend time here, but: if we had merged the patch 2 years ago, we could now (or in a year from now) argue that we should implement strpos again as that is then faster and a performance improvement. You know what I mean? -
Claus Due abandoned the change 01/15/20, 12:00
Fine by me, I'd rather not spend any more time on this one. Just know that the implementation we use is technically off-label and is only mitigated by opcode optimisation because strpos() is so frequently "used wrong".