1087330 - Implement the promise microtask queue on top of something with O(1) first element removal

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[:Paolo Amadini]

As a follow-up to bug 1013625, the Promise microtask queue should be implemented on top of a templated class similar to nsDeque.

Comment 1

[Boris Zbarsky [:bzbarsky]]

I ran into this today causing a serious perf problem (testcase coming up).  I'm not sure we need, for the moment, a generic "dequeue of refcounted things", so I just wrote up a one-off intrusive linked list for this case.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase that takes about 10x as long as it should because of all the memmoves

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Make the data structure we use for our promise microtask queue have O(1) first element removal, not O(N)

Comment 4

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8595725 [details] [diff] [review]
Make the data structure we use for our promise microtask queue have O(1) first element removal, not O(N)

This doesn't work because we have tests that include CycleCollectedJSRuntime.h when XPCOM_GLUE_AVOID_NSPR is defined, and hence can't have nsRunnable.  I guess I get to add some more headers somewhere here.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Attachment: Make the data structure we use for our promise microtask queue have O(1) first element removal, not O(N)

Comment 6

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

Why don't we just use mozilla::LinkedList, or std::list or std::queue here?

Comment 7

[Boris Zbarsky [:bzbarsky]]

We can, at the cost of two allocations per runnable instead of one for the former two. 

std::queue might be the way to go, if I knew what it's actual backing implementation is...  I guess I can just hope that it would be OK.  I can do that if we're sure its no-exceptions safe.

Comment 8

[Kyle Huey (Exited; not receiving bugmail, old account, do not use)]

std::queue appears to just be an alias for std::dequeue, at least in glibc.

Basically, I'll r+ this if you want it, I just want to make sure you've thought through the alternatives.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Attachment: Make the data structure we use for our promise microtask queue have O(1) first element removal, not O(N)

Well, this seems to perform almost as well, and sure is simpler code....

Comment 10

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/fc1b65394523

Comment 11

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/fc1b65394523