Title: Add a C accelerator for difflib.SequenceMatcher · Issue #150184 · python/cpython · GitHub
Open Graph Title: Add a C accelerator for difflib.SequenceMatcher · Issue #150184 · python/cpython
X Title: Add a C accelerator for difflib.SequenceMatcher · Issue #150184 · python/cpython
Description: Feature or enhancement Proposal: Disclaimer: I guided Claude Code to generate the code, the benchmarks and the summary below. I felt it's safe to use AI for this issue because it is purely a logical module port and does not touch any of ...
Open Graph Description: Feature or enhancement Proposal: Disclaimer: I guided Claude Code to generate the code, the benchmarks and the summary below. I felt it's safe to use AI for this issue because it is purely a logica...
X Description: Feature or enhancement Proposal: Disclaimer: I guided Claude Code to generate the code, the benchmarks and the summary below. I felt it's safe to use AI for this issue because it is purely a lo...
Opengraph URL: https://github.com/python/cpython/issues/150184
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Add a C accelerator for difflib.SequenceMatcher","articleBody":"# Feature or enhancement\n\n### Proposal:\n\nDisclaimer: I guided Claude Code to generate the code, the benchmarks and the summary below. I felt it's safe to use AI for this issue because it is purely a logical module port and does not touch any of the Python core.\n\n# Add a C accelerator for `difflib.SequenceMatcher`\n\n## Enhancement\n\nAdd a C accelerator module `_difflib` for `difflib.SequenceMatcher`, modeled after the `decimal`/`_pydecimal`/`_decimal` pattern. Output is bit-identical to the existing pure-Python implementation (including the documented leftmost-maximal-match tie-break); the win comes from constant-factor optimizations (the algorithm is still Ratcliff-Obershelp).\n\nAcross six realistic workloads, the accelerator is **5–15× faster than pure Python** on CPython `main` (3.16-dev), and faster than both existing PyPI accelerators (`cdifflib`, `cydifflib`) on every workload tested.\n\n## Preserving the pure-Python implementation\n\nThe pure-Python `SequenceMatcher` is preserved verbatim as a reference/fallback. The layout mirrors `decimal`/`datetime`/`pickle`:\n\n- `Lib/_pydifflib.py` — the existing pure-Python implementation, no behavior change. Self-contained; alternative Python implementations can use it directly.\n- `Lib/difflib.py` — a thin shim:\n - `from _pydifflib import *` brings in everything (`Differ`, `HtmlDiff`, `unified_diff`, `ndiff`, `get_close_matches`, …)\n - re-exports a handful of private helpers (`_calculate_ratio`, `_mdiff`, `_format_range_unified`, `_format_range_context`) that existing tests reference\n - `lazy from _pydifflib import can_colorize, get_theme` preserves the existing lazy-import contract that `LazyImportTest` enforces while keeping the names visible as runtime attributes (which `test_pyclbr.test_easy` checks)\n - `try: from _difflib import SequenceMatcher` + subclasses it to inherit the slow-path methods (`quick_ratio`, `real_quick_ratio`, `get_grouped_opcodes`) from the pure-Python class\n - rebinds `_pydifflib.SequenceMatcher` to the C-accelerated subclass after defining it, so the helper functions in `_pydifflib` (which look up `SequenceMatcher` in their own module globals) transparently pick up the speedup. Without this rebind, `difflib.unified_diff` and friends would see zero benefit from the accelerator.\n\nWhen `_difflib` is unavailable, the shim is a no-op and `SequenceMatcher` stays the pure-Python class.\n\n## Optimization phases\n\nEach phase preserves the algorithm; each row shows what changed and why.\n\n| phase | what changed | why |\n|---|---|---|\n| 1 | C port of `find_longest_match`; `j2len` replaced with paired int arrays + generation counter (no per-row clear) | Eliminates per-row dict allocation + per-`j` dict probe in the inner DP loop. |\n| 2 | C port of `chain_b`; type-specialized iteration of `b` for `str`/`list`/`tuple`/`bytes` | `chain_b` became >50% of remaining cost after phase 1; ~25k `setdefault`+`append` in Python. |\n| 3 | Full Ratcliff-Obershelp recursion in C; DP and extension passes operate on `int32` label arrays (`a_lbl`, `a_dp`, `b_lbl`, `junk_mask`) | Hundreds of FLM calls per `ratio()` each cross the Python/C boundary; extension passes did `PyObject_RichCompareBool` per element. |\n| 4 | Codepoint-keyed `cp_full[]`/`cp_dp[]` arrays for `str` `b`; `str` `a` fast-path reads codepoint and indexes the array | For `str` inputs we paid `PyUnicode_FromOrdinal` + dict-probe per element on both `a` and `b`. |\n| 5 | Bytes fast-path (cp arrays of size 256), persistent DP scratch (no per-call `alloca`/`memset`), skip max-cp scan for UCS1 strings | Bytes paid `PyLong_FromLong` per element under autojunk; pure-Python's per-int allocator costs dominated for the bytes workload. |\n\nPhase 1 is reproduced by monkey-patching `_pydifflib.SequenceMatcher.find_longest_match` with an early C port that still talks to the Python `b2j` dict; phase 2 also swaps in a C `__chain_b`; phase 3 disables the codepoint-keyed lookup tables on top of the current code; phase 4 disables only the phase-5-specific changes (bytes fast-path and the UCS1 max-codepoint shortcut). All five measurements run on the same release-mode in-tree CPython `main` build, with pyperf (20 processes × 3 values per workload, default warmup, system tuned via `pyperf system tune`). All times are pyperf mean ± stddev for `SequenceMatcher(...).ratio() + .get_opcodes()`:\n\n| case | pure-Py | phase 1 | phase 2 | phase 3 | phase 4 | phase 5 (final) |\n|---|---|---|---|---|---|---|\n| str_2k_similar | 908 ± 24 us | 391 ± 12 us | 268 ± 12 us | 228 ± 6 us | 132 ± 2 us | 133 ± 8 us |\n| str_8k_similar | 3.73 ± 0.08 ms | 1.61 ± 0.05 ms | 1.12 ± 0.06 ms | 988 ± 38 us | 619 ± 23 us | 628 ± 18 us |\n| lines_difflib | 5.64 ± 0.04 ms | 1.29 ± 0.02 ms | 1.25 ± 0.01 ms | 1.03 ± 0.01 ms | 1.09 ± 0.01 ms | 1.09 ± 0.01 ms |\n| ints_3k | 16.1 ± 0.0 ms | 3.31 ± 0.01 ms | 3.12 ± 0.02 ms | 2.22 ± 0.01 ms | 2.18 ± 0.02 ms | 2.18 ± 0.02 ms |\n| lines_big | 25.0 ± 0.1 ms | 4.77 ± 0.03 ms | 4.46 ± 0.05 ms | 2.87 ± 0.03 ms | 2.84 ± 0.01 ms | 2.84 ± 0.02 ms |\n| bytes_8k | 213 ± 0 ms | 23.7 ± 0.2 ms | 23.2 ± 0.2 ms | 15.0 ± 0.1 ms | 14.8 ± 0.1 ms | 14.5 ± 0.1 ms |\n\nSpeedup over pure-Python (means only, derived from the row above):\n\n| case | phase 1 | phase 2 | phase 3 | phase 4 | phase 5 (final) |\n|---|---:|---:|---:|---:|---:|\n| str_2k_similar | 2.32× | 3.39× | 3.98× | 6.88× | 6.83× |\n| str_8k_similar | 2.32× | 3.33× | 3.78× | 6.03× | 5.94× |\n| lines_difflib | 4.37× | 4.51× | 5.48× | 5.17× | 5.17× |\n| ints_3k | 4.86× | 5.16× | 7.25× | 7.39× | 7.39× |\n| lines_big | 5.24× | 5.61× | 8.71× | 8.80× | 8.80× |\n| bytes_8k | 8.99× | 9.18× | 14.20× | 14.39× | 14.69× |\n\nReading the table: each phase adds an optimization that monotonically helps the workloads it targets. Phase 3 (label-array DP + recursion-in-C) is the single largest jump on int/line workloads; phase 4 (codepoint-keyed tables for `str`) drives the doubling on `str` workloads; phase 5 contributes a measurable but smaller bytes win, and on the other workloads it's at the noise floor (within ±0.5 σ of phase 4). The pyperf standard deviations are \u003c3% in every cell, so the small phase-4-vs-phase-5 swings on `str_2k`, `str_8k`, and `lines_difflib` are well inside measurement noise — not a regression.\n\n## Benchmark hardware and software\n\nAll numbers in this issue were collected on the same machine and software configuration:\n\n- **CPU**: Intel Xeon Silver 4410Y (Sapphire Rapids), 2 sockets × 12 cores × 2 threads = 48 hardware threads, 3.9 GHz max turbo (disabled for benchmarks).\n- **RAM**: 256 GB.\n- **OS**: Ubuntu 24.04.2 LTS, Linux 6.14.0.\n- **Compiler**: GCC 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04.1).\n- **System tuning**: `sudo pyperf system tune` (Turbo Boost disabled, `performance` CPU governor, ASLR off, IRQ affinity pinned).\n- **pyperf**: 2.10.0.\n- **Python**: CPython `main` at commit `5f4fbc10f68`, built `--enable-shared` release mode (no `--with-pydebug`), `-O3`. Python 3.12 numbers use the system Python 3.12.3 in a dedicated venv on the same host.\n\n## Benchmark workloads\n\nSix workloads, all comparing two sequences that are mostly identical with a small percentage of perturbations — the realistic case difflib is designed for:\n\n- **str_2k_similar / str_8k_similar** — two random lowercase-ASCII strings of 2,000 and 8,000 characters; about 5% of positions randomly substituted. Character-level diff; `b2j` keys are 1-char strings.\n- **lines_difflib** — `_pydifflib.py` as a list of ~2,100 lines vs the same list with every 50th line replaced by a comment. Line-level diff over Python source.\n- **lines_big** — the same file replicated ×3 (~6,300 lines), every 80th line perturbed. Larger line-level diff with line repetition.\n- **ints_3k** — list of 3,000 random ints in [0, 500] vs the same list with about 5% of positions randomly substituted. Tests the path where `b2j` keys are Python ints.\n- **bytes_8k** — `bytes` of 8,000 random bytes vs the same with about 5% mutated. Tests the bytes fast-path; pure-Python pays a `PyLong_FromLong` per element when building `b2j`.\n\nThe benchmark measures end-to-end `SequenceMatcher(None, a, b)` followed by `s.ratio()` and `s.get_opcodes()` with `autojunk` enabled (the default).\n\n## Ours vs the original pure-Python on CPython `main`\n\nMeasured on the in-tree CPython `main` (3.16-dev, release-mode, no `--with-pydebug`) where the patch lives, using pyperf (20 processes × 3 values per workload). Pure Python is `_pydifflib.SequenceMatcher` (the same code as the existing `difflib.SequenceMatcher`); the accelerated column is the C-backed `difflib.SequenceMatcher` after the shim picks up `_difflib`:\n\n| case | pure-Py (mean ± std) | accel (mean ± std) | speedup |\n|---|---:|---:|---:|\n| str_2k_similar | 908 ± 24 us | 133 ± 8 us | 6.83× |\n| str_8k_similar | 3.73 ± 0.08 ms | 628 ± 18 us | 5.94× |\n| lines_difflib | 5.64 ± 0.04 ms | 1.09 ± 0.01 ms | 5.17× |\n| ints_3k | 16.1 ± 0.0 ms | 2.18 ± 0.02 ms | 7.39× |\n| lines_big | 25.0 ± 0.1 ms | 2.84 ± 0.02 ms | 8.80× |\n| bytes_8k | 213 ± 0 ms | 14.5 ± 0.1 ms | 14.69× |\n\n\u003cdetails>\n\u003csummary>Bench script (pyperf, ours vs pure-Python on the in-tree CPython main build)\u003c/summary>\n\nThe script below picks the implementation via the `DIFFLIB_IMPL` env var, so the same script measures any combination of `py` (stdlib `difflib`), `pyours` (the pure-Python `_pydifflib`), `ours` (the in-tree `_difflib` C accelerator), `cdifflib`, or `cydifflib`. For the table above I ran it twice:\n\n```bash\n# Pure-Python reference (does not need the C accelerator installed).\nDIFFLIB_IMPL=pyours PYTHONPATH=/tmp ./python bench_pyperf.py \\\n -o results/main_pyours.json \\\n --inherit-environ=DIFFLIB_IMPL,PYTHONPATH\n\n# C accelerator (drops _difflib.cpython-*.so into /tmp).\nDIFFLIB_IMPL=ours PYTHONPATH=/tmp ./python bench_pyperf.py \\\n -o results/main_ours.json \\\n --inherit-environ=DIFFLIB_IMPL,PYTHONPATH\n\n# Statistical comparison via t-test on per-process means:\n./python -m pyperf compare_to results/main_pyours.json results/main_ours.json\n```\n\n```python\n\"\"\"pyperf benchmark of difflib.SequenceMatcher implementations.\n\nSelects the implementation via the DIFFLIB_IMPL environment variable\n(one of: py, pyours, ours, cdifflib, cydifflib). This avoids needing\ncustom argparse arguments that pyperf would have to propagate to\nworker processes.\n\"\"\"\n\nimport os\nimport random\nimport string\n\nimport pyperf\n\n\ndef make_inputs(pydifflib_path):\n cases = {}\n rng = random.Random(42)\n s1 = ''.join(rng.choices(string.ascii_lowercase, k=2000))\n s2 = list(s1)\n for _ in range(100):\n s2[rng.randrange(len(s2))] = rng.choice(string.ascii_lowercase)\n cases['str_2k_similar'] = (s1, ''.join(s2))\n\n s1 = ''.join(rng.choices(string.ascii_lowercase, k=8000))\n s2 = list(s1)\n for _ in range(400):\n s2[rng.randrange(len(s2))] = rng.choice(string.ascii_lowercase)\n cases['str_8k_similar'] = (s1, ''.join(s2))\n\n with open(pydifflib_path) as f:\n la = f.readlines()\n lb = la[:]\n for i in range(0, len(lb), 50):\n lb[i] = '# tweak\\n'\n cases['lines_difflib'] = (la, lb)\n\n rng = random.Random(7)\n la = [rng.randint(0, 500) for _ in range(3000)]\n lb = la[:]\n for _ in range(150):\n lb[rng.randrange(len(lb))] = rng.randint(0, 500)\n cases['ints_3k'] = (la, lb)\n\n with open(pydifflib_path) as f:\n la = f.readlines() * 3\n lb = la[:]\n for i in range(0, len(lb), 80):\n lb[i] = '# x\\n'\n cases['lines_big'] = (la, lb)\n\n rng = random.Random(99)\n ba = bytes(rng.choices(range(256), k=8000))\n bb = bytearray(ba)\n for _ in range(400):\n bb[rng.randrange(len(bb))] = rng.randrange(256)\n cases['bytes_8k'] = (ba, bytes(bb))\n return cases\n\n\ndef resolve_impl(name):\n if name == 'py':\n import difflib\n return difflib.SequenceMatcher\n if name == 'pyours':\n import _pydifflib\n return _pydifflib.SequenceMatcher\n if name == 'ours':\n import _difflib\n return _difflib.SequenceMatcher\n if name == 'cdifflib':\n import cdifflib\n return cdifflib.CSequenceMatcher\n if name == 'cydifflib':\n import cydifflib\n return cydifflib.SequenceMatcher\n raise ValueError(f\"unknown impl {name!r}\")\n\n\ndef make_workload(SM, a, b):\n def workload():\n s = SM(None, a, b)\n s.ratio()\n s.get_opcodes()\n return workload\n\n\ndef main():\n impl = os.environ['DIFFLIB_IMPL']\n pydifflib_path = os.environ.get(\n 'PYDIFFLIB_PATH', '/path/to/cpython/Lib/_pydifflib.py')\n\n SM = resolve_impl(impl)\n cases = make_inputs(pydifflib_path)\n\n runner = pyperf.Runner()\n runner.metadata['difflib_impl'] = impl\n runner.metadata['SM_class'] = f\"{SM.__module__}.{SM.__qualname__}\"\n\n for name, (a, b) in cases.items():\n runner.bench_func(name, make_workload(SM, a, b))\n\n\nif __name__ == '__main__':\n main()\n```\n\n\u003c/details>\n\n## Apples-to-apples comparison vs PyPI alternatives (CPython 3.12)\n\nTwo existing C accelerators on PyPI: `cdifflib` 1.2.9 (hand-written C) and `cydifflib` 1.2.0 (Cython-generated). The comparison is run on CPython **3.12** (not the in-tree 3.16-dev branch where the patch lives) because `cydifflib`'s wheel build is CMake-based and currently fails to configure against 3.16-dev — it cannot be tested on that runtime. To remove \"different Python version\" as a confound, I rebuilt the new accelerator against the system Python 3.12 headers and installed all four implementations (pure-Python, `cdifflib`, `cydifflib`, ours) into a single Python 3.12 venv so every column below shares the same interpreter, GC, and pure-Python baseline. All measurements use pyperf (20 processes × 3 values per workload, system tuned via `pyperf system tune`).\n\n**Wall time (pyperf mean ± stddev), all on Python 3.12:**\n\n| case | pure-Py | cdifflib 1.2.9 | cydifflib 1.2.0 | ours |\n|---|---:|---:|---:|---:|\n| str_2k_similar | 989 ± 21 us | 529 ± 13 us | 901 ± 14 us | 120 ± 4 us |\n| str_8k_similar | 3.86 ± 0.05 ms | 2.19 ± 0.07 ms | 33.5 ± 0.0 ms | 520 ± 25 us |\n| lines_difflib | 6.15 ± 0.08 ms | 2.74 ± 0.04 ms | 1.88 ± 0.03 ms | 1.08 ± 0.01 ms |\n| ints_3k | 16.5 ± 0.1 ms | 8.71 ± 0.13 ms | 4.31 ± 0.09 ms | 2.39 ± 0.01 ms |\n| lines_big | 25.8 ± 0.2 ms | 11.6 ± 0.1 ms | 21.2 ± 0.0 ms | 2.99 ± 0.04 ms |\n| bytes_8k | 205 ± 1 ms | 127 ± 1 ms | 60.8 ± 0.1 ms | 14.8 ± 0.1 ms |\n\n**Speedup over pure-Python (means only), all measured on Python 3.12:**\n\n| case | cdifflib 1.2.9 | cydifflib 1.2.0 | ours |\n|---|---:|---:|---:|\n| str_2k_similar | 1.87× | 1.10× | 8.24× |\n| str_8k_similar | 1.76× | 0.12× | 7.42× |\n| lines_difflib | 2.24× | 3.27× | 5.69× |\n| ints_3k | 1.89× | 3.83× | 6.90× |\n| lines_big | 2.22× | 1.22× | 8.63× |\n| bytes_8k | 1.61× | 3.37× | 13.85× |\n\n\u003cdetails>\n\u003csummary>Bench script (pyperf, 4-way comparison on CPython 3.12)\u003c/summary>\n\nSame `bench_pyperf.py` as above; in the 3.12 venv where all four implementations are importable, set `DIFFLIB_IMPL` to one of `py`, `cdifflib`, `cydifflib`, `ours` and run once per impl:\n\n```bash\nfor impl in py cdifflib cydifflib ours; do\n DIFFLIB_IMPL=$impl venv/bin/python bench_pyperf.py \\\n -o results/py312_$impl.json \\\n --inherit-environ=DIFFLIB_IMPL\ndone\n\n# Compare any two with a t-test on the per-process means:\nvenv/bin/python -m pyperf compare_to results/py312_py.json results/py312_ours.json\n```\n\n\u003c/details>\n\nObservations:\n\n- **`cydifflib` regresses on char-level diff**: `str_8k_similar` runs at 0.12× of pure Python (≈8× *slower*). Reproducible across pyperf processes (stddev = 0 ms), not a measurement artifact. Looks like per-element Cython wrapping overhead is bad when elements are single codepoints.\n- **`cdifflib` is consistent at ~1.6–2.2×**: a modest constant-factor win that targets `find_longest_match` and `get_matching_blocks` only, leaving `chain_b` in Python.\n- **Ours is the fastest of the three in all six workloads**, by 1.4× (lines_difflib, where cydifflib is also competitive) to 4× (str_8k_similar) to 9× (bytes_8k) over the next-fastest in each row.\n\n## What lets ours go further\n\n`cdifflib` and `cydifflib` both keep the existing data shape: `b2j` is a `dict[elt, list[int]]`, and the inner loop does `PyDict_GetItem` on Python-object keys per outer `i`. The biggest single change in this work is restructuring the state itself:\n\n1. Every distinct element of `b` is assigned a small integer label at `chain_b` time.\n2. Position-indexed `int32_t` arrays (`a_lbl`, `b_lbl`, `a_dp`, `junk_mask`) replace the per-position object lookups.\n3. The whole `get_matching_blocks` recursion (queue + sort + collapse) runs in C, with the DP loop and extension passes operating purely on those int32 arrays — no Python C-API calls in the hot path.\n4. For `str` and `bytes`, codepoint-keyed lookup tables (`cp_full[256]` for UCS1 / `cp_full[max+1]` for wider strings; `cp_full[256]` for bytes) replace the dict-probe entirely. This is what makes the bytes case 13× rather than ~3×.\n\nNeither `cdifflib` nor `cydifflib` does the integer-label transformation; that explains most of the remaining gap.\n\n## Comparison vs GNU `diff(1)` on line workloads\n\nGNU `diff` is a different program (and a different algorithm — Myers diff, O((n+m)D) where D is the edit distance, not Ratcliff-Obershelp); the comparison only makes sense on line-level inputs because GNU `diff` doesn't natively handle character, integer, or byte sequences. The GNU `diff` column includes its full real-world cost: process spawn + reading both files from disk + writing the unified diff to `/dev/null`. The Python columns measure the in-process work `difflib.unified_diff(a_lines, b_lines, lineterm='')` does (the same work `Tools/build/stable_abi.py`, doctest's failure output, and `unittest.assertMultiLineEqual` do under the hood). All numbers are pyperf mean ± stddev:\n\n| workload | GNU diff 3.10 (subprocess) | pure-Py difflib | ours (C accel) |\n|---|---:|---:|---:|\n| lines_difflib (~2,100 lines) | 1.48 ± 0.01 ms | 6.16 ± 0.03 ms | 1.14 ± 0.01 ms |\n| lines_big (~6,300 lines) | 2.50 ± 0.09 ms | 26.7 ± 0.2 ms | 2.46 ± 0.02 ms |\n| lines_huge (~32,000 lines, 5%) | 13.5 ± 0.2 ms | 280 ± 1 ms | 24.6 ± 0.2 ms |\n\nReading the table:\n\n- **Small/medium line diffs (≤ ~6k lines)**: ours is *competitive with or faster than* GNU `diff` end-to-end. GNU `diff`'s subprocess + file-IO floor (~1–2 ms) is the same order of magnitude as the actual diff work at this size, so the in-process Python+C path comes out ahead.\n- **Large line diffs (32k lines)**: GNU `diff` pulls ahead, ~1.8× faster. That's Myers diff's asymptotic edge over Ratcliff-Obershelp showing up at scale. Pure-Python `difflib` is **20× slower than GNU diff** here; ours closes most of that gap but not all of it.\n\n**Why the crossover, briefly**: GNU `diff` uses Myers diff — for \"mostly identical\" inputs, edit distance D is small so its O((n+m)D) behaves like O(n+m) — *linear* in n. Ratcliff-Obershelp is super-linear in expected case. Holding the perturbation rate constant, scaling n by 15× (2k → 32k lines) grows ours' time by ~22× and GNU diff's algorithm time by ~9×. Combined with GNU diff's fixed ~1 ms subprocess overhead, the crossover lands around **n ≈ 10–15k lines**.\n\nThis is well above the sizes CPython callers actually hit (doctest failures, `assertMultiLineEqual`, the 2,833-line stable-ABI manifest), so for real workloads we're in the \"GNU diff loses to us because of IO floor\" zone. The discussion thread linked at the top covers the asymptotic angle (suffix-automaton work for `autojunk=False`) — that's the orthogonal path that would close the remaining gap on >10k-line inputs.\n\n\u003cdetails>\n\u003csummary>Bench script (pyperf, GNU diff vs difflib.unified_diff)\u003c/summary>\n\nThe script selects the implementation via `DIFFLIB_IMPL` (`gnudiff`, `pyours`, or `ours`) so all three columns above share the same input generation and pyperf invocation pattern.\n\n```bash\nrm -f results/gnu_*.json\nfor impl in gnudiff pyours ours; do\n DIFFLIB_IMPL=$impl PYTHONPATH=/tmp ./python bench_gnudiff.py \\\n -o results/gnu_$impl.json \\\n --inherit-environ=DIFFLIB_IMPL,PYTHONPATH\ndone\n\n# Compare any two via t-test on the per-process means:\n./python -m pyperf compare_to results/gnu_pyours.json results/gnu_ours.json\n```\n\n```python\n\"\"\"Compare GNU diff(1) vs difflib.unified_diff on identical line inputs.\n\nGNU diff uses Myers diff, not Ratcliff-Obershelp -- the outputs are\nstructurally different, but the wall-time comparison is informative for\nthe line-level workloads (the only case GNU diff handles natively).\nChar-level / bytes / int sequences aren't included because GNU diff\ndoesn't have a meaningful native equivalent.\n\"\"\"\n\nimport os\nimport random\nimport subprocess\nimport tempfile\n\nimport pyperf\n\n\ndef make_inputs(pydifflib_path):\n cases = {}\n with open(pydifflib_path) as f:\n la = f.readlines()\n lb = la[:]\n for i in range(0, len(lb), 50):\n lb[i] = '# tweak\\n'\n cases['lines_difflib'] = (la, lb)\n\n with open(pydifflib_path) as f:\n la = f.readlines() * 3\n lb = la[:]\n for i in range(0, len(lb), 80):\n lb[i] = '# x\\n'\n cases['lines_big'] = (la, lb)\n\n # ~32k lines, ~5% perturbation\n with open(pydifflib_path) as f:\n la = f.readlines() * 15\n lb = la[:]\n rng = random.Random(123)\n for _ in range(len(lb) // 20):\n i = rng.randrange(len(lb))\n lb[i] = f\"# changed line {i}\\n\"\n cases['lines_huge'] = (la, lb)\n return cases\n\n\ndef make_temp_files(a_lines, b_lines):\n fa = tempfile.NamedTemporaryFile(mode='w', delete=False, suffix='.a')\n fa.writelines(a_lines); fa.close()\n fb = tempfile.NamedTemporaryFile(mode='w', delete=False, suffix='.b')\n fb.writelines(b_lines); fb.close()\n return fa.name, fb.name\n\n\ndef main():\n impl = os.environ['DIFFLIB_IMPL'] # gnudiff | pyours | ours\n pydifflib_path = os.environ.get(\n 'PYDIFFLIB_PATH', '/path/to/cpython/Lib/_pydifflib.py')\n cases = make_inputs(pydifflib_path)\n\n runner = pyperf.Runner()\n runner.metadata['impl'] = impl\n\n if impl == 'gnudiff':\n # Write inputs once; bench the subprocess invocation. This\n # deliberately includes process spawn + file IO + writing the\n # diff to /dev/null -- the real cost of using GNU diff.\n for name, (a, b) in cases.items():\n path_a, path_b = make_temp_files(a, b)\n def workload(_a=path_a, _b=path_b):\n # GNU diff exits 1 when files differ; that's success.\n subprocess.run(\n ['/usr/bin/diff', '-u', _a, _b],\n stdout=subprocess.DEVNULL,\n stderr=subprocess.DEVNULL,\n check=False,\n )\n runner.bench_func(name, workload)\n else:\n if impl == 'pyours':\n import _pydifflib as mod\n elif impl == 'ours':\n import difflib as mod # picks up _difflib via the shim\n else:\n raise SystemExit(f\"unknown impl {impl!r}\")\n unified_diff = mod.unified_diff\n for name, (a, b) in cases.items():\n def workload(_a=a, _b=b, _ud=unified_diff):\n # Materialize the generator to match the work GNU diff\n # does (it writes the whole diff out).\n list(_ud(_a, _b, lineterm=''))\n runner.bench_func(name, workload)\n\n\nif __name__ == '__main__':\n main()\n```\n\n\u003c/details>\n\n## Integration details\n\n- **Build**: `Modules/_difflibmodule.c` (heap type, per-interpreter GIL supported, `Py_mod_gil = Py_MOD_GIL_NOT_USED` for free-threading, `PyType_GetModuleByDef` for subclass-safe state lookup), wired via `PY_STDLIB_MOD_SIMPLE([_difflib])` in `configure.ac` and a one-line entry in `Modules/Setup.stdlib.in`. `configure` regenerated via the standard `Tools/build/regen-configure.sh` (autoconf 2.72 docker image); global string tables regenerated via `make regen-all`.\n- **Argument Clinic**: all seven methods (`__init__`, `set_seqs`, `set_seq1`, `set_seq2`, `find_longest_match`, `get_matching_blocks`, `get_opcodes`, `ratio`) use `/*[clinic input]` blocks; argument parsing is generated into `Modules/clinic/_difflibmodule.c.h`.\n- **Documentation**: an `impl-detail` block added to `Doc/library/difflib.rst` mentions the C accelerator, the `_pydifflib` reference, bit-identical output, and the typical 5–25× speedup range.\n- **Tests**: when the accelerator is present, `Lib/test/test_difflib.py` programmatically generates a `*_PurePython` variant of each existing TestCase that monkey-patches `difflib.SequenceMatcher` to `_pydifflib.SequenceMatcher` for the duration of the test (similar in spirit to `test_decimal`'s `C*` / `Py*` class pairs, but non-invasive — no test method changes). With the accelerator built, `test_difflib` runs 100 tests (61 C-path + 39 Py-path); without it, the 60 original tests run as before.\n- **Source annotations**: the C file uses `[phase N]` comments throughout to map sections of code to the optimization phases described above, so a reviewer can grep `[phase 4]` to see exactly which code was added for the codepoint-keyed lookup tables, etc.\n\nAll 3,611 tests pass across `test_difflib`, `test_pyclbr`, `test_doctest`, `test_unittest`, `test_argparse`, `test_traceback`.\n\n## Cost on real CPython workloads\n\nFor the CPython test suite as a whole, the impact is small — `assertEqual` only calls `ndiff` on failure, doctest only computes diffs on failure, `argparse`/`traceback`'s `get_close_matches` filters out 99% of pairs via `quick_ratio` before reaching `ratio()`. On the difflib-using test subset (~33s):\n\n| test | stock | accel | speedup |\n|---|---:|---:|---:|\n| test_difflib | 1.41s | 0.49s | 2.9× |\n| test_doctest | 3.55s | 3.29s | 1.1× |\n| test_genericalias | 0.40s | 0.34s | 1.2× |\n| (others within noise) | | | |\n\nWhere users feel it is during **development**: a failed `unittest.assertEqual` on a 2000-item list goes from 115 ms → 30 ms; doctest's `unified_diff` on a long mismatch goes from ~50 ms → ~4 ms; `Tools/build/stable_abi.py`'s ~2,800-line manifest diff goes from 43 ms → 4 ms (11×). Useful for iteration, not for green CI.\n\n## Previous discussion\n\n- [Algorithmic complexity of difflib](https://discuss.python.org/t/algorithmic-complexity-of-difflib/105844) — the suffix-automaton proposal ([#144132](https://github.com/python/cpython/issues/144132)). That work and this work are orthogonal: SAM addresses pathological / very-large-input asymptotic complexity; this addresses constant-factor cost on typical workloads.\n- `cdifflib` and `cydifflib` on PyPI have demonstrated demand for a C-accelerated `SequenceMatcher` for years.\n\n### Has this already been discussed elsewhere?\n\nNo response given\n\n### Links to previous discussion of this feature:\n\n_No response_\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-150188\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/blhsing","@type":"Person","name":"blhsing"},"datePublished":"2026-05-21T09:05:01Z","url":"https://github.com/python/cpython/issues/150184"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:213bfa39-26ff-2e52-8a95-d85e7cd7b066 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | C810:313081:20B0C6C:2AF2951:6B02368D |
| html-safe-nonce | 4414850495acae08d0108447d72de33187cbe9e42d9de0b3eb16085991673c3d |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJDODEwOjMxMzA4MToyMEIwQzZDOjJBRjI5NTE6NkIwMjM2OEQiLCJ2aXNpdG9yX2lkIjoiNDc1MjAwODY4OTM5MzQyMjEiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 59639d1526cf0751a4d422ead773624cce4743c78f4cf979cabf6e3f0ffde5f2 |
| hovercard-subject-tag | issue:4493222466 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/150184/issue_layout |
| twitter:image | https://opengraph.githubassets.com/b452583c197acf8548dae764293d19e5887758f1fac533adebf588736dbfe1b9/python/cpython/issues/150184 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/b452583c197acf8548dae764293d19e5887758f1fac533adebf588736dbfe1b9/python/cpython/issues/150184 |
| og:image:alt | Feature or enhancement Proposal: Disclaimer: I guided Claude Code to generate the code, the benchmarks and the summary below. I felt it's safe to use AI for this issue because it is purely a logica... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | blhsing |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width