Skip to content

fix: optimize LCS diff from O(m*n) to O(n) space#329

Merged
tomasz-tomczyk merged 2 commits intomainfrom
fix/lcs-diff-memory
Apr 21, 2026
Merged

fix: optimize LCS diff from O(m*n) to O(n) space#329
tomasz-tomczyk merged 2 commits intomainfrom
fix/lcs-diff-memory

Conversation

@tomasz-tomczyk
Copy link
Copy Markdown
Owner

@tomasz-tomczyk tomasz-tomczyk commented Apr 21, 2026 •
edited
Loading

Summary

  • Replace full DP matrix in ComputeLineDiff with Hirschberg's divide-and-conquer algorithm
  • Reduces memory from O(m*n) to O(n) — prevents OOM on large AI-generated plans

Benchmark results (Apple M2 Pro, count=3)

Before (O(m*n) DP matrix)

Size ns/op B/op allocs/op
100 lines 36,738 112,464 112
1,000 lines 2,619,892 8,379,741 1,015
5,000 lines 53,601,601 206,429,800 5,021

After (Hirschberg O(n) space)

Size ns/op B/op allocs/op
100 lines 67,685 74,560 597
1,000 lines 3,351,780 1,083,169 5,994
5,000 lines 73,199,472 6,644,619 29,997

Impact

Size Memory reduction Time tradeoff
100 lines -34% (112KB → 75KB) +84% slower
1,000 lines -87% (8.4MB → 1.1MB) +28% slower
5,000 lines -97% (206MB → 6.6MB) +37% slower

The Hirschberg algorithm trades modest CPU time for dramatically less memory. At 5K lines: 206MB → 6.6MB. This prevents OOM on large AI-generated plans while keeping runtime under 75ms — well within acceptable for an interactive tool.

Test plan

  • All 14 existing diff tests pass with -race
  • Full test suite passes
  • Reviewed by Go expert agent — approved
  • Benchmarked before/after on Apple M2 Pro

🤖 Generated with Claude Code

tomasz-tomczyk and others added 2 commits April 21, 2026 22:14
@tomasz-tomczyk @claude
fix: reduce ComputeLineDiff memory from O(m*n) to O(n) using Hirschbe…
1e282da 
…rg's algorithm

The previous LCS implementation allocated a full (m+1)*(n+1) int matrix,
which for a 10K-line file consumes ~400MB. Replace with Hirschberg's
divide-and-conquer algorithm that uses only two rows (O(n) space, ~80KB
for 10K lines) while producing identical diff output.

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
@tomasz-tomczyk @claude
style: convert if-else chains to switch in LCS functions
abbc126 
Fixes gocritic ifElseChain lint.

Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
@tomasz-tomczyk tomasz-tomczyk merged commit a995f77 into main Apr 21, 2026
4 checks passed
@tomasz-tomczyk tomasz-tomczyk deleted the fix/lcs-diff-memory branch April 21, 2026 21:24
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

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@tomasz-tomczyk