Ускорьте итерацию по соседям в графе
У меня есть статический граф (топология не изменяется со временем и известна во время компиляции), где каждый узел в графе может иметь одно из трех состояний. Затем я моделирую динамику, когда у узла есть вероятность изменения своего состояния с течением времени, и эта вероятность зависит от состояния его соседей. По мере того, как график увеличивается, моделирование становится очень медленным, но после некоторого профилирования я обнаружил, что большая часть времени вычислений была потрачена на итерации по списку соседей.
Мне удалось повысить скорость моделирования, изменив структуру данных, используемую для доступа к соседям на графике, но мне было интересно, есть ли лучшие (более быстрые) способы сделать это.
Моя текущая реализация выглядит так:
Для графа с N узлы помечены из 0 в N-1 и среднее количество соседей KЯ храню каждое состояние как целое число в std::vector<int> states и количество соседей для каждого узла в std::vector<int> number_of_neighbors,
Для хранения информации о соседях я создал еще два вектора: std::vector<int> neighbor_lists который хранит, по порядку, узлы, которые являются соседями к узлу 0узел 1, …, узел Nи индексный вектор std::vector<int> index который хранит для каждого узла индекс своего первого соседа в neighbor_lists,
Итак, у меня есть четыре вектора:
printf( states.size() ); // N
printf( number_of_neighbors.size() ); // N
printf( neighbor_lists.size() ); // N * k
printf( index.size() ); // N
При обновлении узла i Я получаю доступ к соседям так:
// access neighbors of node i:
for ( int s=0; s<number_of_neighbors[i]; s++ ) {
int neighbor_node = neighbor_lists[index[i] + s];
int state_of_neighbor = states[neighbor_node];
// use neighbor state for stuff...
}
Подводя итог моему вопросу: есть ли более быстрая реализация для доступа к соседним узлам в фиксированной графовой структуре?
В настоящее время я поднялся до N = 5000 за приличное количество времени симуляции, но я стремился к N ~ 15.000, если это вообще возможно.
Решение
Важно знать порядок величины N потому что, если оно не слишком высокое, вы можете использовать тот факт, что вы знаете время компиляции топологии, чтобы вы могли поместить данные в std::arrayс известных размеров (вместо std::vectors), используя наименьший возможный тип для (при необходимости) экономии памяти стека, определим некоторые из них как constexpr (Все кроме states).
Так что если N не слишком большой (ограничение стека!), вы можете определить
-
statesкакstd::array<std::uint_fast8_t, N>(8 бит на 3 состояния достаточно) -
number_of_neighborsкакconstexpr std::array<std::uint_fast8_t, N>(если максимальное число соседей меньше 256, в противном случае тип больше) -
neighbor_listкакconstexpr std::array<std::uint_fast16_t, M>(гдеMявляется известной суммой числа соседей), если 16 бит достаточно дляN; больший тип в противном случае -
indexкакconstexpr std::array<std::uint_fast16_t, N>если 16 бит достаточно дляM; больший тип в противном случае
Я думаю (я надеюсь), что использование массивов известных измерений, которые constexpr (когда это возможно) компилятор может создать самый быстрый код.
Что касается обновления кода … Я старый программист на C, поэтому я привык пытаться оптимизировать код так, как это делает современный компилятор, поэтому я не знаю, является ли следующий код хорошей идеей; в любом случае, я бы написал такой код
auto first = index[i];
auto top = first + number_of_neighbors[i];
for ( auto s = first ; s < top ; ++s ) {
auto neighbor_node = neighbor_lists[s];
auto state_of_neighbor = states[neighbor_node];
// use neighbor state for stuff...
}
— РЕДАКТИРОВАТЬ —
ОП указать, что
В настоящее время я поднялся до N = 5000 за приличное количество времени симуляции, но я стремился к N ~ 15.000, если это вообще возможно.
Так что 16 бит должно быть достаточно — для типа в neighbor_list И в index — а также
-
statesа такжеnumber_of_neighborsоколо 15 кБ каждый (30 кБ с использованием 16-битной переменной) -
indexсоставляет около 30 кБ.
Мне кажется, что это разумные значения для переменных стека.
Проблема может быть neighbor_list; если среднее число соседей мало, скажем 10, чтобы исправить число, мы имеем, что M (сумма соседей) около 150’000, поэтому neighbor_list около 300 кБ; не низкий, но разумный для некоторой среды.
Если среднее число большое — скажем, 100, чтобы исправить другое число -, neighbor_list стать около 3 МБ; в некоторых средах оно должно быть высоким.
Другие решения
В настоящее время вы получаете доступ к сумме (K) узлов для каждой итерации. Это звучит не так уж плохо … пока вы не нажмете доступ к кешу.
Для менее чем 2 ^ 16 узлов вам нужен только uint16_t чтобы идентифицировать узел, но с K соседями вам понадобится uint32_t индексировать список соседей.
Как уже упоминалось, 3 состояния могут храниться в 2 битах.
Итак, имея
// your nodes neighbours, N elements, 16K*4 bytes=64KB
// really the start of the next nodes neighbour as we start in zero.
std::vector<uint32_t> nbOffset;
// states of your nodes, N elements, 16K* 1 byte=16K
std::vector<uint8_t> states;
// list of all neighbour relations,
// sum(K) > 2^16, sum(K) elements, sum(K)*2 byte (E.g. for average K=16, 16K*2*16=512KB
std::vector<uint16_t> nbList;
Ваш код:
// access neighbors of node i:
for ( int s=0; s<number_of_neighbors[i]; s++ ) {
int neighbor_node = neighbor_lists[index[i] + s];
int state_of_neighbor = states[neighbor_node];
// use neighbor state for stuff...
}
переписать свой код в
uint32_t curNb = 0;
for (auto curOffset : nbOffset) {
for (; curNb < curOffset; curNb++) {
int neighbor_node = nbList[curNb]; // done away with one indirection.
int state_of_neighbor = states[neighbor_node];
// use neighbor state for stuff...
}
}
Таким образом, чтобы обновить один узел, вам нужно прочитать текущее состояние из statesчитать смещение от nbOffset и использовать этот индекс для поиска списка соседей nbList и индекс из nbList искать соседние государства в states,
Первые 2, скорее всего, уже будут в L1 $, если вы будете проходить по списку линейно. Чтение первого значения из nbList для каждого узла может быть L1 $, если вы вычисляете узлы линейно, в противном случае это, скорее всего, вызовет L1 $ и, скорее всего, промах L2 $, следующие операции чтения будут предварительно аппаратно выбраны.
Линейное чтение через узлы имеет дополнительное преимущество, заключающееся в том, что каждый список соседей будет считываться только один раз за итерацию набора узлов и, следовательно, вероятность того, что states пребывание в L1 $ резко возрастет.
Уменьшение размера states может повысить вероятность того, что он останется в L1 $ в дальнейшем, при небольшом расчете можно сохранить 4 состояния по 2 бита в каждом байте, уменьшив размер states до 4КБ. Таким образом, в зависимости от того, сколько «вещей» вы делаете, вы можете иметь очень низкую частоту пропадания кэша.
Но если вы будете прыгать в узлах и делать «вещи», ситуация быстро ухудшается, вызывая почти гарантированный промах L2 $ для nbList и потенциальный L1 $ отсутствует для текущего узла, а K вызывает state, Это может привести к замедлению в 10-50 раз.
Если в последнем сценарии с произвольным доступом вы должны рассмотреть возможность сохранения дополнительной копии состояния в списке соседей, что экономит стоимость доступа states К раз. Вы должны измерить, если это быстрее.
Что касается встраивания данных в программу, то вы бы немного выиграли, если бы не имели доступа к вектору, в этом случае я бы оценил их как менее 1% выигрыша от этого.
In-lining и constexpr агрессивно ваш компилятор будет кипятить ваш компьютер годами и отвечать «42«В качестве конечного результата программы. Вы должны найти золотую середину.