parallelize computation of list comprehensions

[malingaperera]

Even though some programming languages have easy methods to parallelize list comprehensions, python doesn't have anything as such. So there are two main options around this.

1. use of map() function: Python allows the use of map and reduce operation in parallel without any change to method signature. This is the the recommended way to parallelly process a list. However, in python 2.7 map function only take functions with one argument (in python 3 it can take many arguments). With the map function, private code look like below. User have to use map rather than directly calling the fft in the list comprehension.

   AccelerometerData = [e.AccelerometryDataFilesItr for e in DemoEvents if e.hasField("AccelerometryDataFilesItr")]
   fft_comp = map(fft, AccelerometerData)

2. Convert list comprehension to parallelized code at code generation point (visit_list_comprehension). This might be complex as the list comprehension is generic. Furthermore there is a risk as we are changing the actual user code .

In addition, in the current setup, we run a worker per processor. So individual worker usually don't have access multiple processors. So it might be good to focus on thread based parallelism rather than processor level parallelism. When we are using thread based parallelism we rarely get any improvement for I/O bound jobs. However, thread based method should have a impact on I/O based jobs like fft calculation (as we are accessing s3 files). If we need, we can have a config parameter to define parallelism method (process or thread) and make it flexible.

@sjd201, @benston3 what do you think about that?

[sjd201]

Ultimately, I would like the parallelism to be completely transparent to the user. So user ought to be able to write:

AccelerometerData = [fft(e.AccelerometryDataFilesItr) for e in DemoEvents if e.hasField("AccelerometryDataFilesItr")]

However, we can do this for now. I would however like to get to processor based parallelism.

With respect to the multiple argument problem I guess you can always code around this (just create a list of tuples to go into the function). However, it does raise the issue of when we port to python 3.

[malingaperera]

@sjd201: About the workaround for the multiple argument problem, I also thought of the same solution you mentioned. However, in my mind I had couple of issues on that.

First, it might need changes in all functions with more than one argument to take tuples (pow, cmp, divmod, etc.). However I'm not sure how much we might need them in a list comprehension (as list comprehension most of the time work with single list).

Secondly, it will look somewhat unnatural for some common functions to take in single argument as we are more familiar using then with multiple parameters (ex: pow(2, 3))

Being said that, if we only need this for custom built functions like FFT we can always design them to take only one parameter.

Continuing on that ticket, I will analyze the possibility of getting the desired behavior (completely transparent parallelism) via changing the visitor class. furthermore will work on the processor level parallelism.

[malingaperera]

@sjd201: I tried to change the code to run in parallel (so user can simply input a list comprehension and it will be processed parallely), however it's not truly transparent as user can see the changed code in the sv output, Do we have to change this as well?

 Ex:
> AccelerometerData = [fft(e.AccelerometryDataFilesItr) for e in DemoEvents if e.hasField("AccelerometryDataFilesItr")]
> sv
AccelerometerData = //changed code

[sjd201]

I think there are separate variables for code and mccode. If you change the mccode one it shouldn't show. (Maybe this isn't true for the deterministic code though). However, I think we need a deeper solution to this problem in general. I think we should be passing the expression trees around and then constructing the evaluation code from them when we want to run it rather than when we are parsing the trees in the first instance.

[malingaperera]

@sjd201 Problem was in another visitor method visit_private_list that does not pass the evalcode, with that in place it was possible to get the sv to show the original code and make it fully transparent. I have finalized and pushed this approach to branch issue/42 before moving to the bigger solution.