Skip to content

Alignment punt threshold (15) is far too conservative given the memoization #23

Description

@lassevk

ElementSimilarityDiffElementAligner<T> bails out to a plain delete+insert when a change section exceeds a combined size:

private const int MaximumChangedSectionSizeBeforePuntingToDeletePlusAdd = 15;
// ...
if (length1 + length2 > MaximumChangedSectionSizeBeforePuntingToDeletePlusAdd)
    return new List<DiffElement<T?>>();

The comments justify this by fear of exponential blow-up ("recursive solution the combinations could get big fast"). But CalculateBestAlignment is memoized on AlignmentKey(lower1, lower2), so the number of distinct states is bounded by length1 * length2 and each is computed once — the algorithm is O(length1 × length2), not exponential.

Consequences of the low threshold:

  • Any changed block with more than ~15 combined elements gets no similarity-based alignment at all; you just get a block of deletes followed by a block of inserts. For line-level text diffs this means a fairly small changed region loses all the nice Modify/Replace alignment.

Suggestions:

  • Raise the threshold substantially (it's a quadratic guard, not exponential), or
  • Replace the hard cutoff with a product-based guard (e.g. length1 * length2 <= N) that reflects the real cost, and/or make it configurable via DiffOptions.

The comment block (src/DiffLib/Alignment/ElementSimilarityAligner.cs:16-21 and :93-97) should also be corrected since it mis-describes the complexity.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions