map() with concurrency ignores elements order

Artem-Maliuha commented 4 years ago

(This issue tracker is only for bug reports or feature requests, if this is neither, please choose appropriate channel from http://bluebirdjs.com/docs/support.html)

Please answer the questions the best you can:

1) What version of bluebird is the issue happening on? 3.7.0

2) What platform and version? (For example Node.js 0.12 or Google Chrome 32) Node 10.16.3

3) Did this issue happen with earlier version of bluebird? I dont know, but looks like yes ))

map() with concurrency option ignores elements order. It's unexpected behavior. mapSeries doesn't solving it because it doesn't have concurrency. I can make code donation.

benjamingr commented 4 years ago

Thanks for opening this issue. This behavior s by design and has been discussed in the past. It is also explained in the docs.

ZaLiTHkA commented 4 years ago

@benjamingr, I've been reading through historic issues related to this same topic, but I can't seem to find any clear indication as to how/why this is "by design". every time this comes up, the collaborator's generic response is "because that's how it is".

furthermore, the documentation doesn't do much to explain how the mapped array will actually be processed, instead stating in a very generic way that:

The order map calls the mapper function on the array elements is not specified, there is no guarantee on the order in which it'll execute the maper on the elements.

meanwhile, MappingPromiseArray.prototype._drainQueue itself inside src/map.js shows quite clearly what will happen..

start processing promises from the array start (as any "map" methods do in the JS world), until the defined concurrency limit is reached
pick the next promise from the array end as soon as one of the in flight promises settles

even looking at the tests provided in test/mocha/map.js it's clear to see that this is/was "known" to the Bluebird devs... this behaviour doesn't appear in the initial concurrency tests because these are run on an array with a length of 3 and { concurrency: 2 }, which means it handles the first two elements, then the final one, resulting in the same output. whereas an input of [1, 2, 3, 4] with { concurrency: 2 } in the exact same test would give an output of [1, 2, 4, 3].

going further down the same test file, there's a much more comprehensive concurrency test that mas an input of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with { concurrency: 2 } to an output of [0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5].

the point here that really perplexes me is that this whole story could be fixed by changing a single line of code, simply making MappingPromiseArray.prototype._drainQueue use queue.shift() in place of queue.pop().

this way the tests could be adjusted to have an input of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with { concurrency: 2 } match an output of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

for context, I have an action I need to perform on few hundred "targets" from a hybrid mobile app, but I cannot process them all simultaneously because it overloads the platform it's running on. sometimes the action fails within milliseconds, sometimes it takes a few seconds to complete.

I've tried using Lodash chunk to create an array of arrays to process as promises (no Bluebird required there), but if I process each "chunk" using Promise.all(), then it only moves on to the next chunk all promises in the current one have settled, which causes unwanted delays in the overall process.

the most efficient way for me to handle this is with Bluebird map using concurrency... while it's not required that I have the output in the same order as the input, it does make the user feedback on this process seem far more logical, simply because of the order.

so... considering a number of people have (and I assume, will continue to) ask about this specifically, why are the maintainers so dead set against changing this one line of code..?

edit: I've updated tests and provided a PR for reference, see #1631 for details.

spion commented 4 years ago

@ZaLiTHkA here is why the order is random:

https://codesandbox.io/s/why-bluebird-order-random-vy36y

I get the output:

Pipeline 1, processing item 1 time 236 
Pipeline 1, processing item 2 time 48 
Pipeline 1, processing item 3 time 168 
Pipeline 1, processing item 4 time 214 
Pipeline 1, processing item 5 time 198 
Pipeline 1 finished item 2 
Pipeline 2, processing item 2 
Pipeline 2 finished item 2 
Pipeline 1 finished item 3 
Pipeline 2, processing item 3 
Pipeline 1 finished item 5 
Pipeline 2, processing item 5 
Pipeline 1 finished item 4 
Pipeline 2 finished item 3 
Pipeline 2, processing item 4 
Pipeline 2 finished item 4 
Pipeline 1 finished item 1 
Pipeline 2, processing item 1 
Pipeline 2 finished item 1 
Pipeline 2 finished item 5

If the array or iterable contains promises the behavior is to start mapping them immediately as soon as they become available rather than waiting for them in order. The difference between passing non-promises and promises in the array was deemed confusing, and reliance on having the order a breaking change if in the future some or all of the array elements become promises. Therefore the decision was made to have a randomized order in all cases.

This was probably a mistake but at this point, it might be risky to change this behavior. I recommend using the excellent utility library https://github.com/ForbesLindesay/throat

We can update the docs to refer people to the above library if that seems helpful.

tyscorp commented 4 years ago

This was probably a mistake but at this point, it might be risky to change this behavior.

Semver major should mitigate some of this risk.

spion commented 4 years ago

Personally, I would be looking into migrating off of Bluebird and to native promises and async/await. In that sense avoiding the custom utility methods in bluebird and using throat is still a better choice long term as it reduces the lock-in of your code.

We should probably be looking into implementing all extension methods in a separate library as static methods and recommending against the use of methods. Native promises and async/await don't work with custom promises or subclassing.

What backward-incompatible change would you suggest?

not accepting promises in the array? (likely the best choice but very likely to break people's code)
waiting for the promises in the array, in order, when mapping? (unlikely to break any code but likely to be significantly slower, more resource hungry and more complex to implement)
running in order for non-promises and out of order for promises? (we still want to avoid this as its a refactoring hazard)

ZaLiTHkA commented 4 years ago

@ZaLiTHkA here is why the order is random:

https://codesandbox.io/s/why-bluebird-order-random-vy36y

Out of curiosity, do you know of a way to load dependencies from a GitHub repo in CodeSandbox? I've been trying, but I can't get it work. Note: I did set the new branch in my fork as the default if that matters.

Edit: I pushed the js folder into a separate branch and got CodeSandbox to load my fork instead. I did have to set this temp branch as "default" for this to work though: https://codesandbox.io/s/why-bluebird-order-random-f8g9i

If the array or iterable contains promises the behavior is to start mapping them immediately as soon as they become available rather than waiting for them in order.

The changes I propose and have made in my fork don't affect that in any way...

To clarify, if an array of 10 Promises is passed to Bluebird's map method along with concurrency limit of 5, the current release will:

take the first 5 and start processing those
when one settles, it pops the next one from the input array

What I propose changes this so that it instead:

take the first 5 and start processing those
when one settles, it shifts the next one from the input array

The only thing this changes is the order in which they're retrieved from the input array of values.. As with the current release, all input elements are still just as free to resolve whenever they do.

So how is this a bad thing?

benjamingr commented 4 years ago

So how is this a bad thing?

Basically:

.pop() is fast, if you store an array (like V8) as a chunk of memory all it has to do is decrement an index (length) by 1 and return the value stored there. It's an O(1) operation.

.shift needs to move the whole array around every time. It's an O(n) operation.

benjamingr commented 4 years ago

Bluebird could do something different - the queue holds all the indexes that are being handled when mapping. We don't actually have to do that and we could instead increment a pointer as a form of deleting or do something else that's clever and doesn't require shifting the whole array around. That would still maybe require more memory?

I don't really understand your use case or why it matters to you that well - because you typically shouldn't care about the order or async operations when mapping since you have concurrency and you can iterate sequentially with each.

ZaLiTHkA commented 4 years ago

I am well aware of the performance difference between Array pop and shift, but I'm pretty sure that would make a nominal difference in this case. Looks like the Bluebird codebase does include performance tests, so maybe that could help work out how much of an impact this has?

I don't really understand your use case or why it matters to you that well - because you typically shouldn't care about the order or async operations when mapping since you have concurrency and you can iterate sequentially with each.

In my specific case, the app I'm working on runs through a list of all potential network IP addresses based on the current device's WiFi info, for each one it attempt to open a TCP socket on a specific port in order to request information to identify a proprietary hardware device. On iOS, this process fails if I try open a socket connect to more than 25-odd at once.

Using map with concurrency in the current release of Bluebird causes it to start process from x.x.x.1 up to x.x.x.20, then when one finishes it pulls x.x.x.254, then x.x.x.253, etc.. As you can imagine, running through this process without concurrency takes a few minutes instead.

I started down the rabbit hole because the powers-that-be at my workplace insist on having the app scan through the list of potential IP address in order. Nothing more than that.

Anyways, they're happy with the app behaviour using my fork of Bluebird, so I guess I'll just stick to that one until I find a better alternative.

benjamingr commented 4 years ago

You can always split the data and the concurrency:

const ipAddresses = ['x.x.x.1', ..., 'x.x.x.255'];
const tickets = Array(ipAddresses.length).fill(); // just the tickets.
Promise.map(tickets, () => {
  const item = ipAddresses.shift();
  return process({item, index: ipAddresses.length });
}, { concurrency: whatever });

And then you pay the cost of shifting in your code (and not bluebird's)

Looks like the Bluebird codebase does include performance tests, so maybe that could help work out how much of an impact this has?

Last time it was checked it was noticeable but it's possible shift has somehow gotten a lot faster (although I am not sure how that might happen.

ZaLiTHkA commented 4 years ago

All fair points there.. I'm not trying to imply that there are no other ways to handle it, I guess that's just one of the many joys of software development.

Personally I do still feel that it's worth making Bluebird's map method process the provided array in the same order, regardless of whether or not the concurrent processing limit is used, if for no other reason that to make it's own behaviour more consistent overall. Either way, I think I'll leave my PR open for further scrutiny down the line.

By the way, thanks for the healthy debate, it's a refreshing change from the all-too-common short replies some project contributors/maintainers give to say "that won't happen", without investing the time to work out why it either should or shouldn't. :)

benjamingr commented 4 years ago

Happy to debate and again, I would be happy to take the change if we can prove there is no performance regression.

cdhowie commented 4 years ago

I have a branch that fixes this issue (e473d9fd29f08071043390816aa9dd93bf63b910) hopefully with no performance regression. I couldn't find any benchmarks that use the concurrency option so I'm not even sure that the performance of the existing map() function with limited concurrency is known/understood.

This patch alters mapping to be strictly ordered on the input (when the input elements are not promises, or resolve in order) without using shift() by retaining the current queue position. This allows forward movement through the queue without O(n) reassignments for each element during queue draining.

I've corrected the failing test to expect the results in order. Since this is tested behavior, I'm not sure if this is considered to break backwards compatibility and require a major semver release. My argument would be that no, this is not a semver break:

The documentation already states that order in which elements are passed to the mapping function is not specified.
If the input array contains promises, the order in which elements are passed to the mapping function depends on the order in which those promises are resolved.

With this patch, we could strengthen the guarantee regarding the mapper invocation when the input array contains no promises, or those promises are resolved in order.

If this looks acceptable, I can create a PR.

ZaLiTHkA commented 4 years ago

FWIW, I still haven't had a chance to see what performance hit shift would add here in place of pop, but considering we all already know that there is one, I would personally take @cdhowie's implementation over my own. Going to close my PR in the meantime to clear it out of the way.

petkaantonov commented 4 years ago

Order is not guaranteed, not because of shift is slower than pop but because it is much faster to process the items as soon as they arrive rather than in order.

petkaantonov commented 4 years ago

Also order here only means the order of calling the callback, not the order of items. Of course the order of items is ordered and in the same order as the original array.

AbdelrahmanHafez commented 2 years ago

Here's a list of things we could do that would not be a breaking change.

1- Offer an option for people to decide whether they need to pick items in sequence or randomly, even if they were promises, the developers can decide what works best for them. 2- Pick items in sequence by default, if it's a pending promise, go to the next ready item (non-promise values or resolved/rejected promises).

I'd happily put in a PR with both changes.

petkaantonov / bluebird

map() with concurrency ignores elements order #1626