preallocation tests (completely rewritten)

main.cpp

struct BaseObj
{
	BaseObj() { }
	virtual ~BaseObj() { }
};

struct SmallObj : BaseObj
{
	char data[100];
	~SmallObj()
	{
		//lo << "smallobj dtor" << endl;
	}
};

struct BigObj : BaseObj
{
	char data[500];
	~BigObj()
	{
		//lo << "bigobj dtor" << endl;
	}
};

int main()
{
	PreAllocator p{65000};								// << this preallocator is VERY speed-dependent on the allocated space
	PreAllocatorChunk pc{sizeof(BigObj), 200};			// << this preallocator can hold different objects of different types, as long as (their size <= chunk size)
	PreAllocatorStatic<BigObj> ps{100};					// << this preallocator can hold only a specific type

	startBenchmark();
	{
		vector<BaseObj*> bases;

		for(int k{0}; k < 10000; ++k)
		{
			for(int i{0}; i < 100; ++i) bases.push_back(new SmallObj);
			for(int i{0}; i < 100; ++i) bases.push_back(new BigObj);
			for(auto& b : bases) delete b;
			bases.clear();
		}
	}
	lo << lt("new/del") << endBenchmark() << endl;

	startBenchmark();
	{
		vector<SmallObj*> sb;
		vector<BigObj*> bb;

		for(int k{0}; k < 10000; ++k)
		{
			for(int i{0}; i < 100; ++i) sb.push_back(p.create<SmallObj>());
			for(int i{0}; i < 100; ++i) bb.push_back(p.create<BigObj>());
			for(auto& b : sb) p.destroy<SmallObj>(b);
			for(auto& b : bb) p.destroy<BigObj>(b);
			sb.clear();
			bb.clear();
		}
	}
	lo << lt("prealloc") << endBenchmark() << endl;

	startBenchmark();
	{
		vector<SmallObj*> sb;
		vector<BigObj*> bb;

		for(int k{0}; k < 10000; ++k)
		{
			for(int i{0}; i < 100; ++i) sb.push_back(pc.create<SmallObj>());
			for(int i{0}; i < 100; ++i) bb.push_back(pc.create<BigObj>());
			for(auto& b : sb) pc.destroy<SmallObj>(b);
			for(auto& b : bb) pc.destroy<BigObj>(b);
			sb.clear();
			bb.clear();
		}
	}
	lo << lt("prealloc chunk") << endBenchmark() << endl;

	startBenchmark();
	{
		vector<BigObj*> bb;

		for(int k{0}; k < 10000; ++k)
		{
			for(int i{0}; i < 100; ++i) bb.push_back(new BigObj);
			for(auto& b : bb) delete b;
			bb.clear();
		}
	}
	lo << lt("new/del static bigobj") << endBenchmark() << endl;

	startBenchmark();
	{
		vector<BigObj*> bb;

		for(int k{0}; k < 10000; ++k)
		{
			for(int i{0}; i < 100; ++i) bb.push_back(ps.create());
			for(auto& b : bb) ps.destroy(b);
			bb.clear();
		}
	}
	lo << lt("prealloc_static static bigobj") << endBenchmark() << endl;

	return 0;
}

Preallocator.h

#ifndef SSVU_PREALLOCATOR
#define SSVU_PREALLOCATOR

#include <vector>
#include <stack>
#include <algorithm>
#include <functional>
#include <stdexcept>
#include <cmath>
#include "SSVUtils/Global/Typedefs.h"

namespace ssvu
{
	using MemUnit = char;
	using MemUnitPtr = MemUnit*;
	using MemSize = decltype(sizeof(MemUnit)); // Should always be 1 byte

	template<typename T> constexpr MemSize getKBsToBytes(const T& mValue) { return mValue * 1024; }
	template<typename T> constexpr MemSize getMBsToBytes(const T& mValue) { return mValue * 1024 * 1024; }
	template<typename T> constexpr MemSize getGBsToBytes(const T& mValue) { return mValue * 1024 * 1024 * 1024; }

	struct MemRange
	{
		// MemRange is a range of memory [begin, end)
		MemUnitPtr begin, end;
		inline MemRange(MemUnitPtr mStart, MemUnitPtr mEnd) : begin{mStart}, end{mEnd} { }
		inline MemSize getSize() const { return sizeof(MemUnit) * (end - begin); }
	};

	class PreAllocatedBuffer
	{
		private:
			Uptr<MemUnit[]> buffer;
			MemRange range;

		public:
			inline PreAllocatedBuffer(MemSize mSize) : buffer{new MemUnit[mSize]}, range{&buffer[0], &buffer[mSize]} { }
			inline MemUnitPtr getBegin() const		{ return range.begin; }
			inline MemUnitPtr getEnd() const		{ return range.end; }
			inline const MemRange& getRange() const	{ return range; }
	};

	class PreAllocator
	{
		private:
			PreAllocatedBuffer buffer;
			std::vector<MemRange> available;

			inline void unifyFrom(unsigned int mIndex)
			{
				MemUnitPtr lastEnd(available[mIndex].end);
				auto toChange(std::begin(available) + mIndex);
				auto itr(toChange + 1);

				for(; itr != std::end(available); ++itr)
					if(itr->begin == lastEnd) lastEnd = itr->end;
					else break;

				// Erase all but the first unified elements, then change the first one with
				// the updated range

				available.erase(toChange + 1, itr);
				toChange->begin = available[mIndex].begin;
				toChange->end = lastEnd;
			}

			inline void unifyContiguous()
			{
				std::sort(std::begin(available), std::end(available), [](const MemRange& mA, const MemRange& mB){ return mA.begin < mB.begin; });
				//for(unsigned int i{0}; i < available.size(); ++i) unifyFrom(i);
				unifyFrom(0);
			}

			inline std::vector<MemRange>::iterator findSuitableMemory(MemSize mRequiredSize)
			{
				// Tries to find a memory piece big enough to hold mRequiredSize
				// If it is not found, contiguous memory pieces are unified
				// If it is not found again, throws an exception

				for(int i{0}; i < 2; ++i)
				{
					for(auto itr(std::begin(available)); itr != std::end(available); ++itr) if(itr->getSize() >= mRequiredSize) return itr;
					unifyContiguous();
				}
				throw std::runtime_error("PreAllocator couldn't find suitable memory (required: " + toStr(mRequiredSize) + ")");
			}

		public:
			PreAllocator(MemSize mBufferSize) : buffer{mBufferSize}
			{
				// Add the whole buffer to the available memory vector
				available.push_back(buffer.getRange()); return;
			}

			template<typename T, typename... TArgs> inline T* create(TArgs&&... mArgs)
			{
				// Creates and returns a T* allocated with "placement new" on an available piece of the buffer
				// T must be the "real object type" - this method will fail with pointers to bases that store derived instances!

				const auto& requiredSize(sizeof(T));
				const auto& suitable(findSuitableMemory(requiredSize));

				MemUnitPtr toUse{suitable->begin};
				MemRange leftover{toUse + requiredSize, suitable->end};

				available.erase(suitable);
				if(leftover.getSize() > 0) available.push_back(leftover);

				return new (toUse) T{std::forward<TArgs>(mArgs)...};
			}
			template<typename T> inline void destroy(T* mObject)
			{
				// Destroys a previously allocated object, calling its destructor and reclaiming its memory piece
				// T must be the "real object type" - this method will fail with pointers to bases that store derived instances!

				auto objStart(reinterpret_cast<MemUnitPtr>(mObject));
				available.emplace_back(objStart, objStart + sizeof(T));
				mObject->~T();
			}

			std::string getMemRangesStr()
			{
				std::string result{"Available mem\n"};
				for(const auto& mr : available) result += toStr(mr.getSize()) + "\n";
				return result;
			}
	};

	class PreAllocatorChunk
	{
		private:
			MemSize chunkSize;
			PreAllocatedBuffer buffer;
			std::stack<MemRange, std::vector<MemRange>> available;

		public:
			PreAllocatorChunk(MemSize mChunkSize, unsigned int mChunks) : chunkSize{mChunkSize}, buffer{chunkSize * mChunks}
			{
				for(auto i(0u); i < mChunks; ++i)
				{
					MemUnitPtr chunkBegin(buffer.getBegin() + (i * chunkSize));
					available.emplace(chunkBegin, chunkBegin + chunkSize);
				}
			}

			template<typename T, typename... TArgs> inline T* create(TArgs&&... mArgs)
			{
				auto toUse(available.top().begin);
				available.pop();
				return new (toUse) T{std::forward<TArgs>(mArgs)...};
			}
			template<typename T> inline void destroy(T* mObject)
			{
				// Destroys a previously allocated object, calling its destructor and reclaiming its memory piece
				// T must be the "real object type" - this method will fail with pointers to bases that store derived instances!

				auto objStart(reinterpret_cast<MemUnitPtr>(mObject));
				available.emplace(objStart, objStart + chunkSize);
				mObject->~T();
			}
	};

	template<typename T> class PreAllocatorStatic
	{
		private:
			PreAllocatedBuffer buffer;
			std::stack<MemRange, std::vector<MemRange>> available;

		public:
			PreAllocatorStatic(unsigned int mChunks) : buffer{sizeof(T) * mChunks}
			{
				for(auto i(0u); i < mChunks; ++i)
				{
					MemUnitPtr chunkBegin(buffer.getBegin() + (i * sizeof(T)));
					available.emplace(chunkBegin, chunkBegin + sizeof(T));
				}
			}

			template<typename... TArgs> inline T* create(TArgs&&... mArgs)
			{
				auto toUse(available.top().begin);
				available.pop();
				return new (toUse) T{std::forward<TArgs>(mArgs)...};
			}
			inline void destroy(T* mObject)
			{
				auto objStart(reinterpret_cast<MemUnitPtr>(mObject));
				available.emplace(objStart, objStart + sizeof(T));
				mObject->~T();
			}
	};
}

#endif