Threading in python using a generator

Question

I am creating an algorithm that brute force searches for conditions of a 3x3 matrix using a generator object to create all possible combinations. Currently, the amount of time needed to run it on a single thread would take a massive amount of time, however I have access to a computer with many cores (64), so threading it to have at least 20 threads would be a very viable option.

However, I cannot simply convert the generator object to a list and split the list up into equal sized chunks. The amount of RAM required to store the list of lists is far too high.

My single threaded approach (simplified for the question) is as follows:

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p     
        for i in range(low + 1, len(xs)):       
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p     
            xs[low], xs[i] = xs[i], xs[low]

generator_obj = permute(range(9))
for l in generator_obj:
    search_conditions(l)

What would be a good approach to threading this?

Answer 1

1. Even if you have multiple threads, they will still be in the same process, which will only execute on a single core.

2. Rather than splitting the data into a fixed number of equal chunks, why not create a set of batches on the fly? For instance, you can

   • use the generator to create a list of items to process which will be small enough to avoid any danger of filling the RAM,
   • use advice from: https://stackoverflow.com/a/1269055/3366796
   • or save the list of lists to disk using pickle, msgpack, or a database
   • then, using a separate script, use subprocess.Popen to process each batch and write the results back to disk
   • Wait for the processes to finish, then have another routine aggregate the results

This approach will use the power of your multi-core system, though some thought should be put into ensuring that the disk will not become a bottleneck.

Edit: I would try this -> http://www.dabeaz.com/coroutines/coprocess.py