Preserve order when collecting results

[anuraaga]

When using CollectWithErrs, I noticed that the results aren't returned in the order of invocations of .Go.

Items are added in order from the pipe

https://github.com/wandb/parallel/blob/main/collect.go#L188

And the pipe is sent to immediately when Go completes

https://github.com/wandb/parallel/blob/main/collect.go#L348

To have order, I can return an indexed struct and sort myself, but I was wondering if it would make sense to do this in the library? It seems to make the executor easier to use, especially when compared to e.g. errgroup. Otherwise, maybe the doc comment can include a note that results aren't ordered in any way?

[mumbleskates]

the results indeed are not ordered. there are a couple approaches we could take to this, but i did indeed opt to leave them in the order of their natural completion as they flow through the synchronization bottleneck.

it would be possible for "collect"-like executors to make the results (and perhaps errors) to have a guaranteed partial ordering that corresponds with the order their originating .Go(...) invocations occurred. The main reasons we don't do that now is that doing so is more costly and infrequently needed in the originating codebase. If the thing being replaced is a channel that results will be read from (for example), order doesn't matter at all; the slice is just a place to store a collection of items. As discussed in the readme, golang does not provide a synchronized collection type of any kind.

so yeah: what we observed is that we never needed this ordering guarantee. if it's not needed, providing that guarantee makes it 1) harder to improve, 2) slower, and 3) probably confusing to users when the invocations aren't totally-ordered (for example, when .Go(...) invocations are interleaved from multiple concurrent goroutines).

i don't love giving the ordering guarantee by default, when the "collect" executors just work the same as the "feed" executors except deferring the results (in the order their invocations finish) into a slice. However, it'd be fine (and pretty easy) to add a composing wrapper -- either in this package, or even outside it -- that assigns ascending sequence numbers to the invocations, pairs the results with them, and re-orders the outputs by that order at collection time.

[anuraaga]

Thanks @mumbleskates - yeah I ended up replacing collect with a normal executor filling in a preallocated slice.

I think for me the word collect may have some implications from other languages like Java, and I don't know why but I imagined Promise.all when looking at the collecting executor. So just documenting unordered to make it clearer for someone like me with assumptions like that would be enough.

That being said, I also wonder what the use case of collect is if the result isn't ordered. The only cases I've run into require knowing which input each output corresponds to, or otherwise there isn't really anything to do with the results. Do you know a use case where unordered works, assuming the caller isn't sorting themselves? Also for the example of interleaved .Go calls, I just can't imagine using collect in that case since indeed it's too random.

[mumbleskates]

yes, a lot of the time when we have an exact known number of ordered destination slots that all need to be filled it is better & easier to use parallel.ErrGroup instead one of the value-collectors and have the invocations write their values directly into their captured destination. they still end up in exactly the right place, it's almost exactly as easy, and while it doesn't have the same kind of elegant functional data flow... well, those who have a deep need for that kind of thing are honestly better served looking elsewhere than golang, which is not a good language for clean data handling. (the collect apis do try to offer this, and maybe there is some value to offering ordered variants of the collect apis; you have raised an interesting point here, i'm considering it. not positive if it ought to be the default tho)

That being said, I also wonder what the use case of collect is if the result isn't ordered.

homogenous result sets, basically. just as not all collections need to contain unique values, not all collections need to be sequences; they just need to contain items, and be iterable. for example if you are performing a join against a foreign dataset or even a remote lookup api and you are going to need to alphabetize by the resulting value anyway, there is no value in retaining the orderedness of your inputs that bear no relation to the final ordering.

just think of the "collect" apis as extremely similar to the "feed" apis, except they "collect" the output values into a slice for you, rather than making you do it yourself. that is pretty much all they do, at present.