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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 2 18:25:31 EDT 2013


Sure!

Attached please find an archive with the tests.
Actually they are quite naive - they simply run the code snippet in loop 
for several hundreds times.

Sincerely,
Ivan

On 03.04.2013 1:49, Louis Wasserman wrote:
> 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 <mailto: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>
>         <mailto: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>
>            
>         <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>
>             <mailto:Concurrency-interest at cs.oswego.edu
>         <mailto:Concurrency-interest at cs.oswego.edu>>
>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>
>
>
> -- 
> Louis Wasserman

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130403/3983a7ba/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 8011215-benchmark.tar
Type: application/x-tar
Size: 10240 bytes
Desc: not available
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130403/3983a7ba/attachment-0001.tar>


More information about the Concurrency-interest mailing list