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

未關閉
  • 哪裡不對？
#161,746 3 則留言 1 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
4/5
預估耗時
3-5 天
新手友好度
25/100
Issue 類型
功能
描述清晰度
描述清楚
活躍度
停滯
技術堆疊
c, python
領域
backend

研究方向

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.

由索引模型根據 Issue 內容生成。

描述

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
主要語言
Python
星號
78.2k
分支
36.6k
平均合併
19 小時 57 分鐘
30 天內合併 PR
630

環境準備

在 Codespaces 中開啟

在瀏覽器裡用你自己的 GitHub 帳號啟動這個專案的開發容器。

從這裡開始

  1. 先讀完整個 Issue，再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫，在一個分支上完成修改。
  4. 送出 Pull Request，並在描述裡引用這個 Issue 編號。

python/cpython 的其他 Issue

查看 python/cpython 的全部 Issue

相似的 Issue

更多 Python Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。