Fast Bitmap Fit: A CPU Cache Line friendly memory allocator for single object allocations

The pseudo-code below shows an example of how memory is allocated, used, deallocated, and then allocated again resulting in poor memory locality and cache performance for a simple data structure such as a linked list.

List lst = {}; // empty list.

// Populate the list.
for (i = 0; i < 10000; ++i) {
  // Insert a random number in the range [0..100] into the list.
  lst.append(random(100));
}

// Iterate over all the elements of the list.
// it is an iterator into the linked list lst.
for (it = lst.begin(); it != lst.end(); ++it) {
  // This will access memory in the order returned by the
  // allocator. Typically, for the first use, this is in address
  // order.
  print(it.value());
}

// Sort the list in ascending order of element value.
lst.sort();

// Return memory for linked list nodes back to the allocator.
lst.clear();

// Populate the list again.
for (i = 0; i < 10000; ++i) {
  // Insert a random number in the range [0..100] into the list.
  // This time around, the memory returned by the allocator
  // could be either in memory order or in the order returned
  // by List::clear(). If it’s the latter, then consecutive nodes
  // in the linked list will be randomly ordered.
  lst.append(random(100));
}

// Iterate over all the elements of the list.
// it is an iterator into the linked list lst.
for (it = lst.begin(); it != lst.end(); ++it) {
  // This will access memory in the order returned by the
  // allocator. If the memory address of the nodes is random,
  // this will thrash the cache, and negatively impact the
  // application’s running time due to an increase in CPU
  // cache misses.
  print(it.value());
}

Modern CPUs have L1/L2 caches to make references to main memory faster for data that can be stored in the CPU cache. Access to data in the L1 and L2 caches can be 200x and 15x faster than access to main memory[4].

Hence, it’s very much preferred to keep as much of the active data set in the CPU’s L1/L2 cache. Once data is in the cache, every attempt should be made to use as much of it as possible. Alternatively, we should attempt to lay the data out in memory such that data used together in time is laid out close together in space (in memory).

Additionally, application inefficiencies resulting from inefficient placement of data are very hard to detect and reason about [1, 10]. Hence, every effort must be made to ensure that programming abstractions support effective data locality by design.

General purpose memory allocators have been built and studied for a long time. There are some popular algorithms that are used very commonly.

1. 1.

   First Fit[5]: Typically implemented to optimize for allocation speed at the expense of memory fragmentation.

2. 2.

   Best Fit[6]: Typically implemented to minimize memory fragmentation at the expense of allocation speed.

3. 3.

   Binary Buddy[5]: Memory returned in sizes that are the closest power of 2 greater than or equal to the requested memory size.

4. 4.

   Bitmap Fit[7]: Bitmaps are used to keep track of fixed-size memory blocks that are free/used. Bitmaps need to be scanned to locate free memory of a specified size that is a multiple of the block size. The implementation relies on specific processor instructions related to bit manipulation, and the run-time cost is linear in the worst case. There have been more efficient variants proposed[8], but these remain fairly complex in terms of implementation complexity.

The most commonly used single object allocation strategy employs the use of buckets. These are lists of memory chunks of a fixed size, bucketed by size. Typically, the buckets are either multiples of a fixed page size or memory blocks that are powers of 2. This strategy results in efficient allocation/deallocation cost, but suffers from the problem of randomizing memory blocks over the lifetime of a long running application, since these free lists are maintained in the order in which memory was returned back to the memory allocator.

This paper builds on prior work which describes a bitmap allocator[9] that has the desirable memory-locality/cache-friendliness properties, but not the desirable efficient running time in the worst-case.

1. 1.

   No need to access user-memory: The Fast Bitmap Fit allocator maintains metadata separate from the data blocks. A an allocator that uses arenas and free-lists uses an intrusive linked list to chain together free blocks of the same size. This means that a traversal of the linked list necessarily needs to bring in the memory that will be returned to the user into the CPU’s cache.

2. 2.

   No memory alignment requirements: Since the Fast Bitmap Fit allocator maintains a bitmap in a separate part of the memory, the user-memory doesn’t need to align memory to pointer-size width (which is necessary in case the free-list pointers need to be maintained in the same location as the memory block to be returned to the user). Even $1$-byte blocks can truly be allocated and returned to the calling application. This means no forced internal fragmentation because no lower-bound is imposed by the allocator itself on the size of each user-returnable memory block.

Let’s take a concrete example. Assume that the allocator pre-allocates space for 8 objects of a fixed size $S$. Hence, we first allocate a memory block of size $S\times 8$ bytes. Each one of these $8$ memory blocks will have an associated bit indicating whether it is available $(0)$ or used $(1)$. These $8$ bits will make up the leaf levels of a complete binary tree-structure. This structure will have $8-1=7$ internal nodes, and hence $7$ additional bits for internal nodes. In all, we need $8+7=15$ additional bits of data to store metadata about which memory locations are available/used, and how to locate them quickly.

The bitmap is shown graphically below, with bit positions ranging from $0$ to $14$. This bitmap corresponds logically to the full binary tree also shown in the image below.

Significance of a bit’s value: The bit at position $0$ is the root node of the entire structure. If this bit has a value $0$, then it means that there is at least one free memory location available in the structure. If this bit has a value $1$, then it means that all the memory location in this structure are occupied.

Left/Right Child Arithmetic: To find the left child of a node at index idx, we go to the bit at position $\texttt{idx}\times 2+1$, whereas to find the right child of the same node, we visit the bit at position $\texttt{idx}\times 2+2$.

First, we start at the root (bit-$0$), and walk our way down left or right (preferring the left sub-tree if there’s a free object available in the sub-tree) till we reach a leaf node. In the example below, we start at node $0$, and end up at node $7$.

Now, we mark node $7$ as unavailable by setting the bit at index $7$ to $1$, and walk our way up the tree, always performing the logical $AND$ of sibling nodes to determine the value of the parent node. Once we hit a node where we didn’t update the value of the bit in that internal node, we can safely stop propagating up to the root of the tree.

The graphic below shows one more allocate operation being performed where another memory slot is marked as used.

The cost of each Allocate operation is $\Theta(\log{}n)$.

Let’s assume we’re starting with a tree which has $6$ nodes used as shown below.

Suppose the user requested to free the $6^{th}$ memory location (node $12$). We’d start at bit number $12$ in our bitmap, and keep walking up, setting all visited bits to $0$ as we walk up to the root. We can stop as soon as we find a bit that is already $0$ since all bits above it (up to the root) will already be $0$ by definition once we find an internal node with the value $0$.

The cost of each Free/Deallocate operation is $O(\log{}n)$.

Some applications may require allocating memory that is close to an already piece of allocated memory because it is expected that both objects will be used simultaneously. In such a scenario, it is beneficial for both the objects to live on the same page that is cached in the CPU’s L1/L2 cache. This allocator design supports this operation too to some degree.

The algorithm below isn’t guaranteed to find nodes as close to the target node as possible, but assuming a full factor of  60%-80%, there’s a good chance that one will find a node next to the provided ”hint” node’s address.

The general idea is to traverse down from the root of the tree, moving down in the direction of the target (hint) node as long as there is a free node available in that subtree. If there’s a choice to be made to go down the left or right subtree, choose the side that has free nodes closer to the ”hint” node’s location.

• •

  In the image below, the node $11$ is the ”hint” node.

• •

  We start at the root node $0$ and try to move down the tree toward the node $11$ (right child).

• •

  When we get to node $2$, we notice that it’s occupied, and we back up and instead go to node $1$ (left child of the root), which has a free node under it.

• •

  Here, we need to choose which side we wish to explore first. We choose the right child of this node (node $4$) since that node has children closer in memory to the hint node (node $11$).

• •

  Again we move down the right child of node $4$ to node $10$ (which is a leaf node), and stop here.

You can see that the node located is close in space (memory) to the hint node.

We now mark nodes as allocated as we did in the allocate method by walking up the parents of the left node, performing a boolean AND of the use/free bits at every level.

The cost of each Allocate-with-hint operation is $\Theta(\log{}n)$.