Skip to main content

Custom Allocators

Custom alloctors can be implemented easily by defining a new class that satisfies the low-level allocator interface. By calling a base class the allocator user-interface is automatically generated.

Implementing a new allocator​

Implementing a new allocator is easy. Given a struct

the following (lowlevel) interface should be implemented:

Finally, by calling the following base class the implementation is completed:

For an example, please have a look at the corresponding implementation of the DefaultAllocator that uses malloc/free.

The allocator base class​

The allocator base class generates and completes the implementation of myallocator. It implements the following basic interfaces

We already covered the implementation of owns. The implementation of __allocators_best_friend is also straightforward. It looks like this:

The idea of wrapping the three key allocator functions in one function is inspired from Lua's lua_Alloc. See also the blog post on an allocator API for C.

Let's look at the allocate method:

The implementation of __allocate, __reallocate and __deallocate is specific to each allocator.

Use in containers​

Here follows an example of a simple DynamicStack class. A couple of interesting things are the following:

  • The allocator is not passed as a template type parameter!
  • A __dtor method need not be implemented to release the dynamic resources. One is generated automatically since __dtor is implemented for block.
  • In new an opaque block is automatically cast to a S = alloc.SmartBlock(T).
  • A get and set method is available for SmartBlock objects of type S. Essentially, S = alloc.SmartBlock(T) is a smart pointer type.

The above class can be used as follows:

Recursive datastructures​

Recursive datastructures, such as linked lists can be implemented using specialized __dtor's and keeping an array of nodes, or, directly, using smart blocks. The implementation of block supports automatic destruction of recursive datastructures, and even cycles. Here follows an example of a cyclical double linked list:

To do:​

The following things remain:

  • The current implementation of block.methods.__dtor relies on recursion. LLVM may not be able to fully optimize the recursion to a loop, which may seriously limit the size of such datastrutures due to limits in stack-space. In the near future I will rewrite the algorithm using a while loop.
  • Right now only a default allocator is implemented based on malloc, realloc, calloc and aligned_alloc. Other standard allocators need to be implemented, such as, a 'stack', 'arena', 'freelist' allocators, etc.
  • Functionality for composing allocators to build new ones.
  • A SmartBlock(T) can already be cast to a SmartBlock(vector(T)) for primitive types T. By adding a __for metamethod it would become possible to iterate over a SmartBlock(vector(T)) and enable 'SIMD' instructions in a range for loop.