• entries
    743
  • comments
    1924
  • views
    580106

Allocator Pools

Sign in to follow this  
Aardvajk

862 views

After a brief battle with a bad phase of mental health issues, I've yet again restarted Om from scratch. I want to try a different approach to look up of variables this time as I was encountering some problems using the approach of storing indices from top of stack backwards. Instead this time, I'm going to try storing a stack offset when a function is called, then reference variables from this offset upwards. But more about that in the future when I see how it works out.


Pool Allocators

One thing I wanted to sort out this time around was to implement some kind of pool allocation strategy for the things that are dynamically created during the run time phase of the scripting engine. The engine stores complex objects on the heap and uses unsigned int references to them to store directly on the VM stack (basically references into an array that recycles used slots when they are freed).

We have a small and fixed number of different types of these complex entities - [font='courier new']FunctionEntity[/font], [font='courier new']StringEntity[/font], [font='courier new']ObjectEntity[/font] and [font='courier new']ArrayEntity[/font]. There is also [font='courier new']MessageEntity[/font] which is not used as part of the scripting, but as a way to pass error messages back to the user of the library from within the [font='courier new']Om::Value[/font] interface.

What I have currently come up with on this iteration of Om is the following approach. First we have a pool allocator based on the standard strategy of allocating blocks and daisy-chaining free pointers. You can find this approach described all over the internet.

#ifndef OBJECTPOOL_H#define OBJECTPOOL_H#include "framework/PodVector.h"template class object_pool{public: object_pool() : free(0) { } ~object_pool(){ for(auto &c: chunks) delete c; } template T *allocate(Args&&... args); void release(T *p){ p->~T(); reinterpret_cast(p)->next = free; free = reinterpret_cast(p); }private: object_pool(const object_pool&); void operator=(const object_pool&); struct chunk { char values[chunk_size * sizeof(T)]; }; struct slot { slot *next; }; void enlarge(); pod_vector chunks; slot *free;};template template T *object_pool::allocate(Args&&... args){ if(!free) enlarge(); char *p = reinterpret_cast(free); free = free->next; return new(p) T(std::forward(args)...);}template void object_pool::enlarge(){ chunk *c = new chunk(); chunks.push_back(c); free = reinterpret_cast(c->values); for(unsigned int i = 0; i < chunk_size * sizeof(T); i += sizeof(T)) { reinterpret_cast(c->values + i)->next = reinterpret_cast(c->values + i + sizeof(T)); } reinterpret_cast(c->values + (sizeof(T) * (chunk_size - 1)))->next = 0;}#endif // OBJECTPOOL_HNote that [font='courier new']pod_vector[/font] is just another library class I have that implements the simplest possible vector for POD types, using straight memcpy and pointers for iterators. This is pretty critical as it is used in a lot of places - the value stack in the VM for example - and I don't want to take the chance that the standard library vector introduces any overhead, but I have to be very careful to only use [font='courier new']pod_vector[/font] in the appropriate places.

The varadic template system is a real boon for writers of allocators. Look how easy it is to implement the [font='courier new']allocate()[/font] method in such a way that the user can just forward any constructor arguments (or none) supported by the T type.

Now, each pool has to contain fixed size objects, and the different entities are different sizes, so we need to wrap this up in such a way that we can use an explicit template specialisation to refer to different pools. For this we have the [font='courier new']EntityMemory[/font] class.

#ifndef ENTITYMEMORY_H#define ENTITYMEMORY_H#include "framework/ObjectPool.h"#include "machine/entity/FunctionEntity.h"#include "machine/entity/StringEntity.h"class EntityMemory{public: EntityMemory(){ } static const unsigned int chunk = 256; template T *allocate(Args&&... args){ return pool().allocate(std::forward(args)...); } template void release(Entity *e){ pool().release(static_cast(e)); }private: template object_pool &pool(){ } object_pool functionPool; object_pool stringPool;};template<> object_pool &EntityMemory::pool(){ return functionPool; }template<> object_pool &EntityMemory::pool(){ return stringPool; }#endif // ENTITYMEMORY_HSo under the hood, we have different pools for the different types of entity, but we use template specialisation to allow the interface to provide the same functions, but selectable by providing a template argument. For example:

StringEntity *s = mem.allocate("hello world");While this is nice to look at, it also means we can call the allocation methods from other template functions when we don't know what the actual type is.

With this in mind, we can tidy up the interface a little by adding some methods to the [font='courier new']State[/font] object that contains both the [font='courier new']EntityMemory[/font] and the [font='courier new']EntityHeap[/font]. The [font='courier new']EntityHeap[/font] is a recycling array of pointers to Entity* that provides the look up access based on the index:

class State{public: State(Om::Engine &engine); EntityHeap eh; EntityMemory em; template T &entity(Entity::Id id){ return static_cast(*eh[id]); } template const T &entity(Entity::Id id) const { return static_cast(*eh[id]); } template Entity::Id allocate(Args&&... args){ return eh.add(em.allocate(std::forward(args)...)); }};There we see the use of making [font='courier new']EntityHeap[/font]'s interface based on template specialisation, since we can call it when we don't know what the actual type is.

So in the code that uses all this, we can now just do something like:

bool Machine::mkEnt(const TypedValue &v){ switch(v.type()) { case Om::Type::String: vs.push_back(TypedValue(Om::Type::String, s.allocate(s.tc[v.toUint()]))); break; default: return false; } s.inc(vs.back()); return true;}And the actual memory for the [font='courier new']StringEntity[/font] is provided by the pool. Similarly, to release it, we can do:

void State::dec(const TypedValue &v){ if(isReferenceType(v.type())) { Entity *e = eh[v.toUint()]; --e->refs; if(e->refs == 0) { e->release(*this); eh.remove(v.toUint()); switch(v.type()) { case Om::Type::String: em.release(e); break; case Om::Type::Function: em.release(e); break; default: break; } } }}There might be a way to automate that switch statement there so that this code does not need to be modified as more entity types are added. Will have to have a think about that.

So to anyone saying C++ is dead, just look at how expressive the combination of existing features and new features are empowering us to be. Thanks for reading.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now