Strategie alokacji dla obiektów w kolejce

Question

Mam klasę w następujący sposób:

typedef struct grid_cell_type {
int x;
int y;
grid_cell_type(int x0, int y0){
    x=x0;
    y=y0;
}

} komórka_siatki;

Przepompuję około 100 milionów z nich w kolejce.

W tej chwili dzieje się to w następujący sposób:

my_queue.push(new grid_cell(x0,y0));

Indywidualna alokacja wszystkich tych obiektów na kawałki wydaje się, że prawdopodobnie nie jest tak szybka, jak alokacja masowa.

Masz jakieś przemyślenia na temat najlepszej strategii do realizacji tutaj?

c++ memory-management queue

1

Richard 3 marzec 2012, 06:36

Answer 1

Są to małe i samodzielne obiekty - umieść je bezpośrednio w kolejce zamiast umieszczać wskaźniki.

W rzeczywistości, w systemie 64-bitowym i zakładając, że int jest 32-bitowy (co jest na przykład w Visual C++), wskaźnik będzie tak duży jak sam obiekt! Więc nawet jeśli masz rozdzielacz zbiorczy, nadal płacisz tę cenę.
Ogólny alokator pamięci będzie nie tylko kosztowny pod względem czasu, ale również będzie miał narzut na obiekt, który w tym przypadku zmniejszy sam obiekt (nie dotyczy alokatora zbiorczego).

Chociaż możesz opracować dość wydajny schemat alokacji „zbiorczej”, myślę, że łatwiej jest obejść ten problem i całkowicie uniknąć alokacji poszczególnych obiektów.

--- EDYTUJ ---

Możesz wepchnąć elementy do std::queue w ten sposób:

struct grid_cell {

    grid_cell(int x0, int y0) {
        x=x0;
        y=y0;
    }

    int x;
    int y;

};

// ...

std::queue<grid_cell> q;

q.push(grid_cell(0, 0));
q.push(grid_cell(0, 1));
q.push(grid_cell(0, 2));
q.push(grid_cell(1, 0));
q.push(grid_cell(1, 1));
q.push(grid_cell(1, 2));

W przypadku std::priority_queue musisz zdecydować, jak chcesz kolejność elementów.

--- EDYCJA 2 ---

@Richard Twój kod jest zupełnie inny.

Dla każdego push, twój kod przydzieli nowy blok pamięci dynamicznej, skonstruuje w nim obiekt (tj. przypisze x i y), a następnie wciśnie wskaźnik do tego bloku pamięci do kolejki.
Mój kod konstruuje obiekt bezpośrednio w jego „gnieździe” w większym bloku pamięci, który został wstępnie przydzielony przez sam queue. A jak już zauważyłeś, kilka dużych alokacji są lepsze niż wiele małych.

Twój kod to:

podatne na wycieki pamięci
płacisz za dodatkowe miejsce na wskaźniki,
podatne na fragmentację pamięci i
jak już wspomniałem, istnieje narzut na obiekt.

Specjalistyczny alokator hurtowy może usunąć dwa ostatnie problemy, ale dlaczego nie usunąć ich wszystkich?

--- EDYTUJ 3 ---

Jeśli chodzi o szybkość, ogólna alokacja pamięci dynamicznej jest kosztowna (około 40-50 instrukcji maszynowych dla najlepszych alokatorów).

Wyspecjalizowany alokator bloków byłby znacznie szybszy, ale nadal masz problem z opóźnieniem pamięci: trzymanie wszystkiego razem gwarantuje lepszą lokalizację pamięci podręcznej i jest znacznie bardziej odpowiednie dla logiki pobierania wstępnego procesora niż wielokrotne „przeskakiwanie” między kolejką a rzeczywistym obiekty przez usuwanie odwołań do wskaźników.

3

Branko Dimitrijevic 3 marzec 2012, 07:56

Answer 2

Mógłbyś zrobić jedną dużą ich tablicę i przydzielić z niej.

int allocation_index = 0;
grid_cell_type* cells = new grid_cell_type[100*1000*100];
my_queue.push(&cells[allocation_index++]);

Unikniesz wtedy kosztów związanych ze 100 milionami małych wiadomości. Czyszczenie jest wtedy tak proste jak delete [] cells;.

EDYTUJ: W tym konkretnym przypadku to, co powiedział Branko, jest prawdopodobnie najlepszym wyborem. Zakładając, że używasz std::queue, automatycznie przydzieli potrzebną pamięć. To, co zasugerowałem, lepiej pasowałoby do większych obiektów.

3

Kyle 3 marzec 2012, 06:58

Strategie alokacji dla obiektów w kolejce

2 odpowiedzi

Podobne pytania

Nowe pytania

c++