pjfanning opened a new pull request, #3506:
URL: https://github.com/apache/pekko/pull/3506
### Motivation
`SelectChildPattern` compiled its glob to a regular expression with
`Helpers.makePattern`
(`Helpers.scala:46`), which quotes the literal runs but turns every `*` into
`.*`. A chain of
those backtracks badly. Measured on JDK 17, matching a pattern against a
name of all `a`s that
cannot satisfy the trailing literal:
```
glob 5 stars (12 chars), name 30 chars -> 5 ms
glob 8 stars (18 chars), name 30 chars -> 214 ms
glob 10 stars (22 chars), name 30 chars -> 1098 ms
glob 12 stars (26 chars), name 30 chars -> 3485 ms
glob 8 stars (18 chars), name 36 chars -> 1204 ms
glob 10 stars (22 chars), name 36 chars -> 9427 ms
glob 12 stars (26 chars), name 36 chars -> 46987 ms
```
An `ActorSelectionMessage` carries its pattern elements in the message
(`MessageContainerSerializer.scala:83-92`), and `SelectChildPattern`'s
constructor compiles the
pattern, so both the compile and the match are reachable from one small
message.
`ActorSelection.deliverSelection` runs on the caller's thread for a local
selection and, for a
remote one, directly on the inbound stream thread
(`MessageDispatcher.scala:93`, deliberately,
"to make sure it is not stuck on busy user actor").
My first thought was to cap the pattern length in the serializer. The
numbers above say that
would have been useless: 26 characters is already enough, and it is not a
suspicious-looking
pattern. The cost has to come out of the matching itself.
Note that `untrusted-mode` does not cover this either — its check
(`MessageDispatcher.scala:81-93`) runs after deserialization, so it stops
the matching but not
the compiling.
### Modification
Add `org.apache.pekko.util.Glob` (`@InternalApi`), which matches the same
grammar — `?` is
exactly one character, `*` is any run, everything else is literal — with the
standard
single-backtrack-point wildcard algorithm: it remembers only the most recent
`*` and how much
it has consumed, so it never revisits a decision more than once per input
position. Worst case
is proportional to the product of the two lengths; in practice it is linear.
`ActorSelection.deliverSelection` now matches through
`SelectChildPattern.matches`.
`SelectChildPattern.pattern` is kept for compatibility but is now `lazy`, so
deserializing a
selection no longer compiles a regular expression at all.
Nothing else used `Helpers.makePattern`, which is public API and is left in
place.
I did not add a cap on the number of selection elements. Once matching is
linear the remaining
per-element cost is a small object allocation, already bounded by the frame
size.
### Result
The same selections match as before, in time linear in practice.
### Tests
- `sbt "actor-tests/testOnly org.apache.pekko.util.GlobSpec"` — 6 passed.
The important one is
`agree with the regular expression it replaces, exhaustively over short
inputs`: every pattern
over `{a, b, *, ?}` up to length 4 (341 of them) against every input over
`{a, b}` up to
length 4, compared against `Helpers.makePattern`. All agree, so the
grammar is unchanged.
- `sbt "actor-tests/testOnly org.apache.pekko.actor.ActorSelectionSpec"` —
28 passed, including a
new end-to-end test that sends a wildcard selection with the pathological
pattern to a parent
with a 36 character child and asserts it returns in under 3 seconds.
- That end-to-end test was checked to discriminate: reverted to the regex
matching it fails with
`42561317850 was not less than 3000000000` — 42.5 seconds.
- `sbt "remote/testOnly
org.apache.pekko.remote.serialization.MessageContainerSerializerSpec"` — 3
passed
- `sbt "actor/mimaReportBinaryIssues"` — no issues
- `sbt "actor/scalafmtCheckAll" "actor-tests/scalafmtCheckAll"
headerCreateAll` — clean
### References
None. `Glob.scala` is new code and carries the standard ASF header.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
