Ma vie avec Boost Graph Library

L'article, dont la première partie est présentée ici, contient diverses considérations de l'auteur, accumulées au cours du long développement d'un système spécialisé de recherche de connexions sociales, basé sur la Boost Graph Library (BGL). Cette section (technique) résume les impressions de l'auteur sur l'utilisation de cette bibliothèque, soulève des problèmes d'instrumentation lors de la création d'applications graphiques et aborde certains problèmes pratiques de métaprogrammation en C ++.

BGL et ce avec quoi il est mangé

La bibliothèque de modèles BGL est probablement connue de tout développeur ayant rencontré des tâches graphiques. Apparue dans Boost 1.18.1 en 2000, elle a immédiatement gagné des critiques d'approbation de classiques du genre comme Alexander Stepanov. Le guide de la bibliothèque, compilé par Jeremy Sik, Lai-Kwan Lee et Andrew Lamsdane, a été publié en russe en 2006 par Peter (original - Jeremy G. Siek, Lie-Quan Lee et Andrew Lumsdaine, «The Boost Graph Library», 2001 , Addison-Wesley). La bibliothèque a été intensivement mise à jour et développée presque jusqu'à la fin de 2013 (Boost 1.55.0). En particulier, en 2005, l'annonce de sa version distribuée (PBGL) est apparue, qui a été incluse dans Boost à partir de la version 1.40 en 2009 et reste à ce jour une sorte de standard de facto pour le calcul graphique sur des clusters haute performance, en tout cas, dans le monde académique. Pour autant que l'histoire des commits puisse être jugée, jusqu'en 2005, le principal développeur de la bibliothèque était Jeremy Sik, après 2005 - Douglas Gregor, et en général à divers moments, un nombre considérable de personnes diverses ont travaillé sur la bibliothèque. Les publications qui lui sont consacrées sont apparues à plusieurs reprises sur habr.com: tout d'abord, une série d'articles de Vadim Androsov est à noter: [ 1 , 2 , 3 ]. Ainsi, en principe, une littérature bonne et diversifiée est consacrée à la bibliothèque, mais sa propre documentation, également, d'une manière générale, assez étendue, souffre quelque peu du fait que:

1. Sa table des matières et ses sections racine, qui prétendent fournir une liste exhaustive des entités clés, n'ont pas changé depuis 2001. Par exemple, l'auteur de ces lignes, qui croyait naïvement que:

   Le BGL fournit actuellement deux classes de graphiques et un adaptateur de liste de bords:
   
   liste_adjacence
   adjacency_matrix
   edge_list

   , après un certain temps, j'ai été surpris de trouver la représentation compressée_sparse_row_graph (matrice creuse) implémentée en 2005. Une histoire similaire a eu lieu avec l'algorithme de Bron-Kerbosch. Ne croyez pas la table des matières, utilisez une recherche directe dans les fichiers d'en-tête;
   
2. Il n’existe pas de liste unique commentée des catégories internes de la bibliothèque (container_category, parallel_edge_traits, iterator_stability, etc., etc.) nécessaires pour implémenter vos propres vues. Des problèmes de compréhension de ce qui se passe dépassent, apparemment, tous les utilisateurs de la bibliothèque qui veulent creuser plus profondément, ce qui conduit à l'apparition d'un `` type de code de travail '', ce qui prend beaucoup de temps et d'efforts pour l'amener à un état complet: voir, par exemple, une discussion typique .

Le nombre de catégories et de sélecteurs divers, y compris ceux qui prêtent à confusion, est si grand que les auteurs eux-mêmes s'y trompent parfois. Par exemple, dans les constructeurs du comprimé_sparse_row_graph déjà mentionnés ci-dessus, dans la version actuelle, il y a une erreur systématique entraînant des plantages lors de la tentative de copie d'une liste d'adjacence non dirigée:



Il peut être noté ici à l'occasion que le test complet d'un tel mécanisme flexible est un problème distinct, car il s'accompagne d'une explosion combinatoire du nombre de substitutions possibles.

Il convient de noter avec regret qu'à l'heure actuelle, les principaux développeurs ont apparemment perdu tout intérêt à poursuivre les travaux sur la bibliothèque et qu'au cours des six dernières années, elle n'a nullement épuisé son potentiel de développement et ne s'est même pas complètement libérée des incohérences internes et des erreurs directes, en vol libre. Les plans exprimés dans la région de 2011 pour étendre considérablement l'ensemble des méthodes et couvrir de nouveaux domaines de la théorie des graphes (y compris en ajoutant un support de partitionnement de graphes interne à la capacité de lire le format METIS) sont restés sans suite. Il semble également que la bibliothèque pourrait bénéficier beaucoup (au moins en termes de lisibilité) de l'utilisation généralisée de nouveaux produits qui sont devenus la norme après 2011.

Ainsi, les problèmes liés au choix d'une bibliothèque de référence pour les applications graphiques lors de la recherche à partir de 2019 ne semblent pas aussi clairs que nous le souhaiterions, et au cours des 5 dernières années, l'incertitude a augmenté plutôt que diminué.

Cette situation provoque une certaine tristesse, car la création d'un mécanisme universel similaire à BGL, en soi, est une sorte d'exploit intellectuel, à la fois en termes de puissance de l'approche et de richesse de l'arsenal de méthodes universelles mises en œuvre (une bonne cent et une centaine de threads simples et quelques dizaines distribués) la bibliothèque, pour autant que l'auteur de ces lignes soit connu, n'a toujours pas d'égal.

À l'heure actuelle, seule cette bibliothèque permet, en principe, sans perte de performances, d'imposer des accords stricts sur la présentation des données et la perte de contrôle sur les mécanismes internes de la bibliothèque elle-même, de séparer complètement les algorithmes de graphes et les représentations graphiques, ce qui rend ces dernières complètement indépendantes des métadonnées associées aux arêtes et sommets ( qui, en principe, est évidemment la manière la plus correcte de faire les choses).

Le mot «fondamentalement» est utilisé ici pour une raison. En considérant une situation spécifique en utilisant l'exemple de la classe compressée_sparse_row_graph de longue durée déjà mentionnée ci-dessus, nous pouvons noter, par exemple, les écarts suivants par rapport aux normes élevées:

1. L'opérateur [] pour la liste d'adjacence et la matrice clairsemée gèrent différemment les propriétés internes et externes des arêtes (propriétés internes et groupées): la première ne renvoie que des propriétés externes (les internes ne sont accessibles qu'avec property_map), la seconde renvoie une propriété de structure de trame contenant une liste commune de propriétés.
2. La fonction get pour obtenir l'index de bord à l'aide de boost :: property_map <compress_sparse_row_graph, boost :: edge_index_t> :: type est tombée dans boost :: detail, et non dans boost, comme dans tous les autres cas.

Enfin, dans le modèle compress_sparse_row_graph, la spécialisation du graphe non orienté (boost :: undirectedS) est restée non satisfaite.

À cet égard, lors de l'utilisation de la propriété edge_index (numéro de série de bord), des difficultés supplémentaires se posent du fait que pour la liste d'adjacence, cette propriété doit être explicitement définie comme interne et en tant que telle peut être modifiée arbitrairement, mais pour un graphique non orienté, sa valeur ne dépend pas de la direction où passe la côte. Pour une matrice clairsemée (toujours directionnelle), il s'agit d'une propriété_map constante intégrée d'une forme spéciale (calculée comme un index dans un tableau d'arêtes). Par conséquent, les valeurs des bords venant en sens inverse (représentant un graphique non orienté) ne peuvent pas changer et seront toujours différentes.

Toutes ces divergences conduisent à l'impossibilité de "simplement remplacer la représentation graphique par une représentation équivalente" lors de l'appel de fonctions algorithmiques, ce qui mine considérablement le principal avantage de la bibliothèque. Dans la pratique, dans de tels cas, soit une spécialisation excessive du code est requise, soit son traitement pour exclure des éléments avec des comportements différents, ou un tel ajustement des modèles de graphique afin qu'ils «se comportent de manière identique» avec différentes définitions d'attributs, ou, enfin, la suppression de fichiers individuels de la bibliothèque et la création "Version boost personnelle."

De plus, les inconvénients suivants, moins importants, peuvent être notés:

• Les dimensions des descripteurs internes des représentations graphiques ont un impact significatif sur la consommation de mémoire nécessaire pour stocker le graphique, et affectent parfois les performances des algorithmes.
  
  Certaines vues (le même comprimé_sparse_row_graph) vous permettent de contrôler ces dimensions. D'autres (adjacency_list) n'ont pas de tels paramètres et utilisent toujours des entiers 64 bits (généralement redondants), qui ne peuvent pas être remplacés sans modifier le code;
  
• Malgré le fait que les auteurs de la bibliothèque aient prévu très, très bien, certaines primitives manifestement nécessaires n'étaient pas incluses dans la bibliothèque. Par exemple, il n'y a aucune fonction comme reverse_edge qui effectue une inversion de bord.
  
  L'implémentation de telles fonctions dépend bien entendu de la représentation graphique: dans ce cas, elle peut être implémentée par un échange trivial d'éléments d'une paire, une recherche plus ou moins efficace par conteneur, ou pas du tout. Il est difficile pour l'utilisateur final de comprendre toute cette variété d'options, d'autant plus que, selon l'idéologie de la bibliothèque, les membres internes des descripteurs ne devraient pas l'intéresser.
  
• De même, certains scripts, loin d'être sans valeur, sont tombés de la bibliothèque. Par exemple, vous pouvez définir des prédicats d'arête qui utilisent filter_graph pour transformer un graphe non orienté en graphe orienté, mais il n'y a aucun moyen de porter cette transformation à l'attention de la bibliothèque. Par conséquent, les algorithmes réguliers pour les graphiques dirigés ne se compileront pas avec un tel objet, et les algorithmes pour les graphiques non dirigés ne fonctionneront pas correctement avec lui.
  
  Quelque part dans le quartier, il y a le sujet de la prise en charge des graphiques techniquement non directionnels qui ont un marqueur de direction de service sur les bords. Cependant, une attention accrue à ce point de vue peut être due à la nature particulière des tâches que l'auteur résout, et l'intérêt généralisé pour soutenir de tels objets n'est pas évident.
  
• Quant à la fonction reverse_edge, prise comme exemple ci-dessus, il n'y a pas du tout une option incroyable que la fonction souhaitée soit présente quelque part dans les entrailles de la bibliothèque, mais pour une raison quelconque, elle a reçu un nom non évident. Cela conduit au problème suivant, qui à première vue n'est pas grave, mais ralentit considérablement le travail avec des bibliothèques de modèles complexes (pas seulement BGL, bien qu'il soit clairement parmi les leaders selon ce critère): travail avec des systèmes étendus de fonctions implicitement liées sans typage explicite des paramètres et avec la sémantique d'utilisation non évidente (souvent la moins transparente que la plus réfléchie) est physiquement difficile, et les environnements de développement existants ne fournissent aucun support pour cela dans le développeur:
  
  
  
  En fait, les assistants automatiques:
  
  
  1. Conçu principalement pour la prise en charge de la POO, lorsqu'un ensemble de fonctions est lié à l'objet de droite en fonction de son type. Avec des fonctions globales qui peuvent se trouver à gauche d'un type (et encore moins d'un ensemble de types), elles sont bien plus utiles même si tous les types sont connus.
  2. Ils ne sont même pas capables de travailler avec des modèles simples. La version de l'assistant visuel utilisée par l'auteur, ayant devant lui la définition d'une classe modèle avec des paramètres par défaut, propose de spécifier une «substitution de test» afin de pouvoir générer un indice pour la classe. Si vous la rencontrez, il ne se passe absolument rien.
  3. De plus, ils sont moins capables de comprendre les qualificatifs de métaprogramme, même les plus simples, tels que enable_if.
  4. À propos d'un scénario typique: «nous sommes à l'intérieur d'une fonction de modèle qui est appelée à partir d'un nombre indéfini de longueurs indéfinies de chaînes d'autres fonctions, y compris celles de modèle», il est impossible de parler sans larmes. Dans ce cas, vim reste vraiment le meilleur ami du programmeur.
  
  Un autre aspect de la même situation peut être illustré en utilisant la première ligne du fragment de code montré dans la figure précédente. Le lecteur est invité à compléter les requêtes «boost current time» vs «CRT current time» et à comparer les résultats. Oui, boost :: date_time (maintenant partiellement déplacé vers std) permet de faire correctement beaucoup de choses complexes, tandis que CRT vous permet de faire plusieurs opérations triviales de manière incorrecte, mais dans les situations courantes du ménage, CRT est plus pratique de tous les points de vue et polynomiaux les constructions de la forme posix_time :: second_clock :: local_time (un exemple doux) ont tendance à se transformer en hiéroglyphes errant dans le programme. Priver le développeur de l'accès à la bibliothèque personnelle de ces hiéroglyphes et la vitesse de développement ira à zéro .
  
  Boost :: string_algo permet de tout faire avec des chaînes, mais, honnêtement, chaque opération pas tout à fait banale est accompagnée d'une session de relecture de la documentation pour rafraîchir la logique générale de la bibliothèque, les noms des prédicats, ainsi qu'un exercice séparé pour découvrir la compatibilité des paramètres. Une situation similaire se produit avec les opérations de tokenisation dans boost :: regexp, avec une logique interne sans faille de ce dernier.
  
  Si une telle situation se produit avec les bibliothèques les plus couramment utilisées, il n'est pas surprenant que BGL, en tant que bibliothèque plus spécialisée, dans laquelle, par exemple, il existe des fonctions make_property_map_function et make_function_property_map qui ne sont pas liées les unes aux autres, ainsi qu'une fonction get sacramentelle qui est rechargée dans n'importe quel le nombre d'arguments de tout type pose les mêmes problèmes, mais sous une forme hypertrophiée. Oui, n'importe quelle tâche peut être résolue par la chaîne d'appel get, mais, hélas, toutes les chaînes get ne résolvent pas ce problème.
  
  La lecture d'un tel code peut être facile et agréable, il peut même ressembler à un synopsis d'un algorithme formellement écrit dans un langage naturel, mais lors de l'écriture, l'impossibilité de remplacer des mots par des synonymes, etc. des manifestations de raideur, n'est pas caractéristique d'un vrai.
  
• D'une manière générale, on ne peut pas ne pas répéter l'observation banale, mais non moins vraie, que la métaprogrammation en C ++ est toujours littéralement basée sur les effets secondaires des outils de langage, dont le but initial était différent, et même les idées les plus simples sur la base de En conséquence, le métalangage est difficile à exprimer et à lire, et la liaison du code de modèle au système archaïque de fichiers inclus ne facilite pas la vie du développeur et ne réduit pas la quantité de code traitée par le compilateur.
  
  (D'un autre côté, les mises à jour régulières pour booster et std apportent beaucoup de constructions pas tout à fait triviales et souvent extrêmement utiles et des solutions inattendues, qui permettent vraiment d'écrire du code plus clair et compact à moindre coût. Cependant, le flux de nouveaux produits est si large, inégal et mal structuré que le plus important ajouts à la bibliothèque standard, même évidents tels que les options / apply_visitor ou ceux mentionnés ci-dessous, si les avantages conceptuels de leur application dans le contexte d'un projet spécifique ne sont pas pertinents Pour aller de soi, sans l'aide d'un événement heureux, ils peuvent perdre le focus pendant longtemps, si vous ne passez pas une partie importante de votre temps de travail à suivre de manière réfléchie directement les nouveaux produits, à étudier des exemples non triviaux de leur utilisation et à tenter mentalement de les appliquer à un code existant. pour faire face à ce problème - pour garder pour cinq programmeurs C ++ pratiquants un C ++ - un théoricien qui ne s'occupe que des problèmes de priorité des nouveaux produits, de leur mise en œuvre tions du projet et les praticiens de l'éducation sélective. Conclusion: ne démarrez pas C ++ - projets avec moins de développeurs ).
  
• Enfin, objectivement, le problème le plus grave qui se produit lors de l'utilisation du code passe-partout BGL . Supposons que nous utilisons un algorithme de modèle qui fait un passage à travers un graphique et prend une représentation du graphique G comme argument. Dans un cas typique, cette représentation dépend des filtres superposés aux sommets et aux arêtes $$$F_v$, $$$F_e$et schéma de poids $$$W$. Pour travailler avec des graphiques filtrés, BGL propose la classe de modèle filter_graph mentionnée ci-dessus, la manière d'y attacher le schéma de pondération est à la discrétion de l'utilisateur. Les foncteurs représentant $$$F_v$, $$$F_e$et $$$W$peut inclure au moins les vues suivantes:
  
  
  • Directement un wrapper pour une fonction représentant un schéma de pondération et des prédicats représentant des filtres (lentement, sans perte d'initialisation);
  • Caches sur ces wrappers, mappage des descripteurs de bord / nœud aux index de bord / nœud, adressage du bitmap et du tableau de valeurs (sans pertes d'initialisation, avec une augmentation progressive de la vitesse telle qu'utilisée)
  • Mappage direct des descripteurs de nœuds / arêtes aux tableaux de valeurs remplies (nécessite une initialisation, mais peut être construit sur la base de la représentation précédente; la vitesse atteint son maximum).
  
  Ainsi, si cet algorithme était écrit dans un style traditionnel, trois sélecteurs avec au moins trois branches dans chacun apparaîtraient dans son corps (et la nécessité d'ajuster le corps lorsque de nouvelles représentations apparaissent). Étant donné que chaque ramification dans le corps de l'algorithme, qui s'exécute un grand nombre de fois lors du passage dans le graphique, entraîne une perte de temps notable, le désir d'éviter ces pertes tout en conservant le code du même style traditionnel peut conduire à plus de 27 implémentations de l'algorithme pour diverses combinaisons de représentations.
  
  Le style de métaprogramme devrait vous sauver de ces problèmes, vous permettant de prendre en charge une métafonction décrivant l'algorithme qui génère implicitement toutes les implémentations nécessaires (et aussi, éventuellement, certaines, et peut-être une quantité considérable, inutile si les structures de code d'exécution ne génèrent pas de facto certaines combinaisons de types, qui ), .
  
  , , 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 ... } 

  
  Il peut être réécrit de manière un peu plus compacte en utilisant la variante <...> sous la forme suivante:
  
  

    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); } 

  
  L'inconvénient de cette forme d'écriture est la nécessité d'une énumération explicite des types type_1, type_2, ... dans la déclaration de variante. Ces types peuvent être encombrants, l'enregistrement à l'aide de declval / result_of_t ne peut pas être moins encombrant.
  
  Lorsque vous en utilisez, il n'est pas nécessaire de répertorier les types, mais il n'y a aucun moyen d'obtenir un apply_visitor analogique.
  
  L'utilisation d'une fonction de modèle make_variant, qui vous permet d'écrire du code du type suivant, se suggère:
  
  

    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, ...), ... ); 

  
  mais le remède n'est pas meilleur que la maladie.
  
  En général, il existe une situation typique pour la métaprogrammation en C ++, lorsque pour exprimer une idée très simple, vous devez utiliser tout un arsenal d'outils auxiliaires avec un résultat qui n'est pas très satisfaisant en termes de lisibilité et de facilité d'enregistrement. Essentiellement, je voudrais pouvoir écrire quelque chose comme ceci:
  
  

    //   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 ... } 

  
  ou même:
  
  

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

  
  Cette dernière option, bien qu'elle soit complètement supprimée du style C ++, semble la plus pratique, car il peut y avoir plus d'une variable arg pour laquelle le type est sélectionné, et il n'y a aucune raison d'anticiper la logique de leur construction .
  
• Le revers de la même situation est l'utilisation de structures auxiliaires (par exemple, la mise en cache) qui implémentent un script qui mérite le nom d'une "variable de modèle", mais diffère de l'extension standard C ++ 14 du même nom.
  
  Le code correspondant peut ressembler à ceci:
  
  

    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); } }; 

  
  Ici, comme ci-dessus, les longues constructions expriment l'idée simple d'accéder à une variable représentant le cache par un nom spécifique, quelle que soit la dimension de la valeur mise en cache (en passant de manière transparente à travers le code appelant).
  
  Par souci de concision, le code est donné pour le cas où un seul type peut être actif, mais dans la pratique, la situation est plus courante lorsque plusieurs conteneurs peuvent exister simultanément (il peut être facilement implémenté dans le même style en utilisant tuple et facultatif).
  
  L'implémentation de la fonction get <...> suppose que le code appelant a une idée du type de valeur en cache auquel il souhaite accéder (par exemple, entier ou virgule flottante).
  
  La situation où la valeur exacte du type n'est pas importante pour l'appelant n'est pas moins courante. Dans ce cas, le script select_value_type / apply_visitor du paragraphe précédent est reproduit (ajusté pour la multiplicité possible de valeurs, ce qui implique de visualiser les types dans l'ordre décroissant de priorité).
  
• Jusqu'à présent, il n'y avait pratiquement aucune mention de PBGL dans ce texte. Cela s’explique par la petite expérience de l’auteur de travailler avec cette partie de la bibliothèque (à propos de laquelle l’auteur lui-même, avec un certain scepticisme, se réfère à tout ce qui est écrit ci-dessous dans ce paragraphe, et appelle les autres à faire de même). En fait, une telle expérience se résume à plusieurs expériences, sur le même type de problèmes de recherche qui ont démontré sur des données pratiques la perte d'une version distribuée à une solution locale 3-5 fois en mémoire et 15-20 fois en performance globale (l'origine de cette figure effrayante est expliquée ici et commentée en plus dans les paragraphes suivants) . Étant donné la plus grande complexité du travail avec des structures distribuées, le choix en faveur de la version locale allait de soi dans une telle situation.
  
  Expliquons la mécanique du fonctionnement PBGL en utilisant un exemple typique de l'algorithme de marche delta. Dans cette version parallèle de l'algorithme de Dijkstra, la file d'attente prioritaire est remplacée par un tableau de «compartiments». Les éléments qui tombent dans un "bucket" sont traités en parallèle. Dans sa forme originale, la stimulation delta est un algorithme typique pour les systèmes de mémoire partagée.
  
  Dans la version distribuée, les événements suivants se produisent: dans PBGL, lors du chargement, le graphique est dispersé entre les processus, et chaque processus a une plage continue de nombres de sommets. Ainsi, par le nombre global de sommets, il est facile de savoir à quel processus il appartient. En conséquence, chaque processus à chaque tour de l'algorithme stocke une partie du "bucket" contenant les sommets appartenant à ce processus. Tous les processus sélectionnent et traitent simultanément les sommets de leurs parties des "compartiments" un par un, tout en envoyant des messages sur la nécessité de mettre à jour les "compartiments" suivants aux processus qui possèdent des sommets voisins. Il est facile de voir que, toutes choses égales par ailleurs, une augmentation du nombre de processus entraîne une augmentation du nombre de messages qu'ils envoient. En conséquence, le temps d'exécution de l'algorithme peut non seulement ne pas diminuer, mais même augmenter. En particulier, le lancement de plusieurs processus MPI pour résoudre ce problème sur une machine physique avec une certaine probabilité ne conduira qu'à une augmentation de la charge totale du processeur sans gain de temps.
  
  Il convient de noter que la stimulation delta est l'algorithme de recherche distribué le plus rapide (sur trois pris en charge par la bibliothèque).
  
  Ainsi, si le graphique n'est pas préparé au préalable, il doit être divisé en blocs de taille maximale, un bloc par machine physique. Par préparation préalable, nous entendons ici renuméroter les sommets du graphe de sorte que les plages continues de nombres utilisées par PBGL, si possible, correspondent à des sous-graphes peu connectés. Des packages tels que METIS, paraMETIS et Zoltan sont utilisés à ces fins. Il est difficile de travailler avec des graphiques dynamiques dans ce mode.
  
  En général, selon les résultats des expériences décrites, l'auteur a eu l'impression que le fonctionnement normal du cluster PBGL n'est possible qu'avec des équipements de communication spéciaux, et il est logique d'utiliser des machines avec un nombre minimum de cœurs et des performances de threads maximales comme nœuds d'un tel cluster. Les auteurs de Trinity dans leur article soutiennent que leur stockage distribué fonctionne beaucoup plus efficacement - l'auteur a du mal à commenter cette déclaration, mais, compte tenu des circonstances ci-dessus, le trouve tout à fait possible: l'architecture PBGL porte un sceau distinct du temps où les machines multicœurs n'ont pas encore reçu une large distribution.
  
  PBGL partage également les problèmes de la version monothread: une certaine synchronisation de code, une documentation et des exemples, aggravés par la plus grande complexité du système et moins d'utilisateurs désireux de partager une expérience utile.
  

BGL et autres animaux

Compte tenu d'une liste assez longue de plaintes spécifiques, il ne sera pas inapproprié de se demander: l'auteur peut-il recommander BGL pour de nouveaux projets en 2019. La réponse est la suivante: l'auteur pense que les bibliothèques de ce style et les applications qui en découlent doivent avoir un avenir . En ce qui concerne le choix d'une bibliothèque de référence pour un projet particulier, nous devons considérer sérieusement l'instrumentation, sans perdre de vue les problèmes énumérés ci-dessus. La réponse, évidemment, dépend de nombreuses circonstances, y compris, mais sans s'y limiter, celles énumérées dans les paragraphes suivants:

• Qu'il s'agisse de travailler avec des graphiques dans un projet est la base de la fonctionnalité ou une tâche facultative;
• Un projet peut-il obtenir un avantage grâce à l'utilisation de plusieurs représentations ou fonctionne-t-il avec des algorithmes dactylographiés tout à fait suffisants?
• Le type de simultanéité le plus avantageux pour le projet;
• Nuances organisationnelles: le désir de métaprogrammation en C ++ chez les salariés (notamment les programmeurs mathématiques), etc.

Probablement, toutes choses égales par ailleurs, l'utilisation de BGL peut être justifiée soit dans le cas d'une très petite utilisation ponctuelle (pour extruder ou copier un morceau de code de travail et oublier), soit pour un grand système pour lequel une flexibilité accrue paiera une entrée lourde et d'autres coûts au fil du temps. Dans d'autres cas, il est logique d'étudier soigneusement d'autres options.

Quant aux alternatives possibles, leur liste comprend au moins les éléments suivants :

La question de la classification de divers logiciels orientés pour travailler avec des graphiques présente un intérêt général particulier. Leur diversité, sans parler du nombre, est très grande. Sans prétendre terminer la classification (et même la corriger formellement), nous pouvons cependant essayer de mettre en évidence les domaines importants suivants dans le développement d'applications graphiques:

1. Graphique SGBD (neo4j, etc.).
   
   Les systèmes de ce type se concentrent sur l'exécution d'opérations transactionnelles sur de grands graphiques (disques distribués). Bien que l'API d'un tel système puisse être très développée, la vitesse d'exécution des algorithmes de graphes eux-mêmes, pour autant que l'on puisse en juger, n'est pas la première priorité. Le système peut même ne pas essayer de charger le graphique entier en mémoire. Pour la modification et la traversée de graphe, les langages déclaratifs (SPARQL, Cypher, Gremlin) sont pris en charge. Une grande importance est attachée à assurer la continuité avec les systèmes SQL traditionnels.
2. Extensions graphiques des systèmes de traitement des mégadonnées travaillant dans le paradigme carte / réduction (GraphX ​​dans Spark, Pegasus et Giraph pour Hadoop) et des systèmes de cluster indépendants ( MS Trinity / MS Graph Engine , GraphLab). Les premiers à effectuer des opérations sur le graphique implémentent le modèle Google Pregel (mais pas seulement) et peuvent être configurés pour une utilisation incluant des nœuds de calcul parallèles massifs. Ceux-ci et d'autres peuvent être utilisés, entre autres, comme base pour des projets de logiciels d'entreprise.
   
   Bien que l'API de ces systèmes puisse être assez développée (entre autres, GraphX ​​prend en charge SPARQL et Cypher), l'objectif principal lorsque vous travaillez avec eux est de résoudre les problèmes d'infrastructure. GraphX ​​se caractérise par l'immuabilité des données et un biais dans le pipeline de toutes les opérations. MS Trinity n'inclut actuellement pas de méthodes de haut niveau et ne fournit qu'un ensemble de primitives pour travailler avec des nœuds et des bords. Les systèmes fonctionnant sur Hadoop sont, en principe, peu utiles pour résoudre des problèmes de graphes arbitraires.
   
3. Bibliothèques d'outils réellement universelles qui implémentent des ensembles de méthodes plus ou moins larges (BGL / PBGL, LEMON etc.), y compris massivement parallèles (nvGraph, Gunrock).
   
   Sur la base de ceux-ci, des systèmes d'application peuvent être créés pour adapter les algorithmes graphiques à des domaines spécifiques.
4. Systèmes et bibliothèques spécialisés notamment dans des problèmes complexes d'importance universelle (METIS, paraMETIS, Zoltran: partitionnement de graphes, GraphViz, Gephi: visualisation, GraphBLAS: algorithmes algébriques pour travailler avec des graphes, etc.).
   
   De nombreuses applications graphiques indépendantes peuvent être affectées sous condition à cette catégorie, dont une analyse détaillée nécessiterait trop de temps. Ce dernier contient des applications de toutes les variétés imaginables: académiques et commerciales, mono-utilisateur et multi-utilisateurs, apparues récemment et existant depuis plus d'une décennie, etc.

Une partie obscure mais significative des applications graphiques se concentre sur les tâches d'analyse de réseau et, déjà, d'analyse de réseau social (détection de communauté). Curieusement, les systèmes d'analyse de liens (utilisés, en règle générale, par divers "combattants du crime"), qui présentent certaines similitudes avec le système que nous développons, sont beaucoup moins courants. Dans tous les cas, sans vérification spéciale, il est difficile de déterminer la nature des modèles de données utilisés par divers systèmes et les limitations de performances associées, les volumes pris en charge, les ensembles d'opérations, etc.

Remarques

1. BGL n'est pas une bibliothèque purement en-tête, mais pour le moment, la seule fonctionnalité qui nécessite une liaison est (plutôt facultative) de travailler avec les fichiers GraphViz DOT. Par conséquent, dans la grande majorité des cas, la liaison et la liaison automatique avec la version appropriée de libbost-graph pour inclure les en-têtes BGL dans la configuration Boost ne sont pas nécessaires. Ainsi, par souci de cohérence avec la bibliothèque libboost-regex utilisée par les fonctions BGL non-en-tête, il est pratique de simplement brancher l'en-tête boost \ regex.hpp à partir du code de projet, même si ce dernier n'utilise pas d'expressions régulières.
2. Un chaos supplémentaire est introduit par la présence d'entités dont l'équivalence apparente encourage la chasse aux chats noirs (éventuellement absents) dans les pièces sombres .
3. Avant de procéder à sa description (en utilisant un exemple spécifique, où il s'est manifesté particulièrement fortement et désagréablement), nous notons que l'auteur est parmi les rares personnes chanceuses travaillant avec un projet chargé dans un puissant système d'exploitation Windows et la gamme de compilateurs MSVC sauvée par Dieu. Il est possible que les problèmes décrits ci-dessous soient des artefacts de cette gamme de compilateurs: une variété de circonstances particulières rendent difficile la conduite d'une expérience comparative avec gcc / clang dans l'environnement * nix. Si c'est le cas, vous ne pouvez que féliciter les utilisateurs d'autres compilateurs.
4. Pour adoucir qui, dans certains cas, le constexpr récemment apparu aidera probablement.
5. Dans notre cas, cela a conduit à une attention particulière à la fonction d'économie d'état, qui permet un débogage avec commodité, amenant d'abord le système à l'état initial souhaité dans un assemblage optimisé.
6. Dans ma pratique, pour diverses raisons, il était nécessaire de convertir les paramètres d'exécution en arguments de modèle, et assez souvent j'ai dû recourir à des méthodes très précises et très élaborées (inspirées des implémentations désormais obsolètes de boost typeof et boost lambda pour C ++ 98, qui ont directement touché le traiter la technique de programmation en C ++ comme une solution au rébus), parmi lesquels l' étoile brille la sélection de l'argument en divisant par deux , mais, en général, les principaux problèmes avec de telles opérations ont toujours été associés à l'impossibilité d'exporter type sélectionné en dehors du champ d'application, ce qui a donné lieu à des motifs exotiques.
7. ( — 80 4 50 200 , ) ( ) - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].