jpedroh / generic-merge / 10121129498

80%

push

github

perf: Introduce an auxiliary table for efficient matching existence check (#67)

Sure, here's the revised version with the term "auxiliary HashMap":

This work follows up on #66. Currently, the Matchings API provides a
quick way to retrieve a matching entry for two arbitrary nodes. However,
a common use case during the merge process involves finding a matching
entry for a node without prior knowledge of which other node it matches
with. While we have an API for this scenario, it is inefficient as it
may iterate over all matchings in the worst case.

This PR introduces an enhancement to address this inefficiency. The
approach involves storing an auxiliary HashMap where both the key and
value are nodes, say A and B. This way, there is an entry in the HashMap
only if there is a matching between node A and B. This allows us to
quickly check if a matching for node A exists by simply checking if an
entry is present in the HashMap. This change reduces the lookup time to
O(1), at the cost of additional memory usage and some performance
overhead in building and updating this auxiliary HashMap, which were
found to be negligible compared to the performance gains achieved.

576 of 1044 branches covered (55.17%)

Branch coverage included in aggregate %.

21 of 21 new or added lines in 3 files covered. (100.0%)

2053 of 2213 relevant lines covered (92.77%)

12713.78 hits per line