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

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

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

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

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

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

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