4 ms·

While it's clever, it is also counter intuitive. I would expect an array to be 0(n) when inserting from the beginning. If I wanted something fast from both side

While it's clever, it is also counter intuitive. I would expect an array to be 0(n) when inserting from the beginning. If I wanted something fast from both side, I'd use a double ended queue[1]. This, as the author shows, lead to unexpected behavior. [1] https://en.wikipedia.org/wiki/Double-ended_queue https://en.wikipedia.org/wiki/Double-ended_queue

Karellen 2y ago
Isn't this kind of negated by the fact that `delete arr[n]` working the way it does has required JavaScript arrays to never have been "real" arrays, in the entire history of the language?
- eyelidlessness 2y ago
  I don’t think so. There’s a little bit more nuance to it (because it involves array “holes”—almost a third kind of null), but delete on an array index is semantically closer to assigning undefined to the index. It doesn’t actually delete the presence of the index.
  - Karellen 2y ago
    > It doesn’t actually delete the presence of the index. Doesn't it? Try: a = [ 6, 7, 8, 9, 10 ] delete a[2] for (x in a) { console.log(x) }
    - eyelidlessness 2y ago
      It doesn’t. It deletes the property “2”, but the index 2 remains present as a “hole” (like I mentioned before, almost a third kind of null). That removes it from iteration over the array object’s properties (i.e. your for-in loop), but doesn’t remove the index from the array or its iterable value representation: https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4EMBOAKAlAWAFB9EgBcACZEgXhIG0SA2AGhIHYmAOJgTiYEYAGEgF0A3HgLgoceNBABzdACIARrABmIVLAVNk02GFlEAFjpz5c61CXSEIpAB4kQqsphIBvPCW8lbMBDLy9jrwAJZgACaw9gDyquj2mGYAvmLmUXBEsGTUAEyCaX5SgYrIqlmo2mR6BsamaZbWtg5OLshunrg+vhL+0nIJIeFRsfGJKXhAA https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4E... If you click run there and look at the logged output, you’ll see: 1. The length remains the same after the delete statement 2. The items after index 2 keep their index 3. The for-of loop continues to iterate over index 2 (which now produces an undefined value on read)
      - Karellen 2y ago
        > the index 2 remains present as a “hole” (like I mentioned before, almost a third kind of null). It's an interesting model, and I think it definitely has its uses when reasoning about JS arrays. I'm not yet convinced it's the best model, but it's something I'm going to have to let percolate through my brain for a while to weigh it up properly. Thanks.
      - Dylan16807 2y ago
        I think you're misinterpreting how for-of works. For-of will iterate over deleted keys in the exact same way that it iterates over keys that never existed. let a = []; a[7] = 7; for (let v of a) console.log(v); > undefined, undefined, undefined, undefined, undefined, undefined, undefined, 7
  - recursive 2y ago
    > It doesn’t actually delete the presence of the index. It actually removes the index. > Object.keys([9,,9]) [ "0", "2" ] The value of the `length` property does nothing to imply the presence or lack of any keys. This is covered in the "exotic objects" behavior section in chapter 10 of the ECMAscript spec.
    - eyelidlessness 2y ago
      It removes the property key. It does not remove the index. You can see the distinction in the iterator produced by the array prototype’s keys method which, per ECMAScript spec chapter 23, yields the array’s indexes. And they are, in fact, determined by the array’s length. You can delete every property corresponding to an array’s indexes, and you’ll get the same result.
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.
deleted 2y ago
[deleted]

Karellen 2y ago

Isn't this kind of negated by the fact that `delete arr[n]` working the way it does has required JavaScript arrays to never have been "real" arrays, in the entire history of the language?

eyelidlessness 2y ago
I don’t think so. There’s a little bit more nuance to it (because it involves array “holes”—almost a third kind of null), but delete on an array index is semantically closer to assigning undefined to the index. It doesn’t actually delete the presence of the index.
- Karellen 2y ago
  > It doesn’t actually delete the presence of the index. Doesn't it? Try: a = [ 6, 7, 8, 9, 10 ] delete a[2] for (x in a) { console.log(x) }
  - eyelidlessness 2y ago
    It doesn’t. It deletes the property “2”, but the index 2 remains present as a “hole” (like I mentioned before, almost a third kind of null). That removes it from iteration over the array object’s properties (i.e. your for-in loop), but doesn’t remove the index from the array or its iterable value representation: https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4EMBOAKAlAWAFB9EgBcACZEgXhIG0SA2AGhIHYmAOJgTiYEYAGEgF0A3HgLgoceNBABzdACIARrABmIVLAVNk02GFlEAFjpz5c61CXSEIpAB4kQqsphIBvPCW8lbMBDLy9jrwAJZgACaw9gDyquj2mGYAvmLmUXBEsGTUAEyCaX5SgYrIqlmo2mR6BsamaZbWtg5OLshunrg+vhL+0nIJIeFRsfGJKXhAA https://www.typescriptlang.org/play/?#code/MYewdgziA2CmB0w4E... If you click run there and look at the logged output, you’ll see: 1. The length remains the same after the delete statement 2. The items after index 2 keep their index 3. The for-of loop continues to iterate over index 2 (which now produces an undefined value on read)
    - Karellen 2y ago
      > the index 2 remains present as a “hole” (like I mentioned before, almost a third kind of null). It's an interesting model, and I think it definitely has its uses when reasoning about JS arrays. I'm not yet convinced it's the best model, but it's something I'm going to have to let percolate through my brain for a while to weigh it up properly. Thanks.
    - Dylan16807 2y ago
      I think you're misinterpreting how for-of works. For-of will iterate over deleted keys in the exact same way that it iterates over keys that never existed. let a = []; a[7] = 7; for (let v of a) console.log(v); > undefined, undefined, undefined, undefined, undefined, undefined, undefined, 7
- recursive 2y ago
  > It doesn’t actually delete the presence of the index. It actually removes the index. > Object.keys([9,,9]) [ "0", "2" ] The value of the `length` property does nothing to imply the presence or lack of any keys. This is covered in the "exotic objects" behavior section in chapter 10 of the ECMAscript spec.
  - eyelidlessness 2y ago
    It removes the property key. It does not remove the index. You can see the distinction in the iterator produced by the array prototype’s keys method which, per ECMAScript spec chapter 23, yields the array’s indexes. And they are, in fact, determined by the array’s length. You can delete every property corresponding to an array’s indexes, and you’ll get the same result.

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.

deleted 2y ago

[deleted]