RFR [8005953] Speedup construction of CopyOnWriteArraySet in special cases

[Ivan Gerasimov]

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<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
>
>