ConcurrentModificationException
Fredrik Staxeng
Yes, this is a homework question. :-) No threads involved yet.
I have a specification to implement which calls for a collection of
objects to to receive a method call tick() each. In that method call,
there is supposed to be an inherited method remove(), that removes
the object from that collection.
Implicit in the specifiacation is that other objects also can be
removed.
Obviously an ArrayList won't work, but imagine my surprise when
LinkedList didn't work either. I got a ConcurrentModificationException.
This seems to be a bit overkill, since iterators for linked lists
are naturally stable.
Now, I can't be the only one wanting to do this.
What is the recommened approach?
a) Keep a list of deleted objects and remove them after the iteration.
b) Design your own collection?
--
Fredrik Stax\"ang | rot13: sf...@hcqngr.hh.fr
Gordon Beaton
> Yes, this is a homework question. :-)
Inte din, väl?
/gordon
--
[ do not send me private copies of your followups ]
g o r d o n . b e a t o n @ e r i c s s o n . c o m
Michael Borgwardt
> Obviously an ArrayList won't work, but imagine my surprise when
> LinkedList didn't work either. I got a ConcurrentModificationException.
> This seems to be a bit overkill, since iterators for linked lists
> are naturally stable.
Are they? What if the element you're looking at or the one after it
is the one being removed?
> Now, I can't be the only one wanting to do this.
> What is the recommened approach?
>
> a) Keep a list of deleted objects and remove them after the iteration.
> b) Design your own collection?
Neither. Use a ListIterator and its remove() method.
Fredrik Staxeng
>Fredrik Staxeng wrote:
>> Obviously an ArrayList won't work, but imagine my surprise when
>> LinkedList didn't work either. I got a ConcurrentModificationException.
>> This seems to be a bit overkill, since iterators for linked lists
>> are naturally stable.
>
>Are they? What if the element you're looking at or the one after it
>is the one being removed?
prev->next = next ;
next->prev = prev ;
I think this works even under those circumstances.
>> Now, I can't be the only one wanting to do this. What is the
>> recommened approach? a) Keep a list of deleted objects and remove
>> them after the iteration.
>> b) Design your own collection?
>
>Neither. Use a ListIterator and its remove() method.
I need to be able to delete other objects also.
Michael Borgwardt
>>Are they? What if the element you're looking at or the one after it
>>is the one being removed?
>
>
> prev->next = next ;
> next->prev = prev ;
>
> I think this works even under those circumstances.
No. At least the semantics are not anymore intuitive,
the iterator might skip elements or return a element
twice.
>>Neither. Use a ListIterator and its remove() method.
>
> I need to be able to delete other objects also.
Note that ListIterator allows you to go back as well as forward.
If that's not sufficient, then I'd say the best solution is to
collect the indexes of the elements that are to be removed and
then do a second iteration using remove().
Fredrik Staxeng
>Fredrik Staxeng wrote:
>>>Are they? What if the element you're looking at or the one after it
>>>is the one being removed?
>> prev->next = next ;
>> next->prev = prev ;
>> I think this works even under those circumstances.
>
>No. At least the semantics are not anymore intuitive,
>the iterator might skip elements or return a element
>twice.
Well, you are right. Calling next() moves the iterator too early,
so the next element will be returned even if it is deleted.
I don't see how the same element could be returned twice though,
or how an element might be skipped.
>>>Neither. Use a ListIterator and its remove() method.
>> I need to be able to delete other objects also.
>
>Note that ListIterator allows you to go back as well as forward.
>If that's not sufficient, then I'd say the best solution is to
>collect the indexes of the elements that are to be removed and
>then do a second iteration using remove().
I think I will collect pairs of <Object o, boolean deleted>.
This is not what bugs me, it's that I need to have a flag that
tells the remove routine if there is an active iteration.
Michael Borgwardt
> I don't see how the same element could be returned twice though,
> or how an element might be skipped.
Not due to removing an element, but an inserted element could be skipped.
For an element to be returned twice, concurrent modification from
a separate thread is necessary.
>>Note that ListIterator allows you to go back as well as forward.
>>If that's not sufficient, then I'd say the best solution is to
>>collect the indexes of the elements that are to be removed and
>>then do a second iteration using remove().
>
>
> I think I will collect pairs of <Object o, boolean deleted>.
> This is not what bugs me, it's that I need to have a flag that
> tells the remove routine if there is an active iteration.
Ah, so you *do* have two threads accessing the list concurrently?
In that case, why not use synchronization?
Fredrik Staxeng
>Fredrik Staxeng wrote:
>> I don't see how the same element could be returned twice though,
>> or how an element might be skipped.
>
>Not due to removing an element, but an inserted element could be skipped.
>For an element to be returned twice, concurrent modification from
>a separate thread is necessary.
I have not given any futher thought to how LinkedList works. I chose
to implement a StableList class, with iterator that keep pointing
to the same element even in the presence of insertions and removals.
It was much easier that I thought it would be when I looked at
the LinkedList source code.
What happens when the element the iterator is pointing at is removed?
The next and prev links are still valid, so the element that
was adjacent when the element was in the list is returned when
you call next. Of course, this means that *iter == *(iter.next().prev()),
does not necessarily hold.
What happens when an element is removed or inserted the links are
updated so that the iterators will return the current following
or preceding element.
>> I think I will collect pairs of <Object o, boolean deleted>. This is
>> not what bugs me, it's that I need to have a flag that
>> tells the remove routine if there is an active iteration.
>
>Ah, so you *do* have two threads accessing the list concurrently?
>In that case, why not use synchronization?
No, in the object sys carrying the list:
while(iter.hasNext()) {
e = iter.next();
e.tick();
}
In the element object e
tick() {
if(--life == 0)
sys.remove(e)
}
But I want the sys.remove() method to work immediately when called outside
of an iteration.
But my approach raises some questions. StableList extends
AbstractSequentialList, and inherits most methods from that. The
iterator implements the ListIterator interface.
Of course the iterators aren't fail-fast. They don't fail at at all.
Is this totally unthinkable in Java?
The iterator does not implement the previousIndex or nextIndex
operations. I could do that in linear time, but I want to see
first when those methods are needed.
The StableList class does not implement size(). Of course that
could easily be done, but then I would not have discovered that
the add() method from AbstractSequentialList calls size().
And yes, thread synchronization. I have put everything that accesses
any fields in the list object, or in any of the nodes, inside
synchronize blocks. This includes the iterator methods. I use the list
object to synchronize on. (The single lock approach to the deadlock
problem).
I am thinking of changing this approach. I am looking into
Collections.synchronizedList approach.
Michael Borgwardt
> What happens when an element is removed or inserted the links are
> updated so that the iterators will return the current following
> or preceding element.
How do you do that? By keeping a reference to all active iterators,
testing and updating them all?
> Of course the iterators aren't fail-fast. They don't fail at at all.
> Is this totally unthinkable in Java?
No, but fail-fast is thought to be preferable because otherwise,
concurrent modification can lead to unexpected results, and
the nastiest kind of bug: race conditions.
Steve Horsley
So the object might choose to remove itself from the Collection during
the call to tick()? In that case, I would be inclined to make a new
temporary Collection based on the old one, and then iterate the temporary
one. That way they are free to modify the original Collection in any
way they like without upsetting your Iterator.
Collection temp = new ArrayList(myCollection);
Iterator i = temp.iterator();
while(i.hasNext()) {
...
}
BTW, regarding concurrent modification of a LinkedList being stable,
I believe that ConcurrentModificationException was really meant for
multi-threading, where all bets are off.
Steve
Fredrik Staxeng
>So the object might choose to remove itself from the Collection during
>the call to tick()? In that case, I would be inclined to make a new
>temporary Collection based on the old one, and then iterate the temporary
>one. That way they are free to modify the original Collection in any
>way they like without upsetting your Iterator.
>
> Collection temp = new ArrayList(myCollection);
> Iterator i = temp.iterator();
> while(i.hasNext()) {
> ...
> }
That is simple, elegant, and wonderfully inefficient way, if you
don't mind me saying so.
>BTW, regarding concurrent modification of a LinkedList being stable,
>I believe that ConcurrentModificationException was really meant for
>multi-threading, where all bets are off.
Yes, but I get it even for a single thread. You have probably seen my
later messages, and I believe that I have a safe way of doing
modification even from other threads.
BTW, comments like "all bets are off" scare me a bit. Does it mean that
people avoid that part of the language?
Carl Howells
> steve....@cwcom.cwplc.com (Steve Horsley) writes:
>
>
>>So the object might choose to remove itself from the Collection during
>>the call to tick()? In that case, I would be inclined to make a new
>>temporary Collection based on the old one, and then iterate the temporary
>>one. That way they are free to modify the original Collection in any
>>way they like without upsetting your Iterator.
>>
>> Collection temp = new ArrayList(myCollection);
>> Iterator i = temp.iterator();
>> while(i.hasNext()) {
>> ...
>> }
>
>
> That is simple, elegant, and wonderfully inefficient way, if you
> don't mind me saying so.
>
Hmm... I mind it. Because it's not true. From a big-O standpoint, the
iteration of the list dominates the copying trivially. From a practical
standpoint, that's also true unless you're doing basically no work per
object.
Fredrik Staxeng
>Fredrik Staxeng wrote:
>> steve....@cwcom.cwplc.com (Steve Horsley) writes:
>>
>>> So the object might choose to remove itself from the Collection
>>> during the call to tick()? In that case, I would be inclined to
>>> make a new temporary Collection based on the old one, and then
>>> iterate the temporary
>>>one. That way they are free to modify the original Collection in any
>>>way they like without upsetting your Iterator.
>>>
>>> Collection temp = new ArrayList(myCollection);
>>> Iterator i = temp.iterator();
>>> while(i.hasNext()) {
>>> ...
>>> }
>> That is simple, elegant, and wonderfully inefficient way, if you
>> don't mind me saying so.
>>
>
>Hmm... I mind it. Because it's not true. From a big-O standpoint,
>the iteration of the list dominates the copying trivially. From a
The copying is linear in time, and the iteration is also linear,
unless the work you do per object is higher than constant, so
this way does not increase the Big-O, timewise.
However, in space you go from O(1) to O(n). You get to O(n^3) by
accumulating O(n):s by accident.
>practical standpoint, that's also true unless you're doing basically
>no work per object.
True for time overhead.
The space overhead is likely to be the same as putting a deleted
flag into the objects. It is better than my proposed solution of
collecting pairs of <Object, boolean>. But the overhead is not
static, it's per iteration loop. In this case the iteration will
be called repeatedly.
It suffers from a problem for it's intended use, namely that
deleted objects can get one more tick. I forgot to mention this
requirement.
I know that this does not matter for the problem at hand, but this
is just a learning excercise. I have met both time and space
performance problems in practice, and I would like to know how
to deal with them in Java.
If you think that garbage collector in Java can be expected to
be good enough that generating lots of garbage is not a problem,
then it would be good to know that.
On the other hand it would, even at this early stage, would be good to
know about time and memory profilers.
Steve Horsley
> Carl Howells <chow...@cs.uoregon.edu> writes:
>
> >Fredrik Staxeng wrote:
> >> steve....@cwcom.cwplc.com (Steve Horsley) writes:
> >>
> >>> So the object might choose to remove itself from the Collection
> >>> during the call to tick()? In that case, I would be inclined to
> >>> make a new temporary Collection based on the old one, and then
> >>> iterate the temporary
> >>>one. That way they are free to modify the original Collection in any
> >>>way they like without upsetting your Iterator.
> >>>
> >>> Collection temp = new ArrayList(myCollection);
> >>> Iterator i = temp.iterator();
> >>> while(i.hasNext()) {
> >>> ...
> >>> }
> unless the work you do per object is higher than constant, so
> this way does not increase the Big-O, timewise.
>
> However, in space you go from O(1) to O(n). You get to O(n^3) by
> accumulating O(n):s by accident.
>
creates 3 new Objects per iteration of the list:
* an ArrayList, which contains
* an Object[] full of references to your Objects
* an Iterator (which you were going to create anyway).
Remember that this is using a *shallow* copy of the list.
This may be where your confusion lies.
<snip>
> It suffers from a problem for it's intended use, namely that
> deleted objects can get one more tick. I forgot to mention this
> requirement.
>
In what way? Are objects in the list going to delete _other_ objects
from the list? If so then yes, using a temporary snapshot list will
tick() objects deleted during the sweep. Also, clearly, we cannot
unTick() objects that get deleted _after_ being tick()ed.
Steve
Fredrik Staxeng
>Fredrik Staxeng <fst...@update.uu.se> wrote in message news:<1mptszc...@Tempo.Update.UU.SE>...
>> Carl Howells <chow...@cs.uoregon.edu> writes:
>>
>> The copying is linear in time, and the iteration is also linear,
>> unless the work you do per object is higher than constant, so
>> this way does not increase the Big-O, timewise.
>>
>> However, in space you go from O(1) to O(n). You get to O(n^3) by
>> accumulating O(n):s by accident.
>>
>Actually, I think the space usage is quite reasonable too. This only
>creates 3 new Objects per iteration of the list:
> * an ArrayList, which contains
> * an Object[] full of references to your Objects
> * an Iterator (which you were going to create anyway).
>Remember that this is using a *shallow* copy of the list.
>This may be where your confusion lies.
I know it's a shallow copy. I am not confused :-)
>> It suffers from a problem for it's intended use, namely that
>> deleted objects can get one more tick. I forgot to mention this
>> requirement.
>>
>In what way? Are objects in the list going to delete _other_ objects
>from the list? If so then yes, using a temporary snapshot list will
>tick() objects deleted during the sweep. Also, clearly, we cannot
>unTick() objects that get deleted _after_ being tick()ed.
Yes, that is what is going to happen.
Anyway, the consensus seem to be that a temporary Collection is
the Java way of doing it. There seems to be little interest
in my linked list with stable iterators, and it seems like it
is foreign concept to Java programmers. They start talking about
threads (are the Java spinlocks really that bad?) and that
iterators are supposed to failfast (it's good fail fast, but
what about not failing at all?)