сокращение требований к памяти для списка смежности

Question

Я использую adjacency_list широко. У меня так много графиков загружено одновременно, что память становится проблемой. Я делаю статический анализ программы и сохраняю callgraph и потоковые диаграммы дизассемблированного двоичного файла в графах наддува. Таким образом, я могу иметь несколько десятков тысяч функций == flowgraphs и один гигантский каллиграф. Я действительно хотел бы уменьшить использование памяти для моего графики, все еще используя BGL.

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

больше вопросов:
1) Каковы затраты памяти на использование свойств вершин и ребер? я их немало.
2) можно ли убедить BGL использовать усадку, чтобы соответствовать идиома? Как я понимаю, списки смежности используют push_back для добавления кромки. Можно ли уменьшить использование памяти путем замены результирующий вектор с копией самого себя? Может быть, копируя весь график?
3) Можно ли использовать распределители пулов наддува с BGL? Как далеко как я могу сказать, BGL в настоящее время выполняет множество небольших распределений - Я действительно хотел бы избежать этого по соображениям эффективности пространства и времени выполнения.

Кто-нибудь уже создал версию BGL, оптимизированную для использования памяти? Стоит ли использовать существующие графовые структуры и дополнить их Пользовательские распределители или что-то такое, или это более плодотворно, чтобы написать свой собственный реализация и стараться оставаться интерфейсом совместимым с BGL так Я могу продолжать использовать его алгоритмы?

С наилучшими пожеланиями,

Sören

Answer 1

В BGL существует малоизвестный тип графа, называемый графом «сжатый разреженный ряд». Кажется, что он довольно новый и не связан с индексными страницами. Тем не менее, он использует красивый маленький трюк, чтобы получить представление графа как можно меньше. http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

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

Он также хранит свойства вершин / ребер в векторах, таким образом предоставляя наименьшие возможные издержки для них.

Обратите внимание, что версия, поставляемая с последней версией 1.40, поддерживает только диаграммы направленности (в отличие от двунаправленной). Если вам нужно иметь возможность эффективно перебирать внешние и внутренние ребра вершины (как я это сделал), вам нужно проверить ствол усиления из subversion. Иеремия очень помог мне добавить эту функцию по моей просьбе.

Answer 2

1. Издержки зависят от того, какую версию вы используете, и выбрали ли вы «связанные» свойства или нет. Я использовал только связанные свойства и читал код. Я ожидаю, что каждый набор свойств стоит вам 2 указателя + размер используемого вами типа пакета + размер каждого из прикрепленных свойств. Ничего из того, что проверяет концепцию, не осталось в бинарном файле. Хотя у вас есть код, почему бы просто не измерить стоимость? Если у вас нет каких-либо инструментов, чтобы помочь, попробуйте просто создать графики известных размеров в буферах известных размеров. Что-то в конечном итоге потерпит неудачу, и в этот момент вы должны иметь счет.

2. Вы пытались дозвониться до adjacency_list<blah>.swap(adjacency_list& x)? Я надеюсь, что это уменьшит контейнеры надлежащим образом.

3. ???

Я начал писать что-то вроде системы, которую вы описываете, но в итоге отказался от BGL и переключился на кодирование моих собственных алгоритмов для работы в базе данных sqlite со всеми символами компоновщика.

Answer 3

Как ответ на вопрос:

3) Можно ли использовать BGL-распределители повышающего пула? Насколько я могу судить, BGL в настоящее время выполняет множество небольших распределений - я действительно хотел бы избежать этого по соображениям эффективности пространства и времени выполнения.

Код скопирован с здесь :

 template <class Allocator>
  struct list_with_allocatorS { };

  namespace boost {
    template <class Alloc, class ValueType>
    struct container_gen<list_with_allocatorS<Alloc>, ValueType>
    {
      typedef typename Alloc::template rebind<ValueType>::other Allocator;
      typedef std::list<ValueType, Allocator> type;
    };
  }

  // now you can define a graph using std::list 
  //   and a specific allocator  
  typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;

Answer 4

Поскольку BGL предназначен для взаимодействия с устаревшими или пользовательскими графиками , вам, вероятно, лучше написать свой собственный график.