René's URL Explorer Experiment


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

direct link

Domain: github.com

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/:user_id/:repository/pull/:id/files(.:format)
route-controllerpull_requests
route-actionfiles
fetch-noncev2:3e2a8d80-0ed5-68d8-89ee-9c7f60ed5db7
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-id8FA8:299992:20B8751:2B05A2D:6B023B6F
html-safe-noncee817369eed46815f23440c6d1de6f3132237801eb7045df2deb38c8425a18bb3
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4RkE4OjI5OTk5MjoyMEI4NzUxOjJCMDVBMkQ6NkIwMjNCNkYiLCJ2aXNpdG9yX2lkIjoiMTkxMDgxNjMxODgzMjEzMDkyNyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9
visitor-hmac9d87c4c43b9b15bfcfa17134034574df75c601e257f2b75ff3e1e3d80cb17ce5
hovercard-subject-tagpull_request:1440071074
github-keyboard-shortcutsrepository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///pull_requests/show/files
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/python/cpython/pull/106877/files
twitter:imagehttps://avatars.githubusercontent.com/u/13121107?s=400&v=4
twitter:cardsummary_large_image
og:imagehttps://avatars.githubusercontent.com/u/13121107?s=400&v=4
og:image:altdifflib.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_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
None87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456
turbo-cache-controlno-preview
diff-viewunified
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 full-width
disable-turbotrue
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

Links:

Skip to contenthttps://github.com/python/cpython/pull/106877/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fpull%2F106877%2Ffiles
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%2Fpull%2F106877%2Ffiles
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fpull_requests%2Fshow%2Ffiles&source=header-repo&source_repo=python%2Fcpython
Reloadhttps://github.com/python/cpython/pull/106877/files
Reloadhttps://github.com/python/cpython/pull/106877/files
Reloadhttps://github.com/python/cpython/pull/106877/files
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
Sign up for GitHub https://github.com/signup?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
terms of servicehttps://docs.github.com/terms
privacy statementhttps://docs.github.com/privacy
Sign inhttps://github.com/login?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
gaogaotiantianhttps://github.com/gaogaotiantian
python:mainhttps://github.com/python/cpython/tree/main
gaogaotiantian:difflib-perfhttps://github.com/gaogaotiantian/cpython/tree/difflib-perf
Conversation 4 https://github.com/python/cpython/pull/106877
Commits 2 https://github.com/python/cpython/pull/106877/commits
Checks 0 https://github.com/python/cpython/pull/106877/checks
Files changed https://github.com/python/cpython/pull/106877/files
Please reload this pagehttps://github.com/python/cpython/pull/106877/files
gh-106865: Improve difflib.find_longest_match performance with cache https://github.com/python/cpython/pull/106877/files#top
Show all changes 2 commits https://github.com/python/cpython/pull/106877/files
5f35b0d Improve difflib performance with a cache gaogaotiantian Jul 18, 2023 https://github.com/python/cpython/pull/106877/commits/5f35b0dbb9ebec63d805d230e01b4a0676e613af
0396f81 📜🤖 Added by blurb_it. blurb-it[bot] Jul 18, 2023 https://github.com/python/cpython/pull/106877/commits/0396f814eb56defa9adcc5433cc48ca08bd1f2c5
Clear filters https://github.com/python/cpython/pull/106877/files
Please reload this pagehttps://github.com/python/cpython/pull/106877/files
Please reload this pagehttps://github.com/python/cpython/pull/106877/files
difflib.py https://github.com/python/cpython/pull/106877/files#diff-4517a87c0d1215c3a18d0a4dffffc879ff09b86c522a5396a28c60090a397436
2023-07-18-23-45-19.gh-issue-106865.dxO3Qr.rst https://github.com/python/cpython/pull/106877/files#diff-2edcb21aebc9390d52b953814465a8b2da5e2af2d2914f35dcd7cedee1d79bc5
Lib/difflib.pyhttps://github.com/python/cpython/pull/106877/files#diff-4517a87c0d1215c3a18d0a4dffffc879ff09b86c522a5396a28c60090a397436
View file https://github.com/gaogaotiantian/cpython/blob/0396f814eb56defa9adcc5433cc48ca08bd1f2c5/Lib/difflib.py
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/106877/{{ revealButtonHref }}
https://github.com/python/cpython/pull/106877/files#diff-4517a87c0d1215c3a18d0a4dffffc879ff09b86c522a5396a28c60090a397436
https://github.com/python/cpython/pull/106877/files#diff-4517a87c0d1215c3a18d0a4dffffc879ff09b86c522a5396a28c60090a397436
Misc/NEWS.d/next/Library/2023-07-18-23-45-19.gh-issue-106865.dxO3Qr.rsthttps://github.com/python/cpython/pull/106877/files#diff-2edcb21aebc9390d52b953814465a8b2da5e2af2d2914f35dcd7cedee1d79bc5
View file https://github.com/gaogaotiantian/cpython/blob/0396f814eb56defa9adcc5433cc48ca08bd1f2c5/Misc/NEWS.d/next/Library/2023-07-18-23-45-19.gh-issue-106865.dxO3Qr.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/106877/{{ revealButtonHref }}
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.