perf(aggs): bound the zone-offset probe to a six-byte window at the end - #119
Merged
Conversation
…g it (#96) PR #91 taught parse_date_ms to accept `+HHMM` zone offsets, but put the new `%z` try immediately after the RFC3339 fast path. parse_date_ms runs per date field per document on ingest, and offsetless ISO values — the overwhelmingly common shape, and one no zone-offset pattern can ever match — reach neither RFC3339 nor `%z`, so every one of them started paying for a doomed offset parse before reaching the branch that does match. Measured ~1.9x on that path. Moving the `%z` try to the end of the chain fixes offsetless values but hands the bill to `+HHMM`, the class #91 exists to serve: it then falls through a dozen doomed parses first, 4.7x slower than before. Neither order is free. So keep the original order and gate the parse on a cheap shape check instead. chrono's `%z` needs an explicit sign (`+`, `-`, or MINUS SIGN U+2212), it cannot appear before byte 11 (the shortest datetime chrono will accept in front of it is `5-1-2T3:4:5`), and it needs `HHMM` behind it, so it cannot sit in the last four bytes. Canonical `YYYY-MM-DDTHH:MM:SS` separators pin the field widths and raise that floor to byte 18 — 18 and not 19, because one-digit seconds are legal and `2025-01-02T03:04:5+00:00` really does parse. Finding a sign in that window is a necessary condition for the parse, so a value that fails the check cannot have parsed. The check over-matches in every judgement call: a false positive only costs the parse that would have run anyway, a false negative would silently drop a date out of every aggregation. Release-mode ns/call, minimum over four interleaved runs pinned to one core, this box being shared (identical-code classes below show the noise floor): #91 %z-last guarded offsetless ISO 314.9 161.0 161.3 <- 1.95x, the hot path +HH:MM (RFC3339) 30.8 30.8 30.8 +HHMM (no colon) 206.2 962.4 205.9 <- 4.68x vs %z-last Z-suffixed 27.7 27.3 27.2 epoch integer 360.0 352.0 323.2 date only 272.0 195.9 196.4 space separated 670.6 595.2 604.3 garbage 339.1 332.7 302.3 epoch JSON number 3.7 3.6 3.6 No class is slower than #91; the two the guard cannot spare (`+HHMM`, which must still parse, and the space-separated form, whose head is not canonical) pay a bounded 3-9ns for the check itself. Behaviour is unchanged. A differential harness carrying verbatim copies of all three versions ran 213,559 inputs — every offset spelling, chrono's one-digit field widths, colon/space runs inside the offset, U+2212, signed and wide years, single-edit mutations of six skeletons at every position, and 200k pseudo-random strings over a date alphabet — and the three output dumps are byte-identical (sha256 b5bb3e0b18e4...). 4,800 of those inputs are `%z`- parseable, with signs as early as byte 11 and 1,827 of them before byte 18, so both lower bounds are exercised rather than assumed; forcing the canonical floor to 19 makes the harness fail on `2025-01-02T03:04:5+00:00`. In-tree, `parse_date_ms_golden_matrix` pins 74 shapes to the values the pre-guard code produced, `zone_offset_guard_never_false_negatives` re-asserts the one-sidedness over ~11k generated inputs, and `nocolon_offset_parse_is_guarded` counts the parses that actually ran — placement is invisible to results, so the saving has to be asserted as work skipped rather than as a value returned.
The guard added for issue #96 was correct but paid for itself with a worse regression: it hunted for the offset's sign by scanning `[11, len - 5)`, which is O(len). Any value whose window holds no `+`, `,`, `-` or non-ASCII byte — prose, digits, anything long — ran that scan to the end, where before the guard `parse_date_ms` failed in O(1)-ish time. Measured, per-pass paired timings pinned to one core, ns/op before the guard -> with it: 512 B 214 -> 326, 4 KB prose 214 -> 1139, 4 KB digits 254 -> 1214, 64 KB 804 -> 15587. That is a 19x regression on the same per-document path the guard exists to make cheaper. A `%z` offset cannot be anywhere but the end: it closes the pattern and `parse_from_str` insists the whole value be consumed, so an accepted value ends with the offset's two minute digits and the sign sits a fixed distance in front of them — `len - 5` for `±HHMM`, `len - 6` for `±HH:MM` and `±HH MM`. So the probe now reads a six-byte tail (sign + `HH` + one separator + `MM`, named and derived from those spellings) and nothing else. No scan, no loop, no dependence on length. chrono's separator scanner does accept a longer run — `+00 : 00` really does parse — which walks the sign out of any constant window. Chasing that run would put the O(len) back, so it is over-matched from the separators it leaves behind instead: the probe stays one-sided, and an over-match only pays for the parse that would have run anyway. Now best-or-tied on every class, against both origin/main and the scanning guard (ns/op, 12 pinned runs x 41 interleaved passes, median of per-pass ratios; 1.00x here is the noise floor, established by the two classes that return before the probe is even reached): class main prev now vs main vs prev offsetless ISO 211.8 107.2 108.2 0.513x 1.001x +HH:MM 19.8 19.8 19.8 1.000x 1.000x +HHMM 136.8 136.1 135.9 0.997x 0.999x Z-suffixed 18.0 17.9 17.9 1.000x 1.001x epoch integer 241.8 219.6 219.8 0.910x 0.998x 128 B sign-free 215.3 218.2 197.0 0.905x 0.897x 512 B sign-free 213.5 325.9 195.1 0.906x 0.593x 4 KB prose 213.9 1139.1 197.4 0.920x 0.169x 4 KB digits 254.1 1213.7 232.1 0.912x 0.192x 64 KB sign-free 804.3 15587.1 774.2 0.974x 0.048x Output is unchanged: 16315 values — every zone spelling including `+0000`, `+00:00`, `+00 00`, `+00:::00`, `Z`, `z` and U+2212, offsetless ISO, epoch integers, fractional seconds of every width, garbage and multi-kilobyte blobs — parse byte-identically under origin/main, the scanning guard and this probe. `zone_offset_probe_window_is_bounded` pins the property the scan lost: the probe's answer is fixed by the last six bytes plus the length, so filler in front of them cannot change it or add work — including filler made entirely of the bytes the old scan was hunting for, at 64 B through 64 KB.
…scan
`zone_offset_probe_window_is_bounded` is true but does not discriminate: it
grows a HOMOGENEOUS filler and asserts the answer does not change, and an
O(len) scan's answer is invariant under exactly that transformation — a `"+"`
filler contains a `+` at every length and an `"a"` filler contains none at any
length. Verified by mutation: replacing the probe's body with the previous
unbounded scan leaves that test green, so nothing in the suite would have
caught the regression coming back.
The property that characterises the fix is that the answer depends on
`(len, last ZONE_OFFSET_PROBE_BYTES bytes)` and nothing else. The new test
holds BOTH the length and the window fixed and perturbs every byte strictly
below the window, over 8 tail shapes x 5 lengths x 9 single-byte edits.
Mutation-checked both ways on this tree:
bounded probe (as shipped) -> passes, 3 168 checks
unbounded scan restored -> FAILS at "editing byte 14 of 22 ... to 0x3a",
while the old scaling test still passes
xerj-org
force-pushed
the
fix/issue-96-v3
branch
from
August 1, 2026 23:03
480b45e to
ae37b41
Compare
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
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.
Closes #96
PR #91 added a no-colon zone-offset branch to
parse_date_msbut placed it before the naive fast paths, costing roughly 2x on offsetless ISO values. That is a per-document ingest path.Two earlier attempts are worth stating, because each was blocked for a real reason and this one has to answer both.
+HHMMby ~5x, which is the exact class fix(engine): parse_date_ms accepts no-colon numeric zone offsets #91 existed to serve.O(len)scan on the same per-document path, measured 16.1x slower on a 64 KB value than having no guard at all.What this does
The probe reads a fixed six-byte window at the end of the value and nothing else. No scan, no dependence on length.
A constant window is sufficient rather than lucky.
%zcloses the pattern and chrono'sparse_from_strreturnsTOO_LONGunless the whole input is consumed, so an accepted value ends with the offset's two minute digits and everything the offset needs sits at a fixed distance from that end. The separator run is over-matched from the bytes it leaves behind rather than chased, because chasing it is exactly theO(len)cost being removed. The probe is deliberately one-sided: a false positive only pays for a parse that would have run anyway, a false negative would change results.Performance
Three independent builds on three different cores, 8 process runs x 40 passes each,
CLOCK_THREAD_CPUTIME_ID,taskset-pinned, with bit-identical control copies to establish the noise floor (~0.3%). ns/op:+HH:MM+HHMMNo class is slower in all three builds against either baseline.
+HHMMis 0.998 / 0.996 / 1.002 vs main, a tie at the identical-code floor.Correctness
Zero mismatches against
mainover 72,462 constructed values, of which 23,377 are%z-parseable: every zone spelling, non-ASCII separators (U+00A0, U+2028, U+2029, U+3000, U+2007, U+205F, U+1680), U+2212 minus, minute-digit boundaries (+0059/+0060/+0069), truncated offsets, i64 bounds, signed and wide years, a separator-run attack grid, a length grid to 64 KB, and a single-edit mutation grid.The window was attacked, not assumed. 11,714 corpus values are
%z-accepted with their sign byte strictly below the six-byte window, and all matchmain. Walking a real offset out step by step puts the sign 23 bytes outside the window, andmainand this branch agree on all 35 such cases.The regression test, and why the first one did not count
The original bounded-window test grew a homogeneous filler and asserted the answer did not change. That is true but does not discriminate: an
O(len)scan's answer is invariant under exactly that transformation, since a"+"filler contains a+at every length and an"a"filler contains none at any length. Verified by mutation — restoring the unbounded scan left that test green.The replacement pins the property that actually characterises the fix: the answer is a function of
(len, last six bytes)and nothing else. It holds both length and window fixed and perturbs every byte below the window, over 8 tail shapes x 5 lengths x 9 single-byte edits (3,168 checks).Mutation-checked both ways:
editing byte 14 of 22 ... to 0x3a, while the old scaling test still passesNote
const _: () = assert!(ZONE_OFFSET_PROBE_BYTES == 6)is load-bearing, not decorative: the slice pattern binding the window is refutable, so a width change would silently never match and the probe would answerfalsefor everything.