-
-
Save DmitrySoshnikov/07650cfb8f178cffe7276f96fd619008 to your computer and use it in GitHub Desktop.
/** | |
* Pool-allocator. | |
* | |
* Details: http://dmitrysoshnikov.com/compilers/writing-a-pool-allocator/ | |
* | |
* Allocates a larger block using `malloc`. | |
* | |
* Splits the large block into smaller chunks | |
* of equal size. | |
* | |
* Uses bump-allocated per chunk. | |
* | |
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com> | |
* MIT Style License, 2019 | |
*/ | |
#include <iostream> | |
using std::cout; | |
using std::endl; | |
/** | |
* A chunk within a larger block. | |
*/ | |
struct Chunk { | |
/** | |
* When a chunk is free, the `next` contains the | |
* address of the next chunk in a list. | |
* | |
* When it's allocated, this space is used by | |
* the user. | |
*/ | |
Chunk *next; | |
}; | |
/** | |
* The allocator class. | |
* | |
* Features: | |
* | |
* - Parametrized by number of chunks per block | |
* - Keeps track of the allocation pointer | |
* - Bump-allocates chunks | |
* - Requests a new larger block when needed | |
* | |
*/ | |
class PoolAllocator { | |
public: | |
PoolAllocator(size_t chunksPerBlock) : mChunksPerBlock(chunksPerBlock) {} | |
void *allocate(size_t size); | |
void deallocate(void *ptr, size_t size); | |
private: | |
/** | |
* Number of chunks per larger block. | |
*/ | |
size_t mChunksPerBlock; | |
/** | |
* Allocation pointer. | |
*/ | |
Chunk *mAlloc = nullptr; | |
/** | |
* Allocates a larger block (pool) for chunks. | |
*/ | |
Chunk *allocateBlock(size_t chunkSize); | |
}; | |
// ----------------------------------------------------------- | |
/** | |
* Allocates a new block from OS. | |
* | |
* Returns a Chunk pointer set to the beginning of the block. | |
*/ | |
Chunk *PoolAllocator::allocateBlock(size_t chunkSize) { | |
cout << "\nAllocating block (" << mChunksPerBlock << " chunks):\n\n"; | |
size_t blockSize = mChunksPerBlock * chunkSize; | |
// The first chunk of the new block. | |
Chunk *blockBegin = reinterpret_cast<Chunk *>(malloc(blockSize)); | |
// Once the block is allocated, we need to chain all | |
// the chunks in this block: | |
Chunk *chunk = blockBegin; | |
for (int i = 0; i < mChunksPerBlock - 1; ++i) { | |
chunk->next = | |
reinterpret_cast<Chunk *>(reinterpret_cast<char *>(chunk) + chunkSize); | |
chunk = chunk->next; | |
} | |
chunk->next = nullptr; | |
return blockBegin; | |
} | |
/** | |
* Returns the first free chunk in the block. | |
* | |
* If there are no chunks left in the block, | |
* allocates a new block. | |
*/ | |
void *PoolAllocator::allocate(size_t size) { | |
// No chunks left in the current block, or no any block | |
// exists yet. Allocate a new one, passing the chunk size: | |
if (mAlloc == nullptr) { | |
mAlloc = allocateBlock(size); | |
} | |
// The return value is the current position of | |
// the allocation pointer: | |
Chunk *freeChunk = mAlloc; | |
// Advance (bump) the allocation pointer to the next chunk. | |
// | |
// When no chunks left, the `mAlloc` will be set to `nullptr`, and | |
// this will cause allocation of a new block on the next request: | |
mAlloc = mAlloc->next; | |
return freeChunk; | |
} | |
/** | |
* Puts the chunk into the front of the chunks list. | |
*/ | |
void PoolAllocator::deallocate(void *chunk, size_t size) { | |
// The freed chunk's next pointer points to the | |
// current allocation pointer: | |
reinterpret_cast<Chunk *>(chunk)->next = mAlloc; | |
// And the allocation pointer is moved backwards, and | |
// is set to the returned (now free) chunk: | |
mAlloc = reinterpret_cast<Chunk *>(chunk); | |
} | |
// ----------------------------------------------------------- | |
/** | |
* The `Object` structure uses custom allocator, | |
* overloading `new`, and `delete` operators. | |
*/ | |
struct Object { | |
// Object data, 16 bytes: | |
uint64_t data[2]; | |
// Declare out custom allocator for | |
// the `Object` structure: | |
static PoolAllocator allocator; | |
static void *operator new(size_t size) { | |
return allocator.allocate(size); | |
} | |
static void operator delete(void *ptr, size_t size) { | |
return allocator.deallocate(ptr, size); | |
} | |
}; | |
// Instantiate our allocator, using 8 chunks per block: | |
PoolAllocator Object::allocator{8}; | |
int main(int argc, char const *argv[]) { | |
// Allocate 10 pointers to our `Object` instances: | |
constexpr int arraySize = 10; | |
Object *objects[arraySize]; | |
// Two `uint64_t`, 16 bytes. | |
cout << "size(Object) = " << sizeof(Object) << endl << endl; | |
// Allocate 10 objects. This causes allocating two larger, | |
// blocks since we store only 8 chunks per block: | |
cout << "About to allocate " << arraySize << " objects" << endl; | |
for (int i = 0; i < arraySize; ++i) { | |
objects[i] = new Object(); | |
cout << "new [" << i << "] = " << objects[i] << endl; | |
} | |
cout << endl; | |
// Deallocate all the objects: | |
for (int i = arraySize - 1; i >= 0; --i) { | |
cout << "delete [" << i << "] = " << objects[i] << endl; | |
delete objects[i]; | |
} | |
cout << endl; | |
// New object reuses previous block: | |
objects[0] = new Object(); | |
cout << "new [0] = " << objects[0] << endl << endl; | |
} | |
/* | |
size(Object) = 16 | |
Allocating block (8 chunks): | |
new [0] = 0x7ff85e4029e0 | |
new [1] = 0x7ff85e4029f0 | |
new [2] = 0x7ff85e402a00 | |
new [3] = 0x7ff85e402a10 | |
new [4] = 0x7ff85e402a20 | |
new [5] = 0x7ff85e402a30 | |
new [6] = 0x7ff85e402a40 | |
new [7] = 0x7ff85e402a50 | |
Allocating block (8 chunks): | |
new [8] = 0x7ff85e402a60 | |
new [9] = 0x7ff85e402a70 | |
delete [0] = 0x7ff85e4029e0 | |
delete [1] = 0x7ff85e4029f0 | |
delete [2] = 0x7ff85e402a00 | |
delete [3] = 0x7ff85e402a10 | |
delete [4] = 0x7ff85e402a20 | |
delete [5] = 0x7ff85e402a30 | |
delete [6] = 0x7ff85e402a40 | |
delete [7] = 0x7ff85e402a50 | |
delete [8] = 0x7ff85e402a60 | |
delete [9] = 0x7ff85e402a70 | |
new [0] = 0x7ff85e402a70 | |
*/ |
It is not an alternative it is a comparison ... my version of your allocator is basically the same
https://github.com/dbj-data/comparing_allocation_libs
Next "thing" to do is efficient array allocation using Shoshnikov allocator.
@DBJDBJ, nice work, thanks! I'll take a deeper look at this repo.
Finished fiddling with it, literally a minute ago. Thanks for the star.
Array allocation is currently naive and with an obvious bug inside. To tired right now so not in use currently.
@DmitrySoshnikov, hi, wouldn't there be a problem chaining those chunks if the chuck size is smaller than the pointer size?
for (int i = 0; i < mChunksPerBlock - 1; ++i) {
chunk->next = reinterpret_cast<Chunk *>(reinterpret_cast<char *>(chunk) + chunkSize);
chunk = chunk->next;
}
@JunLin820119 - thanks, that's a good point. And in this case you would need to keep an extra field, for data and still for chaining the blocks, as any allocator does.
@DmitrySoshnikov, got it, thanks for replying and everything. This PoolAllocator solves one of my big problem.
Btw, I added an extra member "std::vector<void> v_block_address"*, to record the starting address of each allocated blocks, so that I can free all the memories allocated during runtime.
void* PoolAllocator::allocate(size_t buffer_size)
...
if (mAlloc == nullptr)
{
mAlloc = allocateBlock(buffer_size);
v_block_address.push_back(mAlloc);
}
...
@JunLin820119 , yes, that's a good optimization since you can directly remove the blocks.
@DBJDBJ, absolutely, always glad to see different alternative solutions to a problem.