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

Stanimir Simeonoff stanimir at riflexo.com
Tue Apr 2 17:53:49 EDT 2013


My usual use of COWList (set) would be over 99%+ addIfAbsent to return
true.
The tricky part of the benchmark would be running w/ L1 cache full and
observing the effects of the double traverse to the rest of the code. The
effects would be more pronounced w/ shared L1 cache, i.e. hyperthreading
-as the 2nd traverse can trash the cache.

Stanimir


On Wed, Apr 3, 2013 at 12:34 AM, 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>wrote:
>
>> Hello everybody!
>>
>> Please review my proposal for the CopyOnWriteArrayList.addIfAbsent()
>> method optimization.
>>
>> http://washi.ru.oracle.com/~igerasim/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
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130403/fc441357/attachment.html>


More information about the Concurrency-interest mailing list