GeezerVison is showing github.com — Use the Neri–Schneider algorithm for ordinal-to-date conversion in datetime · Issue #161746 · python/cpython
Use the Neri–Schneider algorithm for ordinal-to-date conversion in datetime #161746DescriptionProposal
ord_to_ymd() in Modules/_datetimemodule.c and _ord2ymd() in Lib/_pydatetime.py
convert a proleptic Gregorian ordinal to (year, month, day). They still use the
algorithm from 2002: four divisions by the 400/100/4/1-year cycle lengths, a
special case for December 31 at the end of a 4- or 400-year cycle, and a month
estimate that is "either exact or one too large" and is corrected afterwards
(for about 24% of dates).
Neri and Schneider, "Euclidean affine functions and their application to
calendar algorithms" (Softw Pract Exper. 2023;53(4):937–970,
https://arxiv.org/abs/2102.06959) give an algorithm with no lookup tables and
no estimate-and-correct step. GCC's libstdc++, the Linux kernel, .NET and Go
already use it. I propose replacing both functions with their Figure 12.
The conversion is used by date.fromordinal(), date.fromisocalendar(),
fromisoformat() with ISO week dates, strptime() with %j or week
directives, and date/datetime ± timedelta when the result leaves the
current month by more than one day.
Verification
- Same results as
main for all 3,652,059 ordinals (0001-01-01 … 9999-12-31):
SHA-256 over every date.fromordinal() result, plus fromisocalendar() and
date + timedelta, for both the C and the pure-Python implementations.
- C: same results for every positive
int ordinal (1 … 2**31-1), including
the error messages past 9999-12-31; checked with gcc 13 and clang.
- Pure Python: same results for 2.3 million other integers, including negative
and huge ones.
- test_datetime, test_calendar, test_strptime, test_time, test_zoneinfo,
test_plistlib and test_xmlrpc pass. The PR adds a test for the first and
last days of every month in years at the ends of the 4-, 100- and 400-year
cycles.
Benchmarks
pyperf, x86-64 VM, gcc 13.3, -O3, no PGO; µs per 1000 operations:
| Benchmark |
main |
patched |
Speedup |
date.fromordinal, random dates |
35.6 |
25.3 |
1.40x |
date + timedelta(days=40) |
42.9 |
35.7 |
1.20x |
date.fromisocalendar |
83.5 |
71.0 |
1.18x |
datetime + timedelta(days=40) |
37.9 |
34.1 |
1.11x |
date.fromordinal, consecutive dates |
26.3 |
23.8 |
1.10x |
date + timedelta(days=1), 1000 steps |
32.8 |
31.8 |
1.03x |
The C function itself takes 3-4 ns per call instead of 15-16 ns on random
dates (gcc 13 and clang, -O3). The pure-Python date.fromordinal() is about
1.3x faster.
With a PGO build (--enable-optimizations, gcc 13.3) of main (e3262d9) and of
the patch, 1,000,000 operations, best of 7, builds alternated:
| Operation |
main |
patched |
Speedup |
date.fromordinal, random dates |
62.6 ms |
45.9 ms |
1.36x |
date + timedelta(days=90) |
69.0 ms |
60.8 ms |
1.13x |
date.fromisoformat('2024-W07-1') |
88.6 ms |
77.8 ms |
1.14x |
date + timedelta(days=10) |
53.0 ms |
52.5 ms |
1.01x |
pyperformance 1.14.0 (--fast, same two PGO builds, 119 benchmarks in common):
geometric mean 1.00x. No pyperformance benchmark exercises this code path, so
no change is expected there; the differences per benchmark are noise.
Other platforms and checks
- 32-bit x86 (
gcc -m32): full CPython build; the seven test suites above
pass, the all-dates digest is identical, and the C function matches the old
one for every positive int.
- AArch64 (clang cross build, run under QEMU): the C function matches the old
one for every positive int.
- UBSan + ASan (gcc): no reports over every positive
int.
- No warnings with
-Wall -Wextra -Wpedantic -Wconversion -Wsign-conversion
(gcc, 64- and 32-bit) or clang -Weverything on the new function.
- Full test suite (
./python -m test -j2): 52,706 tests; the only failures
are test_socket and test_urllib, which fail the same way on unpatched main
in my sandbox (no network).
- Not tested locally: Windows/MSVC and macOS (left to CI).
I used an AI assistant
(Claude) to research the algorithm and prepare the patch; I reviewed the change
and its verification myself and can explain every line.
Linked PRs
Reacted by Gregory P. Smith Activitypicnixz commented on Nov 10, 2026
pyperf, x86-64 VM, gcc 13.3, -O3, no PGO; µs per 1000 operations:
Can you (1) show the benchmark script (2) clearly say whether we were using the C implementation or not and the numbers for both implementations? mazalovmx commented on Nov 10, 2026 Thanks for the questions!
(2) The table in the issue measured the C implementation (_datetime, the one import datetime gives you). I've now re-measured both implementations separately with the script below, on main (e891a91) and on this PR (e2feb05), from the same two builds.
Setup: x86-64, Debian trixie in Docker on WSL2, gcc 14.2.0, default ./configure (-O3, no PGO), pyperf 2.11.0 with default settings (20 processes). Each value is the time for 1000 operations. This VM is fairly noisy (std dev around 5–15%), so small differences are not significant; pyperf hides those.
C implementation (_datetime)
| Benchmark |
main |
PR |
|
date.fromordinal, random dates |
72.1 µs |
55.8 µs |
1.29x faster |
datetime + timedelta(days=40) |
88.7 µs |
71.5 µs |
1.24x faster |
date + timedelta(days=40) |
91.9 µs |
75.8 µs |
1.21x faster |
date.fromisocalendar |
162 µs |
147 µs |
1.10x faster |
date.fromordinal, consecutive dates |
62.1 µs |
57.4 µs |
1.08x faster |
date + timedelta(days=1), 1000 steps |
72.4 µs |
75.7 µs |
not significant |
| Geometric mean |
|
|
1.14x faster |
Pure-Python implementation (_pydatetime)
| Benchmark |
main |
PR |
|
date.fromordinal, random dates |
2.56 ms |
1.87 ms |
1.37x faster |
date.fromordinal, consecutive dates |
2.42 ms |
1.80 ms |
1.35x faster |
date.fromisocalendar |
4.04 ms |
3.34 ms |
1.21x faster |
date + timedelta(days=1), 1000 steps |
4.21 ms |
3.49 ms |
1.21x faster |
date + timedelta(days=40) |
4.24 ms |
3.59 ms |
1.18x faster |
datetime + timedelta(days=40) |
21.7 ms |
19.7 ms |
1.10x faster |
| Geometric mean |
|
|
1.23x faster |
(The pure-Python date + timedelta(days=1) gains because _pydatetime always goes through _ord2ymd() when adding a timedelta; the C code skips ord_to_ymd() when the result stays in the same month or leaves it by only one day, so it doesn't.)
(1) The script; run it with each build as ./python bench_ordinal.py --impl c -o c.json and --impl py -o py.json, then python -m pyperf compare_to main-c.json pr-c.json --table:
bench_ordinal.py
"""Benchmark the ordinal -> (year, month, day) conversion in datetime.
Usage:
python bench_ordinal.py --impl c -o c.json
python bench_ordinal.py --impl py -o py.json
--impl c benchmarks the C accelerator (_datetime),
--impl py benchmarks the pure-Python implementation (_pydatetime).
Each benchmark value is the time for 1000 operations.
"""
import random
import pyperf
N = 1000
def load(impl):
if impl == "c":
import _datetime as mod
else:
import _pydatetime as mod
# Make sure we really got the implementation we asked for.
# (_pydatetime sets __name__ = "datetime", so look at the spec instead.)
want = "_pydatetime" if impl == "py" else "_datetime"
assert mod.__spec__.name == want, mod.__spec__.name
return mod
def make_benchmarks(mod):
date, datetime, timedelta = mod.date, mod.datetime, mod.timedelta
rng = random.Random(12345)
max_ord = date.max.toordinal()
# Leave room so that d + 40 days stays in range.
rand_ords = [rng.randint(1, max_ord - 100) for _ in range(N)]
rand_dates = [date.fromordinal(o) for o in rand_ords]
rand_dts = [datetime(d.year, d.month, d.day, 12, 30) for d in rand_dates]
rand_iso = [d.isocalendar() for d in rand_dates]
consec_ords = list(range(738000, 738000 + N))
start = date(2024, 1, 1)
td1, td40 = timedelta(days=1), timedelta(days=40)
def fromordinal_random(loops):
fromordinal = date.fromordinal
t0 = pyperf.perf_counter()
for _ in range(loops):
for o in rand_ords:
fromordinal(o)
return pyperf.perf_counter() - t0
def fromordinal_consecutive(loops):
fromordinal = date.fromordinal
t0 = pyperf.perf_counter()
for _ in range(loops):
for o in consec_ords:
fromordinal(o)
return pyperf.perf_counter() - t0
def date_add_40(loops):
t0 = pyperf.perf_counter()
for _ in range(loops):
for d in rand_dates:
d + td40
return pyperf.perf_counter() - t0
def datetime_add_40(loops):
t0 = pyperf.perf_counter()
for _ in range(loops):
for d in rand_dts:
d + td40
return pyperf.perf_counter() - t0
def fromisocalendar_random(loops):
fromisocalendar = date.fromisocalendar
t0 = pyperf.perf_counter()
for _ in range(loops):
for y, w, wd in rand_iso:
fromisocalendar(y, w, wd)
return pyperf.perf_counter() - t0
def date_add_1_steps(loops):
t0 = pyperf.perf_counter()
for _ in range(loops):
d = start
for _ in range(N):
d = d + td1
return pyperf.perf_counter() - t0
return [
("date.fromordinal, random dates", fromordinal_random),
("date + timedelta(days=40)", date_add_40),
("date.fromisocalendar", fromisocalendar_random),
("datetime + timedelta(days=40)", datetime_add_40),
("date.fromordinal, consecutive dates", fromordinal_consecutive),
("date + timedelta(days=1), 1000 steps", date_add_1_steps),
]
def add_cmdline_args(cmd, args):
cmd.extend(("--impl", args.impl))
def main():
runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)
runner.argparser.add_argument("--impl", choices=("c", "py"), required=True)
args = runner.parse_args()
mod = load(args.impl)
runner.metadata["datetime_impl"] = mod.__spec__.name
for name, func in make_benchmarks(mod):
runner.bench_time_func(f"[{args.impl}] {name}", func)
if __name__ == "__main__":
main() StanFromIreland commented on Nov 10, 2026 Generally, I think I like the algorithm (regardless of the little performance gain). It's a bit simpler than our current method (written by Tim twenty years ago).
CC @tim-one
MetadataMetadataStatusShow more project fields
DevelopmentNo branches or pull requestsIssue actions
|