commit 6ff1559691d1c91add2193065d3fa563171f3ed7
author Sebastian Zarnekow <sebastian.zarnekow@gmail.com> Mon Apr 15 11:20:57 2019 +0200
committer Andrey Loskutov <loskutov@gmx.de> Sun Apr 21 10:54:42 2019 +0200
tree 8a08073584871130198024fc07c1d7a033190826
parent 613881dc780425fd54173639c561922b9fcc5ff3

Bug 545491 - Improved performance of ReferenceCollection

The implementation of reference collection suffered from a couple
of quadratic lookup operations in its logic to determine, whether
the collection includes certain names.

Instead of doing a simple nested loop scanning of the given arrays,
we apply an algorithm based on the reduced runtime complexity of
binary searches.

The reference collections are long living objects that are far more
often queried than modified. Now we use a simple comparator to sort the
arrays by length and content. When the collection is asked whether it
contains another list of names, these names have to be interned. In
addition to the interning, we also sort the argument arrays. Now we
do have a total of three pairs of arrays, each of the paired arrays is
sorted by the same criteria. That allows to walk both arrays pairways
so even if the worst case, we do no longer need O(n*m) with
n=first.length and m = second.length, but only O(2*(n+m)) comparisons.
For longer arrays, we even use binary search logic to skip more than
one array index when we advance the iteration.

In our scenario, this reduced the accumulated time for invocations of
include from 90s to less than one second.

Change-Id: Ib35b4250ab34fbab55723ebe1f9ad345afca86dd
Signed-off-by: Sebastian Zarnekow <sebastian.zarnekow@gmail.com>
Signed-off-by: Andrey Loskutov <loskutov@gmx.de>