Proposal: don't use Arrays for a queue

[frank-dspeed]

Hi Justin my frind i see your coding a queue system as engineer for distributed services i can tell you out of my expirence that arrays are much slower then in memory buffers.

Solution one dequeue

The Probally fastes queue code around in the nodejs community:

• https://github.com/petkaantonov/deque

1000 items in the queue:

double-ended-queue x 15,532,714 ops/sec ±0.19% (96 runs sampled)
built-in array x 6,501,398 ops/sec ±0.87% (95 runs sampled)
node-deque x 2,938,068 ops/sec ±3.50% (68 runs sampled)

2 million items in the queue

double-ended-queue x 14,425,547 ops/sec ±0.17% (94 runs sampled)
node-deque x 2,815,628 ops/sec ±10.56% (76 runs sampled)
built-in array x 19.23 ops/sec ±0.35% (51 runs sampled)

Solution 2 the even better method!

Using most stream which is internal based on a improved dequeue version.

• https://github.com/cujojs/most/blob/master/src/Queue.js

This method outperforms even dequeue it self and is the most modern method a stream is in fact a queue of events :)

Deep into the weeds

Why not use an Array?

Arrays take linear O(N) time to do shift and unshift operations. That means in theory that an array with 1000 items is 1000x slower to do those operations than a deque with 1000 items. 10000x slower with 10000 items and so on.

V8 implements a trick for small arrays where these operations are done in constant time, however even with this trick deque is still 4x faster.

But arrays use "native" methods, they must be faster!

In V8, there is almost no advantage for a method to be a built-in. In fact many times built-ins are at a severe disadvantage of having to implement far more complex semantics than is actually needed in practice. For example, sparse array handling punishes almost every built-in array method even though nobody uses sparse arrays as is evidenced by the popularity of the underscore library which doesn't handle sparse arrays in the same way across different browsers.

Using double-ended queue as a normal queue

Queue is a more commonly needed data structure however a separate implementation does not provide any advantage in terms of performance. Aliases are provided specifically for the queue use-case. You may use .enqueue(items...) to enqueue item(s) and .dequeue() to dequeue an item.

Additional Sources

• https://en.wikipedia.org/wiki/Double-ended_queue
• https://en.wikipedia.org/wiki/Double-ended_priority_queue

but i need to point out using most as queue and priority queue is the most efficient clean way in nodejs that i know till today.

[justinbmeyer]

Thanks for sharing. I’d happy accept a pull request. Otherwise, I’ll get to changing this after making canjs work with the existing implementation.

[frank-dspeed]

@justinbmeyer do you accept a PR using most streams as queue? or simple double encoded queue? I ask because you could be opinionated about dependencys. for me in general most is always a must have :) as there is no faster implamentation around. the most best about most is its A+ Promise Compatible

• https://github.com/cujojs/most/

[justinbmeyer]

I’m guessing it can’t be directly used because of the logging and different needs for CanJS’s queues. We’ll probably need to use parts of their code (and make sure to reference it).

Sent from my iPhone

On Oct 17, 2017, at 6:43 AM, Frank Lemanschik notifications@github.com wrote:

@justinbmeyer do you accept a r PR using most streams as queue? or simple double encoded queue? I ask because you could be opinionated about dependencys. for me in general most is always a must have :) as there is no faster implamentation around.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[frank-dspeed]

@justinbmeyer it can and logging is also well with it as we can simple split the streams for that general errors include stacktrace as they are Promises.

I Start refactore queue.js then i start over the rest. and keep the api

[frank-dspeed]

@justinbmeyer i am famouse for my monades :) i would love to code that directly with only most

[justinbmeyer]

@frank-dspeed just a heads up ... I'm not actually doing .unshift() ... I keep track of the index of the last task to run. This makes it so the only list method I use is push(). I assumed that housing these tasks even after they have ran isn't a problem because we only hold onto them until the queue is empty (which should happen synchronously, before garbage collection could get them anyway).

[justinbmeyer]

I've wondered if a singly linked list might be the fastest implementation.

[frank-dspeed]

I think you should let it flow through most at end you process via loop and write the result ===lasttask into a var you already know that stream values are out as soon as processed. this is a ideal design. Linked lists with a obj pointer are sure ok and fast but lead to garbage collection and in general to be fast you don't want to even Tigger garbage collection. but I found out we get all the pros with less cons without a queue in a total other way need to talk about that .

[frank-dspeed]

//Start with some tasks
//most.fromPromise() if a promise returns it and so on
let myProcessing = most.from([arrayOfTasks])
// MultiCast does what it says its resource sharing of a stream
.multicast()

myProcess.observe(processing)
// lastTask sets the last task to something but!
//myProcess when it has a return value === lastTask that can be one Time used as Promise
myProcess.observe(lastTasks)

but anyway you should look into gitter i gave you there some links and Matthew but i think without real talking Matthew don't understands what i mean.

i found total new ways that no framework uses at present that will be the future of Composing and Loading Applications on a Browser Like Platform.

i got mega amazing results but much to much to say it in some lines. Its about webcomponents fetch prefetch import browser api's :)

[frank-dspeed]

@justinbmeyer can you tell me how you planned to use this queue where will the tasks come from what do you plan as source i looked now into all related libs like ssr and can-view-callbacks all that has something to do with rendering can-stache can-component it would really help me to find the data source that your targeting.

but i think my new concepts bypasses your data source as it will not use much composing of can-component inside can-component inside stache