Question: I have a dictionary D of {string:list} entries, and I compute a function 
f( D[s1],D[s2] ) --> float 
for a pair of strings (s1,s2) in D.

Additionally,
I have created a custom matrix class LabeledNumericMatrix that allows me to perform assignments such as m[ ID1, ID2 ] = 1.0 .

I need to calculate f(x,y) and store the result in m[x,y] for all 2-tuples in the set of strings S, including when s1=s2.
This is easy to code as a loop, but execution of this code takes quite some time as the size of the set S grows to large values such as 10,000 or more.

None of the results I store in my labeled matrix m depend on each other.
Therefore, it seems straightforward to parallelize this computation by using python's multithread or multiprocess services.
However, since cPython doesn't truly allow my to simultaneously execute calculation of f(x,y) and storage of m[x,y] through threading, it seems that multiprocess is my only choice.
However, I don't think multiprocess is designed to pass around 1GB data structures between processes, such as my labelled matrix structure containing 10000x10000 elements.

Can anyone provide advice of (a) if I should avoid trying to parallelize my algorithm, and (b) if I can do the parallelization, how to do such, preferably in cPython?

Answer: 
You definitely won't get any performance increase with `threading` - it is an inappropriate tool for cpu-bound tasks.

So the only possible choice is `multiprocessing`, but since you have a big data structure, I'd suggest something like [`mmap`](http://docs.python.org/library/mmap.html) (pretty low level, but builtin) or [`Redis`](http://redis.io/) (tasty and high level API, but should be installed and configured).
Have you profiled your code? Is it just calculating f that is too expensive, or storing the results in the data structure (or maybe both)?

If f is dominant, then you should make sure you can't make algorithmic improvements before you start worrying about parallelization. You might be able to get a big speed up by turning some or all of the function into a C extension, perhaps using [cython](http://cython.org/). If you do go with multiprocessing, then I don't see why you need to pass the entire data structure between processes?

If storing results in the matrix is too expensive, you might speed up your code by using a more efficient data structure (like [array.array](http://docs.python.org/library/array.html) or [numpy.ndarray](http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.html)). Unless you have been very careful designing and implementing your custom matrix class, it will almost certainly be slower than those.