I have implemented the following pool allocator in C++:
template <typename T>
struct pool {
private:
struct node {
node* next;
T element;
};
private:
std::vector<node*> m_Chunks;
node* m_Head = nullptr;
uint64 m_MaxElements = 0;
bool m_Resizable;
public:
pool(pool const&) = delete;
pool& operator=(pool const&) = delete;
pool(uint64 nElems, bool resiz = false)
: m_Resizable{ resiz } {
m_Head = alloc_chunk(nElems);
}
pool(pool&& o)
: m_Chunks{ std::move(o.m_Chunks) }, m_Head{ o.m_Head },
m_MaxElements{ o.m_MaxElements }, m_Resizable{ o.m_Resizable } {
}
pool& operator=(pool&& o) {
for (auto n : m_Chunks) {
std::free(n);
}
m_Chunks = std::move(o.m_Chunks);
m_Head = o.m_Head;
m_MaxElements = o.m_MaxElements;
m_Resizable = o.m_Resizable;
return *this;
}
~pool() {
for (auto n : m_Chunks) {
std::free(n);
}
}
operator bool() const {
return m_Chunks.size();
}
T* alloc() {
if (!m_Head) {
if (m_Resizable) {
m_Head = alloc_chunk(m_MaxElements);
if (!m_Head) {
return nullptr;
}
}
else {
return nullptr;
}
}
auto h = m_Head;
m_Head = m_Head->next;
return &h->element;
}
void free(T* ptr) {
if (!ptr) {
return;
}
uint8* mem_raw = reinterpret_cast<uint8*>(ptr);
mem_raw -= offsetof(node, element);
node* mem_head = reinterpret_cast<node*>(mem_raw);
mem_head->next = m_Head;
m_Head = mem_head;
}
private:
node* alloc_chunk(uint64 num) {
uint64 alloc_sz = sizeof(node) * num;
node* mem = reinterpret_cast<node*>(std::malloc(alloc_sz));
if (!mem) {
return nullptr;
}
m_Chunks.push_back(mem);
node* it = mem;
for (uint64 i = 1; i < num; ++i, ++it) {
it->next = it + 1;
}
it->next = nullptr;
m_MaxElements += num;
return mem;
}
};
Is the implementation good/correct? Can I make the code higher quality somehow? I have written a small test that stress-tests it and it seems OK, performance is about 5 to 10 times better than default operator new.
Are there modern C++ elements I could use? I've learnt C++11 and 14 this year in college and I've tried to use my knowledge here. I know this should mean that I should make it exception-safe, but games usually not use exceptions (that's why I've included operator bool for minimal error checking) so I've decided not to.
Edit: The test code I used
template <typename FN>
void measure_exec(const char* name, FN f) {
auto start = std::chrono::steady_clock::now();
f();
auto t = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start);
std::cout << name << " took " << t.count() << "ms." << std::endl;
}
struct message {
int id;
double timestamp;
};
int main(void) {
std::srand(std::time(nullptr));
std::vector<message*> control;
std::vector<message*> test;
measure_exec("Pool", [&]{
mem::pool<message> pool{ 32, true };
for (uint64 i = 0; i < 200000; ++i) {
if (i % 15) {
// Allocate
int r_id = std::rand();
double r_time = double(std::rand()) / std::rand();
auto t = pool.alloc();
t->id = r_id;
t->timestamp = r_time;
test.push_back(t);
}
else if (control.size()) {
// Delete
uint64 idx = std::rand() % control.size();
test.erase(test.begin() + idx);
}
}
});
measure_exec("New", [&]{
for (uint64 i = 0; i < 200000; ++i) {
if (i % 15) {
// Allocate
int r_id = std::rand();
double r_time = double(std::rand()) / std::rand();
control.push_back(new message{ r_id, r_time });
}
else if (control.size()) {
// Delete
uint64 idx = std::rand() % control.size();
control.erase(control.begin() + idx);
}
}
});
std::cin.get();
return 0;
}
Note that I haven't really tested anything like this before, this testing method was a complete shot in the dark. I know because of randomness it can be unfair but repeating the test yielded similar results. Yes I know I don't free memory but I don't think it matters that much.
std::aligned_storage
. You are still hitting the memory system a lot more than you could/should. \$\endgroup\$