List iterator thread safety

Discussion in 'Python' started by Emanuele D'Arrigo, Aug 24, 2009.

  1. 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
    Emanuele D'Arrigo, Aug 24, 2009
    #1
    1. Advertising

  2. Emanuele D'Arrigo

    Aahz Guest

    In article <>,
    Emanuele D'Arrigo <> wrote:
    >
    >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.
    --
    Aahz () <*> http://www.pythoncraft.com/

    "I support family values -- Addams family values" --www.nancybuttons.com
    Aahz, Aug 27, 2009
    #2
    1. Advertising

  3. On Aug 27, 2:01 am, (Aahz) wrote:
    > 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
    Emanuele D'Arrigo, Aug 27, 2009
    #3
  4. Emanuele D'Arrigo

    Peter Otten Guest

    Emanuele D'Arrigo wrote:

    > On Aug 27, 2:01 am, (Aahz) wrote:
    >> 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.


    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
    Peter Otten, Aug 27, 2009
    #4
  5. Emanuele D'Arrigo

    Carl Banks Guest

    On Aug 27, 5:03 am, "Emanuele D'Arrigo" <> wrote:
    > On Aug 27, 2:01 am, (Aahz) wrote:
    >
    > > 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.


    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
    Carl Banks, Aug 27, 2009
    #5
  6. On Thursday 27 August 2009 15:26:04 Carl Banks wrote:

    > 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
    Hendrik van Rooyen, Aug 27, 2009
    #6
  7. Emanuele D'Arrigo

    Carl Banks Guest

    On Aug 27, 7:25 am, Hendrik van Rooyen <>
    wrote:
    > On Thursday 27 August 2009 15:26:04 Carl Banks wrote:
    >
    > > 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.


    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
    Carl Banks, Aug 27, 2009
    #7
  8. On Thursday 27 August 2009 16:50:16 Carl Banks wrote:
    > On Aug 27, 7:25 am, Hendrik van Rooyen <>
    > wrote:


    > > 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.


    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
    Hendrik van Rooyen, Aug 28, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hans

    What is thread safety?

    Hans, Oct 11, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    570
    Sahil Malik
    Oct 12, 2004
  2. George Ter-Saakov

    LiteralControl thread safety.

    George Ter-Saakov, Apr 5, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    318
    Martin Dechev
    Apr 6, 2004
  3. Simon Harvey

    A thread safety question

    Simon Harvey, Aug 6, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    391
    Alvin Bruney [MVP]
    Aug 6, 2004
  4. Replies:
    6
    Views:
    628
    Jim Langston
    Oct 30, 2005
  5. David Bilsby
    Replies:
    5
    Views:
    2,025
    David Bilsby
    Oct 9, 2007
Loading...

Share This Page