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?

1
Richard 3 marzec 2012, 06:36

2 odpowiedzi

Najlepsza odpowiedź

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:

  1. podatne na wycieki pamięci
  2. płacisz za dodatkowe miejsce na wskaźniki,
  3. podatne na fragmentację pamięci i
  4. 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

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