ConcurrentArrayList
Philipp
I can't find an implementation of a "ConcurrentArrayList", that is an
ArrayList which has the same concurrency properties as
ConcurrentHashMap has for HashMap:
- concurrent reads and writes with little contention
- safe interation while modification takess place (no
ConcurrentModificationException)
Is there such a thing?
Thanks Phil
John B. Matthews
<c52abccd-e618-4cc9...@o15g2000yqm.googlegroups.com>,
Philipp <djb...@gmail.com> wrote:
Depending on your needs, you might look at these:
<http://java.sun.com/javase/6/docs/api/java/util/Collections.html
#synchronizedList(java.util.List)>
<http://www.j2ee.me/javase/6/docs/api/java/util/concurrent/
CopyOnWriteArrayList.html>
--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
Philipp
> In article
> <c52abccd-e618-4cc9-b48e-de95c07e9...@o15g2000yqm.googlegroups.com>,
>
> Philipp <djb...@gmail.com> wrote:
> > I can't find an implementation of a "ConcurrentArrayList", that is an
> > ArrayList which has the same concurrency properties as
> > ConcurrentHashMap has for HashMap:
> > - concurrent reads and writes with little contention
> > - safe interation while modification takess place (no
> > ConcurrentModificationException)
>
> > Is there such a thing?
>
> Depending on your needs, you might look at these:
Yes thanks, I saw these
> <http://java.sun.com/javase/6/docs/api/java/util/Collections.html
> #synchronizedList(java.util.List)>
synchronizedList doesn't allow concurrent reads and writes. All access
is locked by a single mutex lock.
> <http://www.j2ee.me/javase/6/docs/api/java/util/concurrent/
> CopyOnWriteArrayList.html>
CopyOnWriteArrayList has very bad performance characteristics on
writes as the whole content gets copied on each insert.
My first request (concurrent) could be solved as simply as locking
with a ReadWriteLock instead of a mutex (although smarter solutions
exist). Regarding fail-safe Iterators, I'm a bit lost...
Phil
Tom Anderson
I don't think the arrayness of an ArrayList really admits an efficient
concurrent implementation. How would you handle inserts into the middle of
the list?
tom
--
Formal logical proofs, and therefore programs - formal logical proofs
that particular computations are possible, expressed in a formal system
called a programming language - are utterly meaningless. To write a
computer program you have to come to terms with this, to accept that
whatever you might want the program to mean, the machine will blindly
follow its meaningless rules and come to some meaningless conclusion. --
Dehnadi and Bornat
Philipp
Well, insert in the middle is not exactly efficient for an ArrayList
anyway. But I agree that you would need to write-lock all the higher
part of the array before performing the array copy. Note that the
lower part could still remain readable (but not writable).
Other methods do not suffer from these drawbacks: add(Object) set(int,
Object)...
Probably indexOf() would be impossible to use, because there's not
compound action you can make with it (no guarantee that the index is
still correct when you use it). But that's true for synchronizedList
as well; you need to sync on the object to make compound actions,
indexOf() in synchronizedList is useless alone.
Phil
Lew
> Well, insert in the middle is not exactly efficient for an ArrayList
> anyway. But I agree that you would need to write-lock all the higher
> part of the array before performing the array copy. Note that the
That doesn't make sense. If the array grows, it will be copied, and you'll
need to account for the whole array anyway.
> lower part could still remain readable (but not writable).
Only if the array isn't copied internally.
In which case you could read the entire original array while the CopyOnWrite
operation occurs.
> Other methods do not suffer from these drawbacks: add(Object) set(int,
> Object)...
add() most certainly does "suffer" from these "drawbacks". ArrayList
sometimes has to copy the entire internal array for an 'add()'.
set() has problems, too - if you're reading a list while another thread is
setting a value within it, you have a race condition or a possible failure to
pick up the new value by the reading thread, absent proper synchronization.
If the reading thread is iterating, it needs to lock the whole list or content
itself with stale values.
> Probably indexOf() would be impossible to use, because there's not
> compound action you can make with it (no guarantee that the index is
> still correct when you use it). But that's true for synchronizedList
> as well; you need to sync on the object to make compound actions,
> indexOf() in synchronizedList is useless alone.
That's a general truth about all synchronized accesses. Iteration over a
List, for example, unless you're willing to iterate over a possibly stale
copy, requires locking the whole list.
So to deal with operations on an array in a generally safe manner, given that
ArrayList is doing its own CopyOnWrite from time to time, you either need to
manually synchronize, and therefore fully analyze all usage for appropriate
locking patterns, or insist on an always-CopyOnWrite ArrayList.
Now if only java.util.concurrent sported a CopyOnWrite ArrayList ...
--
Lew
Philipp
> Philipp wrote:
> > Well, insert in the middle is not exactly efficient for an ArrayList
> > anyway. But I agree that you would need to write-lock all the higher
> > part of the array before performing the array copy. Note that the
>
> That doesn't make sense. If the array grows, it will be copied, and you'll
> need to account for the whole array anyway.
Note that to insert an element, two copies may happen. First to
increase the backing array size, second to move the objects to make
room for the insert. I'm not saying that both need to have the same
concurrency strategy.
As you point out, in the first stage (ensureCapacity), read calls
could still go through to the old array. This stage is "rare", as the
size increases by 50% on each growth request, so the overall
performance of a ConcurrentArrayList could still be much better than a
synchronizedList(), even if a complete lock of the array is needed
when the backing array grows.
When moving elements for the insert, read calls could be acceptable
for the lower part of the array (new or not).
>
> > Other methods do not suffer from these drawbacks: add(Object) set(int,
> > Object)...
>
> add() most certainly does "suffer" from these "drawbacks". ArrayList
> sometimes has to copy the entire internal array for an 'add()'.
see above
> set() has problems, too - if you're reading a list while another thread is
> setting a value within it, you have a race condition or a possible failure to
> pick up the new value by the reading thread, absent proper synchronization.
> If the reading thread is iterating, it needs to lock the whole list or content
> itself with stale values.
That's the whole point of the concurrent classes (as opposed to
Collections.synchronizedXXX). From the javadoc of ConcurrentHashMap:
"Iterators and Enumerations return elements reflecting the state of
the hash table at some point at or since the creation of the iterator/
enumeration." Yes it may be stale, but not very much. That's the price
for higher throughput and protection from ConcModifException.
> So to deal with operations on an array in a generally safe manner, given that
> ArrayList is doing its own CopyOnWrite from time to time, you either need to
> manually synchronize, and therefore fully analyze all usage for appropriate
> locking patterns, or insist on an always-CopyOnWrite ArrayList.
I still don't see anything in your arguments which fundamentally
forbids a thread-safe List with higher throughput than synchronizedList
(). You say that for some rare operations, the complete array must
locked. Well this does not remove the benefits of having concurrent
reads (get), writes (set) or addition at end of list add(Object).
The approach which is taken by ConcurrentHashMap, is to divide the
whole Map into Segments, the number of which you can specify at
construction time. This allows concurrent access by as many threads as
there are segments (at best). Why would it not be possible to have an
equivalent approach inside a ConcurrentArrayList? Where data is stored
in several arrays, for each of which a start index need to be
maintained. This would also remove the obligation to move the whole
array on an insert (only that base-index needs to be increased for
higher arrays).
Phil
Lew
> Hello
> I can't find an implementation of a "ConcurrentArrayList", that is an
> ArrayList which has the same concurrency properties as
> ConcurrentHashMap has for HashMap:
> - concurrent reads and writes with little contention
> - safe interation while modification takess place (no
> ConcurrentModificationException)
If you don't need random access, perhaps you can use
<http://java.sun.com/javase/6/docs/api/java/util/concurrent/
ConcurrentLinkedQueue.html>
--
Lew
markspace
> Hello
> I can't find an implementation of a "ConcurrentArrayList", that is an
> ArrayList which has the same concurrency properties as
> ConcurrentHashMap has for HashMap:
> - concurrent reads and writes with little contention
> - safe interation while modification takess place (no
> ConcurrentModificationException)
There are also skip lists, which are lists of lists:
<http://java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListSet.html>
<http://java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html>
I thought there was a tree version too, but I don't see it. I might be
thinking of the ConcurrentSkipListMap, which implements SortedMap. This
can be used for tree operations, just set the key and the value to the
same object.
Skip lists:
<http://www.cs.umd.edu/~pugh/>
Skip lists are also discussed in Java Concurrency in Practice, and
Sedgewick's Algorithms in C++, parts 1-4.
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>I can't find an implementation of a "ConcurrentArrayList", that is an
>ArrayList which has the same concurrency properties as
>ConcurrentHashMap has for HashMap:
>- concurrent reads and writes with little contention
>- safe interation while modification takess place (no
>ConcurrentModificationException)
see http://mindprod.com/jgloss/arraylist.html#THEADSAFETY
--
Roedy Green Canadian Mind Products
http://mindprod.com
"The industrial civilisation is based on the consumption of energy resources that are inherently limited in quantity, and that are about to become scarce. When they do, competition for what remains will trigger dramatic economic and geopolitical events; in the end, it may be impossible for even a single nation to sustain industrialism as we have know it in the twentieth century."
~ Richard Heinberg, The Party�s Over: Oil, War, and the Fate of Industrial Societies