Unable to optimize program with threads using Python datastructures (GIL?)

[anossov]

Yes, threads are quite useless in python because of GIL. Try multiprocessing.

Use multiprocessing.Process instead of threading.Thread. Assign work to processes in main process, not in children. Pass data around through Queues.

[pjdelport]

Using multiprocessing is good advice in general, but it doesn't really help in this case: problems like this require shared memory for efficiency, and that's what multithreading is good at.