JDK-6982173: Small problem causing thousands of wasted CPU hours

Martin Buchholz martinrb at google.com
Thu Feb 14 19:33:49 UTC 2019

On Wed, Feb 13, 2019 at 6:45 PM Stuart Marks <stuart.marks at oracle.com>

> If we all agree on this, I'll proceed with working up a changeset for
> JDK-6394757.[3] It's time to fix this one.

Thanks for taking on the fixing of this unfixable problem.
It's important to do lots of documentation/guidance work, esp. a release
Doug and I will take care of anything that needs doing  in jsr166.

In the real world, if performance is important, one might want to sort both
collections (or use collections that are naturally sorted), then do a
two-finger walk through both collections, funneling the results into a
target collection.
Which is N*log(N) + M*log(M) + N + M
With enough work, that might be library-fiable.
Hmmmmm ...
Imagine ConcurrentSkipListSet.removeAll(aNavigableSet) ...
Then by two-finger through both collections, advancing using
higher/ceiling, you should get something like O(min(N*log(N), M*log(M)))
If the argument is not sorted, then it is likely to be worth the effort of
copying it into a sorted set (TreeSet with same comparator?).
Software is hard.

More information about the core-libs-dev mailing list