Using threads for a for-loop in Python

Question

item_list = [("a", 10, 20), ("b", 25, 40), ("c", 40, 100), ("d", 45, 90),
             ("e", 35, 65), ("f", 50, 110)] #weight/value
results = [("", 0, 0)]  #an empty string and a 2-tupel to compare with the new
                        #values

class Rucksack(object):
    def __init__(self, B):
        self.B = B   #B=maximum weight
        self.pack(item_list, 0, ("", 0, 0))

    def pack(self, items, n, current):  
        n += 1   #n is incremented, to stop the recursion, if all
        if n >= len(items) - 1:
            if current[2] > results[0][2]:
                #substitutes the result, if current is bigger and starts no
                #new recursion
                results[0] = current
        else:
            for i in items:
                if current[1] + i[1] <= self.B and i[0] not in current[0]:
                    #first condition: current + the new value is not bigger
                    #than B; 2nd condition: the new value is not the same as
                    #current
                    i = (current[0] + " " + i[0], current[1] + i[1],
                         current[2] + i[2])
                    self.pack(items, n, i)
                else:
                    #substitutes the result, if current is bigger and starts no
                    #new recursion
                    if current[2] > results[0][2]:
                        results[0] = current

rucksack1 = Rucksack(100)

This is a small algo for the knapsack-problem. I have to parallelize the code somehow, but I don't get the thread module so far. I think the only place to work with parallelisation is the for-loop, right? So, I tried this:

def run(self, items, i, n, current):
    global num_threads, thread_started
    lock.acquire()
    num_threads += 1
    thread_started = True
    lock.release()
    if current[1] + i[1] <= self.B and i[0] not in current[0]:
        i = (current[0] + " " + i[0], current[1] + i[1], current[2] + i[2])
        self.pack(items, n, i)
    else:
        if current[2] > results[0][2]:
            results[0] = current
    lock.acquire()
    num_threads -= 1
    lock.release()

but the results are strange. Nothing happens and if I make a keyboardinterrupt, the result is correct, but thats definetly not the sense of the implementation. Can you tell me what is wrong with the second code or where else I could use perallelisation soundly. Thanks.

It makes absolutely no sense to parallelize a CPU-bound task with threads in Python, due to GIL. — bereal
– bereal, Commented Jan 29, 2013 at 20:43
First, are you actually using the thread module? If so, don't, use threading instead, as the very top of the docs tells you to. But, more importantly, you're not creating any threads here. Just adding locks to single-threaded code just makes slower single-threaded code for no benefit. — abarnert
– abarnert, Commented Jan 29, 2013 at 21:24
+1 for @bereal comment, plus I can't be bothered to look at wall-of-gunge array code with i,n,etc. indexes. — Martin James
– Martin James, Commented Jan 30, 2013 at 0:52

abarnert · Accepted Answer · 2013-01-30 19:52:20Z

First, since your code is CPU-bound, you will get very little benefit from using threads for parallelism, because of the GIL, as bereal explains. Fortunately, there are only a few differences between threads and processes—basically, all shared data must be passed or shared explicitly (see Sharing state between processes for details).

Second, if you want to data-parallelize your code, you have to lock all access to mutable shared objects. From a quick glance, while items and current look immutable, the results object is a shared global that you modify all over the place. If you can change your code to return a value up the chain, that's ideal. If not, if you can accumulate a bunch of separate return values and merge them after processing is finished, that's usually good too. If neither is feasible, you will need to guard all access to results with a lock. See Synchronization between processes for details.

Finally, you ask where to put the parallelism. The key is to find the right dividing line between independent tasks.

Ideally you want to find a large number of mid-sized jobs that you can queue up, and just have a pool of processes each picking up the next one. From a quick glance, the obvious places to do that are either at the recursive call to self.pack, or at each iteration of the for i in items: loop. If they actually are independent, just use concurrent.futures, as in the ProcessPollExecutor example. (If you're on Python 3.1 or earlier, you need the futures module, because it's not built into the stdlib.)

If there's no easy way to do this, often it's at least possible to create a small number (N or 2N, if you have N cores) of long-running jobs of about equal size, and just give each one its own multiprocessing.Process. For example:

n = 8
procs = [Process(target=rucksack.pack, args=(items[i//n:(i+1)//n],)) for i in range(n)]

One last note: If you finish your code and it looks like you've gotten away with implicitly sharing globals, what you've actually done is written code that usually-but-not-always works on some platforms, and never on others. See the Windows section of the multiprocessing docs to see what to avoid—and, if possible, test regularly on Windows, because it's the most restrictive platform.

You also ask a second question:

Can you tell me what is wrong with the second code.

It's not entirely clear what you were trying to do here, but there are a few obvious problems (beyond what's mentioned above).

You don't create a thread anywhere in the code you showed us. Just creating variables with "thread" in the name doesn't give you parallelism. And neither does adding locks—if you don't have any threads, all locks can do is slow you down for no reason.
From your description, it sounds like you were trying to use the thread module, instead of threading. There's a reason that the very top of the thread documentation tells you to not use it and use threading instead.
You have a lock protecting your thread count (which shouldn't be needed at all), but no lock protecting your results. You will get away with this in most cases in Python (because of the same GIL issue mentioned above—your threads are basically not going to run concurrently, and therefore they're not going to have races), but it's still a very bad idea (especially if you don't understand exactly what those "most cases" are).

However, it looks like your run function is based on the body of the for i in items: loop in pack. If that's a good place to parallelize, you're in luck, because creating a parallel task out of each iteration of a loop is exactly what futures and multiprocessing are best at. For example, this code:

results = []
for i in items:
    result = dostuff(i)
    results.append(result)

… can, of course, be written as:

results = map(dostuff, items)

And it can be trivially parallelized, without even having to understand what futures are about, as:

pool = concurrent.futures.ProcessPoolExecutor()
results = pool.map(dostuff, items)

Collectives™ on Stack Overflow

Using threads for a for-loop in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related