Visitar URL original
Bound MyersDiff work for large edit distances by tuannx · Pull Request #4450 · assertj/assertj · GitHub
Skip to content

Bound MyersDiff work for large edit distances - #4450

Open
tuannx wants to merge 1 commit into
assertj:mainfrom
tuannx:fix-2345
Open

tuannx wants to merge 1 commit into
assertj:mainfrom
tuannx:fix-2345

Conversation

@tuannx

@tuannx tuannx commented Oct 23, 2026

Copy link
Copy Markdown

Fixes #2345

Problem: MyersDiff allocates O(D²) path nodes, so hasSameTextualContentAs on large, very different files runs for minutes or hours.
Fix: past MAX_EDIT_DISTANCE (10,000) edits, report the region between the common prefix and suffix as a single ChangeDelta.

Measurements (JDK 25, two runs each, allocation via ThreadMXBean):

  • 16k fully different lines: 5.9–6.1 s / 11,728 MB → 0.68–0.70 s / 1,154 MB (same failure message length)
  • 8k fully different lines: 1.3 s / 2,937 MB → 0.66 s / 1,152 MB
  • 0.1% different, 1k–16k lines: unchanged (54–86 ms, 4–8 MB)

Tests: new MyersDiff_diff_Test (fails with the limit disabled: 2 deltas instead of 1); 89 diff/textual-content tests pass; ./mvnw spotless:apply clean.

Check List:

🤖 Generated with Claude Code

Past MAX_EDIT_DISTANCE edits, report the region between the common prefix
and suffix as a single ChangeDelta instead of allocating O(D^2) path nodes.

Fixes assertj#2345
@scordio scordio added status: team discussion An issue we'd like to discuss as a team to make progress and removed status: team discussion An issue we'd like to discuss as a team to make progress labels Oct 23, 2026
@scordio

scordio commented Oct 23, 2026

Copy link
Copy Markdown
Member

Blocked by #2345 (comment).

@scordio scordio added the status: blocked We need to resolve a prerequisite before we can continue label Oct 23, 2026

This branch has not been deployed

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

Labels

status: blocked We need to resolve a prerequisite before we can continue

Projects

None yet

Development

Successfully merging this pull request may close these issues.

hasSameTextualContentAs is hanging with text file

2 participants