Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve efficiency of lehvenshtein_distance method #91835

Merged
merged 2 commits into from May 2, 2022

Conversation

eendebakpt
Copy link
Contributor

@eendebakpt eendebakpt commented Apr 22, 2022

The buffer initialization (which happens many times) is improved by replacing the multiplication with a sum.

@JelleZijlstra
Copy link
Member

JelleZijlstra commented Apr 22, 2022

Have you benchmarked this? MOVE_COST is 2, so the multiplication should just be a bitshift. Chances are that's faster than an additional memory read.

@eendebakpt
Copy link
Contributor Author

eendebakpt commented Apr 22, 2022

@JelleZijlstra Fair point. As long as MOVE_COST is a power of two the compiler can indeed optimize and there is no gain. I benchmarked on my system with MOVE_COST=2 (just the buffer filling in a large for loop):

current main: 1.48 seconds
original PR: 1.55 seconds
updated PR: 0.89 seconds

@eendebakpt eendebakpt changed the title Improve efficiency of lehvensthein_distance method Improve efficiency of lehvenshtein_distance method Apr 22, 2022
@JelleZijlstra JelleZijlstra merged commit feb45d0 into python:main May 2, 2022
12 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants