Immutability and thread safety in Python

Question

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

Answer 1

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.

Answer 2

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])