zmniejszanie wymagań dotyczących pamięci dla listy rozgraniczeń

Question

Używam obszernej listy adjacency_list < vecS, vecS, bidirectionalS ...> . Mam tyle wykresów załadowanych jednocześnie, że pamięć staje się problemem. Robię statyczną analizę programu i przechowuje kalibrację i wykresy przepływu zdemontowanego pliku binarnego na wykresach doładowania. Dzięki temu mogę mieć kilka tysięcy funkcji == grafy przepływów i jeden gigantyczny callgraph . Naprawdę chciałbym zmniejszyć zużycie pamięci dla moich wykresów , nadal korzystając z BGL.

Ponieważ moje wykresy są statyczne po załadowaniu, a liczba krawędzi i wierzchołków jest znana wcześniej, widzę ogromny potencjał optymalizacji. Dla przykładu, chciałbym przydzielić pojedynczy bufor dla wszystkich wierzchołków/krawędzi pojedynczego wykresu i pozwolić, aby wykres właśnie zapisywał indeksy do tego bufora.

więcej pytań:
1) jaki jest koszt pamięci związany z używaniem właściwości wierzchołków i krawędzi? I ma ich sporo.
2) Czy można przekonać BGL, aby użył obkurczenia w celu dopasowania do idiomu ? Jak rozumiem, listy przylegania używają funkcji push_back, aby dodać krawędzie . Czy można zmniejszyć zużycie pamięci, zamieniając wektor wynikowy na kopię samego siebie? Może kopiując cały wykres ?
3) Czy możliwe jest użycie podzielników puli boost z BGL? Jak na razie , ponieważ mogę powiedzieć, że BGL obecnie wykonuje wiele małych alokacji - Naprawdę chciałbym tego uniknąć ze względów związanych z wydajnością przestrzeni i wydajności.

Czy ktoś już zbudował wersję BGL zoptymalizowaną pod kątem użycia pamięci? Czy powinienem spróbować użyć istniejących struktur wykresów i rozszerzyć je o niestandardowych alokatorów lub somesuch, czy jest to bardziej owocne, aby napisać własną implementację i starać się zachować zgodność interfejsu z BGL, aby móc nadal używać jego algorytmów?

pozdrawiam,

Sören 

Answer 1

Istnieje mało znany typ wykresu o nazwie "wykres skompresowanego rzadkiego wiersza" w BGL. Wydaje się być całkiem nowy i nie jest powiązany ze stronami indeksowymi. Wykorzystuje jednak piękny mały trik, aby przedstawić wykres tak mały, jak to tylko możliwe. http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

Używając tego dla niektórych z naszych wykresów, udało mi się już zmniejszyć zużycie pamięci o 20% - więc jest to naprawdę bardzo opłacalna optymalizacja.

Przechowuje również właściwości wierzchołków/krawędzi w wektorach, co daje również najmniejszy możliwy narzut.

Należy pamiętać, że wysyłka w wersji z najnowszym doładowaniem 1.40 obsługuje tylko wykresy kierunkowe (w przeciwieństwie do dwukierunkowych). Jeśli chcesz móc efektywnie wykonywać iteracje nad krawędziami i krawędziami w pionie (tak jak ja), musisz sprawdzić bagażnik dodatkowy z subversion. Jeremiasz był bardzo pomocny w dodaniu tej funkcji na moją prośbę.

Answer 2

Od BGL jest przeznaczony do interoperate with legacy or custom graphs, jesteś prawdopodobnie najlepiej wyłączyć pisanie własnego wykres.

Answer 3

1. Koszty ogólne zależą od używanej wersji i od tego, czy chodzi o właściwości "powiązane", czy nie. Użyłem tylko właściwości pakietu i przeczytanie kodu, którego oczekiwałbym, że każdy pakiet właściwości kosztuje 2 wskaźniki + rozmiar typu pakietu, którego używasz + rozmiar każdej z dołączonych właściwości. Żadna z rzeczy sprawdzających koncepcję nie została w binarnym afaik. Skoro masz już kod, dlaczego nie mierzyć kosztu? Jeśli nie masz żadnych narzędzi, które mogłyby pomóc w generowaniu wykresów o znanych rozmiarach w buforach znanych rozmiarów. W końcu coś się nie powiedzie iw tym momencie powinieneś się liczyć.

2. Czy próbowałeś dzwonić pod numer adjacency_list<blah>.swap(adjacency_list& x)? Mam nadzieję, że odpowiednio zmniejszyłoby to pojemniki.

3. ???

zacząłem pisać coś takiego systemu opisujesz, ale ostatecznie zrezygnował na BGL i włączony do kodowania własnych algorytmów do uruchomienia na bazie sqlite wszystkich symboli łącznikowych.

Answer 4

W odpowiedzi na:

3) Czy jest możliwe aby użyć podzielników basen doładowania z BGL? O ile mogę powiedzieć, że BGL obecnie wykonuje wiele niewielkich alokacji - naprawdę chciałbym tego uniknąć ze względów związanych z wydajnością przestrzeni i wydajności.

kod skopiowany z here:

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;