Skip to content

Use the Neri–Schneider algorithm for ordinal-to-date conversion in datetime #161746

Open

Description

@mazalovmx

Proposal

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

Activity

  1. added
    type-featureA feature request or enhancement
    performancePerformance or resource usage
    stdlibStandard Library Python modules in the Lib/ directory
    on Nov 10, 2026
  2. picnixz commented on Nov 10, 2026

    @picnixz
    Member

    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?

  3. mazalovmx commented on Nov 10, 2026

    @mazalovmx
    Author

    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()
  4. StanFromIreland commented on Nov 10, 2026

    @StanFromIreland
    Member

    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

  5. added 2 commits that reference this issue on Nov 15, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    extension-modulesC modules in the Modules dirperformancePerformance or resource usagestdlibStandard Library Python modules in the Lib/ directorytype-featureA feature request or enhancement

    Projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions