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

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

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

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

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

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

Sören

c++ boost graph memory boost-graph
person BuschnicK    schedule 01.09.2009    source источник
comment
Возможно, это не тот ответ, который вам нравится, но когда дело доходит до подсчета байтов в качестве подготовки к некоторому взлому в какой-либо библиотеке Boost, которая используется только для очень немногих задач, вы получите лучший ответ раньше в списке рассылки пользователей Boost ‹ lists.boost.org/mailman/listinfo.cgi/boost-users›. Другая возможность - прочитать источник...   -  person gimpf    schedule 09.09.2009

Ответы (4)


arrow_upward
8
arrow_downward

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

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

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

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

person BuschnicK    schedule 15.09.2009

arrow_upward
1
arrow_downward

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

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

  3. ???

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

person Mike Burrows    schedule 14.09.2009
comment
Да, я пробовал сжимать по размеру (предложение № 2), но это не очень помогло. Мы также используем серверные части базы данных и в настоящее время поддерживаем mySQL, postgreSQL и SQLite. Однако наши шаблоны доступа для этих конкретных алгоритмов действительно требуют специализированной структуры данных в памяти. - person BuschnicK; 15.09.2009

arrow_upward
0
arrow_downward

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

person me22    schedule 09.09.2009

arrow_upward
0
arrow_downward

В качестве ответа на:

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;
person Lior Kogan    schedule 04.02.2014