Re: [RFC] Prepared Literal String Matching and Replacement
| From: | Artem Ukrainskiy | Date: | Fri, 13 Nov 2026 01:54:53 +0000 |
| Subject: | Re: [RFC] Prepared Literal String Matching and Replacement | ||
| References: | 1 2 | Groups: | php.internals |
| Request: | Send a blank email to internals+get-133094@lists.php.net to get a copy of this message | ||
Hi Larry,
Thanks for the review. I've updated the RFC to v0.4 and redone the
measurements. The algorithm itself got further optimizations, and I revised
the benchmark methodology, so the results are more honest and closer to
real product scenarios. The old numbers ran one text over and over. The CPU
learned it, and the new class looked 3-4 times faster than it is. Calls now
go through a pool of different texts. The code has moved to ext/standard.
I've also substantially rewritten the RFC and the benchmark report. I
removed ambiguous wording and repetition, and put the product scenarios
first.
> My main question is that this feels very niche. Based on the benchmarks,
if I'm reading them correctly, it sounds like 90% of uses would be better
served with the existing APIs. Does this make sense for stdlib then?
That share came from the measurement matrix I picked, not from real
applications, so I don't quote it anymore. Instead the RFC now has three
scenarios on real data: comment moderation, bot detection by User-Agent and
auto-linking PHP manual pages. With a reused object the new class is 8-123
times faster than the fastest existing method. One call on a short text is
slower, and the RFC says so directly. On long texts one call pays off too:
auto-linking 4-16 KiB manual pages with 128-512 names is 2.9-3.6 times
faster.
> For example... would this pay off in a long-running process like
FrankenPHP or Swoole, if the object is saved between requests?
Yes, that's the main use case. The object is built when the worker starts
and lives across requests, so the build is paid once. The Summary table
estimates how many calls repay the build.
> - Matcher::matchAll() returns a list, but each of the items in it
contains, I believe, a unique value. Could it then return a keyed array
for easier lookup?
The items aren't unique. In 'aaa' the key 'a' occurs three times and
'aa'
twice, and different keys can start at the same offset. An array keyed by
keyword or by offset would lose results. getMatchedKeywords() returns the
unique keys. The RFC now spells this out with that example.
> - The inout $count argument to Replacer::replace(): Eew. Please explore
a better way of handling that.
Removed. replace() returns only the string, and a replacement count moved
to Future Scope. Honestly, I don't think it's needed.
> Would swapping Replacer in for strtr() require any subtle logic changes,
or is it a drop-in syntax change?
For a dictionary of non-empty keys and string values the result is the
same. The only differences are in checking the dictionary. An empty key
throws ValueError, while strtr() skips it with a warning. A non-string
value throws TypeError, while strtr() converts it. The object keeps a
snapshot of the dictionary. The RFC lists this in the Replacer section.
> How would one reinitialize it? Do you mean calling the constructor
explicitly, which PHP allows even though it's never ever safe to do anyway?
:-)
Yes, I meant calling $object->__construct(...) again. The error table now
says exactly that.
> The whole point of == on objects is to ask "are these equivalent," and
two Matchers with the same dictionary are equivalent. Thus they should be
==.
Agreed, done. == on Matcher compares the sets of keys, on Replacer the key
=> value pairs, ignoring order. === still compares identity.
> However, is there a use for a Unicode/Grapheme equivalent? Even if
future scope, it's worth mentioning.
Exact UTF-8 search already works, since bytes are compared. A grapheme API
would be useful, for example for highlighting, but it's a separate
contract: grapheme boundaries, offset units, normalization, case. I'm not
including it in this RFC.
> Please also explain why you've chosen to not follow the same semantics as
one of the existing tools
Replacement follows strtr(): existing PHP dictionaries give the same
result, and that matters more to me than compatibility with another
language. Rust's aho-corasick has both modes, and LeftmostLongest picks
matches the same way as Replacer. Go resolves conflicts by argument order:
with the pairs a => Y and aa => X, the string aa becomes YY in Go and X in
Replacer and strtr(). This is in "Design choices". Matching modes might be
a future extension of the API.
> - In "Where existing tools are preferable", there's a broken link in the
2nd paragraph.
That was the {{...}} example, which DokuWiki read as media markup. The item
referred to the old measurements and isn't in v0.4.
> These are closely related enough that I think a single vote is fine.
Agreed.
On Fri, Nov 6, 2026 at 6:54 PM Larry Garfield <larry@garfieldtech.com>
wrote:
> On Fri, Nov 6, 2026, at 6:59 AM, Artem Ukrainskiy wrote:
> > Hi internals,
> >
> > I'd like to open discussion on this RFC:
> > https://wiki.php.net/rfc/prepared_literal_string_matching
> >
> > It proposes Str\Matcher and Str\Replacer for prepared literal substring
> > search and replacement. Matcher provides presence checks, unique matched
> > keywords, occurrence counts, and enumeration of all overlapping matches
> > with byte offsets, using Str\MatchResult objects. Replacer performs
> > non-overlapping replacements, choosing the earliest start and then the
> > longest key, without rescanning inserted text.
> >
> > Both classes prepare an immutable dictionary during construction.
> > Matching is byte-oriented, binary-safe, and case-sensitive. Objects can
> be
> > reused within a request or in long-running applications.
> >
> > I've implemented the API and published reproducible benchmarks covering
> > both prepared calls and one-shot use, including construction and
> destruction.
> > Preparation can pay off even for a single call on some inputs. On others,
> > existing PHP functions or PCRE remain faster, even than a prepared
> object.
> >
> > I propose including these classes in ext/standard in the Str namespace.
> > The current implementation is in ext/strmatch. I'd welcome feedback on
> > the API, integration, error types, and whether Matcher and Replacer
> > should be considered together or separately.
> >
> > Implementation:
> > https://github.com/php/php-src/pull/25122
> >
> > Benchmarks, methodology and raw data:
> >
>
> https://github.com/ArtUkrainskiy/php-src-bench/tree/main/reports/multi-pattern-search
> >
> > --
> > Best regards,
> > Artem Ukrainskiy
>
> This looks interesting, and I'm not opposed to it. It somewhat parallels
> the recently discussed Pcre class.
>
> My main question is that this feels very niche. Based on the benchmarks,
> if I'm reading them correctly, it sounds like 90% of uses would be better
> served with the existing APIs. Does this make sense for stdlib then? It
> would be helpful to include more practical examples of where I'd want to
> use this instead of str_contains(), rather than just a table of byte
> counts. The "Where the API can help" section isn't sufficient as-is.
>
> For example... would this pay off in a long-running process like
> FrankenPHP or Swoole, if the object is saved between requests?
>
> Other issues:
>
> - Matcher::matchAll() returns a list, but each of the items in it
> contains, I believe, a unique value. Could it then return a keyed array
> for easier lookup? (The example suggests I may be wrong, but if so, please
> spell this out explicitly.)
>
> - The inout $count argument to Replacer::replace(): Eew. Please explore a
> better way of handling that. inout params in a language like PHP are the
> absolute last resort.
>
> - I'm not clear if it says explicitly anywhere if there's behavioral
> differences from the existing functions. If so it wasn't clear. Would
> swapping Replacer in for strtr() require any subtle logic changes, or is it
> a drop-in syntax change? That should be made explicit.
>
> - "Reinitializing an already prepared object throws an Error, even if its
> dictionary is empty." - How would one reinitialize it? Do you mean calling
> the constructor explicitly, which PHP allows even though it's never ever
> safe to do anyway? :-) If so, please clarify that's what you mean.
>
> - "two distinct objects compare unequal with ==, even if their
> dictionaries are identical. " - I disagree with this. The whole point of
> == on objects is to ask "are these equivalent," and two Matchers with the
> same dictionary are equivalent. Thus they should be ==.
>
> - The RFC notes that these routines are byte-based only, which is fine, as
> that's what most of PHP is. However, is there a use for a Unicode/Grapheme
> equivalent? Even if future scope, it's worth mentioning.
>
> - In "Design choices," you list how existing implementations in other
> languages differ. Please also explain why you've chosen to not follow the
> same semantics as one of the existing tools, as that means someone moving
> from those languages to PHP is going to be easily confused by the edge
> cases.
>
> - In "Where existing tools are preferable", there's a broken link in the
> 2nd paragraph.
>
> - These are closely related enough that I think a single vote is fine.
> There's no need to separate them.
>
> --Larry Garfield
>
--
Best regards,
Artem Ukrainskiy