4

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?

Alex
  • 167
  • 3
  • 8
  • 4
    Threads aren't going to help you. Multithreading in Python sucks, because the standard implementation of Python has all sorts of thread-unfriendly design and needs a global interpreter lock to make sure simultaneously executing threads don't screw up the interpreter internals. That means it's pretty much one thread at a time. You can try the multiprocessing module, which uses multiple whole Python processes to get around the lock, or you can try a more thread-friendly language. – user2357112 Dec 15 '15 at 18:42
  • try multiprocessing with queue. see [link](https://docs.python.org/2/library/json.html#basic-usage) – taesu Dec 15 '15 at 18:55
  • @user2357112 I'll see what other programming languages are installed on the server for me to work with this evening. I think you linked the wrong page, taesu. Did you mean [this one](https://docs.python.org/2/library/queue.html)? – Alex Dec 15 '15 at 19:11

1 Answers1

4

  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

Community
  • 1
  • 1
whunterknight
  • 91
  • 8
  • Good point about the singular core issue. I'll try out your suggestions as well, but I forgot completely forgot about [itertools](http://stackoverflow.com/questions/3223780/get-a-subset-of-a-generator), which in combination with multiple Python processes should enable me to utilize proper multithreading with minimal bottlenecks. – Alex Dec 15 '15 at 20:18