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

Aberta
  • Algo errado?
#161,746 3 comentários 1 reação 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 1 dia

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
25/100
Tipo de issue
Funcionalidade
Clareza
Claramente especificada
Status de atividade
Estagnada
Stack de tecnologia
c, python
Domínio
backend

Direção de pesquisa

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.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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
Linguagem predominante
Python
Estrelas
78.2k
Forks
36.6k
Merge médio
19h 57min
PRs com merge (30d)
630

Preparar o ambiente

Abrir no Codespaces

Inicia o contêiner de desenvolvimento do projeto no navegador, com a sua própria conta do GitHub.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de python/cpython

Todas as issues de python/cpython

Issues semelhantes

Mais issues de Python

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.