Стратегии размещения объектов в очереди

Question

У меня есть следующий класс:

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

} grid_cell;

Я буду прокачивать примерно 100 миллионов из них через очередь.

Прямо сейчасэто происходит следующим образом:

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

Кажется, что индивидуальное пошаговое распределение всех этих объектов выглядит не так быстро, как некоторое массовое распределение.

Любые мысли относительнолучшая стратегия, чтобы преследовать здесь?

Answer 1

Это небольшие и автономные объекты - поместите их непосредственно в очередь вместо указателей.

• На самом деле в 64-битной системе предполагается, что int равно 32-бит (который есть, например, в Visual C ++), указатель будет таким же большим, как и сам объект!Таким образом, даже если у вас есть массовый распределитель, вы все равно платите эту цену.
• Общий распределитель памяти будет не только дорогостоящим по времени, но и накладными расходами для каждого объекта, что в этом случае приведет к затуханиюсам объект (не относится к групповому распределителю).

Хотя вы могли бы разработать довольно эффективную схему «массового» распределения, я думаю, что проще обойти проблему и вообщеизбегайте выделения отдельных объектов.

--- EDIT ---

Вы можете помещать элементы в std::queue следующим образом:

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));

Для std::priority_queue вам нужно решить, как вы хотите заказать элементов.

--- EDIT 2 ---

@ Ричард Ваш код совершенно другой.

• Для каждого push ваш код выделит новый блок динамической памяти, создаст в нем объект (т.е. назначит x иy) и затем нажмите указатель на этот блок памяти в очереди.
• Моя трескаe создает объект непосредственно в своем «слоте» внутри большего блока памяти, который был предварительно выделен самим queue.И, как вы уже заметили, несколько больших выделений лучше, чем множество маленьких.

Ваш код:

1. подвержен утечкам памяти
2. вы платитедля дополнительного хранения указателей,
3. , склонных к фрагментации памяти, и
4. , как я уже упоминал, есть накладные расходы для каждого объекта.

Специализированный распределитель можетудалить последние две проблемы, но почему бы не удалить их все?

--- EDIT 3 ---

Что касается скорости, общее динамическое распределение памяти составляет дорогой (около 40-50 машинных инструкций для лучших распределителей).

Специализированный распределитель блоков будет намного быстрее, но у вас все еще есть проблема с задержкой памяти: гарантированно будет достигнуто правильное хранение всего вместелучшая локальность кэша и гораздо более подходящая для логики предварительной выборки ЦП, чем многократный «прыжок» между очередью и фактическими объектами путем разыменования указателей.

Answer 2

Вы можете сделать один большой массив из них и выделить из него.

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

Тогда вы избежите накладных расходов на 100 миллионов маленьких новостей. Очистка тогда просто, как delete [] cells;.

РЕДАКТИРОВАТЬ: В данном конкретном случае то, что сказал Бранко, вероятно, ваш лучший выбор Предполагая, что вы используете std::queue, он автоматически выделит необходимую вам память. То, что я предложил, лучше подойдет для более крупных объектов.