jeff/zig-datetime

Watch

Fork 0

Recover the speed lost making posixtz.typeAt correct #6

New issue

Closed

opened 2026-08-31 12:29:45 -05:00 by jeff · 1 comment

jeff commented

2026-08-31 12:29:45 -05:00

Owner

Fixing a correctness bug in 773f3a1 made the POSIX rule path a lot slower,
and the speed is worth getting back.

posixtz.typeAt used to search one year rather than three, which was
about a quarter quicker, and it was wrong: a switch time may be up to 167
hours either side of its day and spill into a neighbouring year, and two
switches landing in the same week can swap order from year to year. Both
shapes came out of fuzzing, neither out of reading it, so typeAt now
defers to spanAt rather than growing a guard for each case.

TimeZone.offsetAt              33 -> 71 ns/op
TimeZone.offsetAt (posix)      47 -> 127 ns/op
TimeZone.atTimestamp           62 -> 104 ns/op
TimeZone.resolve               73 -> 77 ns/op

Two things are behind it. spanAt computes six switches where typeAt
computed two, each one a weekday calculation and a day-number conversion.
And Date.toDaysSinceStartOfEra now does its arithmetic in the wider type,
which it has to: the old one overflowed an i32 from about year 5.9 million.

Carrying each switch with what it opens, rather than deriving that again
from the answer, already took some of it back. What is left, in the order I
would try it:

Compute the neighbouring years lazily. The instant's own year needs two
switches; the year before is only needed when the instant sits before
both of them, and the year after only when it sits after both. That is
two calculations in the middle of a span and four near its ends, rather
than six always.
Narrow the calendar arithmetic again where it is provably safe. Only
the year shift at the start and the era multiplication at the end need
the wider type; year_of_era, day_of_year and day_of_era are all
small and could stay 32-bit.
Reconsider whether spanAt needs a sort at all. Six switches arrive in
two interleaved ascending runs, so a merge would do.

Whatever comes of it, the fuzz targets in src/fuzz.zig are what say it is
still right: zig build test -Dfuzz-iterations=500000 exercises the rules
that broke the old shortcut.

Fixing a correctness bug in 773f3a1 made the POSIX rule path a lot slower, and the speed is worth getting back. `posixtz.typeAt` used to search one year rather than three, which was about a quarter quicker, and it was wrong: a switch time may be up to 167 hours either side of its day and spill into a neighbouring year, and two switches landing in the same week can swap order from year to year. Both shapes came out of fuzzing, neither out of reading it, so `typeAt` now defers to `spanAt` rather than growing a guard for each case. TimeZone.offsetAt 33 -> 71 ns/op TimeZone.offsetAt (posix) 47 -> 127 ns/op TimeZone.atTimestamp 62 -> 104 ns/op TimeZone.resolve 73 -> 77 ns/op Two things are behind it. `spanAt` computes six switches where `typeAt` computed two, each one a weekday calculation and a day-number conversion. And `Date.toDaysSinceStartOfEra` now does its arithmetic in the wider type, which it has to: the old one overflowed an i32 from about year 5.9 million. Carrying each switch with what it opens, rather than deriving that again from the answer, already took some of it back. What is left, in the order I would try it: 1. Compute the neighbouring years lazily. The instant's own year needs two switches; the year before is only needed when the instant sits before both of them, and the year after only when it sits after both. That is two calculations in the middle of a span and four near its ends, rather than six always. 2. Narrow the calendar arithmetic again where it is provably safe. Only the year shift at the start and the era multiplication at the end need the wider type; `year_of_era`, `day_of_year` and `day_of_era` are all small and could stay 32-bit. 3. Reconsider whether `spanAt` needs a sort at all. Six switches arrive in two interleaved ascending runs, so a merge would do. Whatever comes of it, the fuzz targets in `src/fuzz.zig` are what say it is still right: `zig build test -Dfuzz-iterations=500000` exercises the rules that broke the old shortcut.

jeff referenced this issue from a commit

2026-08-31 15:32:34 -05:00

recover the speed a correct typeAt cost

jeff closed this issue

2026-08-31 15:32:34 -05:00

jeff commented

2026-08-31 15:33:32 -05:00

Author

Owner

Done in 85e1f61.

                    was    now    before the correctness fix
offsetAt             70     34     33
offsetAt (posix)    125     51     47
resolve              76     40     73
atTimestamp         104     68     62

resolve ends up well ahead of where it started; atTimestamp is the
one still short, by about 8%.

Three things, roughly the plan in the issue:

Every switch is now arithmetic on a day number. Rule.dayNumber takes
the year's first of January and returns the day the rule picks out, so
placing a switch no longer converts a date, and the three years share
one conversion -- the neighbours are that day stepped by a year's
length.
Date.yearAndFirstDay is that one conversion: civil-from-days stopped
short of the month and day, which were only being added back up again
to recover the first of January. This was the largest single win.
Neighbouring years are computed lazily, and the test for laziness is
proven rather than assumed. When the year's own two switches are more
than ten days inside it, no switch of a neighbouring year can fall
between them, since a switch time is at most 167 hours off its day and
an offset at most 25 hours. An instant between them needs no neighbour;
one outside them needs only the side it fell off of. So the switch set
is two, four or six rather than always six.

The sort is gone as well -- one pass for the nearest switch either side.

The reasoning in (3) is the part that could be wrong the way the original
typeAt was wrong, so spanAtScanning keeps the version that reasons
about nothing and evaluates all three years, and a test holds spanAt
against it over every shape of rule this file, its tests and the fuzzer's
seeds have thought of, swept second by second through the switches and the
turns of the year. Each of the four claims the shortcut rests on was
reintroduced as a bug and the test caught all four. The ten day margin is
covered by a rule whose switch lands on the first of January in one year
and the December before it in the next, which a margin of zero gets wrong.

Verified with the three oracles, 1.8M mutated inputs across six seeds, and
the debug, ReleaseSafe, ReleaseFast, -Dembed-tzdata and
-Dno-system-tzdata builds.

Done in 85e1f61. was now before the correctness fix offsetAt 70 34 33 offsetAt (posix) 125 51 47 resolve 76 40 73 atTimestamp 104 68 62 `resolve` ends up well ahead of where it started; `atTimestamp` is the one still short, by about 8%. Three things, roughly the plan in the issue: 1. Every switch is now arithmetic on a day number. `Rule.dayNumber` takes the year's first of January and returns the day the rule picks out, so placing a switch no longer converts a date, and the three years share one conversion -- the neighbours are that day stepped by a year's length. 2. `Date.yearAndFirstDay` is that one conversion: civil-from-days stopped short of the month and day, which were only being added back up again to recover the first of January. This was the largest single win. 3. Neighbouring years are computed lazily, and the test for laziness is proven rather than assumed. When the year's own two switches are more than ten days inside it, no switch of a neighbouring year can fall between them, since a switch time is at most 167 hours off its day and an offset at most 25 hours. An instant between them needs no neighbour; one outside them needs only the side it fell off of. So the switch set is two, four or six rather than always six. The sort is gone as well -- one pass for the nearest switch either side. The reasoning in (3) is the part that could be wrong the way the original `typeAt` was wrong, so `spanAtScanning` keeps the version that reasons about nothing and evaluates all three years, and a test holds `spanAt` against it over every shape of rule this file, its tests and the fuzzer's seeds have thought of, swept second by second through the switches and the turns of the year. Each of the four claims the shortcut rests on was reintroduced as a bug and the test caught all four. The ten day margin is covered by a rule whose switch lands on the first of January in one year and the December before it in the next, which a margin of zero gets wrong. Verified with the three oracles, 1.8M mutated inputs across six seeds, and the debug, ReleaseSafe, ReleaseFast, `-Dembed-tzdata` and `-Dno-system-tzdata` builds.

No labels

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

jeff/zig-datetime#6

No description provided.

Rows
Columns