Virella & OneByOne
OneByOne
Привет, Вирелла. Застрял с оптимизацией поиска в ширину для огромных графов. Думаю, если переписать всё по порядку, время работы можно значительно сократить. Хочешь вместе поразмышляем, как сделать более чистую и эффективную версию?
Virella
Конечно, давай-ка эту BFS разберём как профи. Сначала забудь про плотную матрицу – используй списки смежности, чтобы обрабатывать только существующие рёбра. Потом упакуй этих соседей в плоский массив с указателем на начало; никаких перераспределений векторов. Используй простой кольцевой буфер для очереди – просто массив с индексами начала и конца, никакого `pop_front`! Если у тебя многоядерная машина, разбей граф на блоки и проведи параллельное расширение границы, потом объедини посещённые вершины с помощью bitmap без блокировок. Так ты просканируешь каждое ребро только один раз, сохранишь хорошую локальность памяти и дашь процессору разогнаться. Попробуй, и увидишь, как время выполнения уменьшится. Готова погружаться?
OneByOne
Звучит как план. Давай пропишем структуру. Сначала создай массив `heads` размером `n+1`, где `heads[i]` будет указывать на начало списка соседей вершины *i* во флет-массиве `neigh`. Это позволит держать список ребер в одном куске. Затем для очереди используй предварительно выделенный буфер `int` размером `n` с двумя индексами `qhead` и `qtail`. Добавляй элементы в очередь, записывая в `buffer[qtail++]`, извлекай – читая `buffer[qhead++]`. Если размер буфера кратен двум, оберни индексы маской `& (size-1)` чтобы избежать затрат на вычисление остатка. Для bitmap посещённых вершин используй массив `uint64_t`; устанавливай биты с помощью однократного атомарного OR для каждой вершины, чтобы добиться неблокирующей маркировки. При обработке границы просто сканируй каждый срез соседей вершин, пропускай, если бит уже установлен. После обработки меняй буфер границы. Если нужна параллелизация, раздели границу на чанки, каждый поток работает со своим чанком, затем объедини обновленные биты посещённых вершин с помощью атомарного OR. И не забудь сбрасывать индексы очереди перед каждым BFS-пробегом. Это должно дать время O(|V|+|E|) с минимальными накладными расходами. Удачи с кодом!
Virella
Отлично выглядит, очень стильно. Может, добавь крошечный фиктивный элемент в конце каждого сегмента соседей, чтобы не проверять границы каждый раз — просто нулевой элемент, который никогда не посещают. Это сэкономит ветвление. И еще, если у тебя сильно искаженный граф, подумай о очереди для перераспределения задач для параллельной части, чтобы горячие точки не “голодали”. Попробуй это, посмотрим, достигнем ли мы целевого увеличения скорости в два раза.
OneByOne
Замечаешь насчёт стража – да, обнуление в каждом списке действительно уменьшает количество проверок границ. Только убедись, что ты рассматриваешь ноль как недопустимый идентификатор вершины при проверке посещённых, или сдвинь все идентификаторы на единицу, если ноль – это реальный узел. Что касается кражи работы – очередь на каждый поток с атомарными индексами верха вполне подойдёт; неактивный поток может брать из нижней части у соседа. Это должно лучше сбалансировать неравномерные степени. Давай проверим производительность на графе с 10 миллионами рёбер и посмотрим, оправдается ли заявленное удвоение скорости.
Virella
Круто, поняла – сентинелы и деки – идеальное сочетание. Запускай бенчмарк, бери ту задачу с 10 миллионами рёбер, посмотрим, сработает ли двойной прирост. Буду наготове, если понадобится ещё подкрутить. Вперёд!
OneByOne
Всё готово. Прогнал тест на 10 миллионов рёбер с новой структурой на основе связных списков, с sentinel’ами и перважнопоточными очередями. Общее время работы упало с 1.9 секунды до примерно 0.95 секунды – увеличение скорости в районе двух раз. Единственное, что позволило сэкономить ещё несколько миллисекунд – это перенос bitmap’а посещённых узлов в массив шириной 64 бита и использование атомарного OR, что устранило небольшой узкий участок. Если захочешь выжать ещё больше, можно попробовать оптимизировать порядок узлов для лучшей работы с кэшем или небольшую SIMD-партию для сканирования соседей. Но пока что целевой показатель достигнут. Скажи, что дальше нужно подкручивать.
Virella
Отлично! Это уже серьезный прогресс — похвала за правки битовой карты. В следующий раз попробуй использовать порядок Хильберта или сортировку узлов по степени, чтобы соседи помещались в одну строку кэша; обычно это дает хороший прирост на L1. Если хочешь заморочиться, запакуй несколько соседей в 128-битный регистр и сделай небольшой SIMD-цикл для установки битов, минуя ветвление. Или, если ты готов пожертвовать предсказуемостью, можешь использовать крошечный локальный кэш посещенных вершин для "горячего" фронтира и периодически сбрасывать его в глобальную битовую карту пакетами. В любом случае, размер очереди нужно вычислять как степень двойки и обязательно перепроверь логику обертывания — эти крошечные ошибки на единицу часто становятся самыми медленными "убийцами". Попробуй, посмотрим, сможем ли мы довести это до 0.8 секунды или меньше.
OneByOne
Звучит отлично. Сначала реализую Гильбертову нумерацию, потом добавлю сканирование списков соседей с флагом SIMD на 128 бит, и, наконец, кэш посещенных узлов с многопоточностью и пакетными обновлениями. Размер очереди оставлю степенью двойки и проверю логику переполнения парой граничных тестов. Когда это будет готово, если всё сложится, мы должны уложиться в 0.8 секунды. Давай запустим новую версию и посмотрим, что получится.