Title: gh-106865: Improve `difflib.find_longest_match` performance with cache by gaogaotiantian · Pull Request #106877 · python/cpython · GitHub
Open Graph Title: gh-106865: Improve `difflib.find_longest_match` performance with cache by gaogaotiantian · Pull Request #106877 · python/cpython
X Title: gh-106865: Improve `difflib.find_longest_match` performance with cache by gaogaotiantian · Pull Request #106877 · python/cpython
Description: difflib.SequenceMatcher does not perform well on large input. This patch tries to improve it by doing some micro optimization on hot path. When dealing with large inputs, for example, large files, almost all the time is spent in find_longest_match, and the hottest code is the nested for loop: for i in range(alo, ahi): # look at all instances of a[i] in b; note that because # b2j has no junk keys, the loop is skipped if a[i] is junk j2lenget = j2len.get newj2len = {} for j in b2j.get(a[i], nothing): # a[i] matches b[j] if j < blo: continue if j >= bhi: break k = newj2len[j] = j2lenget(j-1, 0) + 1 if k > bestsize: besti, bestj, bestsize = i-k+1, j-k+1, k The content in the for loop will execute (ahi - alo) * len(b2j[a[i]]) times. Any optimization in the loop could potentially be a large improvement. The patch runs the same loop for the first time a[i] is found, except that it creates a cache for the valid b2j list - list with j inside the range (blo, bhi). If a[i] already appears before, then the cached list would be used - then the two if checks can be removed. Also, if a[i] already appears before and there is at least one valid content in the list, bestsize would be already set to at least 1 - we can then only do the if k > bestsize check when k is greater than 1 - which happens to be already checked if we use if to check whether j-1 is in the dict. In this way, we eliminated plenty of code on the cached path. This optimization is significant when the cached path is hit frequently, or the "item"s in a repeats frequently. This is the case for any large file (especially file with smaller vocabulary like ascii). I tried this on some of files by hand - a c source file and a README file. benchmark code import difflib import time with open("../viztracer/src/viztracer/modules/snaptrace.c") as f: code = f.read() with open("../viztracer/README.md") as f: readme = f.read() s = difflib.SequenceMatcher(None, code, code) start = time.time() s.get_opcodes() print(time.time() - start) s = difflib.SequenceMatcher(None, code, readme) start = time.time() s.get_opcodes() print(time.time() - start) s = difflib.SequenceMatcher(None, readme, code) start = time.time() s.get_opcodes() print(time.time() - start) The time spent improvement was significant: 0.6531200408935547 0.21375417709350586 0.7097032070159912 to 0.20792889595031738 0.11065959930419922 0.28839802742004395 This patch will have a small negative performance impact on smaller test cases and cases where none of the items in a duplicates. For example, it is significantly slower in test_recursion_limit: def test_recursion_limit(self): # Check if the problem described in patch #1413711 exists. limit = sys.getrecursionlimit() old = [(i%2 and "K:%d" or "V:A:%d") % i for i in range(limit*2)] new = [(i%2 and "K:%d" or "V:B:%d") % i for i in range(limit*2)] difflib.SequenceMatcher(None, old, new).get_opcodes() However, in real world scenario, it does not make much sense to diff/match two sequences with a giant vocabulary, so in almost all actual use cases this should improve the performance. Especially on large sequences. We can, however, check the vocabulary (set(a) / len(a)) and determine whether we want to do this optimization. Extra overhead, potentially better perf on worst case. P.S. changing cache.append to cacheappend = cache.append does not have a observable impact, but I can do that if that's needed. Issue: gh-106865
Open Graph Description: difflib.SequenceMatcher does not perform well on large input. This patch tries to improve it by doing some micro optimization on hot path. When dealing with large inputs, for example, large files, ...
X Description: difflib.SequenceMatcher does not perform well on large input. This patch tries to improve it by doing some micro optimization on hot path. When dealing with large inputs, for example, large files, ...
Opengraph URL: https://github.com/python/cpython/pull/106877
X: @github
Domain: github.com
| 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 | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:3e2a8d80-0ed5-68d8-89ee-9c7f60ed5db7 |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | 8FA8:299992:20B8751:2B05A2D:6B023B6F |
| html-safe-nonce | e817369eed46815f23440c6d1de6f3132237801eb7045df2deb38c8425a18bb3 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4RkE4OjI5OTk5MjoyMEI4NzUxOjJCMDVBMkQ6NkIwMjNCNkYiLCJ2aXNpdG9yX2lkIjoiMTkxMDgxNjMxODgzMjEzMDkyNyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 9d87c4c43b9b15bfcfa17134034574df75c601e257f2b75ff3e1e3d80cb17ce5 |
| hovercard-subject-tag | pull_request:1440071074 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,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/python/cpython/pull/106877/files |
| twitter:image | https://avatars.githubusercontent.com/u/13121107?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/13121107?s=400&v=4 |
| og:image:alt | difflib.SequenceMatcher does not perform well on large input. This patch tries to improve it by doing some micro optimization on hot path. When dealing with large inputs, for example, large files, ... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| 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 full-width |
| disable-turbo | true |
| 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 |
Links:
Viewport: width=device-width