Allocation, sizing and freeing with double-wide bitmaps: Oh my!

time to read 3 min | 424 words

A few years ago I wrote about how you can use a bitmap to efficiently find space to allocate. I ran into a similar scenario recently and had another thought about that. Let’s say that we want to allocate from a buffer, which you can see below:

image

Set bits in the buffer (marked by X) are busy, and cleared bits are empty. We can find a range of cleared bits to allocate easily enough, as I have shown in my previous post.

The question we now need to answer is one of freeing the memory. In the image above, you can see that we have two allocations, the yellow one (the first item) and the green one (which is composed of two cells).

The problem is how do we know what to free in this case? In the case of yellow it is really easy since we can see that it is a single element. But freeing the green element is much harder since we can’t tell its size. Usually you need to keep that size somewhere, and usually you store it into the memory itself (taking some part of the allocation to yourself as metdata overhead).

The advantage of bitmaps is that they are simple, memory efficient, and quite fast. The problem is that they are really limited in what information they give us. The buffer above shows us busy or free, nothing more.

What if we’ll make it more interesting? Instead of using a single bit per cell, we’ll use two. Then we have the following states:

  • 0b00 – free
  • 0b11 – allocated (and has next)
  • 0b10 – end of allocation

This doubles the memory we use, but also gives us a really important property. Given an index in the bitmap, we can easily ask what the allocated is. We just need to find the next cleared bit, and compute the distance. Let’s consider this simple bitmap:

0b_00_01_00_01_11_11_00_01_11_01_01

As you can see, we have the following allocations (I separated each two bits to make it easy to show):

  • 0 – 1 cell
  • 1 – 1 cells
  • 2 – 2 cells
  • 5 – 3 cell
  • 9 – 1 cell

The code to do the actual accounting looks like this:

And now we have a bitmap where the cost of tracking the size of the allocation is a single additional bit.

If you are expecting a lot of big allocations, then this may not be worth it, but if you have many small allocations, removing the need to track this is a major benefit.