Skip to content

fix(perf): optimize levenshtein distance algorithm - #21500

Closed
tom-neara wants to merge 2 commits into
anomalyco:devfrom
tom-neara:levenshtein_perf
Closed

fix(perf): optimize levenshtein distance algorithm#21500
tom-neara wants to merge 2 commits into
anomalyco:devfrom
tom-neara:levenshtein_perf

Conversation

@tom-neara

@tom-neara tom-neara commented Apr 8, 2026

Copy link
Copy Markdown

This fixes an issue where the edit tool was extremely CPU-bound when dealing with large block sizes, often observed with Gemini 3.1 which tends to output larger replacement blocks.

The previous implementation used O(N*M) space by allocating an array of arrays, causing massive garbage collection overhead. The new implementation uses typed arrays and O(min(N,M)) space.

Issue for this PR

Closes #21470

Type of change

  • Bug fix
  • New feature
  • Refactor / code improvement
  • Documentation

What does this PR do?

Reduces the dime and space of levenshtein distance calculation. Before I was seeing constant 100% CPU, now, I see ~20% on average

If you paste a large clearly AI generated description here your PR may be IGNORED or CLOSED!

How did you verify your code works?

I re-installed from my tree and gave it a challenging task using gemini-3.1 and it made progress

Screenshots / recordings

If this is a UI change, please include a screenshot or recording.

Checklist

  • I have tested my changes locally
  • I have not included unrelated changes in this PR

If you do not follow this template your PR will be automatically rejected.

@froody
perf(edit): optimize levenshtein distance algorithm
41871f2 
This fixes an issue where the edit tool was extremely CPU-bound when
dealing with large block sizes, often observed with Gemini 3.1 which
tends to output larger replacement blocks.

The previous implementation used O(N*M) space by allocating an array of
arrays, causing massive garbage collection overhead. The new implementation
uses typed arrays and O(min(N,M)) space.
@github-actions

github-actions Bot commented Apr 8, 2026

Copy link
Copy Markdown
Contributor

Hey! Your PR title perf(edit): optimize levenshtein distance algorithm doesn't follow conventional commit format.

Please update it to start with one of:

  • feat: or feat(scope): new feature
  • fix: or fix(scope): bug fix
  • docs: or docs(scope): documentation changes
  • chore: or chore(scope): maintenance tasks
  • refactor: or refactor(scope): code refactoring
  • test: or test(scope): adding or updating tests

Where scope is the package name (e.g., app, desktop, opencode).

See CONTRIBUTING.md for details.

@tom-neara tom-neara changed the title perf(edit): optimize levenshtein distance algorithm fix(perf): optimize levenshtein distance algorithm Apr 8, 2026
@rekram1-node

rekram1-node commented May 15, 2026

Copy link
Copy Markdown
Collaborator

Automated PR Cleanup

Thank you for contributing to opencode.

Due to the high volume of PRs from users and AI agents, we periodically close older PRs using automated criteria so maintainers can focus review time on the most active and community-supported contributions.

This PR was closed because it matched the following cleanup criteria:

  • The PR was created more than 1 month ago
  • The PR had fewer than 2 positive reactions
  • Positive reactions are counted as thumbs-up, heart, celebration, or rocket reactions on the PR

PRs created within the last month are not affected by this cleanup.

If you believe this PR was closed incorrectly, or if you are still actively working on it, please leave a comment explaining why it should be reopened. A maintainer can review and reopen it if appropriate.

Thanks again for taking the time to contribute.

@jmencak jmencak mentioned this pull request Jun 24, 2026
Closed
@Celibistrial

Celibistrial commented Jun 24, 2026

Copy link
Copy Markdown

Why was this closed? please merge this

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

automated-pr-cleanup

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

OpenCode is heavily cpu-bound

4 participants

@tom-neara @rekram1-node @Celibistrial @froody