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

オープン
  • 何か問題がありますか？
#161,746 コメント 3 件 リアクション 1 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
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分
マージ済み PR（30日）
630

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

python/cpython のほかの issue

python/cpython の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。