In this reprinted <a href="http://altdevblogaday.com/">#altdevblogaday</a>-opinion piece, Blitz Games' Lee Winder presents a custom allocation system that is meant to be both easy to use and simple to understand, without restricting what people could do w
[In this reprinted #altdevblogaday-opinion piece, Blitz Games technical manager Lee Winder presents a custom allocation system that is meant to be both easy to use and simple to understand, without restricting what people could do with them] Quite a few years back, I started developing a custom STL implementation, which was eventually adopted and used throughout our company. One of the most important things to get right when developing any kind of generic container library is the way memory is allocated. It needs to be lightweight, highly flexible and above all easy to understand so people are willing to experiment with it. But STL Allocators have a bad reputation, and it's for a good reason. They are complex, hard to understand and have some interesting behaviour that seems designed to confuse. As a result, I needed to look at how we were going to provide a custom allocation system that was both easy to use and simple to understand without restricting what people could do with them. A Bit of History A while back, BitSquid published a post entitled Custom Memory Allocation in C++. This excellent post covered how the BitSquid engine used an allocator model to perform memory allocation throughout their entire engine. But the FTL requires a slightly different approach, so I won't be treading over already covered ground here. FTL allocators are well-hidden inside containers. The only control you have is specifying the allocator type, which means its use, and how and when objects are allocated and created, is completely fixed with only the allocator itself being able to effect the outcome. Because of this, the allocator behavior needs to be as customizable as possible without requiring any changes the container itself. When the FTL was original started, it was quite small scale and only used by a couple of developers, so allocators were not a priority. The flexibility wasn't needed, so in-container malloc and free allowed us to concentrate on container creation, but obviously this wasn't going to last. The following just describes the various approaches we took, why we dismissed them and what we eventually ended up with. The Initial Approach Allocators should have a minimal overhead. What we didn't want to do was increase the size of every container dramatically when we rolled out customisable allocators. As a result, we initially used an approach used by a couple of vendors and defined the allocator specification using only static members – removing the need for an internal allocator object.
// Completely made up code showing the use of a static based allocator
template
class vector
{
void push_back(void)
{
void* new_memory = Alloc::allocate( sizeof(T) );
T* new_object = new(new_memory) T;
}
};I knew this would limit the flexibility of the allocators, but it had minimal overhead (especially using default template parameters) and wouldn't effect those containers already being used. And besides, programmers are a creative bunch, and I wanted to see what people did with this before resigning it to the scrap heap. But while programmers were able to work around the main limitation of not having allocator state per container, they were having to jump through hoops to get the behavior they wanted. Which made it less likely that other programmers would feel confident enough writing their own allocators, and their ability to really customize their behaviour was too limited. So, we ended up adding allocator state on a per container basis, making it much easier for developers to do what they wanted though it did add at least 4 bytes per container. But I felt that flexibility and simplicity were much more important.
// Completely made up code showing the use of an instanced allocator
template
class vector
{
Alloc m_allocator;
void push_back(void)
{
void* new_memory = m_allocator.allocate( sizeof(T) );
T* new_object = new(new_memory) T;
}
};Allocator Specification The allocator specification is complicated. While I'm sure there are good reasons for some of the decisionss I wanted ours to be much simpler. Sos removing the type information (since our allocators work on raw memory and nothing else), removing the rebind(!) and exception handling (which we don't use) we ended up with the following.
typedef ftl::pair allocated_memory;
class Alloc
{
public:
allocated_memory allocate(const size_t alloc_size);
void deallocate(void* ptr);
};And for the basic allocator, that's it, it doesn't require anything else to work, but it does have one interesting aspect.
typedef ftl::pair allocated_memory;As we can have all sorts of allocator types, what it allocates might not be exactly what you asked for. If it can't allocate all the memory you requested, that's fine, it simply returns allocated_memory(nullptr, 0), but it can also return more than was requested (for example, fixed sized block allocators will do this). This return type simply allows the allocator to return not only the allocated memory, but also how much was allocated, which allows calling objects to take advantage of this additional memory if possible. Most of the time this isn't queried and only what was asked for is given, but it offers an additional level of information which might allow better memory usage in some containers. So, a container will most likely end up with something like the following when adding and removing elements.
// Creating a new object in a container
allocated_memory new_memory = m_allocator.allocate( sizeof(T) );
if (new_memory.first)
T* new_object = new(new_memory.first) T;
// Losing the object now we're done with it
old_object->~T();
m_allocator.deallocate(old_object);This is fine and gives us a very simple entry point for allocators. But by forcing the use of placement new and the destructor call in the container itself, we are limiting what an allocator can do. While the allocators are required to return raw memory, that doesn't mean that it has to internally. Some allocators might pre-create the objects before returning them so creation is front loaded but the forced placement new could mean we're over-riding an object that has already been created. Construction Functions As a result, we want developers to be able to not only over-ride the memory allocation, but also the object creation. 99 percent of allocators won't need to do this so we don't want to add additional requirements to the allocator so instead we can create non-member, non-friend functions, specialized on the allocator, which will do the creation for us.
template
TConstruct* construct(TAlloc& allocator);
template
TConstruct* construct(TAlloc& allocator, const TConstruct& obj);
template
TConstruct* construct(void* allocated_mem);
template
TConstruct* construct(void* allocated_mem, const TConstruct& obj);
template
void destroy(TConstruct* ptr);
template
void destroy(TConstruct* ptr, TAlloc& allocator);So our point of allocation/creation now becomes something much simpler and much more powerful.
// Creating a new object in a container
T* new_object = alloc::construct(m_alloc);
// Lose our existing object and return it back to the allocator
alloc::destroy(old_object, m_alloc);The default version of construct performs the allocation and placement now within the construct function, but should the allocator need something more (or less), simply overloading the function on the allocator type allows complete control over both memory allocation and object creation. The same goes for the destroy function and the automatic call of the objects destructor. No Base Allocator One thing I didn't add to the allocators was a base allocator interface. The allocators are created within the container, with their type defined at the point of the containers declaration. The addition of a base interface (and the associated virtual functions) would have increase the size over-head of the allocator which is something I wanted to avoid and something I thought didn't add enough to warrant the overhead. I was less worried about the overhead of calling a virtual function, as that would be insignificant compared to the overhead of everything else what was going on. Conclusion So, by introducing an allocator model that is much simpler (only two required functions) with more extensible customisation should an allocator need it, developers have complete control over all the memory allocation and importantly the object creation itself. Due to its initial simplicity, developers have no problem creating new allocators that improve both memory and container use in a project, and can start to experiment with better and more efficient allocators quickly. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]
You May Also Like
