For a few years, I've been programming with hierarchical allocators, temp memory, arenas, and all of that. Much like Casey, I can get away without dynamic arrays just fine. I just use fixed-sized arrays or bucket lists and b+trees. If things need to get freed and reused, I use free lists. However, sometimes it's really convenient to at least use a bucket array, where the only part that uses exponential growth (array doubling) is the array of bucket pointers.
The rub is that once you have array doubling in your program, you start to want to lean on a general-purpose heap allocator and use dynamic arrays everywhere (like Jon). This is because free-listing becomes a much harder and more general problem.
Does anyone here use dynamic arrays effectively with some favorite heap implementation that can be used on top of basic, stack-like arena allocation?
The rub is that once you have array doubling in your program, you start to want to lean on a general-purpose heap allocator and use dynamic arrays everywhere (like Jon). This is because free-listing becomes a much harder and more general problem.
Does anyone here use dynamic arrays effectively with some favorite heap implementation that can be used on top of basic, stack-like arena allocation?
Edited by Blake Martin
on
Reason: Initial post
rationalcoder
Does anyone here use dynamic arrays effectively with some favorite heap implementation that can be used on top of basic, stack-like arena allocation?
I don't understand exactly what you mean. If you want a general heap allocator, make one that fits your needs. If your goal is to make dynamic arrays then you can probably have a specific allocator for that instead of a general heap allocator since array contain fixed size elements. There probably isn't one thing to solve all you memory problems.
One thing I do for memory space that can grow is to use VirtualAlloc to reserve (not commit) a big space and committing in block when the memory needs to grow (for example reserving 1Gio and committing by blocks of 1Mio). That way when the memory needs to grow, it doesn't need to move and the pointers don't change. You still have a upper bound to the size, reserved memory cost a bit of memory and you don't want to call VirtualAlloc too often.
I understand what you are saying, but that approach is not a general thing that you want to do for all dynamic arrays in a program. That's a special case thing. I'm talking about trying to support the allocation needs of a program like those that will be written in Jai, since it has convenient, built-in dynamic arrays.
The rub is that you can get really close to having one thing that suits all your memory needs as long as you don't use dynamic arrays at all. Temp memory, free lists, and arenas solve just about everything before you introduce dynamic arrays. Once you have them, you immediately run into a general heap allocator problem again.
You can treat arrays that have grown past a page or two specially and move them to an arena that can grow dynamically without copying, but this can only be done efficiently and conveniently on platforms like Linux, which support mremap with MREMAP_MAYMOVE. To provide consistent performance, you need to program to the lowest common denominator.
The conclusion that I've come to is that you can't really expect to implement dynamic arrays efficiently on top of a normal, stack-like arena. They are an entirely different class of allocations.
The best I've come up with is a compromise that introduces volatility into the arena. If you are using dynamic arrays as your primary basic data structure (like people will in Jai), most of them will be small. Therefore, when someone signals to the allocator that they are reallocating an array (by calling realloc), you consult a small table of power-of-2 free lists. Since there will be many small arrays, the overall wasted memory with those should be minimal. Then, when someone reallocates a big array, you still just allocate the new size and do a memcpy, but you free the arena chunk that the array occupied back to the OS and remove the node from the list. A slightly different approach would be to have two arenas, one for normal allocations and small arrays, and another for handling the big array allocations. That approach is simpler and slightly more efficient, but it requires two arenas.
I've pretty much just decided that I will be using bucket arrays anywhere I would've wanted a dynamic array.
The rub is that you can get really close to having one thing that suits all your memory needs as long as you don't use dynamic arrays at all. Temp memory, free lists, and arenas solve just about everything before you introduce dynamic arrays. Once you have them, you immediately run into a general heap allocator problem again.
You can treat arrays that have grown past a page or two specially and move them to an arena that can grow dynamically without copying, but this can only be done efficiently and conveniently on platforms like Linux, which support mremap with MREMAP_MAYMOVE. To provide consistent performance, you need to program to the lowest common denominator.
The conclusion that I've come to is that you can't really expect to implement dynamic arrays efficiently on top of a normal, stack-like arena. They are an entirely different class of allocations.
The best I've come up with is a compromise that introduces volatility into the arena. If you are using dynamic arrays as your primary basic data structure (like people will in Jai), most of them will be small. Therefore, when someone signals to the allocator that they are reallocating an array (by calling realloc), you consult a small table of power-of-2 free lists. Since there will be many small arrays, the overall wasted memory with those should be minimal. Then, when someone reallocates a big array, you still just allocate the new size and do a memcpy, but you free the arena chunk that the array occupied back to the OS and remove the node from the list. A slightly different approach would be to have two arenas, one for normal allocations and small arrays, and another for handling the big array allocations. That approach is simpler and slightly more efficient, but it requires two arenas.
I've pretty much just decided that I will be using bucket arrays anywhere I would've wanted a dynamic array.
Edited by Blake Martin
on