RFR [8005953] Speedup construction of CopyOnWriteArraySet in special cases

David Holmes david.holmes at oracle.com
Tue Apr 30 11:45:37 UTC 2013

Hi Ivan,

On 30/04/2013 9:41 PM, Ivan Gerasimov wrote:
> Hello everybody!
> Would you please review my proposal to change constructor of
> CopyOnWriteArraySet?

Has this been run past Doug Lea and JSR-166 (ex)EG yet? All 
java.util.concurrent updates have to be coordinated through Doug.


> 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