3 ms·

inlined into a vector I'm not sure what this means. My point was that a vector is like an arena but better in practicality because if someone is 'allocating'

inlined into a vector I'm not sure what this means. My point was that a vector is like an arena but better in practicality because if someone is 'allocating' from an arena, they are then storing that pointer somewhere. In a vector you can store the index somewhere, but you have the much better option of looping through everything and dealing with it contiguously instead of dealing with each element in some isolated way. Also a lot of arena implementations are basically linked lists inside a vector and freeing up the memory means jumping around in memory while dereferencing the pointers to unwind the individual allocations. The advantage is that you can free individual cells of the arena, but the cost of allowing that fragmentation is high. It's much better to avoid that and with hundreds of millions of elements it's likely that the data should be dealt with by just allocating huge chunks of memory and looping through them.

naasking 3y ago
> I'm not sure what this means. It means the structure storage is contained within the vector storage and you return an index, just as if it were an arena. The problem is that such an approach can only allocate a homogenous set of types and sizes. > Also a lot of arena implementations are basically linked lists inside a vector and freeing up the memory means jumping around in memory That's not an arena. The whole point of an arena is deallocation of all elements allocated from that arena is a constant time bulk operation.
- CyberDildonics 3y ago
  That's not an arena. The whole point of an arena is deallocation of all elements allocated from that arena is a constant time bulk operation. I've seen both, you can use empty cells to link to the next empty cell and the head pointer to link to the first empty cell in the chain so that the cells can be arbitrarily freed, but the option is always there to do what you said and do a single bulk deallocation of the actual heap memory allocation instead of dealing with individual cells. My point in all this is the same thing you have been implying. There aren't many differences in techniques so when people are talking about 'arena allocators' most of the time they should just be using a vector.

naasking 3y ago

> I'm not sure what this means. It means the structure storage is contained within the vector storage and you return an index, just as if it were an arena. The problem is that such an approach can only allocate a homogenous set of types and sizes. > Also a lot of arena implementations are basically linked lists inside a vector and freeing up the memory means jumping around in memory That's not an arena. The whole point of an arena is deallocation of all elements allocated from that arena is a constant time bulk operation.

CyberDildonics 3y ago
That's not an arena. The whole point of an arena is deallocation of all elements allocated from that arena is a constant time bulk operation. I've seen both, you can use empty cells to link to the next empty cell and the head pointer to link to the first empty cell in the chain so that the cells can be arbitrarily freed, but the option is always there to do what you said and do a single bulk deallocation of the actual heap memory allocation instead of dealing with individual cells. My point in all this is the same thing you have been implying. There aren't many differences in techniques so when people are talking about 'arena allocators' most of the time they should just be using a vector.