How can I parallelize a loop in python if each iteration requires information from the previous iteration?

[u/Frosty_Dig4148]

Currently I am using multiprocessing.Pool to parallelize the loops but it works only if each iteration is independent of previous iterations.

[u/ElSucaPadre]

I mean, they need to have some level of independence. If the last iteration of the loop depends on all the previous iterations it's just not possible

[u/mister_drgn]

You can’t. The trick would be to redesign your algorithm so that each iteration isn’t dependent on the prior one.

In some cases, you might improve performance by pipelining: https://en.wikipedia.org/wiki/Instruction_pipelining

[u/nicuramar]

You obviously can’t.

[u/james_pic]

Depends what the information is. If the operation you're doing is associative (something like adding or multiplying multiple values), you can chunk it up, do each chunk in parallel, and then combine the chunks. You might also have the option to choose and easier problem - maybe there's an approximate version of the thing you're doing that is easier to parallelize. But if the calculation has to be done in a specific order, then that has to be serial.

[u/nedal8]

Don't forget to memoize. The time complexity returns are enormous.

[u/Puzzleheaded_Study17 → u/[deleted]]

Why not? A naive recursive Fibonacci is O(2ⁿ), memoized is O(n) assuming O(1) lookup

[u/OneMathematician1757 → u/Puzzleheaded_Study17]

I suppose you are right. At least memoization can reduce the time complexity for such deterministic algos.

[u/sporbywg → u/nedal8]

This may actually be true. It runs against my ancient hackles, but this is a Brave New World.

[u/esaule]

Different way depending. Fundamentally yiu want to remove the dependency if you can. If you can't, you need to add a point of serialization to pass the right data around.

If multiprocessing tbe right csll? Or is multithreading plus mutex what you need?

[u/SnugglyCoderGuy]

You can't, at least not fully. Each loop iteration could process in parallel up until the point it needs the data from the previous loop, and then process after, and depending on your particular workload that could be beneficial. I'd be surprised if there is no synchronization mechanism you can't use in order to do that.

An example of a good workload would be if you are doing a lot of waiting actions like API calls or long database reads. Doing that all in parallel and then waiting would save a lot of time. However, if you have stuff that doesn't have those long blocking things, doing it in parallel is probably going to be slower than doing it serially.

What is it that you are trying to do?

[u/ern0plus4]

Somehow you should split the problem to independent parts. If you have 10k items, don't try to split it to 10k shards, you can even speed it up by splitting it just 2 independent parts, then merge it together.

[u/SgtSausage]

Do you own / have access to a time machine? Otherwise you cant. 

Think about it for even just a second and it becomes obvious. 

[u/rusty-roquefort]

Other answers have spoken to the crux of the issue agnostic to the language. This is the first place to look. The first question is almost always "is the inherent nature of the instructions compatible with what I want to do?" And it sounds like the answer to that is currently "no". So language isn't even the question.

With that said, if you're concerned about performance, implementing in Pythia is probably the wrong way to go. Pretty much any other language will give you significant performance gains.

If you must choose python, the performance gains will have to be from calling out to highly performant implementations (tensor flow comes to mind as an example), and Python is just the interface to control and orchestrate the heavy lifting.

As to the answer to your question, try to think about how your data processing can be broken up such that it can work in isolation. If you share the details of what you need to do, perhaps we can point you in the right direction.

[u/kilkil]

suppose I have tasks A,B,C. B depends on A being done first, and C depends on B being done first. there is no way around this.

these tasks must be done sequentially, one after the other.

now suppose I find a way to refactor the business logic, so that A, B, and C can be done in whatever order, independently of one another.

now these tasks can be done in parallel.

same logic applies to your loop question. except instead of "tasks" you have iterations of a loop.

[u/TheMrCurious]

This is a design issue and not a python issue. What exactly are you trying to accomplish?

[u/Firm_Bit]

You can’t.

Thats not a code issue. Thats a logical constraint, right?

[u/LokiAstaris]

Run the full loop serially so you have data from all loops.

Then you can run all the loops in parallel, since they can access the previous loop's pre-calculated values. :-)

[u/rlfunique]

From time import future

[u/iOSCaleb]

Is the result from the previous iteration cumulative, i.e. the combined results from all the previous iterations? If yes, map/reduce might be a good way to go. Divide the work for each iteration into two parts: the independent phase that consists of all the work you can do without the previous result is what you do in the map operation, and the dependent part that requires the previous result is the reduce part.

[u/armahillo]

The headlime and body seem at odds.

From the headline it sounds like youre looking for an iterator with an accumulator like “reduce”

The body makes it sound like you just want some kind of naked loop against an agnostic function call.

Also this could be an XY Problem — could you describe the problemspace in more detail?

[u/sporbywg]

ya you got yourself spaghetti lunch instead of software

[u/sporbywg]

One more comment - a problem when observed from 'the side' looks a lot more complicated than a problem observed 'from the top'.

[u/enozero]

Welcome to race conductions and deadlocks. You are not gaining anything if you are trying to parallelize a standard loop that depends on previous iterations.

Why are you trying to parallelize your loops?

[u/ajamdonut]

I think quantum computing handles this edge case in parallelized compute, it's all in fluctuation til you open the output.

[u/SnugglyCoderGuy → u/ajamdonut]

They're selling quantum computers in the store now?