Threading in Python - What am I missing?

Question

This is my first attempt at threads in Python... And it failed miserably :) I wanted to implement a basic critical zone problem, and found that this code actually doesn't present a problem.

The question: why don't I have problems with the counter increment? Shouldn't the counter have random values after a run? I can only explain this if the incrementing is already executed atomically, or if the threads are not concurrent...

import threading
import time

turnstile_names = ["N", "E", "S", "W"]
count = 0

class Counter(threading.Thread):
    def __init__(self, id):
        threading.Thread.__init__(self)
        self.id = id

    def run(self):
        global count
        for i in range(20):
            #self.sem.acquire()
            count = count + 1
            #self.sem.release()

def main():
    sem = threading.Semaphore(1)

    counters = [Counter(name) for name in turnstile_names]

    for counter in counters:
        counter.start()

    # We're running!

    for counter in counters:
        counter.join()

    print count
    return 0

if __name__ == '__main__':
    main()

Notes: I left the acquire() and release() calls commented to check the difference. I tried to pace the thread adding small sleeps after the increment - no difference

Solution/tests: Thanks Kevin (see accepted answer below). I was just testing changing the loop variable and got this:

Loops    Result
20       99% of the time 80. Sometimes 60.
200      99% of the time 800. Sometimes 600.
2000     Maybe 10% of the time different value
20000    Finally... random numbers! I've yet to see 80000 or 60000.
         All numbers are now random, as originally expected.

I suspect this seems to mean that the thread overhead is in the order of 10^4 increment operations.

Another interesting test (well, in my opinion, at least):

I added time.sleep(random.random()/divisor) after the increment and found, with the loop count again to 20:

divisor     result
100         always 4, so the race condition is always there.
1000        95% of the time 4, sometimes 3 or 5 (once 7)
10000       99% of the time NOT 4, varying from 4 to 13
100000      basically same as 10000
1000000     varying from 10 to 70
10000000... same as previous... (even with time.sleep(0))

Answer 1

If you increase the number of iterations per-thread:

def run(self):
    global count
    for i in range(100000):
        #self.sem.acquire()
        count = count + 1
        #self.sem.release()

Then a race condition does occur. Your script prints e.g. 175165, when 400000 would be expected. This suggests that incrementing is not atomic.

---

Additional evidence that incrementing isn't atomic: the behavior of threads in CPython is mandated by the Global Interpreter Lock. According to the wiki,

the global interpreter lock, or GIL, is a mutex that prevents multiple native threads from executing Python bytecodes at once.

If the GIL has bytecode-level granularity, then we expect incrementing to not be atomic, because it takes more than one bytecode to execute, as demonstrated by the dis module:

>>> import dis
>>> def f():
...     x = 0
...     x = x + 1
...
>>> dis.dis(f)
  2           0 LOAD_CONST               1 (0)
              3 STORE_FAST               0 (x)

  3           6 LOAD_FAST                0 (x)
              9 LOAD_CONST               2 (1)
             12 BINARY_ADD
             13 STORE_FAST               0 (x)
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE

Here, the act of incrementing is performed by byte codes 6 through 13.

---

So why did the original code not exhibit the race condition? This seems to be due to the short life expectancy of each thread - by looping only 20 times, each thread would complete its work and die before the next thread started its own work.

Answer 2

In Cpython, thread safety is determined by atomicity (a single bytecode is not interrupted), the GIL (python locks a single thread for about 100 "ticks") and luck. Decompiling a simpler function,

>>> import dis
>>> count = 0
>>> def x():
...     count = count + 1
... 
>>> dis.dis(x)
  2           0 LOAD_FAST                0 (count)
              3 LOAD_CONST               1 (1)
              6 BINARY_ADD          
              7 STORE_FAST               0 (count)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE        

We see that the code can be interrupted between a load and a store. This could mean that one thread loads a value, is suspended and eventually the overwrites a larger value with its result.

Now luck comes into play. Doing the operation 20 times isn't much. Lets change your code to take the count as a parameter and see what happens with larger values

import threading
import time
import sys

turnstile_names = ["N", "E", "S", "W"]
count = 0

class Counter(threading.Thread):
    def __init__(self, id):
        threading.Thread.__init__(self)
        self.id = id

    def run(self):
        global count
        for i in range(int(sys.argv[1])):
            #self.sem.acquire()
            count = count + 1
            #self.sem.release()

def main():
    sem = threading.Semaphore(1)

    counters = [Counter(name) for name in turnstile_names]

    for counter in counters:
        counter.start()

    # We're running!

    for counter in counters:
        counter.join()

    print count
    return 0

if __name__ == '__main__':
    main()

One one run I got:

td@timsworld2:~/tmp/so$ python count.py 1
4
td@timsworld2:~/tmp/so$ python count.py 2
8
td@timsworld2:~/tmp/so$ python count.py 20
80
td@timsworld2:~/tmp/so$ python count.py 200
749
td@timsworld2:~/tmp/so$ python count.py 2000
4314

With 2000 in 4 threads, I've lost nearly half the values.