Структуры данных на практике. Глава 15: Графы и их обход с эффективным использованием кэша

[wataru]

Что-то я не понял про блочный BFS.

Ваше объяснение "почему это работает быстрее" - абсолютно ложно:

Обработка набора узлов перед переходом к следующему уровню

Узлы обрабатываются в том же порядке, по одному, каждый раз следующий берется из очереди. Никакого перехода к следующему уровню тут нет.

Улучшенная временная локальность (многократное использование посещённого массива в кэше)

Нет, работа с посещенным массивом тут будет точно такая же - будут обращения к тем же адресам в том же порядке.

Амортизация оверхеда очереди

Это вы про замену K queue_pop на head += K? Это ничтожная амортизация. Если там, конечно, очередь на массиве. Эти заменяемые K head++ ничтожны по сравнению с остальной работой алгоритма.

Вот сравним алгоритмы. Обычный был:

 while (!queue_empty(q)) {
        node_t *node = queue_pop(q);
        process(node);
        
        for (int i = 0; i < node->num_neighbors; i++) {

Блочный же:

while (head < tail) {
        int block_end = (head + BLOCK_SIZE < tail) ? head + BLOCK_SIZE : tail;
        
        // Обработка блока узлов
        for (int i = head; i < block_end; i++) {
            int node_id = queue[i];
            node_t *node = &g->nodes[node_id];
            
            process(node);
            
            // Добавление соседей в очередь
            for (int j = 0; j < node->num_neighbors; j++) {

Узлы обрабатываются вообще в том же порядке, обращение к тем же самым данным в том же самом порядке - очередь и массив visited.

Единственная разница - "развернута" работа с очередью. Вместо К queue_pop один раз сдвигается head сразу на K позиций. Да вместо К проверок queue_empty() выполняется одно вычисление конца блока и K проверок i < block_end.

Это не должно никак принципиально ускорять код, если только очередь не тормознутая была.

Т.е. тут никакой ни другой алгоритм, просто реализация накрученной общеприменимой очереди (может даже на связных списках) заменена на тривиальный массив. И работа блоками тут не нужна, достаточно вместо queue_pop() делать ++head и в цикле делать head < tail вместо queue_empty.

Или я что-то упускаю из виду?

[alkneu]

>Или я что-то упускаю из виду?

>И работа блоками тут не нужн

Тоже не понял смысл этих телодвижений от автора.

В теории есть какой-то смысл от SIMD+loop unrolling при обработке/слиянии циклов, обрабатывающих соседей для, скажем 2 последовательных вершин, но тогда даже для BLOCK_SIZE==2 для вершин со степенями deg1,deg2 надо делать MD-обработку d12==min(deg1, deg2) пар соседних вершин + остаток для обеих: deg1-d12 соседей для первой и deg2-d12 для второй (чуть проще если нарушить симметрию и свапнуть, чтобы deg1>=deg2), но:

• Нет гарантии, что 2*d12 не будет мал по сравнению с deg1+deg2 (~плохой случай - степень вершин скачет вверх-вниз)

• На вскидку, большая часть работы/задержки происходит не в ALU/FPU, а дожидаясь данные из памяти

  Более логичным выглядит loop unrolling независимо для каждого цикла обхода соседей, но все равно особым SIMD тут не пахнет (так же большую часть времени ждём данные из памяти/кэша).

>параллельный обход графа

В худшем случае это BFS всё равно O(depth==расстояние до самой дальней вершины от начальной)=O(n) (по крайней мере мере, для реализаций без ухищрений вроде "подсчитаем для каждой вершины список соседей соседей/2-neighborhood, после этого делаем BFS в новым графе, но с depth_new~= depth/2", но с этим "ухищрением" память и общая работа n--> n**2)

Не говоря о том, что цена атомиков за операцию, ЕМНИП x10-100-1000

[wataru]

А еще CSR от обычных компактных списков смежности принципиально не отличается. В CSR вы храните всех соседей в одном массиве и во втором начало и конец куска. В компактных списках смежности вы опять же храните всех соседей в одном массиве, но вместо двух индексов вы храните указатель на начало и количество элементов. Какая-то разница в производительности у вас получается из-за замены массива структур на структуру массивов, а не из-за смены представления графа.

CSR - Это и есть научное название "компактного списка смежности".

Объяснение опять с потолка взято, или сгалюционированно нейросетями.

Упорядочивание в ширину

Это натягивание совы на глобус. Вы чтобы ускорить BFS должны сначала запустить BFS для упорядочивания элементов. Это тупо предподсчет получается. Да, если посчитать что-то заранее, вычисления будут быстрее. Но это не оптимизация.

[Jijiki]

кстати да не оптимизация, приведу пример когда она не оптимизация без натягиваний на глобус.

let temp=vec![1; 4096];
let cube:(Vec<f32>,Vec<i32>)=(Vec::new(),Vec::new());
//даже если u32 делать разница есть, но несущественная
for i in 0..16{
  for j in 0..16{
    for k in 0..16{
      этот цикл даже если делать деревянным будет переусложнением
      тоесть если элементов в данном 
      примере 4096(граней * 6 треугольников *2
      , а для АО вообще вершины будут нужны) можно обойтись циклом,
      это цикл для предрасчета, в данном примере, например, 
      подсчет сторон куба видимых граней.
    }
  }
}
//full chunk cube:4096 - это только 1 чанк, а их много
//надо получить {vertices,indexs}, через маску 1/0 - наличие кубика

единственный варик это мир через BSP получается, но это другой мир...

нет ну можно подумать 6х дерево, я вчера пробовал, но это всё не то, теряется локальность данных по сравнению с массивом, а вот Golden Source, там красиво получается по коллизиям и отрисовке с генерацией...

[lightln2]

Что мне больше всего тут непонятно, это как там на графе из 500 вершин и 6000 ребер даже в самой оптимизированной версии насчиталось почти миллион cache misses.

Ну и вообще, я посмотрел в оригинал, он оставляет странное впечатление - товарищ работает с низкоуровневым программированием, пишет книгу аж из 20 глав, в ней все баззворды на своих местах. Но он зациклен на cache misses, и его аргументация местами очень странная. То ли очень неаккуратно написано (при чем тут Radix Tree?), то ли вообще цифры с потолка взяты.

[lightln2]

А по теме, есть хорошая лекция от MIT про оптимизацию BFS, с акцентом на многопоточность, но и однопоточные оптимизации тоже раскрываются. Там, кстати, рассказывают, как именно считаются эти cache misses, и как оптимизации их улучшают.

Это все если граф влезает в память. BFS для графов, которые не влезают в память - это отдельный мир, с десятилетиями научных исследований и сотней эзотерических алгоритмов.