6 ms·

~lol, imagine not doubling the capacity of a dynamic array upon allocation.~ In all seriousness, this is a great read, and I was mildly surprised JS was about

~lol, imagine not doubling the capacity of a dynamic array upon allocation.~ In all seriousness, this is a great read, and I was mildly surprised JS was about the same speed as Wasm once TurboFan kicks in. As a compiler engineer, it's nice step back and appreciate the myriad of runtime-based optimizations that can be done with modern JIT compilers. That being said, assembly script doesn't perform and high-level optimizations upon compilation, so I wonder how fast it will be once fully matured.

kevingadd 6y ago
The correct growth rate is typically not actually 2x, but it's certainly not +1 either :)
- RicardoLuis0 6y ago
  growth rate varies between use cases, too small and you pay on performance overhead, too large and you pay on memory overhead, 2x is a decent mid-spot
  - masklinn 6y ago
    Wasn’t there some consideration that with 2x you could never reuse previous contiguous allocations but at 1.4 (ish?) it was an option and improved fragmentation in some cases? Of course it depends on the behaviour and binning (or lack thereof) of your allocator. Edit: it’s 1.5, any growth factor below 2 has this property, how far below 2 regulates how quickly it happens, https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#motivation https://github.com/facebook/folly/blob/master/folly/docs/FBV... > it can be mathematically proven that a growth factor of 2 is rigorously the worst possible because it never allows the vector to reuse any of its previously-allocated memory. > [...] > choosing 1.5 as the factor allows memory reuse after 4 reallocations; 1.45 allows memory reuse after 3 reallocations; and 1.3 allows reuse after only 2 reallocations
    - dahfizz 6y ago
      I'm not sure I understand the benefit of this. With a growth factor < 2, you have a chance of getting back chunks of memory that were previously used. That doesn't affect fragmentation / cache hits since all your data is always in the current chunk. What am I missing?
- adrusi 6y ago
  Eh, at the point you're tuning the growth factor, you might consider just not using a dynamically sized array
  - eru 6y ago
    Depends on whether you are talking about tuning the growth factor for a single instance, or whether you are talking about tuning the default growth factor in general. Eg Python has put a lot of thought into their dynamic array (and dict) growth factors.
- hansvm 6y ago
  I don't see this brought up very often, but you have a huge world of flexibility in choosing growth rates beyond just adding constants for an O(n) amortized append time or multiplying by a constant for O(1). E.g., if you choose x -> x(1+1/log(x)) then you get an amortized append time of O(log(n)) while paying a memory overhead approaching 0% for large datasets. The distribution of (and SLOs for) appends relative to other operations can make that kind of idea more or less attractive, but even common data structures have a lot of room for improvement if you can tailor them to your use case a little bit.
brabel 6y ago
> assembly script doesn't perform and high-level optimizations upon compilation IIRC it does because it uses binaryen[0] (as claimed in the link) which is an optimizing compiler. [0] https://github.com/WebAssembly/binaryen https://github.com/WebAssembly/binaryen
- dassurma 6y ago
  Author here. It’s a trade-off for simplicity. It’s a small team and they are still working towards feature completeness. Deferring optimization to Binaryen is the easy way out at the cost of not having high-level optimizations. If they finish their IR, that will most likely change.

kevingadd 6y ago

The correct growth rate is typically not actually 2x, but it's certainly not +1 either :)

RicardoLuis0 6y ago
growth rate varies between use cases, too small and you pay on performance overhead, too large and you pay on memory overhead, 2x is a decent mid-spot
- masklinn 6y ago
  Wasn’t there some consideration that with 2x you could never reuse previous contiguous allocations but at 1.4 (ish?) it was an option and improved fragmentation in some cases? Of course it depends on the behaviour and binning (or lack thereof) of your allocator. Edit: it’s 1.5, any growth factor below 2 has this property, how far below 2 regulates how quickly it happens, https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#motivation https://github.com/facebook/folly/blob/master/folly/docs/FBV... > it can be mathematically proven that a growth factor of 2 is rigorously the worst possible because it never allows the vector to reuse any of its previously-allocated memory. > [...] > choosing 1.5 as the factor allows memory reuse after 4 reallocations; 1.45 allows memory reuse after 3 reallocations; and 1.3 allows reuse after only 2 reallocations
  - dahfizz 6y ago
    I'm not sure I understand the benefit of this. With a growth factor < 2, you have a chance of getting back chunks of memory that were previously used. That doesn't affect fragmentation / cache hits since all your data is always in the current chunk. What am I missing?
adrusi 6y ago
Eh, at the point you're tuning the growth factor, you might consider just not using a dynamically sized array
- eru 6y ago
  Depends on whether you are talking about tuning the growth factor for a single instance, or whether you are talking about tuning the default growth factor in general. Eg Python has put a lot of thought into their dynamic array (and dict) growth factors.
hansvm 6y ago
I don't see this brought up very often, but you have a huge world of flexibility in choosing growth rates beyond just adding constants for an O(n) amortized append time or multiplying by a constant for O(1). E.g., if you choose x -> x(1+1/log(x)) then you get an amortized append time of O(log(n)) while paying a memory overhead approaching 0% for large datasets. The distribution of (and SLOs for) appends relative to other operations can make that kind of idea more or less attractive, but even common data structures have a lot of room for improvement if you can tailor them to your use case a little bit.

brabel 6y ago

> assembly script doesn't perform and high-level optimizations upon compilation IIRC it does because it uses binaryen[0] (as claimed in the link) which is an optimizing compiler. [0] https://github.com/WebAssembly/binaryen https://github.com/WebAssembly/binaryen

dassurma 6y ago
Author here. It’s a trade-off for simplicity. It’s a small team and they are still working towards feature completeness. Deferring optimization to Binaryen is the easy way out at the cost of not having high-level optimizations. If they finish their IR, that will most likely change.