Implment queues using DLLs #1205
Conversation
|
also /cc @mikestopcontinues @bbrowning @zeluis9 |
| arrayEach(data, function(task) { | ||
| var item = { | ||
| data: task, | ||
| priority: priority, | ||
| callback: typeof callback === 'function' ? callback : noop | ||
| }; | ||
|
|
||
| q.tasks.splice(_binarySearch(q.tasks, item, _compareTasks) + 1, 0, item); | ||
|
|
||
| setImmediate(q.process); |
There was a problem hiding this comment.
note this change, moved process outside of the loop. I think this is the correct behaviour
|
I'll be happy to, but it might have to wait until the weekend. Deadlines! :) |
|
|
||
| DLL.prototype.insertAfter = function(node, newNode) { | ||
| newNode.prev = node; | ||
| newNode.next = node.next; |
There was a problem hiding this comment.
Will this add prev and next properties to items people push to queues? Perhaps the list should store {prev, next, data} objects, where data points to the original object.
There was a problem hiding this comment.
no, push wraps the item in an internal object already, {data, callback} for queue and {data, callback, priority} for priority queue
|
Also, what do our benchmarks look like with these changes? (Just realized I haven't tried to run those since modularization.) |
1330ms total vs. 34200ms total (it will sometimes tie on the smaller suites but generally time is 1.3s for this pr, 36s for rc-6) |
|
Damn, thats impressive. Looks like with small queues it will be slower, but at those sizes, the list overhead is negligible anyway. |
|
Also, I realize this is a subtle breaking change -- the |
|
Ye, that's why I changed the variable name and want to get this in v2.
|
|
Also based on CS intuition-fu I'd expect this to be faster in all cases Ye, that's why I changed the variable name and want to get this in v2.
|
|
For the record, this totally fixes my issue. Thanks @megawac. You rock! |
|
good to hear 🎉 @mikestopcontinues thanks for getting back |
A linked list is a more optimal method to keep track of a stack of tasks as we can end up mutating the
tasksvery frequently. The previous solution could have been further optimized to avoid several splices (i.e. doing 1 splice instead of n in several scenarios), though a linked list solution should generally be more performant./cc @aearly
Fixes #756