4 ms·

The problem is, JavaScript doesn't have a rich collections library built in, so the collections that do exist are pushed in all directions. The article you link

by paulgb 2y ago

The problem is, JavaScript doesn't have a rich collections library built in, so the collections that do exist are pushed in all directions. The article you linked actually highlight's JavaScript's array as the double-ended queue implementation: > Javascript's Array prototype & Perl's arrays have native support for both removing (shift and pop) and adding (unshift and push) elements on both ends. Unfortunately, trying to predict O-notation bounds in JavaScript is a fool's errand. The spec usually (always?) doesn't mention expected bounds, so it can depend on the runtime and the heuristics the runtime uses to decide what underlying data structure to use. I was surprised to learn that even implementing isEmpty(ob) in Javascript is an O(n) operation on most runtimes.

madeofpalk 2y ago
> The spec usually (always?) doesn't mention expected bounds Actually, I was just reading the other day that there are a few places where the specs do explicitly state expectations, such as performance characsteristics for Map/Set/WeakMap/WeakSet > Maps must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Maps. It is not intended to be a viable implementation model. https://tc39.es/ecma262/multipage/keyed-collections.html#sec-map-objects https://tc39.es/ecma262/multipage/keyed-collections.html#sec...
- psd1 2y ago
  Bloom filter and gpu
hajile 2y ago
As far as the spec is concerned, JS arrays are actually JS objects. The keys of JS arrays are technically stringified numbers. Because it is essentially a hashtable, there is no guarantee that the array is contiguous. It's not commonly done, but you could add something like `"myNonNumberKey"` to your array and things would actually work mostly as expected because the methods in question only work on stringified keys that contain only numbers (numbers like "01" aren't counted and the length property doesn't include any of these non-number keys). I'm not completely sure, but I believe these extra properties prevent some optimizations, so use at your own risk. When your array has holes, decent performance simply isn't possible, so giving hard O limitations would be mostly meaningless because the required performance characteristics would be so bad. This is where the JIT magic comes into play. They don't actually stringify your keys normally, but if they detect something requires these keys (eg, calling `Object.keys()` on your array), they can work around this at the expense of some performance. If you use the third function parameter for something like `.map()`, they can handle it, but there are edge cases (eg, what happens when you are halfway through the array then unshift or splice the first item?) that will slow things down. They could make stronger guarantees about arrays in the spec, but that creates a couple headaches. They would have to basically enshrine a second array specification. That specification would have all kinds of weird edge cases with the current array specification (like that `.unshift()` during a `.map()` issue). Those things are currently offloaded to implementations with the handwaving "you may do things better as long as the user can't tell the difference"). The other issue is that small implementations (eg, QuickJS or Duktape) that have hardware limitations in measured in kb don't have the space to guarantee these advanced features. They are constrained to pick just the one, slow implementation (maybe with a handful of the most important fast optimizations that are easy to implement) so they fit on the MCUs they were designed for. Finally, there is a record/tuple proposal that could allow a lot stricter standards and better performance guarantees for iterating a long tuple in a way that behaves like an immutable array.
Karellen 2y ago
> I was surprised to learn that even implementing isEmpty(ob) in Javascript is an O(n) operation on most runtimes. That is surprising. Where `n` is the number of members, yes? Surely that kind of operation should either return false immediately if there are no members, or return true in constant time if there is at least one member? ...although, do you have to iterate through the inherited members and check for `hasOwnProperty()`? Is it maybe O(n) where `n` is the number of enumerable inherited properties?
- paulgb 2y ago
  You would think, right? The JS runtime itself must have a constant time way to know this, but it’s not exposed anywhere. The best you can do is iterate over the keys and bail the first time you get a key. But (at least in V8) iterating over the keys does some work up front that is O(n), even if you bail at the first key!
  - patates 2y ago
    I think the issue is that the arrays are allowed to have holes: test = new Array(2) -> Array [ <2 empty slots> ] test[1] = true -> true test.length -> 2 test[0] -> undefined test[3] -> undefined test.some(x => x) -> true delete test[1] -> true test.some(x => x) -> false

by paulgb 2y ago

madeofpalk 2y ago

> The spec usually (always?) doesn't mention expected bounds Actually, I was just reading the other day that there are a few places where the specs do explicitly state expectations, such as performance characsteristics for Map/Set/WeakMap/WeakSet > Maps must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Maps. It is not intended to be a viable implementation model. https://tc39.es/ecma262/multipage/keyed-collections.html#sec-map-objects https://tc39.es/ecma262/multipage/keyed-collections.html#sec...

psd1 2y ago
Bloom filter and gpu

hajile 2y ago

As far as the spec is concerned, JS arrays are actually JS objects. The keys of JS arrays are technically stringified numbers. Because it is essentially a hashtable, there is no guarantee that the array is contiguous. It's not commonly done, but you could add something like `"myNonNumberKey"` to your array and things would actually work mostly as expected because the methods in question only work on stringified keys that contain only numbers (numbers like "01" aren't counted and the length property doesn't include any of these non-number keys). I'm not completely sure, but I believe these extra properties prevent some optimizations, so use at your own risk. When your array has holes, decent performance simply isn't possible, so giving hard O limitations would be mostly meaningless because the required performance characteristics would be so bad. This is where the JIT magic comes into play. They don't actually stringify your keys normally, but if they detect something requires these keys (eg, calling `Object.keys()` on your array), they can work around this at the expense of some performance. If you use the third function parameter for something like `.map()`, they can handle it, but there are edge cases (eg, what happens when you are halfway through the array then unshift or splice the first item?) that will slow things down. They could make stronger guarantees about arrays in the spec, but that creates a couple headaches. They would have to basically enshrine a second array specification. That specification would have all kinds of weird edge cases with the current array specification (like that `.unshift()` during a `.map()` issue). Those things are currently offloaded to implementations with the handwaving "you may do things better as long as the user can't tell the difference"). The other issue is that small implementations (eg, QuickJS or Duktape) that have hardware limitations in measured in kb don't have the space to guarantee these advanced features. They are constrained to pick just the one, slow implementation (maybe with a handful of the most important fast optimizations that are easy to implement) so they fit on the MCUs they were designed for. Finally, there is a record/tuple proposal that could allow a lot stricter standards and better performance guarantees for iterating a long tuple in a way that behaves like an immutable array.

Karellen 2y ago

> I was surprised to learn that even implementing isEmpty(ob) in Javascript is an O(n) operation on most runtimes. That is surprising. Where `n` is the number of members, yes? Surely that kind of operation should either return false immediately if there are no members, or return true in constant time if there is at least one member? ...although, do you have to iterate through the inherited members and check for `hasOwnProperty()`? Is it maybe O(n) where `n` is the number of enumerable inherited properties?

paulgb 2y ago
You would think, right? The JS runtime itself must have a constant time way to know this, but it’s not exposed anywhere. The best you can do is iterate over the keys and bail the first time you get a key. But (at least in V8) iterating over the keys does some work up front that is O(n), even if you bail at the first key!
- patates 2y ago
  I think the issue is that the arrays are allowed to have holes: test = new Array(2) -> Array [ <2 empty slots> ] test[1] = true -> true test.length -> 2 test[0] -> undefined test[3] -> undefined test.some(x => x) -> true delete test[1] -> true test.some(x => x) -> false