0

I am wondering how v8 solves the problem of storing arrays in a fragmented memory. Basically, what is the array data structure in v8. I assume under the hood v8 has to deal with the problem of memory fragmentation. I have read that C allocated arrays with contiguous memory which makes sense since you are allocating it directly anyways. But with JavaScript it is dynamic so it seems you can't allocate them contiguously always.

Given memory blocks of 8 bytes free ○ and allocated ●, imagine this scenario.

○○○○○○○○○○○○○○○○○○○○○○○○○○○

Then you add an array of 5 items:

●●●●●○○○○○○○○○○○○○○○○○○○○○○

Then you add another array to a different part of memory:

●●●●●○○○○◖◖◖○○○○○○○○○○○○○○○

The question is, if you add 10 more items to the first array, how does it work:

●●●●●●●●●◖◖◖●●●●●●○○○○○○○○○

Wondering if you are keeping track of the array structure somewhere else instead of just the fact that they are contiguous (like in C).

Lance
  • 75,200
  • 93
  • 289
  • 503
  • I think there is compaction in the v8 GC. And arrays have some extra space preallocated, if it does not fit - it's simply being reallocated. – zerkms Apr 23 '18 at 23:57
  • @zerkms what about the case where the memory is close to full and there is no space to fill the whole array contiguously but there is space for it to be fragmented. Also, reallocation seems like it would be a performance impact but I'm not sure. – Lance Apr 24 '18 at 00:05
  • In that case allocation fails. "performance impact" --- performance is not the absolute metric. It's an impact compared to "what"? If you don't do that you have to deal with mapped arrays, so instead of paying a low cost reallocation once (computers copy contiguous slices of memory really well) - you would pay that cost every time you lookup. – zerkms Apr 24 '18 at 00:14

1 Answers1

2

V8 developer here. Every array (both sparse/dictionary and dense/array mode) has one backing store for elements. When more elements are added than the backing store can hold, a new backing store is allocated and all elements are copied over. In this event the backing store is grown by a factor (not just one element), which is what gives you amortized-constant element addition performance. When not enough memory (or contiguous memory) for a new backing store is available, V8 crashes with an out-of-memory error.

jmrk
  • 34,271
  • 7
  • 59
  • 74