Closed Bug 1087330 Opened 10 years ago Closed 9 years ago

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

Categories

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

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla40
Tracking Status
firefox40 --- fixed

People

(Reporter: Paolo, Assigned: bzbarsky)

References

Details

Attachments

(2 files, 2 obsolete files)

As a follow-up to bug 1013625, the Promise microtask queue should be implemented on top of a templated class similar to nsDeque.
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.
QA Contact: bzbarsky
Summary: Implement the microtask queue on top of a templated deque class → Implement the microtask queue on top of something with O(1) first element removal
Summary: Implement the microtask queue on top of something with O(1) first element removal → Implement the promise microtask queue on top of something with O(1) first element removal
Assignee: nobody → bzbarsky
Status: NEW → ASSIGNED
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.
Attachment #8595725 - Attachment is obsolete: true
Attachment #8595725 - Flags: review?(khuey)
Why don't we just use mozilla::LinkedList, or std::list or std::queue here?
Flags: needinfo?(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.
Flags: needinfo?(bzbarsky) → needinfo?(khuey)
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.
Flags: needinfo?(khuey)
Well, this seems to perform almost as well, and sure is simpler code....
Attachment #8600541 - Flags: review?(khuey)
Attachment #8596069 - Attachment is obsolete: true
Attachment #8596069 - Flags: review?(khuey)
https://hg.mozilla.org/mozilla-central/rev/fc1b65394523
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla40
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.