3 ms·

Honestly, the fact that AssemblyScript's Array implementation does not double the internal capacity but instead adds just one more slot when reallocating makes

by debt93 5y ago

Honestly, the fact that AssemblyScript's Array implementation does not double the internal capacity but instead adds just one more slot when reallocating makes me worry about the quality of the language as a whole. I hope it is just an oversight, but come on...

kohlerm 5y ago
Also without an integrated GC, most modern languages do not run well on ASM.
- kohlerm 5y ago
  I meant WASM of course :-)
gvb 5y ago
Doubling the allocation is a "hack" that is helpful when reallocations are common and thus is helpful for languages that extend arrays very often (typical of dynamic languages with GC) and where memory is cheap and plentiful. One of the prime features of assembly language is that the person (compiler) that is generating it expects tight control over what it does. A 2*X allocation when you ask for X is unexpected. Imagine if, when you went to the ATM and withdrew $100, the bank actually withdrew $200 from your account and held back the extra $100 so that, the next time you went to the bank and withdrew $20 it would take it out of the "held back" amount rather than doing another withdraw. I would be very unhappy with that algorithm.
- debt93 5y ago
  It is not a "hack". It is the behavior that I expect from a dynamically resizable array. std::vector in C++ does it, so does Vec in Rust, and they are not dynamic languages with GC.
  - pjmlp 5y ago
    Which std::vector though? ISO C++ places no such requirement on std::vector, each implementation is free to choose their own implementation provided it matches the O() notation requirements. C++ is not like Rust where the implementation dictates the semantics.
- TheCoelacanth 5y ago
  For `push` to extend capacity by just 1 is an absolutely insane default. There is no sensible usage for a method that does that. It turns `for(let i = 0; i < n; i++) { arr.push(x); }` from linear into quadratic. If automatic resizing exists, then it should do it in a sensible way. Otherwise it's just a footgun that you should leave out of the language like C does.
- joppy 5y ago
  In order for append-to-back to have O(1) amortised running time, the capacity needs to be multiplied by some constant >1. Any constant would do just fine in terms of complexity, but 2 is the obvious simple choice, being the first integer greater than 1. If the capacity is only increased by some constant each time, rather than multiplied, this leads to O(n^2) running time for a sequence of n append-to-back operations, surely something to be avoided.

by debt93 5y ago

kohlerm 5y ago

Also without an integrated GC, most modern languages do not run well on ASM.

kohlerm 5y ago
I meant WASM of course :-)

gvb 5y ago

Doubling the allocation is a "hack" that is helpful when reallocations are common and thus is helpful for languages that extend arrays very often (typical of dynamic languages with GC) and where memory is cheap and plentiful. One of the prime features of assembly language is that the person (compiler) that is generating it expects tight control over what it does. A 2*X allocation when you ask for X is unexpected. Imagine if, when you went to the ATM and withdrew $100, the bank actually withdrew $200 from your account and held back the extra $100 so that, the next time you went to the bank and withdrew $20 it would take it out of the "held back" amount rather than doing another withdraw. I would be very unhappy with that algorithm.

debt93 5y ago
It is not a "hack". It is the behavior that I expect from a dynamically resizable array. std::vector in C++ does it, so does Vec in Rust, and they are not dynamic languages with GC.
- pjmlp 5y ago
  Which std::vector though? ISO C++ places no such requirement on std::vector, each implementation is free to choose their own implementation provided it matches the O() notation requirements. C++ is not like Rust where the implementation dictates the semantics.
TheCoelacanth 5y ago
For `push` to extend capacity by just 1 is an absolutely insane default. There is no sensible usage for a method that does that. It turns `for(let i = 0; i < n; i++) { arr.push(x); }` from linear into quadratic. If automatic resizing exists, then it should do it in a sensible way. Otherwise it's just a footgun that you should leave out of the language like C does.
joppy 5y ago
In order for append-to-back to have O(1) amortised running time, the capacity needs to be multiplied by some constant >1. Any constant would do just fine in terms of complexity, but 2 is the obvious simple choice, being the first integer greater than 1. If the capacity is only increased by some constant each time, rather than multiplied, this leads to O(n^2) running time for a sequence of n append-to-back operations, surely something to be avoided.