search

numist / Diffing-Explorations

A playground for diffing experiments along with the algorithms and data structures needed to support them
9 stars 0 forks source link

Experiment: performance improvements to CollectionDifference.init #9

Open numist opened 4 years ago

numist commented 4 years ago

Finally hit 80/20 with CollectionDifference.init(:):

testBtree79ce96ab39To93ba69ec97ByLine:
384.00 ms  100.0%       specialized CorrectnessClub.diffImp<A>(from:to:)
302.00 ms   78.6%        CollectionDifference.init<A>(_:)
51.00 ms    13.2%        _club<A>(from:to:)
30.00 ms     7.8%        _AlphabetTrie.init(for:)

Most of that time is spent in CollectionDifference.init(_validatedChanges:), which was supposed to be the fast path (it skips change validity checking):

302.00 ms  100.0%       CollectionDifference.init<A>(_:)
292.00 ms   96.6%        CollectionDifference.init<A>(_validatedChanges:)
287.00 ms   95.0%         MutableCollection<>.sort(by:)

The diffing algorithms already produce changes in order, so there's room here for an even faster _validatedChanges initializer, and also a fast path through the public initializer that checks order to avoid an unnecessary sort.

numist commented 4 years ago

Looks like reversing the order of the changes passed into CollectionDifference.init(:) cuts the sorting time in half. Still lots more improvement for the built-in diffing algorithm to be made by moving the sort up out of CollectionDifference.init(validatedChanges:) though.