Repository navigation
stripos with large haystack has bad performance #7847
Description
Description
stripos is slow because both input strings are always lowercased completely. This also entails unnecessary memory consumption.
preg_match with case-insensitive flag is a much faster alternative.
Source code:
Line 1914 in 9362d6f
Test case:
<?php
$haystack = str_repeat('A', 1e+7) . 'BBB';
$repetitions = 0;
$start = microtime(true);
do {
strpos($haystack, 'bbb');
$repetitions += 1;
} while (microtime(true) - $start < 5);
$rate = round($repetitions / (microtime(true) - $start));
$rate = str_pad($rate, 8, ' ', STR_PAD_LEFT);
print("strpos: $rate / second\n");
$repetitions = 0;
$start = microtime(true);
do {
stripos($haystack, 'bbb');
$repetitions += 1;
} while (microtime(true) - $start < 5);
$rate = round($repetitions / (microtime(true) - $start));
$rate = str_pad($rate, 8, ' ', STR_PAD_LEFT);
print("stripos: $rate / second\n");
$repetitions = 0;
$start = microtime(true);
do {
preg_match('/bbb/i', $haystack, $match, PREG_OFFSET_CAPTURE);
$repetitions += 1;
} while (microtime(true) - $start < 5);
$rate = round($repetitions / (microtime(true) - $start));
$rate = str_pad($rate, 8, ' ', STR_PAD_LEFT);
print("preg_match: $rate / second\n");Example output:
strpos: 1192 / second
stripos: 176 / second
preg_match: 1118 / second
PHP Version
PHP 8.0.14
Operating System
No response
Activity
iluuu1994 commentedon Dec 28, 2021
Not sure if this qualifies as a bug but there's definitely room for improvement.
cmb69 commentedon Dec 28, 2021
I'd rather treat this as feature request; we probably don't want to replace the current implementation of
stripos()in stable releases (given that it works this way since "forever"), and the recent changes to https://wiki.php.net/rfc/strtolower-ascii may have already improved the performance, and at least should make it easier to avoid usingzend_string_tolower(). Furthermore, I somewhat doubt that the given test script is representative for real world applications, where case-insensitive searches for long ASCII strings appear to be rather rare (and especially the case where we only have to match the first character ofneedleto recognize that we do not have to compare the rest ofneedle, and can procede to the next character of haystack).That said, consider the following drastically simplified but naive patch for master:
The given test script outputs here:
This is even slightly slower than the unpatched variant, so the
zend_string_tolower()andphp_memnstr()approach doesn't appear that bad, especially given thatpreg_match()even rivals the performance ofstrpos().iluuu1994 commentedon Dec 31, 2021
The new algorithm seems to be faster in all cases. Even in the worst case (compared to the old implementation) it is faster, likely because there is no allocation happening. The larger the haystack the more dramatic the difference. There is some variance when executing the benchmark but the difference in the benchmark is way above the margin of error.
kamil-tekiela commentedon Dec 31, 2021
Is there any impact on the memory usage?
iluuu1994 commentedon Dec 31, 2021
@kamil-tekiela It avoids copying of both the haystack and needle so two allocations less essentially. But I haven't measured it. It will likely be insignificant unless the string is very very large as the memory is freed before the function returns.
[-]stripos has very bad performance[/-][+]stripos with large haystack has bad performance[/+]Optimize stripos/stristr