jpedroh / last-merge / 29664497526

91%

Build Type

push

github

Committed by web-flow

Commit Message

perf: Improve tree matching performance with identical subtree fast-path (#82)

This PR optimizes Yang-based tree matching by detecting identical child
sequences before running the full dynamic programming algorithm.

### Changes
- Added a recursive identical subtree matcher (inspired on jDime) that:
  - verifies nodes and descendants match exactly,
  - builds the corresponding `MatchingEntry`s directly,
  - avoids invoking Yang when the optimal matching is already known.
- Added common prefix/suffix detection for child lists, allowing Yang to
operate only on the unmatched middle region.
- Optimized `Matchings` construction and extension to avoid intermediate
`HashMap` allocations.

### Motivation
Yang's dynamic programming phase evaluates all child-pair combinations,
even when trees are already identical. For unchanged code regions, this
introduced unnecessary recursive matching and matrix construction
overhead.

The new fast path preserves Yang's scoring semantics while skipping DP
computation whenever a perfect ordered matching can be proven.

### Performance impact
This optimization is most effective when changes are localized and large
common prefixes or suffixes exist between child lists. In these cases,
the Yang dynamic programming matrix is built only for the unmatched
middle region.

For example, a tree with 1000 children where the first and last 250
children are identical only requires Yang to process the remaining 500
children, reducing the search space significantly.

For trees with small identical regions (e.g., only 10 matching children
at the beginning and end of a 1000-child list), the reduction is
smaller, as Yang still processes most of the original input. For
completely different trees, the additional identical matching checks
introduce only a small overhead before falling back to the original
algorithm.

However, this optimization improves the general case because source code
changes are typically localized: most subtrees remain un... (continued)

Coverage Stats

92 of 111 new or added lines in 4 files covered. (82.88%)

4 existing lines in 2 files now uncovered.

1026 of 1600 relevant lines covered (64.13%)

2.24 hits per line