views:

809

answers:

2

I'm cleaning some of the Python code I wrote when I was...not as knowledgeable. Primarily I am killing some of the complexity that stemmed from an incomplete understanding of threading in Python. I need to make a list of items thread-safe, and I'd like to do it via immutable lists, instead of the usual locking approach. I know that immutable objects are very special with regard to threading because all the thread-safety issues surrounding incomplete state changes simply disappear.

So, I ask: is the following code thread-safe?

class ImmutableList(object):
    def __init__(self):
        self._list = ()

    def __iter__(self):
        return self._list.__iter__()

    def append(self, x):
        self._list = self._list + tuple([x])

I think it is, because a new list is constructed each time. If the list is updated while another thread is iterating through it, the old list will continue to be used for the remainder of the iteration. This is fine by me, but may not be for everyone.

Also, is this a good idea? I only want to apply this to a few situations where the list size is small, and the lists aren't changed much (event listeners spring to mind).

+10  A: 

First of all, appending to a list is already thread-safe in the CPython reference implementation of the Python programming language. In other words, while the language specification doesn't require that the list class be thread-safe, it is anyway. So unless you're using Jython or IronPython or some other Python implementation like that, then you're fine.

Second, you'd also need to overload the other list operations, such as __setitem__ and __setslice__, etc. I'm assuming that your implementation handles this.

Finally, the answer to your question is no: your code isn't thread safe. Consider the following situation:

  • Your list contains (5, 6)
  • Thread 1 tries to append 7, and Thread 2 tries to append 8
  • Thread 1 constructs another tuple (5, 6, 7) and before that can be assigned to _list, there's a context switch
  • Thread 2 performs its assignment, so the list is now (5, 6, 8)
  • Thread 1 gets control of the CPU back and assigns to _list, overwriting the previous append. The list is now (5, 6, 7) and the 8 has been lost.

The moral of this story is that you should use locking and avoid cleverness.

Eli Courtwright
Never thought of this case...thanks!
Matt Green
+1: Just use locks.
S.Lott
+3  A: 

A true immutable list implementation will not allow the underlying list structure to change, like you are here. As @[Eli Courtwright] pointed out, your implementation is not thread safe. That is because it is not really immutable. To make an immutable implementation, any methods that would have changed the list, would instead return a new list reflecting the desired change.

With respect to your code example, this would require you to do something like this:

class ImmutableList(object):
  def __init__(self):
    self._list = ()

  def __iter__(self):
    return self._list.__iter__()

  def append(self, x):
    return self._list + tuple([x])
1800 INFORMATION
+1 for your example of how immutable data structures really work. However, I should point out that your example would be unhelpful to Matt Green, who needs a data structure that can be concurrently modified by multiple threads.
Eli Courtwright
I don't think that is what he really needs, actually it is difficult to tell what it is he needs from the description, but since he is talking about immutable structures it seems like he either doesn't want to concurrently modify it, or he doesn't really understand the correct usage for immutable
1800 INFORMATION