Offline memory manager?

Question

Has anyone thought about how to write a memory manager (in C ++) that is completely branch-free? I wrote a pool, a stack, a queue, and a linked list (allocation from the pool), but I wonder how plausible it is to write a shared memory manager for the branch.

This is all to help create a truly reusable infrastructure for creating a solid parallel processor in ordering and development with support for caching.

Edit: by branching, I mean without direct or indirect function calls and without using ifs. I thought that I could perhaps implement something that first changes the requested size to zero for fake calls, but actually not so much. I feel that this is not impossible, but another aspect of this exercise then profiles it on "unfriendly" processors to see if it is worth trying as hard as this to avoid branching.

Answer 1

While I don't think this is a good idea, one solution would be to have pre-allocated buckets of various sizes of log ₂ , a silly pseudocode:

class Allocator { void* malloc(size_t size) { int bucket = log2(size + sizeof(int)); int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back()); m_buckets[bucket].pop_back(); *pointer = bucket; //Store which bucket this was allocated from return pointer + 1; //Dont overwrite header } void free(void* pointer) { int* temp = reinterpret_cast<int*>(pointer) - 1; m_buckets[*temp].push_back(temp); } vector< vector<void*> > m_buckets; }; 

(Of course, you will also replace std::vector with a simple array + counter).

EDIT: To make this reliable (i.e. handle the situation when the bucket is empty), you will need to add some form of branching.

EDIT2: Here's a little undisclosed log2 function:

 //returns the smallest x such that value <= (1 << x) int log2(int value) { union Foo { int x; float y; } foo; foo.y = value - 1; return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number } 

This gives the correct result for allocations of <33554432 bytes. If you need a large allocation, you will have to switch to paired.

Here's a link on how floating point numbers are represented in memory.

Answer 2

The only way I know to create an invertebrate dispenser is to reserve all the memory that it will potentially use in advance. Otherwise, there will always be some kind of hidden code somewhere to see if we exceed some current capacity, be it in a hidden push_back in a vector that checks if the size exceeds the size used to implement it or something like that .

Here is one such rough example of a fixed alloc, which has a completely non-distributed malloc and free method.

 class FixedAlloc { public: FixedAlloc(int element_size, int num_reserve) { element_size = max(element_size, sizeof(Chunk)); mem = new char[num_reserve * element_size]; char* ptr = mem; free_chunk = reinterpret_cast<Chunk*>(ptr); free_chunk->next = 0; Chunk* last_chunk = free_chunk; for (int j=1; j < num_reserve; ++j) { ptr += element_size; Chunk* chunk = reinterpret_cast<Chunk*>(ptr); chunk->next = 0; last_chunk->next = chunk; last_chunk = chunk; } } ~FixedAlloc() { delete[] mem; } void* malloc() { assert(free_chunk && free_chunk->next && "Reserve memory exhausted!"); Chunk* chunk = free_chunk; free_chunk = free_chunk->next; return chunk->mem; } void free(void* mem) { Chunk* chunk = static_cast<Chunk*>(mem); chunk->next = free_chunk; free_chunk = chunk; } private: union Chunk { Chunk* next; char mem[1]; }; char* mem; Chunk* free_chunk; }; 

Since it is fully forked, it is simply segfaults if you try to allocate more memory than it originally reserved. It also has undefined behavior for trying to free a null pointer. I also avoided doing alignment for a simpler example.