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.
