Skip to main content
Code Review

Return to Question

Tweeted twitter.com/StackCodeReview/status/961200204962725888
added 1933 characters in body
Source Link
Peter Lenkefi
Peter Lenkefi
  • 311
  • 3
  • 10

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.

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.

Source Link
Peter Lenkefi
Peter Lenkefi
  • 311
  • 3
  • 10

Fast pool allocator for games in C++

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.