32bit id allocator of different sizes

32bit_alloc.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <random>
#include <chrono>
#include <cstdint>
#include <limits>
#include <cstring>
#include <cstdlib>

struct IdGen {
	std::random_device rd;
	std::mt19937 gen;
	std::uniform_int_distribution<uint64_t> distrib;

	IdGen(): rd(), gen(rd()), distrib(std::numeric_limits<uint64_t>::min(),
       std::numeric_limits<uint64_t>::max()) {}


	uint64_t next() {
		return static_cast<uint64_t>(distrib(gen));
	}
};

static inline size_t all_ones(size_t x) {
    return (x + 1) == 0;
}

/**
 * 
 * >>> n = (1 << 30) - 1
>>> bin(n ^ (n & (n - 1)))
'0b1'
>>> bin((n & (n - 1)))
'0b111111111111111111111111111110'
to do change to basic allocator 
 * */

#define GET_DATA_SIZE(aid) (1 << (aid >> 27))


/**
 * First 5 bits , data type size
 * other 27 bits, the Nth slot for that value
 * The size is 1 << <size>.
 * 1 << 7 == 128 bytes
 * */
struct IdGenerator {
	static constexpr uint32_t valueMask = (1 << 27) - 1;
	static constexpr uint32_t maxTypeSizeMask = (1 << 5) - 1;
	explicit IdGenerator(size_t sizeType): typePower(sizeType & maxTypeSizeMask),
	                         sizeComponent( typePower << 27 ),
	                         curCount(0) {}
	const size_t typePower;
	const uint32_t sizeComponent;
	uint32_t curCount;


	inline uint32_t next() {
		return sizeComponent | (++curCount & valueMask);
	}
};

// the free list, basically
struct ListBlock {
	const size_t capacity;
	uint32_t* ids = nullptr;
	uint32_t curLen = 0;

	explicit ListBlock(size_t powerOfTwo): capacity(1 << powerOfTwo) {
		ids = (uint32_t*)malloc(capacity * sizeof(uint32_t));
	}

	inline bool add(uint32_t id) {
		if (curLen == capacity)
			return false;
		ids[curLen++] = id;
		return true;
	}

	inline uint32_t remove() {
		if (!curLen)
			return 0;
		return ids[curLen--];
	}
};

/**
 * >>> bin(((1 << 27)-1) & ~0b11)
'0b111111111111111111111111100'
>>> bin(((1 << 27)-1) & ~0b111)
'0b111111111111111111111111000'
 * prevent 1 - 3 byte keys
 * */
static inline size_t determinePower2Size(size_t dsize) {
	return 64 - __builtin_clzll(dsize);
}

struct Allocator {
	IdGenerator gens[8] = {
		IdGenerator(0),
		IdGenerator(1),
		IdGenerator(2),
		IdGenerator(3),
		IdGenerator(4),
		IdGenerator(5),
		IdGenerator(6),
		IdGenerator(7)
	};

	ListBlock freeLists[8] = {
		ListBlock(16),
		ListBlock(16),
		ListBlock(16),
		ListBlock(16),
		ListBlock(16),
		ListBlock(16),
		ListBlock(16),
		ListBlock(16)
	};

	inline uint32_t getId(size_t sizeReq) {
		size_t index = determinePower2Size(sizeReq);
		uint32_t gotFreed = freeLists[index].remove();
		return gotFreed ? gotFreed : gens[index].next();
	}

	inline uint32_t getIdNoFreeList(size_t sizeReq) {
		return gens[determinePower2Size(sizeReq)].next();
	}

	inline uint32_t getIdExact(size_t exactSizeIndex) {
		uint32_t gotFreed = freeLists[exactSizeIndex].remove();
		return gotFreed ? gotFreed : gens[exactSizeIndex].next();
	}

	inline void freeId(uint32_t id) {
		const uint32_t idSize = id >> 27;
		freeLists[idSize].add(id);
	}
};



static void perfTest_getId() {
	static constexpr size_t testSize = 10000000;
	IdGen gens;
	const size_t myChosenSize = gens.next() & ((1 << 6) - 1);
	std::printf("chosen size is %zu\n", myChosenSize);

	size_t total = 0;
	Allocator allObj;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < testSize; ++i)
    {
        uint32_t gotId = allObj.getId(myChosenSize);
        allObj.freeId(gotId);
        total += gotId;
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << total << " getId  " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "us\n";
}

static void perfTest_getIdNoFreeList() {
	static constexpr size_t testSize = 10000000;
	IdGen gens;
	const size_t myChosenSize = gens.next() & ((1 << 6) - 1);
	std::printf("chosen size is %zu\n", myChosenSize);

	size_t total = 0;
	Allocator allObj;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < testSize; ++i)
    {
        uint32_t gotId = allObj.getIdNoFreeList(myChosenSize);
        allObj.freeId(gotId);
        total += gotId;
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << total << " getIdNoFreeList  " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "us\n";
}

static void perfTest_getIdExact() {
	static constexpr size_t testSize = 10000000;
	IdGen gens;
	const size_t myChosenSize = gens.next() & ((1 << 6) - 1);
	std::printf("chosen size is %zu\n", myChosenSize);

	size_t total = 0;
	Allocator allObj;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < testSize; ++i)
    {
        uint32_t gotId = allObj.getIdExact(6);
        allObj.freeId(gotId);
        total += gotId;
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << total << " getIdExact  " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << "us\n";
}

/***
 * chosen size is 32
8103063685000000 getId  143304us
chosen size is 42
8103063685000000 getIdNoFreeList  6305us
chosen size is 18
8103063685000000 getIdExact  41180us
 * */

int main(int argc, char const *argv[])
{
	perfTest_getId();
	perfTest_getIdNoFreeList();
	perfTest_getIdExact();
	return 0;
}