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

Ivan Gerasimov ivan.gerasimov at oracle.com
Tue Apr 2 22:25:31 UTC 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

More information about the core-libs-dev mailing list