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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 30 11:49:48 UTC 2013

On 30.04.2013 15:45, David Holmes wrote:

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. I cc'ed the message to Doug Lea (just checked the sent box to make sure I did). For some reasons I do not see his address in the message received through the list.

David -----

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(); 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