Memory Pool Allocator

Odpowiedz Nowy wątek
2016-12-06 15:36
0

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.

Pozostało 580 znaków

2016-12-06 15:42
0

Aby uruchomić powyższy kod:

// jakies naglowki
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstdint>

using namespace std;

int main() {
    int nSizeInBytes = (2000 * 32);
    InitFrameMemorySystem(nSizeInBytes, 2); // allocate block

    Frame_t Frame_1 = AllocateObject(1776, _HEAPNUM);
    Frame_t Frame_2 = AllocateObject(140, _HEAPNUM);
    Frame_t Frame_3 = AllocateObject(528, _HEAPNUM);
    Frame_t Frame_4 = AllocateObject(108, _HEAPNUM);
    Frame_t Frame_5 = AllocateObject(1776, _HEAPNUM);

    printf("available memory after alloc frame: %d\n", (_apFrame[1] - _apFrame[0]));

    ReleaseFrame(Frame_1);

    printf("available memory after dealloc frame: %d\n", (_apFrame[1] - _apFrame[0]));

    ShutDownFrameMemorySystem();    // deallocate memory block

    return 0;
} 

Kod dla testu, zonk będzie przy ReleaseFrame jak przy zwalnianiu ramki będzie już inna kolejność.

Dzięki za pomoc.

Pozostało 580 znaków

2016-12-06 15:57

Pójdę na łatwizne i tylko zasugeruje poczytanie jak do problemu podeszli inni ludzie, np Andrei Alexandrescu na potrzeby swojej książki oraz jak zmodyfikował ten kod pan Rich Sposato. Daje to jakieś pojęcie jak zabrać się do tematu. No i jest też Boost

edytowany 2x, ostatnio: several, 2016-12-06 16:00

Pozostało 580 znaków

2016-12-07 08:27
0

Dzięki za sugestię, poczytam.
Co do Boost to odpada, max co mogę wykorzystać to czysty C++ 11.

Pozostało 580 znaków

2016-12-07 11:47
0

Nie musisz używać jak nie chcesz/nie możesz, ale boost jest opensource więc można coś od niego "zgapić" ;) Jeżeli dopiero poznajesz temat, to idealnym wg. mnie scenariuszem byłoby napisanie apki z alokatorem będącym cienkim wraperkiem nad czymś gotowym (SmallObjAllocator albo boost.pool), sprofilowanie valgrindem a potem zastąpienie bebechów czymś swoim.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0