Mein Leben mit Boost Graph Library

Der Artikel, dessen erster Teil hier vorgestellt wird, enthält verschiedene Überlegungen des Autors, die während der langen Entwicklung eines speziellen Systems zur Suche nach sozialen Verbindungen auf der Grundlage der Boost Graph Library (BGL) gesammelt wurden. Dieser (technische) Abschnitt fasst die Eindrücke des Autors von der Arbeit mit dieser Bibliothek zusammen, wirft Probleme bei der Instrumentierung beim Erstellen von Diagrammanwendungen auf und geht auf einige praktische Probleme der Metaprogrammierung in C ++ ein.

BGL und womit es gegessen wird

Die BGL-Vorlagenbibliothek ist wahrscheinlich jedem Entwickler bekannt, der auf Diagrammaufgaben gestoßen ist. Als sie im Jahr 2000 in Boost 1.18.1 auftrat, erhielt sie sofort die Zustimmung von Klassikern des Genres wie Alexander Stepanov. Der von Jeremy Sik, Lai-Kwan Lee und Andrew Lamsdane zusammengestellte Bibliotheksführer wurde 2006 von Peter in russischer Sprache veröffentlicht (Original - Jeremy G. Siek, Lie-Quan Lee und Andrew Lumsdaine, „The Boost Graph Library“, 2001 , Addison-Wesley). Die Bibliothek wurde fast bis Ende 2013 intensiv aktualisiert und weiterentwickelt (Boost 1.55.0). Insbesondere im Jahr 2005 erschien die Ankündigung der Distributed Version (PBGL), die seit Version 1.40 im Jahr 2009 in Boost enthalten ist und bis heute eine Art De-facto-Standard für die Grafikberechnung auf Hochleistungsclustern ist. in der akademischen Welt. Soweit die Geschichte der Commits beurteilt werden kann, war bis 2005 der Hauptentwickler der Bibliothek Jeremy Sik, nach 2005 - Douglas Gregor, und im Allgemeinen arbeiteten zu verschiedenen Zeiten eine beträchtliche Anzahl verschiedener Personen an der Bibliothek. Die dazugehörigen Veröffentlichungen sind wiederholt auf habr.com erschienen: Zunächst ist eine Reihe von Artikeln von Vadim Androsov zu beachten: [ 1 , 2 , 3 ]. Grundsätzlich ist der Bibliothek also gute und vielfältige Literatur gewidmet, aber ihre eigene Dokumentation, die im Allgemeinen auch recht umfangreich ist, leidet etwas unter der Tatsache, dass:

1. Das Inhaltsverzeichnis und die Stammabschnitte, die eine vollständige Liste der wichtigsten Entitäten enthalten sollen, haben sich seit 2001 nicht geändert. Zum Beispiel der Autor dieser Zeilen, der naiv glaubte, dass:

   Die BGL bietet derzeit zwei Diagrammklassen und einen Kantenlistenadapter:
   
   adjacency_list
   adjacency_matrix
   edge_list

   Nach einiger Zeit war ich überrascht, die 2005 implementierte Darstellung von compress_sparse_row_graph (Sparse Matrix) zu finden. Eine ähnliche Geschichte fand mit dem Bron-Kerbosch-Algorithmus statt. Glauben Sie dem Inhaltsverzeichnis nicht, verwenden Sie eine direkte Suche in den Header-Dateien;
   
2. Es ist keine einzige kommentierte Liste der internen Kategorien der Bibliothek (container_category, parallel_edge_traits, iterator_stability usw. usw.) erforderlich, um Ihre eigenen Ansichten zu implementieren. Probleme mit dem Verständnis des Geschehens überholen anscheinend alle Benutzer der Bibliothek, die tiefer graben möchten, was zum Auftreten einer „Art von Arbeitscode“ führt, der viel Zeit und Mühe erfordert, um ihn in einen vollständigen Zustand zu bringen: siehe zum Beispiel eine typische Diskussion .

Die Anzahl der Kategorien und verschiedener Selektoren, einschließlich derjenigen, die verwirrend ähnlich sind, ist so groß, dass die Autoren selbst manchmal verwirrt sind. In den Konstruktoren des oben bereits erwähnten komprimierten_sparse_row_graph tritt beispielsweise in der aktuellen Version ein systematischer Fehler auf, der zu Abstürzen führt, wenn versucht wird, eine ungerichtete Adjazenzliste zu kopieren:



Es kann hier gelegentlich angemerkt werden, dass das vollständige Testen eines solchen flexiblen Mechanismus ein separates Problem darstellt, da es mit einer kombinatorischen Explosion der Anzahl möglicher Substitutionen einhergeht.

Mit Bedauern ist anzumerken, dass die Hauptentwickler derzeit offenbar das Interesse an weiteren Arbeiten an der Bibliothek verloren haben und sie in den letzten sechs Jahren keineswegs ihr Entwicklungspotential ausgeschöpft und sich nicht einmal vollständig von internen Inkonsistenzen und direkten Fehlern befreit hat. Die in der Region 2011 geäußerten Pläne, das Methodenspektrum erheblich zu erweitern und neue Bereiche der Graphentheorie abzudecken (einschließlich des Hinzufügens interner Unterstützung für die Graphpartitionierung zur Fähigkeit, das METIS-Format zu lesen), blieben unerfüllt. Es scheint auch, dass die Bibliothek (zumindest in Bezug auf die Lesbarkeit) viel von der weit verbreiteten Verwendung neuer Produkte profitieren könnte, die nach 2011 zum Standard wurden.

Daher sind die Probleme bei der Auswahl einer Referenzbibliothek für Diagrammanwendungen ab 2019 nicht so klar, wie wir es uns wünschen, und in den letzten 5 Jahren hat die Unsicherheit eher zugenommen als abgenommen.

Diese Situation ist etwas traurig, da die Schaffung eines universellen Mechanismus, der BGL an sich ähnlich ist, eine Art intellektuelle Leistung ist, sowohl in Bezug auf die Kraft des Ansatzes als auch auf den Reichtum des Arsenals implementierter universeller Methoden (gut anderthalbhundert Single-Threaded und ein paar Dutzend verteilt). Die Bibliothek ist, soweit der Autor dieser Zeilen bekannt ist, immer noch nicht gleich.

Derzeit erlaubt nur diese Bibliothek grundsätzlich, ohne Leistungseinbußen, strenge Vereinbarungen über die Darstellung von Daten und den Verlust der Kontrolle über die internen Mechanismen der Bibliothek selbst zu treffen, um Graphalgorithmen und Graphendarstellungen vollständig zu trennen, wobei letztere zusätzlich völlig unabhängig von der Darstellung von Metadaten sind, die mit Kanten und Eckpunkten verbunden sind ( Dies ist im Prinzip offensichtlich die korrekteste Vorgehensweise.

Das Wort "grundlegend" wird hier aus einem bestimmten Grund verwendet. In Anbetracht einer bestimmten Situation am Beispiel der bereits oben erwähnten langlebigen Klasse compress_sparse_row_graph können wir beispielsweise die folgenden Abweichungen von hohen Standards feststellen:

1. Der Operator [] für die Adjazenzliste und die Sparse-Matrix behandeln die internen und externen Eigenschaften von Kanten unterschiedlich (interne und gebündelte Eigenschaften): Die erste gibt nur externe Eigenschaften zurück (auf die nur mit property_map zugegriffen werden kann), die zweite gibt eine Rahmenstruktur-Eigenschaft zurück, die eine gemeinsame Liste von Eigenschaften enthält.
2. Die Funktion get zum Abrufen des Kantenindex mithilfe von boost :: property_map <compress_sparse_row_graph, boost :: edge_index_t> :: type wurde in boost :: detail ausgeführt und nicht wie in allen anderen Fällen zum Boosten.

Schließlich blieb in der Vorlage compress_sparse_row_graph die Spezialisierung für das ungerichtete Diagramm (boost :: undirectedS) unerfüllt.

In dieser Hinsicht ergeben sich bei Verwendung der Eigenschaft edge_index (Kanten-Seriennummer) zusätzliche Schwierigkeiten, da diese Eigenschaft für die Adjazenzliste explizit als intern festgelegt werden muss und als solche willkürlich geändert werden kann, für einen ungerichteten Graphen jedoch ihr Wert nicht von der Richtung abhängt wo die Rippe geht. Bei einer dünn besetzten Matrix (immer gerichtet) handelt es sich um eine integrierte Konstante property_map einer speziellen Form (berechnet als Index in einem Array von Kanten). Dementsprechend können sich die Werte für entgegenkommende Kanten (die einen ungerichteten Graphen darstellen) nicht ändern und sind immer unterschiedlich.

All diese Diskrepanzen führen dazu, dass es unmöglich ist, beim Aufrufen algorithmischer Funktionen "einfach die Graphendarstellung durch eine äquivalente zu ersetzen", was den Hauptvorteil der Bibliothek erheblich untergräbt. In der Praxis ist in solchen Fällen entweder eine übermäßige Codespezialisierung erforderlich oder deren Verarbeitung, um Elemente mit unterschiedlichem Verhalten auszuschließen, oder eine solche Anpassung von Diagrammvorlagen, damit sie sich mit unterschiedlichen Attributdefinitionen „identisch“ verhalten, oder schließlich das Entfernen einzelner Dateien aus der Bibliothek und die Erstellung "Persönliche Boost-Version."

Zusätzlich können die folgenden, nicht so bedeutenden Unannehmlichkeiten festgestellt werden:

• Die Abmessungen der internen Deskriptoren von Diagrammdarstellungen haben einen erheblichen Einfluss auf den Speicherverbrauch, der zum Speichern des Diagramms erforderlich ist, und wirken sich manchmal auf die Leistung der Algorithmen aus.
  
  In einigen Ansichten (der gleiche komprimierte_sparse_row_graph) können Sie diese Dimensionen steuern. Andere (adjacency_list) haben keine solchen Parameter und verwenden immer 64-Bit-Ganzzahlen (normalerweise redundant), die nicht ersetzt werden können, ohne den Code zu ändern.
  
• Trotz der Tatsache, dass die Autoren der Bibliothek sehr, sehr viel vorsahen, wurden einige offensichtlich notwendige Grundelemente nicht in die Bibliothek aufgenommen. Zum Beispiel gibt es keine Funktion wie reverse_edge, die eine Kanteninversion durchführt.
  
  Die Implementierung solcher Funktionen hängt natürlich von der Diagrammdarstellung ab: In diesem Fall kann sie durch einen trivialen Austausch von Elementen eines Paares, eine mehr oder weniger effiziente Suche nach Containern oder überhaupt nicht implementiert werden. Für den Endbenutzer ist es schwierig, all diese Vielfalt von Optionen zu verstehen, zumal gemäß der Ideologie der Bibliothek die internen Mitglieder der Deskriptoren für ihn nicht von Interesse sein sollten.
  
• Ebenso fielen einige alles andere als wertlose Skripte aus der Bibliothek. Sie können beispielsweise Kantenprädikate definieren, die filtered_graph verwenden, um ein ungerichtetes Diagramm in ein gerichtetes Diagramm umzuwandeln. Es gibt jedoch keine Möglichkeit, die Bibliothek auf diese Transformation aufmerksam zu machen. Dementsprechend werden reguläre Algorithmen für gerichtete Graphen nicht mit einem solchen Objekt kompiliert, und Algorithmen für ungerichtete Graphen funktionieren nicht korrekt damit.
  
  Irgendwo in der Nachbarschaft gibt es das Thema der Unterstützung für technisch ungerichtete Diagramme, die an den Rändern eine Servicerichtungsmarkierung aufweisen. Eine erhöhte Aufmerksamkeit für diese Ansicht kann jedoch auf die besondere Art der Aufgaben zurückzuführen sein, die der Autor löst, und das weit verbreitete Interesse an der Unterstützung solcher Objekte ist nicht offensichtlich.
  
• Was die reverse_edge-Funktion betrifft, die oben als Beispiel genommen wurde, gibt es überhaupt keine unglaubliche Option, dass die gewünschte Funktion irgendwo im Darm der Bibliothek vorhanden ist, aber aus irgendeinem Grund einen nicht offensichtlichen Namen erhalten hat. Dies führt zu folgendem Problem, das auf den ersten Blick nicht schwerwiegend ist, aber die Arbeit mit komplexen Vorlagenbibliotheken erheblich verlangsamt (nicht nur BGL, obwohl es nach diesem Kriterium eindeutig zu den führenden gehört): Arbeiten mit umfangreichen Systemen implizit verwandter Funktionen ohne explizite Parametertypisierung und mit Die nicht offensichtliche Semantik der Verwendung (oft weniger transparent als durchdacht) ist physikalisch schwierig, und vorhandene Entwicklungsumgebungen bieten dem Entwickler keine Unterstützung dafür:
  
  
  
  In der Tat, automatische Assistenten:
  
  
  1. In erster Linie für die OOP-Unterstützung konzipiert, wenn eine Reihe von Funktionen entsprechend ihrem Typ an das Objekt auf der rechten Seite gebunden ist. Mit globalen Funktionen, die sich links von einem Typ befinden können (geschweige denn eine Reihe von Typen), helfen sie viel schlimmer, selbst wenn alle Typen bekannt sind.
  2. Sie sind lächerlich nicht einmal in der Lage, mit einfachen Vorlagen zu arbeiten. Die vom Autor verwendete Version des visuellen Assistenten, der die Definition einer Vorlagenklasse mit Standardparametern vor sich hat, bietet die Möglichkeit, eine „Testsubstitution“ anzugeben, um einen Hinweis für die Klasse generieren zu können. Wenn Sie sie treffen, passiert absolut nichts.
  3. Darüber hinaus sind sie weniger in der Lage, Metaprogramm-Qualifizierer zu verstehen, selbst die einfachsten wie enable_if.
  4. Über ein typisches Szenario: „Wir befinden uns in einer Vorlagenfunktion, die aus einer unbestimmten Anzahl unbestimmter Kettenlängen anderer Funktionen, einschließlich Vorlagenfunktionen, aufgerufen wird.“ Es ist unmöglich, ohne Tränen zu sprechen. In diesem Fall bleibt vim wirklich der beste Freund des Programmierers.
  
  Ein weiterer Aspekt derselben Situation kann anhand der ersten Zeile des in der vorherigen Abbildung gezeigten Codefragments veranschaulicht werden. Der Leser wird gebeten, die Abfragen "Aktuelle Zeit erhöhen" und "Aktuelle Zeit CRT" zu beantworten und die Ergebnisse zu vergleichen. Ja, boost :: date_time (jetzt teilweise auf std verschoben) ermöglicht es, viele komplexe Dinge korrekt auszuführen, während CRT es Ihnen ermöglicht, mehrere triviale Operationen falsch auszuführen, aber in alltäglichen Haushaltssituationen ist CRT unter allen Gesichtspunkten und polynomischen Gesichtspunkten bequemer Konstruktionen der Form posix_time :: second_clock :: local_time (ein sanftes Beispiel) neigen dazu, sich in Hieroglyphen zu verwandeln, die im Programm wandern. Wenn Sie dem Entwickler den Zugriff auf die persönliche Bibliothek solcher Hieroglyphen entziehen, wird die Entwicklungsgeschwindigkeit auf Null gesetzt .
  
  Boost :: string_algo macht es möglich, alles mit Strings zu tun, aber ehrlich gesagt wird jede nicht ganz triviale Operation von einer Sitzung zum erneuten Lesen der Dokumentation begleitet, um die allgemeine Logik der Bibliothek, die Namen der Prädikate sowie eine separate Übung zum Herausfinden der Kompatibilität von Parametern zu aktualisieren. Eine ähnliche Situation tritt bei Tokenisierungsoperationen in boost :: regexp auf, deren interne Logik fehlerfrei ist.
  
  Wenn eine solche Situation bei den am häufigsten verwendeten Bibliotheken auftritt, ist es nicht überraschend, dass BGL als spezialisiertere Bibliothek, in der beispielsweise make_property_map_function- und make_function_property_map-Funktionen vorhanden sind, die nicht miteinander in Beziehung stehen, sowie eine sakramentale Get-Funktion, die auf eine beliebige Funktion neu geladen wird Die Anzahl der Argumente jeglicher Art führt zu denselben Problemen, jedoch in hypertrophierter Form. Ja, jede Aufgabe kann durch die get-Aufrufkette gelöst werden, aber leider löst nicht jede get-Kette dieses Problem.
  
  Das Lesen eines solchen Codes kann einfach und angenehm sein, es kann sogar wie eine Zusammenfassung eines formal geschriebenen Algorithmus in einer natürlichen Sprache aussehen, aber beim Schreiben ist die Unmöglichkeit, Wörter durch Synonyme usw. zu ersetzen, für eine echte untypisch.
  
• Im Allgemeinen kann man die banale, aber nicht weniger zutreffende Beobachtung nicht verfehlen, dass die Metaprogrammierung in C ++ immer noch buchstäblich auf Nebenwirkungen von Sprachwerkzeugen basiert, deren ursprünglicher Zweck anders war, und sogar auf den einfachsten Ideen auf der Grundlage von Infolgedessen ist die Metasprache schwer auszudrücken und zu lesen, und die Verknüpfung des Vorlagencodes mit dem archaischen System der enthaltenen Dateien erleichtert dem Entwickler das Leben nicht und verringert nicht die vom Compiler verarbeitete Codemenge.
  
  (Auf der anderen Seite bringen regelmäßige Updates für Boost und Standard viele nicht ganz triviale und oft äußerst nützliche Konstrukte und unerwartete Lösungen mit sich, die es wirklich ermöglichen, klareren und kompakteren Code zu geringeren Kosten zu schreiben. Der Strom neuer Produkte ist jedoch so breit, ungleich und schlecht strukturiert, dass der wichtigste Ergänzungen zur Standardbibliothek, auch solche offensichtlichen wie die Optionen / apply_visitor oder die unten genannten, wenn die konzeptionellen Vorteile ihrer Anwendung im Kontext eines bestimmten Projekts nicht relevant sind Selbstverständlich können sie ohne die Hilfe eines glücklichen Ereignisses für lange Zeit unscharf werden, wenn Sie nicht einen erheblichen Teil der Arbeitszeit damit verbringen, neue Produkte direkt und nachdenklich zu verfolgen, nicht triviale Beispiele für ihre Verwendung zu studieren und mentale Versuche zu unternehmen, sie auf einen vorhandenen Code anzuwenden. um dieses Problem zu bewältigen - für jeweils fünf praktizierende C ++ - Programmierer ein C ++ - einen Theoretiker, der sich nur mit Fragen der Priorität neuer Produkte, ihrer Implementierung, beschäftigt gen im Projekt und die selektive Bildung Praktiker. Fazit: Starten Sie keine C ++ - Projekte mit weniger Entwicklern .
  
• Schließlich objektiv das schwerwiegendste Problem, das bei der Arbeit mit BGL-Boilerplate-Code auftritt . Angenommen, wir verwenden einen Vorlagenalgorithmus, der eine Passage durch ein Diagramm erstellt und eine Darstellung von Diagramm G als Argument verwendet. In einem typischen Fall hängt diese Darstellung von den Filtern ab, die den Eckpunkten und Kanten überlagert sind $$$F_v$, $$$F_e$und Gewichtsschema $$$W$. Um mit gefilterten Diagrammen arbeiten zu können, bietet BGL die oben erwähnte Vorlagenklasse filter_graph an. Die Art und Weise, wie das Gewichtsschema daran angehängt wird, liegt im Ermessen des Benutzers. Funktoren vertreten $$$F_v$, $$$F_e$und $$$W$kann mindestens die folgenden Ansichten enthalten:
  
  
  • Direkt ein Wrapper für eine Funktion, die ein Gewichtungsschema darstellt, und Prädikate, die Filter darstellen (langsam, ohne Initialisierungsverlust);
  • Caches über diese Wrapper, Zuordnen von Kanten- / Knoten-Deskriptoren zu Kanten- / Knoten-Indizes, Adressieren einer Bitmap und eines Array von Werten (ohne Initialisierungsverlust, mit einer allmählichen Erhöhung der Geschwindigkeit, wie verwendet);
  • Direkte Zuordnung von Knoten- / Kantendeskriptoren zu Arrays mit gefüllten Werten (erfordert eine Initialisierung, kann jedoch auf der Grundlage der vorherigen Darstellung erstellt werden; die Geschwindigkeit erreicht ihr Maximum).
  
  Wenn dieser Algorithmus in einem traditionellen Stil geschrieben würde, würden drei Selektoren mit jeweils mindestens drei Zweigen in seinem Körper erscheinen (und die Notwendigkeit, den Körper anzupassen, wenn neue Darstellungen erscheinen). Da jede Verzweigung im Hauptteil des Algorithmus, die beim Durchlaufen des Diagramms sehr oft ausgeführt wird, zu einem spürbaren Zeitverlust führt, kann der Wunsch, diese Verluste zu vermeiden und gleichzeitig den Code des gleichen traditionellen Stils beizubehalten, zu mehr als 27 Implementierungen des Algorithmus für verschiedene Kombinationen von Darstellungen führen.
  
  Der Metaprogrammstil sollte Sie vor diesen Problemen bewahren und es Ihnen ermöglichen, eine Metafunktion zu unterstützen, die den Algorithmus beschreibt, der implizit alle erforderlichen Implementierungen generiert (und möglicherweise auch einige und möglicherweise eine beträchtliche Menge an unnötigen Implementierungen, wenn die Laufzeitcodestrukturen de facto einige Typkombinationen nicht generieren). ), .
  
  , , inline- , –O2. - ( 1:3 1:5, – , , ).
  
  , . . , ( ) , «» «» . , . : «» «» , «» , «» .
  
  , : , 100% , , «» . ( , , - , , , , , ).
  
• , , , . C++ , -, , .
  
  , , :
  
  

  void type_selector_fun(type_a a, type_b b, ...) { if (condition_1(a, b, ...)) { auto arg = get_type_1_obj(a, b, ...); run_calc(arg, a, b, ...); } else if (condition_1(a, b, ...)) { auto arg = get_type_2_obj(a, b, ...); run_calc(arg, a, b, ...); } else ... } 

  
  Es kann mit der Variante <...> in etwa folgender Form etwas kompakter umgeschrieben werden:
  
  

    void type_selector_fun(type_a a, type_b b, ...) { variant<type_1, type_2, ...> arg; if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else if ... ... apply_visitor([&](auto arg_){run_calc(arg_, a, b, ...); }, arg); } 

  
  Der Nachteil dieser Schreibweise ist die Notwendigkeit einer expliziten Aufzählung der Typen Typ_1, Typ_2, ... in der Variantendeklaration. Diese Typen können umständlich sein, die Aufzeichnung mit declval / result_of_t kann nicht weniger umständlich sein.
  
  Wenn Sie any verwenden, müssen Sie keine Typen auflisten, aber es gibt keine Möglichkeit, einen analogen apply_visitor zu erhalten.
  
  Die Verwendung einer Vorlagenfunktion make_variant, mit der Sie Code des folgenden Typs schreiben können, bietet sich an:
  
  

    auto arg = make_variant ( bind(condition_1, a, b, ...), bind(get_type_1_obj, a, b, ...), bind(condition_2, a, b, ...), bind(get_type_2_obj, a, b, ...), ... ); 

  
  Aber die Heilung sieht nicht besser aus als die Krankheit.
  
  Im Allgemeinen gibt es eine typische Situation für die Metaprogrammierung in C ++, wenn Sie zum Ausdrücken einer sehr einfachen Idee ein ganzes Arsenal von Hilfswerkzeugen verwenden müssen, deren Ergebnis hinsichtlich Lesbarkeit und einfacher Aufzeichnung nicht sehr zufriedenstellend ist. Im Wesentlichen möchte ich in der Lage sein, Folgendes zu schreiben:
  
  

    //   variant<...>      //  ,   : type_1, type_2 etc. variant<auto...> get_type_obj(typa_a a, type_b b, ...) { if (condition_1(a, b, ...)) { return get_type_1_obj(a, b, ...); } else if (condition_2(a, b, ...)) { return get_type_2_obj(a, b, ...); } else ... } 

  
  oder sogar:
  
  

    select_value_type(arg) { if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else ... ... } run_calc(arg, a, b, …); 

  
  Die letztere Option sieht am praktischsten aus, obwohl sie vollständig aus dem C ++ - Stil entfernt wurde, da es mehr als eine Argumentvariable geben kann, für die der Typ ausgewählt ist, und es keinen Grund gibt, die Logik ihrer Konstruktion vorwegzunehmen .
  
• Die Kehrseite derselben Situation ist die Verwendung von Hilfsstrukturen (z. B. Caching), die ein Skript implementieren, das den Namen einer "Vorlagenvariablen" verdient, sich jedoch von der gleichnamigen C ++ 14-Standarderweiterung unterscheidet.
  
  Der entsprechende Code könnte ungefähr so ​​aussehen:
  
  

    struct CacheHolder { boost::variant< container<T1>, container<T2>, // ... container<TN>> ct; template<typename T> struct result_type_selector { typedef typename if_c<is_compatible<T, T1>::value, T1, if_c<is_compatible<T, T2>::value, T2, // ... if_c<is_compatible<T, TN>::value, TN, std::decay_t<T>>>>::type type; }; template<typename T> auto get() const -> const container<typename result_type_selector<T>::type>& { return boost::get<container<typename result_type_selector<T>::type>>(ct); } }; 

  
  Wie oben drücken lange Konstruktionen die einfache Idee aus, auf eine Variable zuzugreifen, die den Cache unter einem bestimmten Namen darstellt, unabhängig von der Dimension des zwischengespeicherten Werts (transparenter Durchlauf des aufrufenden Codes).
  
  Der Kürze halber wird der Code für den Fall angegeben, dass nur ein Typ aktiv sein kann. In der Praxis ist die Situation jedoch häufiger, wenn mehrere Container gleichzeitig vorhanden sein können (er kann einfach mit Tupel und optional im selben Stil implementiert werden).
  
  Bei der Implementierung der Funktion get <...> wird davon ausgegangen, dass der aufrufende Code eine Vorstellung davon hat, auf welche Art von zwischengespeicherten Werten er zugreifen möchte (z. B. Ganzzahl oder Gleitkomma).
  
  Nicht weniger häufig ist die Situation, in der der genaue Typwert für den Anrufer nicht wichtig ist. In diesem Fall wird das Skript select_value_type / apply_visitor aus dem vorherigen Absatz reproduziert (angepasst an die mögliche Vielzahl von Werten, was bedeutet, dass Typen in absteigender Reihenfolge der Priorität angezeigt werden).
  
• Bisher wurde PBGL in diesem Text praktisch nicht erwähnt. Dies erklärt sich aus der verschwindend geringen Erfahrung des Autors mit der Arbeit mit diesem Teil der Bibliothek (in Verbindung damit bezieht sich der Autor selbst mit einer gewissen Skepsis auf alles, was unten in diesem Absatz geschrieben steht, und ruft andere dazu auf). Tatsächlich läuft ein solches Experiment auf mehrere Experimente mit derselben Art von Suchproblemen hinaus, bei denen gezeigt wurde, dass praktische Daten eine verteilte Version 3-5 Mal im Speicher und 15-20 Mal in der Gesamtleistung an eine lokale Lösung verloren haben (der Ursprung dieser erschreckenden Zahl wird hier erklärt und in den folgenden Absätzen zusätzlich kommentiert). . Angesichts der größeren Komplexität der Arbeit mit verteilten Strukturen war die Wahl der lokalen Version in einer solchen Situation selbstverständlich.
  
  Lassen Sie uns die Mechanik des PBGL-Betriebs anhand eines typischen Beispiels des Delta-Walking-Algorithmus erklären. In dieser parallelen Version des Dijkstra-Algorithmus wird die Prioritätswarteschlange durch ein Array von "Buckets" ersetzt. Elemente, die in einen "Bucket" fallen, werden parallel verarbeitet. In seiner ursprünglichen Form ist die Delta-Stimulation ein typischer Algorithmus für Shared-Memory-Systeme.
  
  In der verteilten Version geschieht Folgendes: In PBGL wird der Graph beim Laden auf die Prozesse verteilt, und jeder Prozess verfügt über einen kontinuierlichen Bereich von Scheitelpunktnummern. Anhand der globalen Scheitelpunktnummer ist es daher leicht zu erkennen, zu welchem ​​Prozess sie gehört. Dementsprechend speichert jeder Prozess bei jeder Umdrehung des Algorithmus einen Teil des "Buckets", der die zu diesem Prozess gehörenden Eckpunkte enthält. Alle Prozesse wählen gleichzeitig die Scheitelpunkte aus ihren Teilen der "Buckets" nacheinander aus und verarbeiten sie, während sie Nachrichten über die Notwendigkeit senden, die folgenden "Buckets" an Prozesse zu aktualisieren, die benachbarte Scheitelpunkte besitzen. Es ist leicht zu erkennen, dass ceteris paribus eine Zunahme der Anzahl der Prozesse zu einer Zunahme der Anzahl der von ihnen gesendeten Nachrichten führt. Infolgedessen kann die Ausführungszeit des Algorithmus nicht nur nicht verringert, sondern sogar erhöht werden. Insbesondere der Start mehrerer MPI-Prozesse zur Lösung dieses Problems auf einer physischen Maschine mit einer bestimmten Wahrscheinlichkeit führt nur zu einer Erhöhung der Gesamtprozessorlast ohne Zeitgewinn.
  
  Es ist zu beachten, dass die Delta-Stimulation der am schnellsten verteilte Suchalgorithmus ist (von drei von der Bibliothek unterstützten).
  
  Wenn das Diagramm zuvor nicht erstellt wurde, sollte es in Blöcke maximaler Größe unterteilt werden, einen Block pro physischer Maschine. Mit vorläufiger Vorbereitung meinen wir hier die Umnummerierung der Eckpunkte des Graphen, so dass die von PBGL verwendeten kontinuierlichen Zahlenbereiche, wenn möglich, lose verbundenen Untergraphen entsprechen. Für diese Zwecke werden Pakete wie METIS, paraMETIS und Zoltan verwendet. Das Arbeiten mit dynamischen Diagrammen in diesem Modus ist schwierig.
  
  Nach den Ergebnissen der beschriebenen Experimente hatte der Autor im Allgemeinen den Eindruck, dass ein normaler Betrieb des PBGL-Clusters nur mit speziellen Kommunikationsgeräten möglich ist, und es ist sinnvoll, Maschinen mit einer minimalen Anzahl von Kernen und maximaler Thread-Leistung als Knoten eines solchen Clusters zu verwenden. Die Autoren von Trinity argumentieren in ihrem Artikel, dass ihr verteilter Speicher viel effizienter arbeitet - der Autor findet es schwierig, diese Aussage zu kommentieren, aber unter den oben genannten Umständen ist dies durchaus möglich: Die PBGL-Architektur trägt ein deutliches Siegel der Zeit, in der Mehrkernmaschinen noch keine breite Verbreitung erhalten haben.
  
  PBGL teilt auch die Probleme der Single-Threaded-Version: einige Codesynchronisierungen, Dokumentationen und Beispiele, die durch die größere Komplexität des Systems und weniger Benutzer, die bereit sind, nützliche Erfahrungen auszutauschen, noch verstärkt werden.
  

BGL und andere Tiere

Angesichts einer ziemlich langen Liste spezifischer Beschwerden ist es nicht unangemessen zu fragen: Kann der Autor BGL für neue Projekte im Jahr 2019 empfehlen? Die Antwort lautet: Der Autor glaubt, dass Bibliotheken dieses Stils und darauf basierende Anwendungen eine Zukunft haben müssen . Bei der Auswahl einer Referenzbibliothek für ein bestimmtes Projekt sollten wir die Instrumentierung ernsthaft in Betracht ziehen und die oben aufgeführten Probleme nicht aus den Augen verlieren. Die Antwort hängt natürlich von vielen Umständen ab, einschließlich, aber nicht beschränkt auf die in den folgenden Absätzen aufgeführten:

• Ob die Arbeit mit Diagrammen in einem Projekt die Grundlage für die Funktionalität oder eine optionale Aufgabe ist;
• Kann ein Projekt durch die Verwendung mehrerer Darstellungen einen Vorteil erzielen oder reicht die Arbeit mit hart typisierten Algorithmen völlig aus?
• Die vorteilhafteste Art der Parallelität für das Projekt;
• Organisatorische Nuancen: der Wunsch nach Metaprogrammierung in C ++ bei Mitarbeitern (insbesondere Mathematikprogrammierern) usw.

Wahrscheinlich, ceteris paribus, kann die Verwendung von BGL entweder im Fall einer sehr kleinen einmaligen Verwendung (zum Extrudieren oder Kopieren eines funktionierenden Codes und zum Vergessen) oder für ein großes System gerechtfertigt sein, für das eine erhöhte Flexibilität für hohe Eintritts- und andere Kosten im Laufe der Zeit bezahlt. In anderen Fällen ist es sinnvoll, andere Optionen sorgfältig zu prüfen.

Die Liste der möglichen Alternativen enthält mindestens die folgenden Elemente :

Von besonderem allgemeinem Interesse ist die Frage der Klassifizierung verschiedener Softwareprodukte, die auf die Arbeit mit Grafiken ausgerichtet sind. Ihre Vielfalt, ganz zu schweigen von der Anzahl, ist sehr groß. Ohne vorzugeben, die Klassifizierung vollständig (und sogar formal korrekt) zu sein, können wir jedoch versuchen, die folgenden wichtigen Bereiche bei der Entwicklung von Diagrammanwendungen hervorzuheben:

1. Graph DBMS (neo4j usw.).
   
   Systeme dieser Art konzentrieren sich auf die Durchführung von Transaktionsoperationen an großen (verteilten Platten-) Graphen. Obwohl die API eines solchen Systems hoch entwickelt sein kann, ist die Geschwindigkeit der Ausführung der Graphalgorithmen selbst, soweit man beurteilen kann, nicht die erste Priorität. Das System versucht möglicherweise nicht einmal, das gesamte Diagramm in den Speicher zu laden. Für die Änderung und Durchquerung von Graphen werden deklarative Sprachen (SPARQL, Cypher, Gremlin) unterstützt. Der Gewährleistung der Kontinuität mit herkömmlichen SQL-Systemen wird große Bedeutung beigemessen.
2. Grafikerweiterungen von Big-Data-Verarbeitungssystemen, die im Map / Reduce-Paradigma (GraphX ​​in Spark, Pegasus und Giraph für Hadoop) und unabhängigen Clustersystemen ( MS Trinity / MS Graph Engine , GraphLab) arbeiten. Die ersten, die Operationen an der Grafik ausführen, implementieren das Google Pregel- Modell (aber nicht nur es) und können für die Verwendung einschließlich massiver paralleler Rechenknoten konfiguriert werden. Sowohl diese als auch andere können unter anderem als Grundlage für Unternehmenssoftwareprojekte verwendet werden.
   
   Obwohl die API solcher Systeme durchaus entwickelt werden kann (unter anderem unterstützt GraphX ​​SPARQL und Cypher), liegt der Schwerpunkt bei der Arbeit mit ihnen auf der Lösung von Infrastrukturproblemen. GraphX ​​zeichnet sich durch Datenveränderlichkeit und eine Verzerrung im Pipelining aller Operationen aus. MS Trinity enthält derzeit keine übergeordneten Methoden und bietet nur eine Reihe von Grundelementen für die Arbeit mit Knoten und Kanten. Systeme, die auf Hadoop laufen, sind im Prinzip wenig nützlich, um beliebige Graphprobleme zu lösen.
   
3. Tatsächlich universelle Werkzeugbibliotheken, die mehr oder weniger breite Methodensätze (BGL / PBGL, LEMON usw.) implementieren, einschließlich massiv paralleler (nvGraph, Gunrock).
   
   Darauf aufbauend können Anwendungssysteme erstellt werden, die Graphalgorithmen an bestimmte Themenbereiche anpassen.
4. Systeme und Bibliotheken, die sich auf besonders komplexe Probleme von universeller Bedeutung spezialisiert haben (METIS, paraMETIS, Zoltran: Graphpartitionierung, GraphViz, Gephi: Visualisierung, GraphBLAS: algebraische Algorithmen für die Arbeit mit Graphen usw.).
   
   Viele unabhängige Grafikanwendungen können dieser Kategorie unter bestimmten Bedingungen zugeordnet werden, deren detaillierte Analyse zu viel Zeit in Anspruch nehmen würde. Letzteres enthält Anwendungen aller denkbaren Arten: akademische und kommerzielle, Einzel- und Mehrbenutzeranwendungen, die vor kurzem erschienen sind und seit mehr als einem Jahrzehnt existieren usw.

Ein dunkler, aber bedeutender Teil der Grafikanwendungen konzentriert sich auf die Aufgaben der Netzwerkanalyse und bereits der Analyse sozialer Netzwerke (Community Detection). Seltsamerweise sind Link-Analyse-Systeme (die in der Regel von verschiedenen "Verbrechensbekämpfern" verwendet werden), die einige Ähnlichkeiten mit dem von uns entwickelten System aufweisen, viel seltener. In allen Fällen ist es ohne eine spezielle Prüfung schwierig, die Art der von verschiedenen Systemen verwendeten Datenmodelle und die damit verbundenen Leistungsbeschränkungen, unterstützten Volumes, Betriebsgruppen usw. zu bestimmen.

Anmerkungen

1. BGL ist keine reine Header-Bibliothek, aber im Moment muss nur mit GraphViz DOT-Dateien (eher optional) verknüpft werden. Daher ist in den allermeisten Fällen keine Verknüpfung und automatische Verknüpfung mit der richtigen Version des Libbost-Diagramms erforderlich, um BGL-Header in die Boost-Konfiguration aufzunehmen. Aus Gründen der Konsistenz mit der libboost-regex-Bibliothek, die von BGL-Funktionen ohne Header verwendet wird, ist es daher zweckmäßig, den Header boost \ regex.hpp einfach aus dem Projektcode einzufügen, auch wenn dieser keine regulären Ausdrücke verwendet.
2. Zusätzliches Chaos entsteht durch die Anwesenheit von Wesenheiten, deren offensichtliche Gleichwertigkeit die Suche nach (möglicherweise abwesenden) schwarzen Katzen in dunklen Räumen fördert .
3. Bevor wir mit seiner Beschreibung fortfahren (anhand eines bestimmten Beispiels, in dem es sich besonders stark und unangenehm manifestierte), stellen wir fest, dass der Autor zu den relativ wenigen glücklichen Menschen gehört, die mit einem geladenen Projekt in einem leistungsstarken Windows-Betriebssystem und der von Gott gespeicherten Reihe von MSVC-Compilern arbeiten. Es ist möglich, dass die unten beschriebenen Probleme Artefakte dieser Compilerreihe sind: Eine Vielzahl besonderer Umstände erschwert die Durchführung eines Vergleichsexperiments mit gcc / clang in einer * nix-Umgebung. In diesem Fall können Sie nur Benutzern anderer Compiler gratulieren.
4. Um zu mildern, was in einigen Fällen das kürzlich erschienene constexpr if wahrscheinlich helfen wird.
5. In unserem Fall führte dies zu einer besonderen Aufmerksamkeit für die Zustandsersparfunktion, die ein bequemes Debuggen ermöglicht und das System zunächst in einer optimierten Baugruppe in den gewünschten Ausgangszustand versetzt.
6. In meiner Praxis bestand aus verschiedenen Gründen die Notwendigkeit, Laufzeitparameter in Vorlagenargumente umzuwandeln, und ich musste ziemlich oft auf sehr genaue, sehr ausgefeilte Methoden zurückgreifen (inspiriert von den jetzt veralteten Implementierungen von Boost Typeof und Boost Lambda für C ++ 98, die direkt auf die Behandeln Sie die Programmiertechnik in C ++ als eine Lösung für den Rebus, unter der der Stern die Auswahl des Arguments durch Teilen in zwei Hälften beleuchtet. Im Allgemeinen waren die Hauptprobleme bei solchen Operationen jedoch immer mit der Unfähigkeit zum Export verbunden ausgewählter Typ außerhalb des Anwendungsbereichs, der zu exotischen Mustern führte.
7. Der oben angegebene zwanzigfache Geschwindigkeitsverlust (in absoluten Zahlen - etwa 80 Sekunden gegenüber 4 in einem Testrichtungsdiagramm mit 50 Millionen Eckpunkten und 200 Millionen Kanten, die als Adjazenzliste dargestellt sind) wurde in einem unvorbereiteten (zufällig unterbrochenen) Diagramm im Vergleich zur lokalen Version erhalten - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].