Thoughts from a C++ library developer.

Memory 0.5: Better build system, Low-level Allocators, BlockAllocator & Your Feedback is needed

I thought the last release has taken a long time, this one took even longer for less changes! But now foonathan/memory is finally released. This time things get low-level to allow a better high-level.

foonathan/memory is a library providing various memory allocators and adapter classes. Those allocators use a new RawAllocator concept that is simpler than STL’s Allocator and allows better control over the allocation aspect. Adapters and traits ensure compatibility with the existing model, allowing usage in STL or other containers.


Better build system

But first, let’s talk about the improved build system. I’ve spend many hours digging through various CMake documentation and tutorials to allow installation and give it find_package() support.

You can use the library as CMake subdirectory as before, but now it can also be installed via the cmake install command. This will install all the headers and build library files system-wide. You can then either use it in your own compiler/build system or call CMake’s find_package():

add_executable(my_exe ...)

find_package(foonathan_memory 0.5 REQUIRED)
target_link_libraries(my_exe PRIVATE foonathan_memory)
# somehow activate C++11 for your target

This also allows multiple installed versions and configurations. A given configuration is determined through the CMAKE_BUILD_TYPE, each build type can (and should) have a different configuration. The debugging options are fixed for the CMake build types Debug, RelWithDebInfo and Release but can be set for no given build type or your own build type as you wish.

I haven’t thoroughly tested it, please contact me if you run into any problems!

I will write a blog post in the near future™ explaining it as well. CMake is really lacking documentation on that matter.

Note that I have removed the ability to use a shorter include prefix, now you have to specify #include <foonathan/memory/xxx.hpp> to get the headers.

Or tamper manually with the include directories - if you like to live dangerously.

Also, after some feedback on my namespace alias post, I’ve removed the option to automatically provide the alias. Now you need to include the header file namespace_alias.hpp for that.

Both changes were necessary to allow a cmake install.

These are the only breaking changes in the release.

Besides some really minor stuff. Or anything that I’ve overlooked.

Low-level Allocators

In the library, I distinguish between two kinds of allocators: low-level allocators and high level arenas.

An arena allocator takes huge memory blocks and subdivides them in some way, examples are memory_pool and memory_stack. A low-level allocator uses some OS facility or similar directly to allocate the memory. Also, all low-level allocators can be used as the type of the default_allocator. The default_allocator is the default choice for the huge memory blocks in the arena.

Yes, I will document this better. More on that if you continue reading.

In 0.4, there were two low-level allocators: heap_allocator, allocating using std::malloc(), and new_allocator, allocating using ::operator new(). Now in 0.5, there are a few more and changes:

  • new_allocator still uses ::operator new()
  • heap_allocator now uses an OS function like HeapAlloc() under Windows
  • new malloc_allocator that will now use std::malloc() under each platform with a standard library
  • new virtual_memory_allocator that uses a virtual memory allocation
  • new static_allocator that uses a fixed-sized array for allocation

The default_allocator is still heap_allocator though.

static_allocator takes a pointer to a static_allocator_storage<Size> and uses it for the allocation. The storage buffer can be placed anywhere, but if you put it onto the normal stack, you have an allocator that handles stack memory. This can be used to have STL containers that do not use the heap at all.

Example here.

For the virtual memory allocation and heap allocation I have specified a tiny API that you can use directly. Heap allocation is done through heap_alloc() and heap_dealloc(), the virtual memory allocation over virtual_memory_reserve/commit/decommit/release(). The latter functions work on single or multiple memory pages only and map to mmap() or VirtualAlloc(). heap_allocator and virtual_memory_allocator are just tiny wrappers above that calling the functions.

BlockAllocator and memory_arena

virtual_memory_allocator just calls virtual_memory_reserve() directly followed by virtual_memory_commit() on the minimum number of pages needed to satisfy the memory request. I agree, that is pretty useless.

But not the variant virtual_memory_block_allocator.

The high-level arena allocators work on huge memory blocks. In 0.4, you could only specify a normal RawAllocator that performs the block allocation but you had no control over the behavior when needing to allocate a new memory block.

Now I’ve introduced a BlockAllocator. A simple BlockAllocator looks like so:

class block_allocator
    block_allocator(std::size_t block_size)
    : block_size_(block_size) {}
    memory_block allocate_block()
        auto mem = ::operator new(block_size_);
        return {mem, block_size_};
    void deallocate_block(memory_block b)
        ::operator delete(b.memory);
    std::size_t next_block_size() const
        return block_size_;    
    std::size_t block_size_;    

memory_block is a type defined by the library, it consists of a pointer to memory and a size of the memory.

This does not only specify how the memory gets allocated but how much. The size of the memory blocks is completely up to the implementation, it could always be the same (like here), double, triple, does not allow growing at all, etc. It is further guaranteed that deallocate_block() will always be given the last allocated block, doing allocations in a stack-like manner.

The new class growing_block_allocator adapter takes a RawAllocator and uses it to allocate memory blocks, each doubling in size (this is as it was before). Template magic ensures that when passing a RawAllocator as template parameter to an arena allocator, it will be wrapped into a growing_block_allocator. This allows using RawAllocators everywhere a BlockAllocator is required. So the default allocator will now in fact be growing_block_allocator<default_allocator>.

The adapter fixed_block_allocator works similar but does not allow any growth, it throws an exception. It can be used to prevent growth of the arena.

But the real power comes when writing customized block allocator. virtual_block_allocator uses it. It takes a block size and how many blocks it should allocate. Then it reserves the appropriate number of pages for num_blocks * block_size, each call to allocate_block() will now commit the appropriate number of pages for block_size and moves a top pointer forwards, deallocate_block() decommit the top block. This behaves like a memory_stack but on blocks/pages, instead of bytes.

A memory_stack<virtual_block_allocator> works thus very similar to the stack allocator described here on Molecular Musings. But the virtual memory part of the stack can be used elsewhere as well, making it more flexible.

The power of BlockAllocators can be used when writing own arena allocators but I do not recommend using them directly. Instead the class template memory_arena provides almost the same interface plus a few additional functions, but it also takes care of storing already allocated memory blocks and deallocates them in the destructor. Optionally, it can also cache blocks instead of calling deallocate_block() on the BlockAllocator, this makes a subsequent allocation possibly faster.

Other changes

The power of BlockAllocator has allowed me to write better tracked allocators. The improved deeply_tracked_allocator takes a fully instantiated type and wil rebind any BlockAllocators it uses to a proxy that also notifies a Tracker over the growth. This works completely extrusive and can be used for your own arena classes as long as they can take a BlockAllocator as template parameter.

This was made possible by a set of traits is_raw_allocator<T> and is is_block_allocator<T> that use template magic to determine whether a given type is a RawAllocator or BlockAllocator - no specialization required (usually). The traits have also enabled me to put a few static_assert()s in places, allowing better error messages and concept checks.

They also seem to work under MSVC 12, which is kind of a miracle.

I’ve also added a few new derived exception classes and optionally extern templates for the most common instantiations (like memory_pool<> or memory_stack<> and all the allocator_traits for library allocators).

There is also a wrapper and adapter for the Polymorphic Memory Resource TS, functioning in both directions. The base memory_resource base class can be set to your own type to, for example, co-exist with Boost’s implementation.

About the documentation

Well, the documentation…

It is okay-ish, but could definitely be improved. The reference part is usable, but I need more examples, better introductions and stuff like that.

They will come, I just haven’t gotten around to it before the release and didn’t want to let you guys wait any longer.

The current documentation can be found here.

Note: I’ve just overwritten the 0.4 documentation.

What’s for the future? - Feedback request!

My list of must-do features has become rather short. But I don’t know all of the needs of the target audience (you!). I’ve put all my time in working on it or other libraries, I cannot use them much in bigger projects. So maybe it is completely useless for you, because it’s missing something/should work differently.

So please contact me! Tweet me, comment, mail me, share it, write issues, write letters, send pigeons to my home, whatever.

Tell me:

  • Are you using the library (already)?
  • If no: Why not?/What kind of crap it is.
  • If yes: How’s been your experience? For what are you using it for?
  • What should be added?
  • What should be improved?
  • What doesn’t work like it should?
  • What is too slow?
  • What is buggy?

The more you tell me, the more I can do for you. The more you tell me, the better the library will be at its 1.0 release!