Queue Feature Request
Hello,
you can try using a Map with unique keys. Map operations are guaranteed to be sublinear on average, and new entries are added to the end.
Then you only need a trivial wrapper for better abstraction:
class Queue {
constructor() {
this._map = new Map();
}
push(value) {
this._map.set({}, value);
}
pop() {
var first = this._map.entries().next();
if (first.done) return;
this._map.delete(first.value[0]);
return first.value[1];
}
get size() {
return this._map.size;
}
}
var q = new Queue();
q.push(1);
q.push(2);
q.pop(); // 1
q.push(3);
q.pop(); // 2
q.pop(); // 3
q.pop(); // undefined
Good insight. I wasn't aware that using an empty object in the Map.set implementation would yield unique keys, but it makes sense... You mention sub-linear time, but not constant? Is Map expected to have a lot of collisions? It seems as if it would be fine, based on the spec, but I'll run a benchmark to see where V8's map ops stand in comparison to the external queue / deque libraries.
Is there any way to extend that to a deque with similar operation times? I don't see anything out-of-box, but it looks like the map iterator keeps a numerical index of the keys. Could this be used to allow an iterator in the reverse direction? tc39.github.io/ecma262/#sec-createmapiterator , the MapNextIndex. Or is this index just meant to be a counter to check for exhaustion of the iterator?
Assuming this Map approach is performant, I still think syntactic sugar would be nice. Although, wrapping up a Map implementation in an alleged Queue might be misleading.
Are there any discussions around including linked structures? Or maybe a reversed Iterable for each iterable?
Best,
Zach Boldyga Scalabull | Founder 1 (866) 846-8771 x 101
In WebKit the array implementation switches to an amortized constant time deque if you use push/pop/shift/unshift in anger. So, a program that just treats arrays as if they were deques should perform great. If you find that it does not perform as well as you would like, then we would love to hear a bug report at bugs.webkit.org.
I think that adding a Deque type is an OK idea. But maybe it's better if all of the implementations get adaptive arrays right.
So both the more modern versions of V8 and Webkit's JIT both make automatic, background attempts to amortize Array's deque-type operations. I wonder why both teams decided to make that change, which deviates from the ECMA standard. Either way, they are able to give a big performance boost without creating any breaking changes to javascript.
That said, I can't comment on WebKit's engine (B3 JIT?), but V8's attempt to amortize shift and unshift operations comes to a screeching halt with large arrays. See the benchmark at the bottom of the page: petkaantonov/deque... This creates a problem - shift appears like it's constant time, but then in some cases it's really slow. So developers, especially the less experienced ones, are thinking that Javascript's Array is meant to be shifted and pushed in tandem, but then that code breaks down depending on the browser or use case.
I notice that a common trend with the browsers is now to layer-up compilers, with general purpose compilers running first, then more optimal compilers running if code gets really hot. So in effect, there are a bunch of different compilers floating around. It seems awfully complex for all of them to try and figure out how to best optimize array shift operations. Something that works well for certain use cases is not going to work well for other use cases. V8 is case-in-point, in the way that it's optimized for small arrays (the more likely case).
Maybe the standards should reflect an approach more like Python's, which breaks lists and deques into two separate entities that excel in their unique use cases. By explicitly separating them, compilers don't have to do the extra leg-work. Then, in addition, slap a big warning on the Array shift operation that says - this is really slow. Compilers can leave in the optimizations if they want, but can also have the liberty of a more simple approach.
I think the fact that the compilers already have support for Map is useful, given the earlier comment on how it can be used for queue operations. But it would also need a way to support deque operations to fully close-out this re-design.
Maybe it makes sense to make an abstraction of the data structure underlying the Map, as it's implemented in the various compilers, add support for some type of reverse iterator, and then support both Map and Deque without the compiler teams having to do much additional work?
Best,
Zach Boldyga Scalabull | Founder 1 (866) 846-8771 x 101
Our queue optimizations are not JIT based.
Thnx Filip. Could you elaborate on how it works, or point me to the relevant code?
If you have a robust solution that trumps V8's, I can take it to the V8 contributor mailing list and try to implement it.
Zach Boldyga Scalabull | Founder 1 (866) 846-8771 x 101
Hello, Sorry if this is an ignorant request, I scanned the proposals and didn't see anything that appeared similar.
Is it appropriate for ECMAScript to include a Queue implementation, or adjust shifting to a constant amortized time operation? Server-side usage of the language is mostly formidable nowadays, and I've run into cases where it would have been convenient to have an in-language queue.
I see in the latest Array.prototype.shift documentation ( tc39.github.io/ecma262/#sec-array.prototype.shift) that shift is still intended to be an O(n) operation, meaning those wanting to implement a proper queue may need to rely on external libraries, like this one: petkaantonov/deque .
As the github link mentions, V8 has a trick to get around array resizing, but for serious users we still need to rely on an external library. It'd be great if this was a built-in feature.
I'm sure someone has looked at this before - what do you think?
Best,
Zach Boldyga Scalabull | Founder 1 (866) 846-8771 x 101