Как избежать "спагетти курсора кучи" в динамических графах?

Общая проблема

Предположим, что вы кодируете систему, состоящую из графика и правил перезаписи графика, которые могут быть активированы в зависимости от конфигурации соседних узлов. То есть у вас есть динамический граф, который непредсказуемо растет во время выполнения. Если вы наивно используете malloc, новые узлы будут распределены в случайных позициях в памяти; после достаточного времени ваша куча будет спагетти-указателем, что даст вам ужасную эффективность кеша. Есть ли какой-либо легкий, инкрементный метод, чтобы сделать узлы, которые соединяются вместе друг с другом в памяти?

Что я пробовал

Единственное, о чем я мог думать, это встраивание узлов в декартово пространство с некоторым физическим упругим моделированием, которое отталкивало/притягивало узлы. Это будет содержать проводные узлы вместе, но выглядит глупо, и я думаю, что накладные расходы на симуляцию будут больше, чем ускорение эффективности кеширования.

Простой пример

Это - это система, которую я пытаюсь реализовать. Этот является кратким фрагментом кода, который я пытаюсь оптимизировать в C. Этот repo является прототипом, рабочая реализация в JS, с ужасной эффективностью кеширования (и самого языка). Это видео показывает систему в действии графически.

Ответ 1

То, что вы ищете, - это проблема линейных компонов. Идеальные решения считаются NP-жесткими, но существуют некоторые хорошие приближения. Вот документ , который должен быть хорошим местом для начала.

Ответ 2

Вы можете посмотреть на это с точки зрения сбора мусора в полупространстве. Это непросто реализовать (я сделал это для интерпретатора), особенно потому, что вы делаете это только для структур с фиксированным размером node. Выделите из одного большого блока (называемого полупространством) памяти. Когда он становится слишком полным или фрагментированным, остановите и скопируйте все в другое (что вы также можете сделать больше). Трюк обновляет все указатели. Для этого существует очень элегантный и эффективный алгоритм, называемый копией сканирования. Там приятное обсуждение этого в Корнелле. Он по существу пересекает ширину графа сначала, копируя его, без какого-либо дополнительного пространства, кроме того, что вы копируете. Хорошим свойством алгоритма является то, что ширина первых уровней заканчивается рядом с каждой копией. Если это достаточно хороший уровень местоположения, вы получите это очень эффективно с помощью этого метода.

Ответ 3

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

Вы можете malloc большой блок памяти при запуске, затем вы выделяете пространство из этого блока. Вам потребуется отдельная структура, чтобы отслеживать, что есть и что не было выделено. Если вы знаете, что все выделенные структуры имеют определенный размер, что упрощает управление распределенным/свободным пространством, то есть массив индексов, в противном случае вы могли бы использовать связанный список указателей в свободном пространстве. Учитывая, что вы, вероятно, будете распределять структуры по одному, вам, вероятно, не нужно беспокоиться о том, чтобы отслеживать самый маленький и/или самый большой смежный блок свободного места.

Одна вещь, о которой вам нужно быть осторожной, - это выравнивание. Опять же, если вы всегда будете выделять память в несколько раз больше одной структуры, это упростит ситуацию, в противном случае, вероятно, хорошая идея обеспечить, чтобы все распределения начинались с границы 4 байта, то есть разница между адресом, который вы а начальный адрес, полученный из malloc, кратен 4.

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

Ответ 4

Это можно рассматривать как проблему graph partitioning, где вы пытаетесь сгруппировать связанные узлы графа на одном блоке памяти. METIS - хороший алгоритм разбиения графов, который, вероятно, не подходит для вашего случая использования, поскольку он требует глобальных операций по всему графику, однако два распределенных алгоритмы разбиения графа, которые могут быть изменены для применения в вашем случае использования, DIDIC и Ja-Be-Ja - первый пытается свести к минимуму количество ребер, пересекающих разделы без учета размера раздела, в то время как последний пытается создать одинаково размерные разделы. Оба алгоритма требуют только локального знания графа для кластеризации каждого node, поэтому, если у вас есть запасные циклы, вы можете использовать их для постепенного перебалансирования графика. Фенхель - это связанный алгоритм, который работает на потоковых графиках, т.е. вы можете использовать Fennel или аналогичный алгоритм при первоначальном распределении графа node, а затем использовать DIDIC/Ja-Be-Ja при перебалансировке графика.