Skip to content

perf(aggs): bound the zone-offset probe to a six-byte window at the end - #119

Merged
xerj-org merged 3 commits into
mainfrom
fix/issue-96-v3
Aug 1, 2026
Merged

perf(aggs): bound the zone-offset probe to a six-byte window at the end#119
xerj-org merged 3 commits into
mainfrom
fix/issue-96-v3

Conversation

@xerj-org

@xerj-org xerj-org commented Aug 1, 2026

Copy link
Copy Markdown
Owner

Closes #96

PR #91 added a no-colon zone-offset branch to parse_date_ms but 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.

  • Moving the branch last fixed the offsetless case and regressed +HHMM by ~5x, which is the exact class fix(engine): parse_date_ms accepts no-colon numeric zone offsets #91 existed to serve.
  • Guarding it with a sign scan fixed both of those and introduced something worse: an unbounded 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. %z closes the pattern and chrono's parse_from_str returns TOO_LONG unless 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 the O(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:

class main scan guard this vs main vs scan guard
offsetless ISO 217.0 110.0 110.2 0.51x 1.00x
+HH:MM 20.6 20.6 20.6 1.00x 1.00x
+HHMM 138.6 139.7 139.7 1.00x 1.00x
Z-suffixed 18.9 18.9 18.9 1.00x 1.00x
epoch integer 251.1 226.7 228.0 0.90x 0.99x
date only 185.0 135.4 135.3 0.74x 1.00x
512 B sign-free 217.8 330.5 196.1 0.91x 0.57x
4 KB prose 220.7 1171.4 198.3 0.90x 0.16x
4 KB digits 265.3 1216.0 238.7 0.91x 0.19x
64 KB sign-free 1035.2 16278.0 1009.2 0.98x 0.05x

No class is slower in all three builds against either baseline. +HHMM is 0.998 / 0.996 / 1.002 vs main, a tie at the identical-code floor.

Correctness

Zero mismatches against main over 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 match main. Walking a real offset out step by step puts the sign 23 bytes outside the window, and main and 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:

  • bounded probe as shipped: passes
  • unbounded scan restored: fails at editing byte 14 of 22 ... to 0x3a, while the old scaling test still passes

Note

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 answer false for everything.

…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
xerj-org merged commit c694fb6 into main Aug 1, 2026
9 checks passed
@xerj-org
xerj-org deleted the fix/issue-96-v3 branch August 1, 2026 23:49
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

parse_date_ms: no-colon offset branch costs ~2x on offsetless ISO values (remedy verified)

1 participant