List iterator thread safety

[Emanuele D'Arrigo]

Let's say I have a list accessed by two threads, one removing list
items via "del myList[index]" statement the other iterating through
the list and printing out the items via "for item in myList:"
statement. Am I right to say this -won't- generate exceptions because
the list iterator is not concerned with the list changing in size
under its nose? Or are there pitfalls I should be aware of?

Manu

 

[Aahz]

Let's say I have a list accessed by two threads, one removing list
items via "del myList[index]" statement the other iterating through
the list and printing out the items via "for item in myList:"
statement. Am I right to say this -won't- generate exceptions because
the list iterator is not concerned with the list changing in size
under its nose? Or are there pitfalls I should be aware of?

Well, I'm not sure about exceptions, but you almost certainly won't get
the results you want.

 

[Emanuele D'Arrigo]

Well, I'm not sure about exceptions, but you almost certainly won't get
the results you want.

What I'd like in this context is to iterate through the items in the
list without processing the same item twice and without skipping item
that are in front of the current iterator position. Somehow I can't
quite prove to myself if this is possible or not over multiple
threads. I.e. a dictionary will throw an exception about the object
changing size while iterating through it. A list doesn't, hence the
question.

Manu

 

[Peter Otten]

What I'd like in this context is to iterate through the items in the
list without processing the same item twice and without skipping item
that are in front of the current iterator position. Somehow I can't
quite prove to myself if this is possible or not over multiple
threads. I.e. a dictionary will throw an exception about the object
changing size while iterating through it. A list doesn't, hence the
question.

This is not even possible in a single thread:

items = [1, 2, 3]
for i in items:

.... print i
.... if 1 in items: items.remove(1)
....
1
3

Basically a list iterator is just a list reference and an index into that
list. No effort is made to keep track of added or removed items.

Peter

 

[Carl Banks]

What I'd like in this context is to iterate through the items in the
list without processing the same item twice and without skipping item
that are in front of the current iterator position. Somehow I can't
quite prove to myself if this is possible or not over multiple
threads. I.e. a dictionary will throw an exception about the object
changing size while iterating through it. A list doesn't, hence the
question.

Deleting items from a list while iterating over it is a bad idea,
exceptions or not.

Hmm, this sounds like something someone might do for a game. You have
a list of objects, and in a given time step you have to iterate
through the list and update each object. Problem is, one of the
enemies is kill before you get to it, so you would like to remove the
object from the list while iterating. Not an easy problem.

For this simple appeoach, I would suggest writing a custom container
(with an underlying list) with state to keep track of the current
iterating position. Whenever an item is removed the index is modified
(so as to prevent skipping objects), and because you are keeping track
of the index yourself there is an iterator that might throw an
exception.

With threads, you would need to use a Condition or something to
sychronize access to the object.


Carl Banks

 

[Hendrik van Rooyen]

Deleting items from a list while iterating over it is a bad idea,
exceptions or not.

Hmm, this sounds like something someone might do for a game. You have
a list of objects, and in a given time step you have to iterate
through the list and update each object. Problem is, one of the
enemies is kill before you get to it, so you would like to remove the
object from the list while iterating. Not an easy problem.

Its not too bad - if you crook a bit - the trick is that you iterate over the
list backwards when you are removing stuff based on index, so that the
remainder does not get jumbled up by losing their positions, as happens when
you do it going forwards.

- Hendrik

 

[Carl Banks]

Its not too bad - if you crook a bit - the trick is that you iterate over the
list backwards when you are removing stuff based on index, so that the
remainder does not get jumbled up by losing their positions, as happens when
you do it going forwards.

That's only if you remove the "current item". The OP has different
threads accessing the list at the same time, so I have to assume that
item being remove is not necessarily the current iteration.


Getting back to the game example, suppose your "list of objects in the
scene" looks like this:

[ HandsomeHero, Enemy1, Bullet1, Enemy2, Bullet2, Enemy3]

It might happen that Bullet1.update() detects a collision with Enemy2,
thus killing Enemy2, which means Enemy2 would have to be removed
before the next iteration. Otherwise you're updating a zombie.
(Which, parenthetically, is another approach.)

Conversely, suppose Bullet2.update() detects a collision with Enemy1,
and Enemy1 is removed from the list. Then Enemy3 is going to be
skipped.

In order to handle both cases (where an item could be removed ahead of
or before the current item), you have to keep track of the current
index and adjust it. A list iterator won't work.


For the record, I use a more sophisticated system that explicitly
resolves cause and effect in my games. That's probably beyond the
scope of this thread, though.


Carl Banks

 

[Hendrik van Rooyen]

On Aug 27, 7:25 am, Hendrik van Rooyen <[email protected]>
wrote:

That's only if you remove the "current item". The OP has different
threads accessing the list at the same time, so I have to assume that
item being remove is not necessarily the current iteration.

Sorry - I did not pick that up - The threading screws the simple scheme up.
In such a situation I would have a thread to run the list - almost like a mini
data base - and link the lot together using queues. It is still a bugger,
though, as one thread could try to kill something that is "checked out" to
another one. Then you have to take hard decisions, and a list is the wrong
structure, because you have to remember state. Better to use a dict, so you
can at least mark a thing as "dead", and check for that before you update.

8<-------- example --------

For the record, I use a more sophisticated system that explicitly
resolves cause and effect in my games. That's probably beyond the
scope of this thread, though.

Yes - it is hairy - and there are probably as many different solutions as
there are programmers, and then some.

- Hendrik