Return to Answer

#ifndef FIXED_ALLOCATOR_HPP #define FIXED_ALLOCATOR_HPP class FixedAllocator { public: /// Creates a fixed allocator with the specified type and block size. explicit FixedAllocator(int type_size, int block_size = 2048); /// Destroys the allocator. ~FixedAllocator(); /// @return A pointer to a newly allocated chunk. void* allocate(); /// Frees the specified chunk. void deallocate(void* mem); private: struct Block; struct FreeElement; FreeElement* free_element; Block* head; int type_size; int num_block_elements; }; #endif #include "FixedAllocator.hpp" #include <cstdlib> struct FixedAllocator::FreeElement { FreeElement* next_element; }; struct FixedAllocator::Block { Block* next; char* mem; }; FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0) { type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement); num_block_elements = block_size / type_size; if (num_block_elements == 0) num_block_elements = 1; } FixedAllocator::~FixedAllocator() { // Free each block in the list, popping a block until the stack is empty. while (head) { Block* block = head; head = head->next; free(head->mem); free(head); } free_element = 0; } void* FixedAllocator::allocate() { // Common case: just pop free element and return. if (free_element) { void* mem = free_element; free_element = free_element->next_element; return mem; } // Rare case when we're out of free elements. // Create new block. Block* new_block = static_cast<Block*>(malloc(sizeof(Block))); new_block->mem = malloc(type_size * num_block_elements); new_block->next = head; head = new_block; // Push all but one of the new block's elements to the free stack. char* mem = new_block->mem; for (int j=1; j < num_block_elements; ++j) { void* ptr = mem + j*type_size; FreeElement* element = static_cast<FreeElement*>(ptr); element->next_element = free_element; free_element = element; } return mem; } void FixedAllocator::deallocate(void* mem) { // Just push a free element to the stack. FreeElement* element = static_cast<FreeElement*>(mem); element->next_element = free_element; free_element = element; } 

#ifndef FIXED_ALLOCATOR_HPP #define FIXED_ALLOCATOR_HPP class FixedAllocator { public: /// Creates a fixed allocator with the specified type and block size. explicit FixedAllocator(int type_size, int block_size = 2048); /// Destroys the allocator. ~FixedAllocator(); /// @return A pointer to a newly allocated chunk. void* allocate(); /// Frees the specified chunk. void deallocate(void* mem); private: struct Block; struct FreeElement; FreeElement* free_element; Block* head; int type_size; int num_block_elements; }; #endif #include "FixedAllocator.hpp" #include <cstdlib> struct FixedAllocator::FreeElement { FreeElement* next_element; }; struct FixedAllocator::Block { Block* next; char* mem; }; FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0) { type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement); num_block_elements = block_size / type_size; if (num_block_elements == 0) num_block_elements = 1; } FixedAllocator::~FixedAllocator() { // Free each block in the list, popping a block until the stack is empty. while (head) { Block* block = head; head = head->next; free(block->mem); free(block); } free_element = 0; } void* FixedAllocator::allocate() { // Common case: just pop free element and return. if (free_element) { void* mem = free_element; free_element = free_element->next_element; return mem; } // Rare case when we're out of free elements. // Create new block. Block* new_block = static_cast<Block*>(malloc(sizeof(Block))); new_block->mem = malloc(type_size * num_block_elements); new_block->next = head; head = new_block; // Push all but one of the new block's elements to the free stack. char* mem = new_block->mem; for (int j=1; j < num_block_elements; ++j) { void* ptr = mem + j*type_size; FreeElement* element = static_cast<FreeElement*>(ptr); element->next_element = free_element; free_element = element; } return mem; } void FixedAllocator::deallocate(void* mem) { // Just push a free element to the stack. FreeElement* element = static_cast<FreeElement*>(mem); element->next_element = free_element; free_element = element; } 

Fixed-sized allocations are easier to speed up without the sequential allocator constraints that prevent you from freeing specific chunks of memory. But making variable-sized allocation faster than the default allocator is pretty tough. Basically making any kind of memory allocator that's faster than malloc is generally extremely tough if you don't apply constraints that narrow its applicability. One solution is to use a fixed-sized allocator for, say, all strings which are 8 bytes or less if you have a boatload of them and longer strings are a rare case (for which you can just use the default allocator). That does mean 7 bytes are wasted for 1-byte strings, but it should eliminate allocation-related hotspots, if, say, 95% of the time, your strings are very short.

The idea here is to make each unrolled node a fixed-size. When you do that, you can use an extremely fast fixed-sized chunk allocator which pools memory. That won't reduce memory use, it'll tend to add to it because of the cost of the links, but you can play with the unrolled size to find a balance suitable for your needs. It's kind of a wacky idea but should eliminate memory-related hotspots since you can now effectively pool memory already-allocated in bulky contiguous blocks and still have the benefits of freeing strings individually. Here's a simple ol' fixed allocator I wrote (illustratory one I made for someone else, devoid of production-related fluff) which you can freely use:

Fixed-sized allocations are easier to speed up without the sequential allocator constraints that prevent you from freeing specific chunks of memory to be reused later. But making variable-sized allocation faster than the default allocator is pretty tough. Basically making any kind of memory allocator that's faster than malloc is generally extremely tough if you don't apply constraints that narrow its applicability. One solution is to use a fixed-sized allocator for, say, all strings which are 8 bytes or less if you have a boatload of them and longer strings are a rare case (for which you can just use the default allocator). That does mean 7 bytes are wasted for 1-byte strings, but it should eliminate allocation-related hotspots, if, say, 95% of the time, your strings are very short.

The idea here is to make each unrolled node a fixed-size instead of variable-sized. When you do that, you can use an extremely fast fixed-sized chunk allocator which pools memory, allocating fixed-sized chunks for variable-sized strings linked together. That won't reduce memory use, it'll tend to add to it because of the cost of the links, but you can play with the unrolled size to find a balance suitable for your needs. It's kind of a wacky idea but should eliminate memory-related hotspots since you can now effectively pool memory already-allocated in bulky contiguous blocks and still have the benefits of freeing strings individually. Here's a simple ol' fixed allocator I wrote (illustratory one I made for someone else, devoid of production-related fluff) which you can freely use:

Another solution that just occurred to me is to use unrolled linked lists which might sound crazy but hear me out.

The idea here is to make each unrolled node a fixed-size. When you do that, you can use an extremely fast fixed-sized chunk allocator which pools memory. That won't reduce memory use, it'll tend to add to it because of the cost of the links, but you can play with the unrolled size to find a balance suitable for your needs. It's kind of a wacky idea but should eliminate memory-related hotspots since you can now effectively pool memory already-allocated in bulky contiguous blocks and still have the benefits of freeing strings individually. Here's a simple ol' fixed allocator I wrote (illustratory one I made for someone else, devoid of production-related fluff) which you can freely use:

#ifndef FIXED_ALLOCATOR_HPP #define FIXED_ALLOCATOR_HPP class FixedAllocator { public: /// Creates a fixed allocator with the specified type and block size. explicit FixedAllocator(int type_size, int block_size = 2048); /// Destroys the allocator. ~FixedAllocator(); /// @return A pointer to a newly allocated chunk. void* allocate(); /// Frees the specified chunk. void deallocate(void* mem); private: struct Block; struct FreeElement; FreeElement* free_element; Block* head; int type_size; int num_block_elements; }; #endif #include "FixedAllocator.hpp" #include <cstdlib> struct FixedAllocator::FreeElement { FreeElement* next_element; }; struct FixedAllocator::Block { Block* next; char* mem; }; FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0) { type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement); num_block_elements = block_size / type_size; if (num_block_elements == 0) num_block_elements = 1; } FixedAllocator::~FixedAllocator() { // Free each block in the list, popping a block until the stack is empty. while (head) { Block* block = head; head = head->next; free(head->mem); free(head); } free_element = 0; } void* FixedAllocator::allocate() { // Common case: just pop free element and return. if (free_element) { void* mem = free_element; free_element = free_element->next_element; return mem; } // Rare case when we're out of free elements. // Create new block. Block* new_block = static_cast<Block*>(malloc(sizeof(Block))); new_block->mem = malloc(type_size * num_block_elements); new_block->next = head; head = new_block; // Push all but one of the new block's elements to the free stack. char* mem = new_block->mem; for (int j=1; j < num_block_elements; ++j) { void* ptr = mem + j*type_size; FreeElement* element = static_cast<FreeElement*>(ptr); element->next_element = free_element; free_element = element; } return mem; } void FixedAllocator::deallocate(void* mem) { // Just push a free element to the stack. FreeElement* element = static_cast<FreeElement*>(mem); element->next_element = free_element; free_element = element; }