3 ms·

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 dy

by 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 gvb 5y ago

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.