Hej,
Mam zagadkę, którą próbuje rozwikłać jak najefektywniej (problem z dealokacją).
Piszę memory allocatora, który może z własnej puli pamięci ustawionej na samym początku, przydzielać obiektom pamięć (o różnym rozmiarze) w czasie działania programu, aby uniknąć fragmentacji pamięci i też dla szybszego ogólnego działania programu:
Ogólnie wygląda to tak, jest blok pamięci, dwa wskaźniki na podstawę i szczyt apBaseAndCap[0-1], i dwa wskaźniki apFrame[0-1], które się przesuwają w zależności od ilości zaalokowanej pamięci:
typedef unsigned char u8;
typedef unsigned int uint;
#define ALIGNUP( nAddress, nBytes ) ( (((uintptr_t)nAddress) + (nBytes)-1) & (~((nBytes) -1 )) )
static int _nByteAlignment; // alignment memory in bytes
static u8 *_pMemoryBlock; // value returned by malloc()
static u8 *_apBaseAndCap[2]; // [0] ptr to base, [1] ptr to peak
static u8 *_apFrame[2]; // [0] ptr to lower frame, [1] ptr to higher frame
// must be called once before start of the system
// nByteAlignment must by power of 2
// return 0 if success, or 1 if an error
int InitFrameMemorySystem(int nSizeInBytes, int nByteAlignment) {
cout << "init" << endl;
// nSizeInByte is a mulitiplicity of nByteAlignment
nSizeInBytes = ALIGNUP(nSizeInBytes, nByteAlignment);
// memory block allocation
_pMemoryBlock = (u8*)malloc(nSizeInBytes + nByteAlignment);
if(_pMemoryBlock == 0) {
// there is no memory
return 1;
}
_nByteAlignment = nByteAlignment;
// set ptr to base
_apBaseAndCap[0] = (u8*)ALIGNUP(_pMemoryBlock, nByteAlignment);
// set ptr to peak
_apBaseAndCap[1] = (u8*)ALIGNUP(_pMemoryBlock + nSizeInBytes, nByteAlignment);
// initialization of lower and higher frame
_apFrame[0] = _apBaseAndCap[0];
printf("lower frame : %d\n", _apFrame[0]);
_apFrame[1] = _apBaseAndCap[1];
printf("higher frame: %d\n", _apFrame[1]);
// success
return 0;
}
void ShutDownFrameMemorySystem() {
free(_pMemoryBlock);
}
// return ptr to base of memory block
// or 0 if there is no more memory
// nHeapNum is the number of heap, 0=bottom, 1=peak
void * AllocFrameMemory(int nBytes, int nHeapNum) {
// first make alignment to proper size
nBytes = ALIGNUP(nBytes, _nByteAlignment);
void * pMem;
cout << "alloc nBytes: " << nBytes << " requested" << endl;
// check if there is available memory
if(_apFrame[0] + nBytes > _apFrame[1]) {
// there is no memory
return 0;
}
// memory allocation
if(nHeapNum) {
// allocation in higher heap, decrease ptr
_apFrame[1] -= nBytes;
pMem = _apFrame[1];
}
else {
// allocation in lower heap, increase ptr
pMem = _apFrame[0];
_apFrame[0] += nBytes;
}
printf("allocated returning: %d\n", pMem);
printf("alloc lower frame : %d\n", _apFrame[0]);
printf("alloc higher frame: %d\n", _apFrame[1]);
return (void*)pMem;
}
typedef struct {
u8* pFrame; // u8
u8* ptrToAllocatedMemory;
int nHeapNum;
} Frame_t;
// return frame (handler) which will be used
// to free memory.
// nHeapNum is a heap number: 0=lower heap, 1=higher heap
Frame_t GetFrame(int nHeapNum) {
Frame_t Frame;
Frame.pFrame = _apFrame[nHeapNum];
Frame.nHeapNum = nHeapNum;
return Frame;
}
#define _HEAPNUM 1
Frame_t AllocateObject(int nSize, int nHeapNum) {
Frame_t Frame;
// allocate object
Frame = GetFrame(_HEAPNUM);
Frame.ptrToAllocatedMemory = (u8*)AllocFrameMemory(nSize, nHeapNum);
if(Frame.ptrToAllocatedMemory == 0) {
cout << " no more memory " << endl;
}
return Frame;
}
void ReleaseFrame(Frame_t Frame) {
assert(Frame.nHeapNum == 1 || (uintptr_t)Frame.pFrame <= (uintptr_t)_apFrame[0]);
assert(Frame.nHeapNum == 0 || (uintptr_t)Frame.pFrame >= (uintptr_t)_apFrame[1]);
_apFrame[Frame.nHeapNum] = Frame.pFrame;
}
Alokacja śmiga, tylko mam problem z dealokacją.
Ponieważ powyższy system dostaje randomowy rozmiar z przedziału (16-1776 ) allokuje to jako int więc potrzebuje z allocatora np. 1776 x 4 = 7104b pamięci, więc allocator przydziela taki blok pamięci i przesyła to dalej do funkcji i zajmuje się nowym przydziałem pamięci.
Gdzieś indziej w systemie sobie siedzi deallocator, który musi zwolnić już nie potrzebną ramkę.
I moje pytanie, jak najefektywniej dla takiego przypadku napisać deallocator (release Frame) aby wiedział co ma zwolnić i aby uniknąć w tym allokatorze fragmentacji?
Lub może da się to zamienić na coś efektywniejszego, bo wszystko rozbija się o to, że w bardzo krótkim odstępie czasu jest allokowanych poprzez new dużo obiektów o różnym rozmiarze requestedSize:(16-1776) dla int * tmp = new int[requestedSize]; a gdzieś indziej są one zwalniane i przez to jest duża fragmentacja danych?
Dzięki za pomoc.