csv.Sniffer.sniff() takes quadratic time on long runs of spaces
維護者通常 1 天內回覆
還沒有人認領這個 Issue。
評估
- 難度
- 2/5
- 預估耗時
- 1-3 小時
- 新手友好度
- 35/100
- Issue 類型
- 缺陷
- 描述清晰度
- 描述清楚
- 活躍度
- 活躍
- 技術堆疊
- python
- 領域
- performance
研究方向
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.
由索引模型根據 Issue 內容生成。
描述
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
- 主要語言
- Python
- 星號
- 77.7k
- 分支
- 38.3k
- 平均合併
- 14 小時 29 分鐘
- 30 天內合併 PR
- 699
環境準備
在瀏覽器裡用你自己的 GitHub 帳號啟動這個專案的開發容器。
- 沒有 Dockerfile 或 Docker Compose 檔案
- 有 Pull Request 範本
- 閱讀貢獻指南
從這裡開始
- 先讀完整個 Issue，再讀專案的貢獻指南。
- 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
- Fork 儲存庫，在一個分支上完成修改。
- 送出 Pull Request，並在描述裡引用這個 Issue 編號。
python/cpython 的其他 Issue
-
topic-socket type-bug
難度 2/5 1-3 小時 新手友好度 72/100
python/cpython#160561 · 7 則留言 ·
維護者通常 1 天內回覆
-
tests topic-profiling type-bug
難度 2/5 1-3 小時 新手友好度 78/100
python/cpython#160334 · 1 則留言 ·
維護者通常 1 天內回覆
-
extension-modules type-bug
難度 2/5 1-3 小時 新手友好度 84/100
維護者通常 1 天內回覆
-
interpreter-core type-feature
難度 1/5 1 小時以內 新手友好度 78/100
python/cpython#160109 · 1 則留言 ·
維護者通常 1 天內回覆
-
extension-modules type-bug
難度 2/5 1-3 小時 新手友好度 72/100
python/cpython#160001 · 3 則留言 ·
維護者通常 1 天內回覆
相似的 Issue
-
難度 2/5 1-3 小時 新手友好度 68/100
nansencenter/geodataset#39 ·
-
bug
難度 2/5 1-3 小時 新手友好度 76/100
awslabs/visual-asset-management-system#804 ·
維護者通常 1 天內回覆
-
follow-up
難度 2/5 1-3 小時 新手友好度 65/100
維護者通常 1 天內回覆
-
難度 2/5 1-3 小時 新手友好度 68/100
維護者通常 1 天內回覆
-
link-rot
難度 1/5 1 小時以內 新手友好度 67/100