1267408 - Remove O(n^2) behavior from Promise-backend.js

Status: RESOLVED WONTFIX

(Toolkit :: Async Tooling, defect)

Description

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Using shift in a loop is quadratic behavior, because all of the elements in the
array need to be shifted down by one. Then the next iteration of the loop does
the same shifting behavior for n-1 elements, and after that n-2 elements,
... which results in an average of n/2 shifts each iteration. n * n/2 = O(n^2).

Comment 1

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Remove O(n^2) behavior from Promise-backend.js

Comment 2

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=3f19cc9f6a0c

Comment 3

[Jim Blandy :jimb]

Comment on attachment 8745072 [details] [diff] [review]
Remove O(n^2) behavior from Promise-backend.js

Review of attachment 8745072 [details] [diff] [review]:
-----------------------------------------------------------------

::: toolkit/modules/Promise-backend.js
@@ +812,5 @@
>      }
>  
>      // Process all the known handlers eagerly.
>      while (this.handlers.length > 0) {
> +      this.handlers.splice(0, this.handlers.length).forEach(h => h.process());

I think x.splice(0, x.length) is equivalent to x.splice(0).

Comment 4

[:Paolo Amadini]

I wonder if this interacts badly with the "this.handlers.length > 1" check above for nested event loops.

Comment 5

[:Paolo Amadini]

Comment on attachment 8745072 [details] [diff] [review]
Remove O(n^2) behavior from Promise-backend.js

Actually, now I remember it does. We can only process one handler at a time otherwise the others are stuck if a nested event loop is started. It's in the big comment just above the patch context, maybe we should add a small comment below as well?

There may be better ways to handle this, but they may add some complexity. Have you noticed this optimization in response to an actual benchmark or just by looking at the code?

Comment 6

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: Remove O(n^2) behavior from Promise-backend.js

This iteration pulls out the check for whether there are "many" handlers
scheduled.

Comment 7

[:Paolo Amadini]

Comment on attachment 8745679 [details] [diff] [review]
Remove O(n^2) behavior from Promise-backend.js

Ah, sorry I was just thinking aloud in comment 4. The problem is not _only_ in the "this.handlers.length > 1" check, but in the fact that if we take out all the handler references from the "handlers" array and copy them to a local array on which we iterate, and one of these handlers starts a nested event loop, then any subsequent handler that now exists only in the local array cannot be processed until the nested event loop terminates.

One of the stuck handlers might well be the one that triggers the condition that causes the nested event loop to terminate, effectively causing a deadlock.

Comment 8

[:Paolo Amadini]

We could use linked lists or something, but honestly if this O(n^2) behavior hasn't been a problem in practice I wouldn't even bother, and prefer the simple solution. The balance can be different if we have an actual issue shown by a performance profile. That's why I asked.

Comment 9

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Ok, fair enough.