EMF Compare 3.3.3M7 - Photon M7 - S201805031224
Improve performance of DiffUtil
Many of the algorithms in DiffUtil are O(n^2) so it is very important to
make them all as efficient as possible.
Operations such as Comparison.getEqualityHelper are relatively expensive
because a search of the eAdapters is involved, so calling this method
repeatedly for each item in a list is pointlessly wasteful. Many of the
signatures are changes to pass along the comparison and the equality
helper.
The ignored elements handling in particular is a performance hot spot.
In the worst case it's O(n^2) on the list size. It's better if we use an
array to make iteration as fast as possible in the contains method; as
such, many signatures are changed to use an array.
Because the equality helper caches the match for the first argument to
matchValues, it's important that in a loop we pass in the loop invariant
argument as the first argument, not the second argument. This simple
thing has a very large impact.
The computeIgnoredElements needs particular attention because of the
massive overhead. Note it's better if callers can rely on the fact that
it returns a set that can be modified. The implementation details are
documented directly in the code. In general, the observation is that
computeIgnoredElements is called repeatedly for the same feature's
value, so many of the computations can be reused, i.e, the differences
associated with each candidate. Also the creation of
UnresolvedDiffMatching is expensive, and it does pointless repeated
computations of the same value in each call to apply; these loop
invariant computations are best done once in the constructor.
Change-Id: Ibdcd43d8fa598d57b4baf48b86ba558109a5d832
Signed-off-by: Philip Langer <planger@eclipsesource.com>
1 file changed
