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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 2 17:34:50 EDT 2013


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>> 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/%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
>     <mailto: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/03c8d39f/attachment.html>


More information about the Concurrency-interest mailing list