3 ms·

How does this work for collection types (ex. dynamic array) that can reallocate after growing? If there's multiple references, with at least one being mutable.

How does this work for collection types (ex. dynamic array) that can reallocate after growing? If there's multiple references, with at least one being mutable. Is there an extra pointer hop as compared to, for example Rust's Vec? i.e. the value on the stack is a pointer to some heap data that has a pointer to the actual array data.

YorickPeterse 3y ago
Arrays store just the pointers to their values, storing them inline isn't supported, like so: ptr to array --> array header size capacity [ val1 ptr --> val1 val2 ptr --> val2 ] At some point I'd like to support stack allocated values as an optimization, including the ability to allocate values directly into arrays, but that's not a priority at this point.
- tubthumper8 3y ago
  Hmm I wasn't talking about the values in the array, whether those are pointers or Int or whatever doesn't matter, but the allocation of the array data itself. If the collection has capacity=2 (2 words) and another element is pushed in, typically you'd double the capacity, allocate new memory (4 words), copy the data over, and deallocate the old data. If the square brackets in your diagram actually represents another pointer then I think we're on the same page, but otherwise I don't see how the data could be allocated in the same chunk as the header/size/capacity if there can be multiple (potentially mutable) references. (hopefully the formatting on this works) ptr -> header size capacity data ptr -> [ val1 val2 ]
  - YorickPeterse 3y ago
    Ah gotcha. Yes, the actual layout of arrays is: header size capacity data ptr Where `data ptr` is a raw pointer to data that is realloc'd as the array grows.

YorickPeterse 3y ago

Arrays store just the pointers to their values, storing them inline isn't supported, like so: ptr to array --> array header size capacity [ val1 ptr --> val1 val2 ptr --> val2 ] At some point I'd like to support stack allocated values as an optimization, including the ability to allocate values directly into arrays, but that's not a priority at this point.

tubthumper8 3y ago
Hmm I wasn't talking about the values in the array, whether those are pointers or Int or whatever doesn't matter, but the allocation of the array data itself. If the collection has capacity=2 (2 words) and another element is pushed in, typically you'd double the capacity, allocate new memory (4 words), copy the data over, and deallocate the old data. If the square brackets in your diagram actually represents another pointer then I think we're on the same page, but otherwise I don't see how the data could be allocated in the same chunk as the header/size/capacity if there can be multiple (potentially mutable) references. (hopefully the formatting on this works) ptr -> header size capacity data ptr -> [ val1 val2 ]
- YorickPeterse 3y ago
  Ah gotcha. Yes, the actual layout of arrays is: header size capacity data ptr Where `data ptr` is a raw pointer to data that is realloc'd as the array grows.