Bug 275279 – [JSC] Use immediate bit-vectors for character class matching in YarrJIT

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[David Degazio]

Currently YarrJIT is relatively naive when it comes to matching character classes, as far as I can tell (ignoring some special cases, i.e. unifying ASCII letters using a bit flip, lookup tables for spaces) there are pretty much two ways we match characters:
 - Binary search over the codepoint values, which is reasonably effective in general for lots of contiguous ranges, but relatively branchy.
 - Sequential character-by-character equality checks (!) for sets of non-range character matches.

The latter especially is super naive, if we have a set of N discontiguous characters we are potentially doing N independent branch-if-equal checks...

I think we can improve this by exploiting the fact that lots of character checks are quite close together. Even considering unicode, my guess is it's pretty likely for ranges in a character class to be close to each other in the codepoint range, or for there to be clusters of codepoints in general within a few tens of each other. In these cases, we can do a single range-check, a subtract, and a bit-vector test to see if a character is within some small set, even if the set is sparse. If we keep the sets small enough, we can also avoid any (data) memory overhead by directly materializing the set into a register.

[Radar WebKit Bug Importer]

<rdar://problem/129419939>

[David Degazio]

Pull request: https://github.com/WebKit/WebKit/pull/29727

[EWS]

Committed 280425@main (34b0b047bb64): <https://commits.webkit.org/280425@main>

Reviewed commits have been landed. Closing PR #29727 and removing active labels.