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

Louis Wasserman lowasser at google.com
Tue Apr 2 21:49:09 UTC 2013

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

More information about the core-libs-dev mailing list