Why the python threads is so frustrating?

Question

# test.py

import threading
import time
import random
from itertools import count

def fib(n):
  """fibonacci sequence
  """
  if n < 2:
    return n
  else:
    return fib(n - 1) + fib(n - 2)

if __name__ == '__main__':
    counter = count(1)
    start_time = time.time()
    def thread_worker():
        while True:
            try:
                # To simulate downloading
                time.sleep(random.randint(5, 10))
                # To simulate doing some process, will take about 0.14 ~ 0.63 second
                fib(n=random.randint(28, 31))
            finally:
                finished_number = counter.next()
                print 'Has finished %d, the average speed is %f per second.' % (finished_number, finished_number/(time.time() - start_time))

    threads = [threading.Thread(target=thread_worker) for i in range(100)]
    for thread in threads:
        thread.start()
    for thread in threads:
        thread.join()

The above is my test script. The thread_worker function takes at most 10.63 seconds to run once. I started 100 threads and expected the results is ~10 times per second. But the actual results were frustrating as following:

...
Has finished 839, the average speed is 1.385970 per second.
Has finished 840, the average speed is 1.386356 per second.
Has finished 841, the average speed is 1.387525 per second.
...

And if i commented "fib(n=random.randint(28, 31))" out, the results is expected:

...
Has finished 1026, the average speed is 12.982740 per second.
Has finished 1027, the average speed is 12.995230 per second.
Has finished 1028, the average speed is 13.007719 per second.
...

Has finished 1029, the average speed is 12.860571 per second.

My question is why it's so slow? I expected ~10 per second. How to make it faster? fib() function is just to simulate doing some process. e.g. extracting data from big html.

Answer 1

If I ask you to bake a cake and this takes you an hour and a half, 30 minutes for the dough, and 60 minutes in the oven, by your logic I would expect 2 cakes to take exactly the same amount of time. However there are some things you are missing. First if I do not tell you to bake two cakes in the beginning you have to make the dough twice, wich is now 2 times 30 minutes. now it actually takes you two hours ( you are free to work on the second cakeonce the first is in the oven).

Now lets assume i ask you to bake four cakes, again I do not allow you to make the dough once and split it for four cakes but you have to make it every time. The time we would expect now is 4*30minutes+ one hour for the alst cake to bake. Now for the sake of example assume your wife helps you, meaning you can do the dough for two cakes in parallel. THe time expected now is two hours, since every person has to bake two cakes. However the oven you have can only fit 2 cakes at a time. The time now becomes 30 minutes to makte the first dough, 1h hour to bake it, while you make the second dough, and after the first two cakes are done you put the next two cakes in the oven. WHich take a nother hour. If you add up the times you will see that it now took you 2 and a half hours.

If you take this further and I ask you for thousand cakes it will take you 500 and a half hours.

What has this to do with threads?

Think of making the dough as an initial computation that creates 100% cpu load. Your wife is the second core in a dual core. The oven is a resource, for which your programm generates 50% load.

In real threadiing you have some overhead to start the threads (I told you toi bake the cakes, you have to ask your wife for help whcih takes time), you compete for resources (i.e. memory access)(you and your wife can"t use the mixer at the same time). THe speedup is sub linear even if the number of threads is smaller than the number fo cores.

Furthermore smart programs download their code once (make the dough once), in the main thread and than duplicate it to threads, there is no nead to duplicate a computation. It does not make it faster just because you compute it twice.

Answer 2

While Manoj's answer is correct I think it needs more explanation. The python GIL is a mutex used in cpython that essentially will disable any parallel execution of python code. It does not make threaded code slower, nor does it actually prevent the OS from scheduling python threads simultaneously on all your cores. It just makes sure only one thread can execute python byte code at the same time.

What does this mean for you? You essentially do two things:

1. Sleep: While performing this function no python code is being executed, you just do nothing for 5 to 10 seconds. In the meantime any other thread can do exactly the same thing. Given that the overhead of calling time.sleep is negligible, you could have thousands of threads and it will probably still scale linearly like you expected. This is why everything works as soon as you comment out the fib line. Your average sleep time is 7.5s so you'd expect 15 calculations per second.
2. A calculation of the Fibonacci sequence: This one is the problem, it is actually executing python code. Let's say it takes about 0.5s per calculation. Now we've seen that you can only run one calculation at the time, no matter how many threads you have. Given that, you'd only get to 2 calculations per second.

Now, it's lower than 15 and 2, mainly because there is some overhead involved. First of all you are printing out data to the screen, this is almost always a surprisingly slow operation. Secondly, you're using 100 threads, which means that you're constantly switching between 100 thread stacks (even if they're sleeping), which is not a lightweight operation.

Note that threading can still be very useful though. For example for blocking calls where the execution is not done by python itself but some other resource. This could be waiting for the result of a socket, a sleep like in your example or even a calculation that is done outside of python itself (e.g. many numpy calculations).

Answer 3

Python threads use Global Interpretor Lock (GIL) to synchronize access of Python interpretor state. Compared to other threads like POSIX threads, usage of GIL can make Python threads significantly slower, especially when dealing with multiple cores. This is well-known. Here is a really good presentation on the same: www.dabeaz.com/python/UnderstandingGIL.pdf‎

Answer 4

You're looking for a faster solution. Memoizing results helps.

import collections
import functools


class Memoized(object):
    """Decorator. Caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned
    (not reevaluated).
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if not isinstance(args, collections.Hashable):
            # uncacheable. a list, for instance.
            # better to not cache than blow up.
            return self.func(*args)
        if args in self.cache:
            return self.cache[args]
        else:
            value = self.func(*args)
            self.cache[args] = value
            return value

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)


if __name__ == '__main__':
    @Memoized
    def fibonacci(n):
        """Return the nth fibonacci number

        :param n: value
        """
        if n in (0, 1):
            return n
        return fibonacci(n - 1) + fibonacci(n - 2)

    print(fibonacci(35))

Try to run it with and without the @Memoized decorator.

Recipe taken from http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize.