_sre: drive a non-ASCII str subject through a character index on the string - #8522
Merged
Conversation
`Wtf8`'s iterators are sequential, so resolving a code point index through them is O(n) and code that indexes the same string repeatedly walks it once per index. `Wtf8Index` is a side table -- one 24-byte group per 64 code points, 0.375 bytes per code point -- that answers the same question in constant time; the layout is PyPy's `UTF8_INDEX_STORAGE`. `StrData` builds one on the first call to the new `char_index_to_byte`, in a slot published by compare-exchange, and drops it with the string. ASCII strings answer from the index itself and never build a table. A clone gets an empty slot, since it indexes its own copy of the buffer. Assisted-by: Claude
The `&Wtf8` drive answers `count` and `create_cursor` by decoding from the start of the subject, so a scan that restarts at successive positions walks the subject once per position, and `slice` walks it again per extracted group. `Utf8Str` holds the `PyStr` and asks it instead: `count` is the cached character length, and `create_cursor` and `slice` resolve their positions through `char_index_to_byte`. Stepping is the `&Wtf8` drive's, unchanged. The table lives on the string, so a `Match` that outlives the scan shares it -- `group` has no cursor of its own to move relative to. `SreStr for &Wtf8` has no callers left; the `StrDrive` impl stays, since `Utf8Str` steps through it. The three subject helpers now share one downcast. Assisted-by: Claude
Contributor
|
No actionable comments were generated in the recent review. 🎉 ℹ️ Recent review info⚙️ Run configurationConfiguration used: Path: .coderabbit.yml Review profile: CHILL Plan: Pro Plus Run ID: 📒 Files selected for processing (5)
📝 WalkthroughWalkthroughAdded a compact, lazily cached WTF-8 index for character-to-byte lookup. Exposed the lookup through ChangesWTF-8 character indexing
Estimated code review effort: 4 (Complex) | ~45 minutes Merge Risk: ⚪ Minimal · up to The PR adds indexed character-position handling for non-ASCII strings while preserving existing behavior and performance for unaffected paths. No actionable merge-blocking risk remains beyond normal checks and review. Suggested reviewers: Sequence Diagram(s)sequenceDiagram
participant Pattern
participant Utf8Str
participant PyStr
participant StrData
participant Wtf8Index
Pattern->>Utf8Str: Construct non-ASCII subject drive
Utf8Str->>PyStr: Request character index conversion
PyStr->>StrData: Delegate char_index_to_byte
StrData->>Wtf8Index: Build or query cached index
Wtf8Index-->>StrData: Return byte offset
StrData-->>PyStr: Return byte offset
PyStr-->>Utf8Str: Return byte offset
🚥 Pre-merge checks | ✅ 5✅ Passed checks (5 passed)
✨ Finishing Touches🧪 Generate unit tests (beta)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Follow-up to #8520, which made
relinear on all-ASCIIstrsubjects by driving themover their bytes. A subject with one non-ASCII character still took the
&Wtf8drive andwas still quadratic: at n=20000,
finditertook 1.27 s and a backreference scan 7.8 s.They now take 4.1 ms and 3.4 ms.
Why it was quadratic
StrDrivepositions are character indices, and the&Wtf8drive resolves one by decodingfrom the start of the subject. Four separate paths pay that:
count()Request::newclampsendwith itcreate_cursorState, whose cursor is nullcreate_cursorGROUPREFderives the group's cursorslice()code_points().take(end).skip(start)The first two make
finditerquadratic; the last makesfindall/sub/split/groupquadratic even though their
SearchIteralready advances one cursor relatively.Making the engine walk relatively instead would fix the cursor cases but not
slice: aMatchoutlives the scan that produced it and has no cursor to be relative to. What allfour have in common is re-deriving something about the subject that the string could
answer once, so that is where the answer goes.
The change
Wtf8Index(new, inrustpython-common) is a table over a WTF-8 buffer: one 24-byte groupper 64 code points, holding a byte offset every fourth code point, so a lookup is one table
read and at most two steps. The layout is PyPy's
UTF8_INDEX_STORAGE(
rpython/rlib/rutf8.py), which solves the same problem for the same reason.StrDatabuilds one on the first call to the newchar_index_to_byte, in a slot publishedby compare-exchange next to the existing character-length cache, and drops it with the
string. ASCII strings answer from the index itself and never build a table.
_sre'sUtf8Strdrive then holds thePyStrrather than a&Wtf8:countis the cachedcharacter length, and
create_cursorandsliceresolve through the table. Stepping is the&Wtf8drive's, unchanged -- the subject is the same buffer decoded the same way, so onlythe operations that resolve a position from scratch differ.
Measurements
Best of 3, same machine, paired against the parent commit. Each row doubles n, so
x4isquadratic and
x2is linear.finditergroup(0)findallsubsplitfindallfinditer, lone-surrogate subjectThe subject is
("항목%04d " % 7) * nand the pattern\d+; the surrogate row replaces thefirst character with
\ud800so the subject is WTF-8 rather than UTF-8.Cost
sys.getsizeof('')goes from 88 to 96: one word per string, whether or not it is everindexed. A string that is indexed pays a further 0.375 bytes per character, and one O(n)
build, on the first lookup.
The paths that must not move, measured by running both binaries alternately (best of 7,
three rounds, minimum reported):
finditerfindallsubfindall[w + "!" for w in words]" ".join(words).split()s[i]in a loopWithin 3%, in both directions, and the pure-string rows do not move. The
bytesrow shiftsby the same 2.5% as the ASCII ones while touching no
PyStrat all, so what is left isbinary layout rather than the extra word -- I would not claim these numbers separate a
sub-3% effect.
Correctness
test_re: run=166, skipped=14, SUCCESS.test_re test_str test_string test_bytes test_json test_codecs test_ucn: 1198 run, 68skipped, byte-identical results before and after.
operations, straddling the ASCII boundary, including a lone surrogate and an embedded NUL
-- still produces 0 differences.
Wtf8Indexhas unit tests checking every index against the buffer's own iterator, overeach encoded width, the group and entry boundaries (1, 3, 4, 5, 63, 64, 65, 127, 128, 129,
255, 256, 257 code points), mixed widths, and lone surrogates.
SreStr for &Wtf8has no callers left and is removed; theStrDriveimpl stays, sinceUtf8Strsteps through it.Not in this PR
StrData::nth_char-- and sostr.__getitem__-- is still O(n) on a non-ASCII string, andthe same table would answer it in constant time. It is left alone because the tradeoff is
different there: a single subscript would pay an O(n) build to replace an O(n) walk, so it
needs a policy for when building is worth it, rather than the unconditional build a regex
scan justifies.
🤖 Generated with Claude Code
Summary by CodeRabbit
New Features
Performance