So...
In microbenchmarks you can clearly see the improvement:
>>> timeit -n500 preg_match_all('/(.{65535})/s', $html100, $m,
PREG_OFFSET_CAPTURE);
=> 39
Command took 0.001709 seconds on average (0.001654 median; 0.854503 total)
to complete.
>>> timeit -n500 preg_match_all('/(.{65535})/s', $html100, $m,
PREG_OFFSET_CAPTURE|PREG_LENGTH_CAPTURE);
=> 39
Command took 0.000991 seconds on average (0.000965 median; 0.495287 total)
to complete.
$html100 is my usual 2,592,386 byte HTML of [[en:Barack Obama]].
But unless you're matching 64k strings like this, it's hard to see a
practical improvement. In my remex-html html parsing benchmark, although
LENGTH_CAPTURE doesn't make things slower, it doesn't make a significant
performance improvement. I built php statically and ran it through
cachegrind to try to figure out why, and found:
2,567,559,670 cycles: total spent executing the tokenizer benchmark
(including reading the file from disk)
1,018,845,290 cycles in zif_preg_match. Optimizing regexps is important
for tokenizers! Of these, we spend
575,478,637 doing the actual match (preg_pcre_match_impl) and
435,162,131 getting the regexp from the cache (!)
(pcre_get_compiled_regex_cache)
This is for 128,794 total regexp matches performed by the tokenizer on this
input.
Of those cycles getting the regex from cache, only 24,116,319 are spent on
cache misses where we are actually compiling regexps (sum of
php_pcre2_jit_compile and php_pcre2_compile).
Instead, 406,007,383 cycles are spent in zend_hash_find(). That's 40% of
the total time spent executing preg_match.
The LENGTH_CAPTURE optimization does reduce the total time spent in
populate_subpat_array from 160,951,690 cycles to 140,042,331 cycles in the
remex-html tokenizer on this benchmark, but that difference is overwhelmed
by (for example) the time spent in zend_hash_find().
The slowdown in zend_hash_find() appears to be due to
https://bugs.php.net/bug.php?id=63180 which disabled interned keys in the
pcre_cache table. Because of this, even if the regexs are interned, we
must pay for a complete zend_string_equal_content() on each match, which
takes time proportional to the length of the regex. This can be quite
large -- for example, for the HTML5 character reference regex in
remex-html, which contains every valid entity name and is 26,137 bytes
long, and we need to do a zend_string_equal_content() on the 26,137 byte
regexp for every ~5 byte entity in the parsed HTML.
--scott
On Wed, Mar 20, 2019 at 4:35 PM C. Scott Ananian cananian@wikimedia.org
wrote:
On Tue, Mar 19, 2019 at 10:58 AM Nikita Popov nikita.ppv@gmail.com
wrote:
After thinking about this some more, while this may be a minor
performance improvement, it still does more work than necessary. In
particular the use of OFFSET_CAPTURE (which would be pretty much required
here) needs one new two-element array for each subpattern. If the captured
strings are short, this is where the main cost is going to be.
The primary use of this feature is when the captured strings are long,
as that's when we most want to avoid copying a substring.
I'm wondering if we shouldn't consider a new object oriented API for
PCRE which can return a match object where subpattern positions and
contents can be queried via method calls, so you only pay for the parts
that you do access.
Seems like this is letting the perfect be the enemy of the good. The
LENGTH_CAPTURE significantly reduces allocation for long match strings, and
it allocates the same two-element arrays that OFFSET_CAPTURE would -- it
just stores an integer where there would otherwise be an expensive
substring. Furthermore, since the array structure is left mostly alone, it
would be not-too-hard to support earlier-PHP versions, with something like:
$hasLengthCapture = defined('PREG_LENGTH_CAPTURE') ? PREG_LENGTH_CAPTURE
: 0;
$r = preg_match($pat, $sub, $m, PREG_OFFSET_CAPTURE | $hasLengthCapture);
$matchOneLength = $hasLengthCapture ? $m[1][0] : strlen($m[1][0]);
$matchOneOffset = $m[1][1];
If you introduce a whole new OO accessor object, it starts becoming very
hard to write backward-compatible code.
--scott
Fair enough. I've created https://github.com/php/php-src/pull/3971 to
implement this feature. It would be good to have some confirmation that
this is really a significant performance improvement before we land it
though.
Nikita
--
(http://cscott.net)