René's URL Explorer Experiment


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

direct link

Domain: github.com


Hey, it has json ld scripts:
{"@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-profiling0
react-import-mapreact,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-controllervoltron_issues_fragments
route-actionissue_layout
fetch-noncev2:213bfa39-26ff-2e52-8a95-d85e7cd7b066
current-catalog-service-hash81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114
request-idC810:313081:20B0C6C:2AF2951:6B02368D
html-safe-nonce4414850495acae08d0108447d72de33187cbe9e42d9de0b3eb16085991673c3d
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJDODEwOjMxMzA4MToyMEIwQzZDOjJBRjI5NTE6NkIwMjM2OEQiLCJ2aXNpdG9yX2lkIjoiNDc1MjAwODY4OTM5MzQyMjEiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmac59639d1526cf0751a4d422ead773624cce4743c78f4cf979cabf6e3f0ffde5f2
hovercard-subject-tagissue:4493222466
github-keyboard-shortcutsrepository,issues,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///voltron/issues_fragments/issue_layout
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/150184/issue_layout
twitter:imagehttps://opengraph.githubassets.com/b452583c197acf8548dae764293d19e5887758f1fac533adebf588736dbfe1b9/python/cpython/issues/150184
twitter:cardsummary_large_image
og:imagehttps://opengraph.githubassets.com/b452583c197acf8548dae764293d19e5887758f1fac533adebf588736dbfe1b9/python/cpython/issues/150184
og:image:altFeature 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:width1200
og:image:height600
og:site_nameGitHub
og:typeobject
og:author:usernameblhsing
hostnamegithub.com
expected-hostnamegithub.com
None87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456
turbo-cache-controlno-preview
go-importgithub.com/python/cpython git https://github.com/python/cpython.git
octolytics-dimension-user_id1525981
octolytics-dimension-user_loginpython
octolytics-dimension-repository_id81598961
octolytics-dimension-repository_nwopython/cpython
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id81598961
octolytics-dimension-repository_network_root_nwopython/cpython
turbo-body-classeslogged-out env-production page-responsive
disable-turbofalse
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release423dbb54c5e7bfecc838eb387c1435eb3d0e760d
ui-targetfull
theme-color#1e2327
color-schemelight dark
react-app-nameissues

Links:

Skip to contenthttps://github.com/python/cpython/issues/150184#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fissues%2F150184
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fissues%2F150184
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fvoltron%2Fissues_fragments%2Fissue_layout&source=header-repo&source_repo=python%2Fcpython
Reloadhttps://github.com/python/cpython/issues/150184
Reloadhttps://github.com/python/cpython/issues/150184
Reloadhttps://github.com/python/cpython/issues/150184
pythonhttps://github.com/python
cpythonhttps://github.com/python/cpython
Codehttps://github.com/python/cpython
Issues5k+ (5k+)https://github.com/python/cpython/issues
Pull requests2.4k (2.4k)https://github.com/python/cpython/pulls
Actionshttps://github.com/python/cpython/actions
Projectshttps://github.com/python/cpython/projects
Security and qualityhttps://github.com/python/cpython/security
Insightshttps://github.com/python/cpython/insights
https://github.com/python/cpython
New issuehttps://github.com/login?return_to=https://github.com/python/cpython/issues/150184
New issuehttps://github.com/login?return_to=https://github.com/python/cpython/issues/150184
Add a C accelerator for difflib.SequenceMatcherhttps://github.com/python/cpython/issues/150184#top
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
type-featureA feature request or enhancementhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-feature%22
https://github.com/blhsing
blhsinghttps://github.com/blhsing
on May 21, 2026https://github.com/python/cpython/issues/150184#issue-4493222466
Algorithmic complexity of difflibhttps://discuss.python.org/t/algorithmic-complexity-of-difflib/105844
#144132https://github.com/python/cpython/issues/144132
gh-150184: difflib C accelerator #150188https://github.com/python/cpython/pull/150188
blhsinghttps://github.com/blhsing
type-featureA feature request or enhancementhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-feature%22
on May 21, 2026https://github.com/python/cpython/issues/150184#event-25796395661
aiskhttps://github.com/aisk
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
on May 21, 2026https://github.com/python/cpython/issues/150184#event-25798082458
https://github.com/picnixz
picnixzhttps://github.com/picnixz
on May 21, 2026https://github.com/python/cpython/issues/150184#issuecomment-4507513787
picnixzhttps://github.com/picnixz
not plannedhttps://github.com/python/cpython/issues?q=is%3Aissue%20state%3Aclosed%20archived%3Afalse%20reason%3Anot-planned
on May 21, 2026https://github.com/python/cpython/issues/150184#event-25800906027
Sign up for freehttps://github.com/signup?return_to=https://github.com/python/cpython/issues/150184
Sign in to commenthttps://github.com/login?return_to=https://github.com/python/cpython/issues/150184
performancePerformance or resource usagehttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22performance%22
type-featureA feature request or enhancementhttps://github.com/python/cpython/issues?q=state%3Aopen%20label%3A%22type-feature%22
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.