Skip to content

fix: replace gotextdiff with linear-space Myers diff to prevent OOM#2311

Merged
talos-bot merged 1 commit intosiderolabs:mainfrom
utkuozdemir:fix/diff-calculation-oom
Feb 12, 2026
Merged

fix: replace gotextdiff with linear-space Myers diff to prevent OOM#2311
talos-bot merged 1 commit intosiderolabs:mainfrom
utkuozdemir:fix/diff-calculation-oom

Conversation

@utkuozdemir
Copy link
Copy Markdown
Member

@utkuozdemir utkuozdemir commented Feb 12, 2026

The gotextdiff/myers library uses the naive Myers algorithm variant that stores the full edit trace, resulting in O((M+N)^2) space complexity.

For machine configs with large inline K8s manifests (thousands of lines), this causes massive memory spikes — e.g., 80K lines allocates ~98 GB and gets OOM-killed.

Replace it with neticdk/go-stdlib/diff/myers which implements the linear-space Myers variant (divide-and-conquer). Memory usage drops from ~25 GB to ~8 MB for 40K-line inputs.

The diff output format is unchanged (unified diff with @@ hunks).

@talos-bot talos-bot moved this to In Review in Planning Feb 12, 2026
@github-project-automation github-project-automation bot moved this from In Review to Approved in Planning Feb 12, 2026
smira added a commit to smira/talos that referenced this pull request Feb 12, 2026
@smira
fix: switch to better Myers algorithm implementation
7821006 
See siderolabs/omni#2311 for the rationale.

Signed-off-by: Andrey Smirnov <andrey.smirnov@siderolabs.com>
@smira smira mentioned this pull request Feb 12, 2026
Merged
@utkuozdemir utkuozdemir force-pushed the fix/diff-calculation-oom branch from 490c6c1 to c9c58a7 Compare February 12, 2026 13:20
@utkuozdemir utkuozdemir force-pushed the fix/diff-calculation-oom branch from c9c58a7 to 0743b99 Compare February 12, 2026 13:20
@utkuozdemir @Unix4ever @oguzkilcan
fix: replace gotextdiff with linear-space Myers diff to prevent OOM
a89d270 
The gotextdiff/myers library uses the naive Myers algorithm variant that stores the full edit trace, resulting in O((M+N)^2) space complexity.

For machine configs with large inline K8s manifests (thousands of lines), this causes massive memory spikes — e.g., 80K lines allocates ~98 GB and gets OOM-killed.

Replace it with neticdk/go-stdlib/diff/myers which implements the linear-space Myers variant (divide-and-conquer). Memory usage drops from ~25 GB to ~8 MB for 40K-line inputs.

The diff output format is unchanged (unified diff with @@ hunks).

Co-authored-by: Artem Chernyshev <artem.chernyshev@talos-systems.com>
Co-authored-by: Oguz Kilcan <oguz.kilcan@siderolabs.com>
Signed-off-by: Utku Ozdemir <utku.ozdemir@siderolabs.com>
@utkuozdemir utkuozdemir force-pushed the fix/diff-calculation-oom branch from 0743b99 to a89d270 Compare February 12, 2026 14:07
@utkuozdemir
Copy link
Copy Markdown
Member Author

utkuozdemir commented Feb 12, 2026

The output of the memory budget test is below. Set the hard threshold to be 50MBs, and the highest allocation with our current tweaks and 75K limit is 28.5 MB:

=== RUN   TestComputeDiff_MemoryBudget
=== RUN   TestComputeDiff_MemoryBudget/small_similar_configs_(100_lines,_few_changes)
    diff_test.go:362: oldData=100 lines, newData=100 lines, allocated=74.0 KB, result=971 bytes
--- PASS: TestComputeDiff_MemoryBudget/small_similar_configs_(100_lines,_few_changes) (0.00s)
=== RUN   TestComputeDiff_MemoryBudget/small_completely_different_(100_lines)
    diff_test.go:362: oldData=100 lines, newData=100 lines, allocated=37.9 KB, result=2800 bytes
--- PASS: TestComputeDiff_MemoryBudget/small_completely_different_(100_lines) (0.00s)
=== RUN   TestComputeDiff_MemoryBudget/medium_similar_(5K_lines,_few_changes)
    diff_test.go:362: oldData=5000 lines, newData=5000 lines, allocated=4.5 MB, result=11836 bytes
--- PASS: TestComputeDiff_MemoryBudget/medium_similar_(5K_lines,_few_changes) (0.00s)
=== RUN   TestComputeDiff_MemoryBudget/medium_completely_different_(5K_lines)
    diff_test.go:362: oldData=5000 lines, newData=5000 lines, allocated=2.3 MB, result=157802 bytes
--- PASS: TestComputeDiff_MemoryBudget/medium_completely_different_(5K_lines) (0.08s)
=== RUN   TestComputeDiff_MemoryBudget/large_similar_(30K_lines,_few_changes)
    diff_test.go:362: oldData=30000 lines, newData=30000 lines, allocated=28.5 MB, result=38441 bytes
--- PASS: TestComputeDiff_MemoryBudget/large_similar_(30K_lines,_few_changes) (0.01s)
=== RUN   TestComputeDiff_MemoryBudget/large_completely_different_(30K_lines)
    diff_test.go:362: oldData=30000 lines, newData=30000 lines, allocated=15.3 MB, result=997804 bytes
--- PASS: TestComputeDiff_MemoryBudget/large_completely_different_(30K_lines) (2.88s)
=== RUN   TestComputeDiff_MemoryBudget/asymmetric:_empty_to_30K_lines
    diff_test.go:362: oldData=0 lines, newData=30000 lines, allocated=5.1 MB, result=348910 bytes
--- PASS: TestComputeDiff_MemoryBudget/asymmetric:_empty_to_30K_lines (0.00s)
=== RUN   TestComputeDiff_MemoryBudget/asymmetric:_50_lines_to_30K_lines
    diff_test.go:362: oldData=50 lines, newData=30000 lines, allocated=5.8 MB, result=348499 bytes
--- PASS: TestComputeDiff_MemoryBudget/asymmetric:_50_lines_to_30K_lines (0.00s)
=== RUN   TestComputeDiff_MemoryBudget/near_threshold_(total_~74K_lines)
    diff_test.go:362: oldData=37000 lines, newData=37000 lines, allocated=19.3 MB, result=1235804 bytes
--- PASS: TestComputeDiff_MemoryBudget/near_threshold_(total_~74K_lines) (4.43s)
=== RUN   TestComputeDiff_MemoryBudget/over_threshold_(total_~76K_lines,_returns_summary)
    diff_test.go:362: oldData=38000 lines, newData=38000 lines, allocated=2.0 KB, result=50 bytes
--- PASS: TestComputeDiff_MemoryBudget/over_threshold_(total_~76K_lines,_returns_summary) (0.00s)
--- PASS: TestComputeDiff_MemoryBudget (7.42s)

@utkuozdemir
Copy link
Copy Markdown
Member Author

utkuozdemir commented Feb 12, 2026

/m

@talos-bot talos-bot merged commit a89d270 into siderolabs:main Feb 12, 2026
34 checks passed
@github-project-automation github-project-automation bot moved this from Approved to Done in Planning Feb 12, 2026
@utkuozdemir utkuozdemir deleted the fix/diff-calculation-oom branch February 12, 2026 14:30
smira added a commit to smira/talos that referenced this pull request Feb 13, 2026
@smira
fix: switch to better Myers algorithm implementation
76483f0 
See siderolabs/omni#2311 for the rationale.

Signed-off-by: Andrey Smirnov <andrey.smirnov@siderolabs.com>
smira added a commit to smira/talos that referenced this pull request Feb 18, 2026
@smira
fix: switch to better Myers algorithm implementation
35ad044 
See siderolabs/omni#2311 for the rationale.

Signed-off-by: Andrey Smirnov <andrey.smirnov@siderolabs.com>
smira added a commit to smira/talos that referenced this pull request Mar 6, 2026
@smira
fix: switch to better Myers algorithm implementation
5ebb00f 
See siderolabs/omni#2311 for the rationale.

Signed-off-by: Andrey Smirnov <andrey.smirnov@siderolabs.com>
(cherry picked from commit 35ad044)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@smira smira smira approved these changes

@Unix4ever Unix4ever Unix4ever approved these changes

@oguzkilcan oguzkilcan oguzkilcan approved these changes

Assignees

No one assigned

Labels

None yet

Projects

Planning
Archived in project

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@utkuozdemir @smira @Unix4ever @oguzkilcan @talos-bot