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

Offen
  • Stimmt etwas nicht?
#161,746 3 Kommentare 1 Reaktion 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Anfängerfreundlichkeit
25/100
Issue-Typ
Feature
Klarheit
Klar beschrieben
Aktivitätsstatus
Veraltet
Tech-Stack
c, python
Bereich
backend

Rechercherichtung

Read ord_to_ymd() in Modules/_datetimemodule.c and _ord2ymd() in Lib/_pydatetime.py, then compare their current logic with the proposed Figure 12 algorithm. Check the datetime and calendar test suites and the month-boundary tests described in the issue. Done means both implementations preserve ordinal conversion results and error behavior while passing the relevant tests; the linked PR indicates work is already underway.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

extension-modules performance stdlib type-feature
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
  • gh-161747
Vorherrschende Sprache
Python
Sterne
78.2k
Forks
36.6k
Ø Merge
19 Std. 57 Min.
Gemergte PRs (30 T.)
630

Entwicklungsumgebung

In Codespaces öffnen

Startet den Dev-Container des Projekts im Browser, mit Ihrem eigenen GitHub-Konto.

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus python/cpython

Alle Issues in python/cpython

Ähnliche Issues

Weitere Issues zu Python

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.