[concurrency-interest] RFR [8011215] optimization of CopyOnWriteArrayList.addIfAbsent()

[Louis Wasserman]

Can we see the implementation of your benchmark?  Accurate benchmarking is
extremely nontrivial.


On Tue, Apr 2, 2013 at 2:34 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com>wrote:

> Thank you Stanimir!
>
> My main goal was to get rid of early and possibly unneeded memory
> allocation.
> I thought that System.arraycopy() would somehow compensate the need to
> traverse the array twice.
> However testing shows that my code works a bit faster at least when
> dealing with Integer arrays of size from 1 to 100.
>
> Sincerely,
> Ivan
>
> On 02.04.2013 23:25, Stanimir Simeonoff wrote:
>
>> The current version is cache oblivious. In any case for smaller arrays
>> (like COW) System.arrayCopy won't yield any noticeable difference.
>> Also, iirc System.arrayCopy places a memory barrier which in the COW case
>> is unneeded.
>>
>> Stanimir
>>
>>
>>
>> On Tue, Apr 2, 2013 at 9:53 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com<mailto:
>> ivan.gerasimov at oracle.**com <ivan.gerasimov at oracle.com>>> wrote:
>>
>>     Hello everybody!
>>
>>     Please review my proposal for the
>>     CopyOnWriteArrayList.**addIfAbsent() method optimization.
>>
>>     http://washi.ru.oracle.com/~**igerasim/webrevs/8011215/**
>> webrev/index.html<http://washi.ru.oracle.com/~igerasim/webrevs/8011215/webrev/index.html>
>>     <http://washi.ru.oracle.com/%**7Eigerasim/webrevs/8011215/**
>> webrev/index.html<http://washi.ru.oracle.com/%7Eigerasim/webrevs/8011215/webrev/index.html>
>> >
>>
>>
>>     Here is the original function body:
>>     ------------------------------**------------------
>>         Object[] elements = getArray();
>>         int len = elements.length;
>>         Object[] newElements = new Object[len + 1]; <-- allocate new
>>     array in advance
>>         for (int i = 0; i < len; ++i) {
>>             if (eq(e, elements[i]))                 <-- check whether
>>     e is null on every iteration
>>                 return false; // exit, throwing away copy
>>             else
>>                 newElements[i] = elements[i];       <-- copy elements
>>     one by one
>>         }
>>         newElements[len] = e;
>>         setArray(newElements);
>>     ------------------------------**------------------
>>     The proposed change is to reuse CopyOnWriteArrayList.indexOf()
>>     function to check if e is already in the array.
>>     If the check passed, new array is allocated withArrays.copyOf().
>>     It uses native System.arraycopy(), which is probably faster than
>>     copying elements in the loop.
>>
>>     Sincerely yours,
>>     Ivan
>>
>>     ______________________________**_________________
>>     Concurrency-interest mailing list
>>     Concurrency-interest at cs.**oswego.edu<Concurrency-interest at cs.oswego.edu>
>>     <mailto:Concurrency-interest@**cs.oswego.edu<Concurrency-interest at cs.oswego.edu>
>> >
>>     http://cs.oswego.edu/mailman/**listinfo/concurrency-interest<http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
>>
>>
>>
>


-- 
Louis Wasserman