Allow for deterministic sub-workflow loop order when parallelisim is set to 1

[dustinblack]

Please describe what you would like to see in this project

Currently when running a foreach loop of a sub-workflow with a list of inputs and parallelism set to 1, the loop over that list will happen in a non-deterministic order rather than sequentially through the list as defined in the input. I would like to see this behavior change such that the loop always happens in the order the input list is defined.

Please describe your use case

Running a set of benchmarks in a loop may involve incrementing a variable with each loop to, for instance, increase the load being tested. When observing the output data, particularly a time series, we expect to analyze that data in the order that the test was defined. Having the data in a non-deterministic order can drastically increase the difficulty of the data analysis.

[webbnh]

Said only partly in jest, it sounds like what you need is a builtin function which will allow your workflow to sort the output list prior to your postprocessing, to put it into the order that you expect.

Would that be useful and applicable as a stop-gap measure? (That is, it might be very easy to add such a builtin function, and it might have general applicability beyond your case, so it would be worth considering on its own, and it might be a quicker path to a solution than an enhancement of foreach.)

[dustinblack]

@webbnh It may indeed be a worthwhile function, but I'll basically be re-sorting the output into the existing order of the input. The function would need nested sorting capabilities (i.e., sort by key1, then by key2).

[jaredoconnell]

Before it got lost, I wanted to copy over Webb's algorithm discussion regarding this from Slack.

4 days ago
@Jared O'Connell, the name of the algorithm that I was thinking of for Arca’s use is Lamport’s Bakery algorithm. However, I suspect that we don’t need to use it verbatim, because we have a much more limited case, and because we potentially want to permit more than one action at a time.

4 days ago
What I would propose is giving each of the actors in the foreach a number (starting from 0), and setting a “threshold” at the level of parallelism desired (setting it to 1 for serial execution). Then each actor checks its number against the threshold and proceeds when its number is less than the value. When an actor finishes, it increases the threshold by one.In this way, the actors will run in numerical order, and only a certain number will run at a time. Obviously, they will only complete in numerical order with a threshold of 1, but the algorithm should work fine regardless of the value of the threshold or the number of actors.The questions are how to arbitrate access to the threshold for read and for write, and what should the actors do when their number is above the threshold? There are lots of possible answers. However, it’s also plausible to avoid these questions if there is some sort of executor which creates the actors when they are eligible to run and synchronizes with their completions, rather than the current approach of creating them all at once and letting them battle it out. This removes the need for the actors to consult the threshold and for them to have to wait for their respective turns. (edited)

[webbnh]

@jaredoconnell, I think you copied one too many messages: I don't think there is any need or applicability for Mellor-Crummy/Scott locks -- that was just for Dave's recollection. 😁