CODEWITHSUNDEEP
c++memory-management
binarez
binarez

Reputation: 809

Smaller per allocation overhead in allocators library

I'm currently writing a memory management library for c++ that is based around the concept of allocators. It's relatively simple, for now, all allocators implement these 2 member functions:

virtual void * alloc( std::size_t size ) = 0;
virtual void   dealloc( void * ptr ) = 0;

As you can see, I do not support alignment in the interface but that's actually my next step :) and the reason why I'm asking this question.

I want the allocators to be responsible for alignment because each one can be specialized. For example, the block allocator can only return block-sized aligned memory so it can handle failure and return NULL if a different alignment is asked for.

Some of my allocators are in fact sub-allocators. For example, one of them is a linear/sequential allocator that just pointer-bumps on allocation. This allocator is constructed by passing in a char * pBegin and char * pEnd and it allocates from within that region in memory. For now, it works great but I get stuff that is 1-byte aligned. It works on x86 but I heard it can be disastrous on other CPUs (consoles?). It's also somewhat slower for reads and writes on x86.

The only sane way I know of implementing aligned memory management is to allocate an extra sizeof( void * ) + (alignement - 1) bytes and do pointer bit-masking to return the aligned address while keeping the original allocated address in the bytes before the user-data (the void * bytes, see above).

OK, my question...

That overhead, per allocation, seems big to me. For 4-bytes alignment, I would have 7 bytes of overhead on a 32-bit cpu and 11 bytes on a 64-bit one. That seems like a lot.

First, is it a lot? Am I on par with other memory management libs you might have used in the past or are currently using? I've looked into malloc and it seems to have a minimum of 16-byte overhead, is that right?

Do you know of a better way, smaller overhead, of returning aligned memory to my lib's users?

Upvotes: 0

Views: 307

Answers (2)

JasonD
JasonD

Reputation: 16582

You could store an offset, rather than a pointer, which would only need to be large enough to store the largest supported alignment. A byte might even be sufficient if you only support smallish alignments.

Upvotes: 1

aakash
aakash

Reputation: 761

How about you implement a buddy system which can be x-byte aligned depending on your requirement.

General Idea:

  1. When your lib is initialized, allocate a big chunk of memory. For our example lets assume 16B. (Only this block needs to be aligned, the algorithm will not require you to align any other block)
  2. Maintain lists for memory chunks of power 2. i.e 4B, 8B, 16B, ... 64KB, ... 1MB, 2MB, ... 512MB.
  3. If a user asks for 8B of data, check the list for 8B, if not available, check list of 16B and split it into 2 blocks of 8B. Give one back to user and the other, gets appended to the list of 8B.
  4. If the user asks for 16B, check if you have at least 2 8B available. If yes, combine them and give back to user. If not, the system does not have enough memory.

Pros:

  1. No internal or external fragmentation.
  2. No alignment required.
  3. Fast access to memory chunks as they are pre-allocated.
  4. If the list is an array, direct access to memory chunks of different size

Cons:

  1. Overhead for list of memory.
  2. If the list is a linked-list, traversal would be slow.

Upvotes: 0

Related Questions