Bucket and Pool Allocators

Bucket Array / List (Typed) #

• Resizable array of fixed length buckets
• When appending to the list, the next index in the latest bucket is used

• Init/Reset:
• Insert element:
• Remove index:
• Remove value:
• Sorted remove (both):
• Count Elements:
• Iterate: no setup + for each element

Downside: Separate free list that takes additional memory.

Bucket Allocator (Typed) #

• Use a Bucket Array together with a free list

Separate free list #

• Init/Reset:
• Allocate:
• Free:
• Count Allocated:
• Iterate: setup (sorting free list) and for each element (check if in free list)

Inplace free list #

• Init/Reset:
• Allocate:
• Free:
• Count Allocated:
• Iterate: setup (writing all free into hashset or something) and for each element to check in the hashset

Pool Allocator (Typed) #

• Fixed sized chunks

• Inplace free list has to store pointers (relative offsets don’t work accross different chunks)… Unless you use s64 for the relative offsets..

• Performance characteristcs same between growable pool allocator and fixed sized allocator

• Init/Reset: memset 0 for relative offsets, else iterate and set the address of the successor slot to each of them

• Allocate:

• Free:

• Iterate: setup (writing all free into hashset or something) and for each element to check in the hashset

Preliminary conclusion #

Inplace free list reult in init/reset time. How can we improve that? This problem would also exist with a out-of-place free list if on init/reset we would have to fill it with all the available spots and then only allocate from the free list.

Solution for init / reset #

We don’t do that however, we treat the free list as something which contains pointers to freed memory but an empty free list does not signal that no free spots are left, it only means that nothing was freed yet. So we usually keep track of the next free location / index too. If the free list is empty, check if the next free location / index is in the owned memory region and if it is, return it and advance the pointer. If the free list was not empty, then return from there and don’t advance the next allocation pointer.

We can apply the same to data structures with an in place free list, which should bring reset / init time down to .

• Pool Allocator
• Bucket Allocator with inplace free list

Problem with iteration over growable allocators with in place free lists #

Iteration would still not be trivial. Maybe the easiest would be to sort the in place freelist “inplace” such that each free entry points to the next free entry in order of the memory, then we don’t need additional space to store the free spots in a more organized way like trees or hashsets (We wanted to save space after all). For iteration we only have to keep track of the next free spot. And while we iterate we only have to compare the current spot to the next free spot to see if the current spot is occupied. The free list would have to be sorted like this:

1. The head of the free list would start at the free spot with the lowest memory address
2. Each free entry points to the next lowest free memory address

This works for a non-growable pool allocator since the memory is contiguous and you would start iteration at the start of the chunk. But when dealing with multiple chunks / buckets that are allocated separately and you don’t have gurantees that you will get back bigger and bigger memory addesses back from the allocator for them you run into a problem, example:

1. Growable pool allocator

      chunk: at 0x00007000
       [|||||||||||||||next->0]
   

2. Chunk gets filled and new chunk is allocated

      chunk: at 0x00007000
       [|||||||||||||||next->0x00002000]
   
      chunk 2: at 0x00002000
       [|||||||||||||||next->0]
   

3. Now if we sort the free list according to the steps above, it would start in chunk 2 (assuming something was freed in there) as the memory addresses are lower than in the original chunk.

4. For iteration we would still start at the original chunk because that is where the pool allocator points to as the first chunk, and the chunks are linked between each other. We would notice that our current chunk already starts (in memory order) after the first free spot. In that case we can’t make any gurantees about which spots are free, whithout walking the free list up until the current chunk.

To avoid that we would have to keep the chunk-list sorted too. This also applies to a bucket allocator with inplace free list. The array which holds the bucket would need to be sorted too. Which is not really a problem because it is a short array, so sorting it is really cheap. We can assure that property at chunk allocation time too, by doing an insertion-sort kinda thing when we allocate a new chunk / bucket and instead of just appending it, we insert it into the existing buckets / chunk structure at the correct place. Chunk / bucket allocation is not so common so that operation would not be too painful, I guess. You would only have a handful of chunks anyways. But this also means we can just sort it on demand (only happens when you want to iterate over it). The actual chunk order does not matter to the pool or bucket allocator.

We cannot afford insertion sort for the free list though. Freeing should always be .

Sorting the free list #

We have to transform the free list from something like

           /-head of free list
           V
[  | 2|10| 1|  |  |  |  |  |--| 9|  ]
 0  1  2  3  4  5  6  7  8  9  10 11

To:

    /-head of free list
    V
[  | 2| 3| 9|  |  |  |  |  |10|--|  ]
 0  1  2  3  4  5  6  7  8  9  10 11

Sort condition: (u64)this_cell.next_prt > (u64)&this_cell

If additional memory consumtion during sort is not of concern, we can just gather all the pointers (head + all the links, excluding the nullptr at the end of the list) into an array list, then sort it, then write it back:

1. The head will be be the first element of the sorted array
2. For each pointer in the array:
   • write to the location it points at:
     • the next pointer in the array if it has a next element
     • nullptr otherwise