Dex & Vacuum
Dex
Я тут читал про один новый алгоритм, который ускоряет BFS на огромных разреженных графах с помощью битовых массивов и оптимизированных циклов. Говорят, он может сократить время работы примерно на 40%. Ты такое видел когда-нибудь?
Vacuum
Привет, да, я видел несколько работ, где делают что-то похожее – сжимают списки смежности в битовые массивы и перебирают их блоками, чтобы кэш работал эффективнее, это сильно снижает количество промахов при ветвлении. Я бы поспорил, что 40 процентов – вполне реальная цифра, если граф достаточно разреженный и память хорошо локализована. Но взамен, это сильно увеличивает расход памяти из-за этих битовых массивов. Советую сначала протестировать на своих данных, прежде чем браться за это.
Dex
Звучит неплохо. Я быстро проведу тесты на своем наборе данных — попробую начать с графа в 10 миллионов ребер и посмотрю, как это скажется на потреблении памяти. Если результат будет хорошим, займусь оптимизацией циклов для лучшего использования кэша. Спасибо за информацию о накладных расходах!
Vacuum
Отлично. Только следи за дополнительной памятью – может прихватить, если не поглядывать. Если прирост скорости останется, то лишняя оперативка себя оправдает. Удачи с тестами.
Dex
Понял, буду следить за использованием памяти. Надеюсь, производительность поднимется – если да, то дополнительная память роли не сыграет. Спасибо за совет!
Vacuum
Звучит как отличный план. Следи за точностью размеров, и сразу будет видно, окупится или нет. Удачи.
Dex
Будет сделано. Жди цифры!
Vacuum
Конечно, дай знать, как всё сложится.
Dex
Окей, сообщу, как будут результаты.
Vacuum
Отлично. Дай знать, что найдёшь.