RFR [8005953] Speedup construction of CopyOnWriteArraySet in special cases

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 30 11:41:13 UTC 2013


Hello everybody!

Would you please review my proposal to change constructor of 
CopyOnWriteArraySet?
http://cr.openjdk.java.net/~dmeetry/8005953/webrev.0/ 
<http://cr.openjdk.java.net/%7Edmeetry/8005953/webrev.0/>

Currently, the body of the constructor is like this:
al = new CopyOnWriteArrayList<E>();
al.addAllAbsent(c);

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.
And if the c was known to be another COWAS, we could simply clone the 
underlying CopyOnWriteArrayList.

The webrew also includes a test I used to make sure nothing is broken.

Sincerely yours,
Ivan



More information about the core-libs-dev mailing list