RFR [8005953] Speedup construction of CopyOnWriteArraySet in special cases (original) (raw)

Jason Mehrens jason_mehrens at hotmail.com
Tue Apr 30 12:55:22 UTC 2013

Ivan,

The addAllAbsent() function has O(c.length^2) complexity, so construction time quickly grows with the input size. However, if we knew that c is a Set, we could construct the COWAS in linear time.

You have to be able to prove that the given Set uses the same equivalence relation as the COWAS. Otherwise, it will fall apart you pass a SortedSet with a Comparator or an identity set.

And if the c was known to be another COWAS, we could simply clone the underlying CopyOnWriteArrayList.

That would be safe.

Jason

More information about the core-libs-dev mailing list