I have a contiguous heap of heterogeneous objects that need not preserve the validity of pointers to previously allocated objects upon a call to allocate, i.e:
int* p = heap.allocate(1);
int* q = heap.allocate(1); // p need not point to the int it was initially pointing to
Say we have a heap, with allocated (a) / unallocated (u) memory (for a heap of objects T, size of u and a == sizeof(T)), like so: uuu a u aa uuuuu
If, using the best-fit allocation strategy, we tried to allocate 4 objects contiguously, we would allocate to the unallocated region of size 5 resulting in the heap:
uuu a u aa aaaa u
However, in terms of minimising memory fragmentation, this is not ideal. Since the heap need not preserve the validity of the pointers returned by the allocate method, we can move allocated objects within the heap. Taking advantage of this fact, for the heap: uuu a u aa uuuuu, we could move the first allocated object to the beginning of the heap (a uuuu aa uuuuu) and then use the best-fit allocation strategy, resulting in the heap: a aaaa aa uuuuu.
This is much better in terms of minimising memory fragmentation, but for large heaps with many unallocated regions with large allocated regions, it would be very slow to do this form of allocation. (Perhaps not if some sort of cost function was defined, that would force the use of best-fit if doing this form of allocation could take too long?)
What is the best allocation strategy (that need not preserve pointer validity to previously allocated objects), so as to minimise allocation time and memory fragmentation?
edit: I shouldn't be using a heap. I will use slab allocation, due to the fact that when I am allocating, I am not allocating random amounts of objects. I will usually be allocating one object at a time, and if I am not, I will probably be allocating N number of objects multiple times.