Hacktoberfest 2026: die Issues, die Maintainer für den Oktober markiert haben – offen und einsteigerfreundlich. Hacktoberfest-Issues durchsuchen

csv.Sniffer.sniff() takes quadratic time on long runs of spaces

Offen
  • Stimmt etwas nicht?
#160,556 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
2/5
Geschätzter Aufwand
1-3 Stunden
Anfängerfreundlichkeit
35/100
Issue-Typ
Bug
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
python
Bereich
performance

Rechercherichtung

Read Lib/csv.py and inspect the regex search in Sniffer._split_dormant() described in the issue. Reproduce the slowdown with the supplied timing sample, then check that the proposed lookbehind preserves matching results while avoiding repeated attempts within a space run. Done means the long-run timings no longer grow quadratically and the existing csv tests pass.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

stdlib type-bug

Bug report

Bug description:

On main, csv.Sniffer().sniff() takes quadratic time when the sample contains a quote character and a long run of spaces that is not followed by one:

import csv, time

for n in (8000, 16000, 32000, 64000):
    sample = 'a' + ' ' * n + 'x"\n'
    t = time.perf_counter()
    try:
        csv.Sniffer().sniff(sample)
    except csv.Error:
        pass
    print(n, round(time.perf_counter() - t, 4))

Seconds, on macOS 27.0.1 (Apple M3):

n main (debug build) main + fix (debug build) 3.15.0 (release, for comparison)
8000 0.050 0.011 0.010
16000 0.153 0.002 0.004
32000 0.598 0.004 0.007
64000 2.373 0.008 0.015

The sample ('a,b' + ' ' * 100_000 + 'c"\n') * 4 takes 23.2 s on main and 0.06 s with the fix.

The cause is the regex in Sniffer._split_dormant() (Lib/csv.py):

m = re.compile(fr'(?:^|([\r\n{cls}]))'
               fr' *{quotechar}').search(part, pos)

The space is a delimiter candidate whenever the sample contains one, so it is in cls. The search then tries a match at every space of the run: [...] matches that space, * consumes the rest of the run, and the match fails on the next character. A run of n spaces costs O(n**2).

A match that starts at a space preceded by a space is never the leftmost one: a match with the same group and the same end also starts at the beginning of the run. Adding the lookbehind (?<! ) after the group skips those positions without changing any result.

This was introduced in gh-83273 (25fea6d64e1) and is in 3.16.0a1. 3.15 and older are not affected.

CPython versions tested on:

3.15, CPython main branch

Operating systems tested on:

macOS

Linked PRs
  • gh-160557
Vorherrschende Sprache
Python
Sterne
77.7k
Forks
38.3k
Ø Merge
14 Std. 29 Min.
Gemergte PRs (30 T.)
699

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.