Pourquoi std :: reduction at-il été ajouté en C ++17?

Question

Je cherchais une explication détaillée de la signification de la description "Valeur de retour" pour std::reduce , qui, selon cppreference.com, est:

Peut-être qu'une fois que je pourrai percevoir correctement l'idée de la section "Valeur de retour", je pourrai mieux déterminer où je devrais choisir std::reduce sur std::accumulate .

Answer 1

Depuis que vous avez demandé une explication approfondie, et la réponse précédente ne couvre que les bases, je prends la liberté d'ajouter une plus approfondi.

std::reduce est destiné à effectuer la deuxième étape majeure du modèle de programmation MapReduce. L'idée de base est que la plate-forme (dans ce cas, l'implémentation C++) fournit ces deux opérations primitives de la carte et de réduire, et le programmeur fournit les opérations de rappel pour chacun des deux qui effectuent le "travail réel".

Fondamentalement, la fonction de rappel pour l'opération de carte cartes une valeur d'entrée à une valeur intermédiaire. Le rappel pour réduire combine deux valeurs intermédiaires dans une valeur intermédiaire. La dernière valeur intermédiaire de gauche devient la sortie de l'ensemble de MapReduce. Il semble être un très restrictive modèle en soi, mais encore, il a une large gamme d'applications.

La plate-forme doit faire plus, bien sûr, comme le "brassage" (distribution des intrants, habituellement en groupes, à différentes unités de traitement) et la planification, mais ce est de peu d'intérêt pour le programmeur d'application.

Par ailleurs, dans la norme C++ de la bibliothèque, la "carte" opération s'appelle transform. Il a reçu le parallélisme de soutien en C++17 ainsi, mais je vais obtenir dans un parallélisme plus tard.

Voici un exemple: disons que nous avons une fonction qui convertit un entier en chaîne de la représentation. Maintenant, étant donné une liste de nombres entiers, nous voulons la représentation textuelle contenant la plus forte proportion de consonnes à la voix. E. g.

• Entrée: 1, 17, 22, 4, 8
• Sortie: vingt-deux

(Essayez par vous-même si vous ne croyez pas à ce résultat.)

Nous pourrions utiliser MapReduce ici à l'aide de notre int-à-fonction texte comme le rappel à la carte (rsp. std::transform), et une fonction qui compte le nombre de consonnes et au chant, et puis sélectionne soit la main gauche ou de droite argument en conséquence. Il y a une certaine inefficacité ici, en particulier, la "ratio" doit être mis en cache, mais ce sont des détails.

Maintenant, votre question peut et, éventuellement, devrait être: Pourquoi devrais-je peut-être des soins? Après tout, jusqu'à présent, vous n'avez pas gagner beaucoup de l'aide par exemple, std::transform et std::reduce de cette façon, et vous pourriez avoir utilisé std::accumulate à la place de celle-ci. La réponse, bien sûr, étant donné un nombre suffisamment grand de valeurs d'entrée, est l'exécution des politiques de l'ancien standard, les modèles de fonction ont des surcharges qui permettent de parallélisme implicite. Mais qui soulève toujours la question de pourquoi on utiliserait MapReduce et pas un pool de threads ou std::async, et un tas d'écrits à la main boucles? Tout d'abord, en particulier pour les "pure" des calculs sur des grands vecteurs ou autres récipients, sans I/O, il est souvent plus commode d'écrire les deux MapReduce rappels parce que vous n'avez pas à traiter avec tous les détails de la façon dont les données d'entrée sont réparties autour de différents threads et ensuite combinés.

Deuxièmement, MapReduce encourage une discipline de la structuration de vos calculs d'une manière qui peut être parallélisée de façon très efficace. Bien sûr, dans un langage de programmation qui prend en charge l'impératif de paradigme, tel que C++, vous pouvez toujours gâcher les choses par le verrouillage d'un tas de mutex, ou de quelque façon que vous pouvez avoir d'interférences avec d'autres threads. Mais le paradigme MapReduce encourage l'écriture indépendante de la cartographie des rappels. Comme une règle simple, si ces tâches partager des données, alors il devrait être en lecture seule afin que les copies de celui-ci peut être stocké dans plusieurs caches CPU en même temps. Bien des tâches d'écriture, combiné avec une plate-forme efficace de la mise en œuvre des algorithmes sous-jacents, peuvent s'adapter à des centaines ou même des milliers de cœurs de PROCESSEUR, comme le montre le MapReduce plateformes déjà en usage commun (comme Apache Hadoop, mais prendre ce seul comme un exemple, et non comme gratuit de la publicité).

Mais la question était surtout sur std::reduce – on peut toujours effectuer cette hautement évolutive de la cartographie et puis exécutez std::accumulate sur les résultats intermédiaires, droit? Et c'est là que nous arrivons à ce que François Andrieux écrit précédemment. accumulate effectue ce que les mathématiciens appellent une gauche pli. Si vous affichez les opérations et leurs opérandes comme un arbre binaire, alors ce serait un gauchisants arbre, par exemple, d'ajouter 1, 2, 3 et 4:

   +
  / \
  + 4
 / \
 + 3
/ \
1 2

Comme vous pouvez le voir, le résultat de chaque opération est l'un des arguments de la prochaine opération. Cela signifie qu'il existe une chaîne linéaire de dépendances de données, et qui est le fléau de tous parallélisme. Pour ajouter un million de numéros, vous avez besoin d'un million d'opérations consécutives, ce qui permet de bloquer un seul cœur, et vous ne pouvez pas en faire un usage quelconque des cœurs supplémentaires. Ils n'ont rien à faire la plupart du temps, et de la communication surcharge emportent largement sur le coût des calculs. (C'est en fait pire que ça parce que les Processeurs modernes peuvent effectuer plusieurs calculs simples par cycle d'horloge, mais cela ne fonctionne pas quand il y a beaucoup de dépendances de données, de sorte que la plupart des ALUs ou les Unités de police constituées sont inutilisées.)

En levant la restriction d'une gauche pli doit être utilisé, std::reduce , la plate-forme pour une utilisation plus efficace des ressources de calcul. Même si vous utilisez le single-threaded la surcharge, la plate-forme pourrait, par exemple, l'utilisation SIMD pour ajouter un million de nombres entiers dans beaucoup moins d'un million d'opérations, et le nombre de dépendances de données sera grandement réduite. 10x plus rapide sur un bien écrit integer outre, réduire ne serait pas une surprise pour moi. Accordé, ce cas particulier pourrait probablement être optimisé en vertu de la comme-si la règle car le C++ mise en œuvre "sait" que entier est plus (ou presque, voir ci-dessous) associatif.

Mais réduire va plus loin que cela, comme il a été mentionné, par l'appui à l'exécution des politiques, c'est à dire dans la plupart des cas multi-core parallélisme. En théorie, l'équilibre arbre binaire de l'exploitation pourraient être utilisés. (Rappelez-vous que l'arbre est équilibré si la profondeur est de moins de deux, ou de la profondeur du sous-arbre gauche est différente de la profondeur du sous-arbre droit au plus à 1.) Un tel arbre n'a qu'logarithmique de la profondeur. Si nous avons un million de nombres entiers, le minimum de profondeur de l'arbre est de 20, donc – théoriquement – donné assez de cœurs et aucune communication de la surcharge, nous pourrions parvenir à un facteur de 50 000 speedup même de l'optimisation mono-thread de calcul. Bien sûr, dans la pratique, c'est une charge de vœu pieux, mais on peut encore s'attendre à de grandes accélérations.

Tout cela étant dit, permettez-moi d'ajouter un rapide avertissement/rappel que la performance n'est pas la même efficacité. À l'aide de 64 cœurs pour chaque 100ms signifie beaucoup plus de performances que d'utiliser une base de 1 000 ms, mais beaucoup moins de l'efficacité de l'UC. Une autre façon de le dire est que la performance est l'efficacité dans le sens de minimiser le temps écoulé, mais il existe d'autres mesures de l'efficacité totale de temps PROCESSEUR utilisé, la RAM utilisée, l'énergie utilisée, et ainsi de suite. La principale motivation de parallèle MapReduce est de fournir une performance plus élevée. Si elle réduit le temps CPU ou de la consommation d'énergie n'est pas claire, et il va très probablement augmenter le pic de l'utilisation de la RAM.

Pour couronner le tout, voici quelques mises en garde. Comme il a été mentionné, reduce est non-déterministe si les opérations ne sont pas associatifs ou non commutative. Heureusement, le plus important opérations arithmétiques telles que l'addition et la multiplication sont associatives et commutatives, droit? Nous savons tous que les entiers et à virgule flottante en plus, par exemple, ont à la fois de ces propriétés. Et bien sûr, je suis facétieux. En C++, ni entier signé de plus ni de virgule flottante de plus, sont associatifs. Pour les nombres à virgule flottante, c'est en raison de différences possibles dans l'arrondissement de résultats intermédiaires. C'est facilement visible si nous, comme un exemple, choisissez une simple virgule flottante format avec deux chiffres significatifs, et de considérer la somme 10 + 0.4 + 0.4. Si cela est fait par la syntaxe C++ les règles de gauche fois, nous obtenons (10 + 0.4) + 0.4 = 10 + 0.4 = 10 car à chaque fois le résultat est arrondi à l'arrière en bas à 10. Mais si nous le faisons comme 10 + (0.4 + 0.4), le premier résultat intermédiaire est de 0,8 et 10 + 0,8 est ensuite arrondi à 11. Aussi, les erreurs d'arrondi peuvent devenir amplifié par une grande profondeur de l'exploitation de l'arbre, donc en faisant un gauche pli est en fait l'une des pires choses que l'on peut faire quand il s'agit de la précision. Il y a plusieurs façons de résoudre ce problème, allant de trier et regrouper les entrées à l'aide d'une augmentation de la précision intermédiaire, mais quand il s'agit de reduce il y a peut être tout simplement aucun moyen d'obtenir 100% run-pour-courir cohérence.

Les autres, peut-être plus surprenant, l'observation, c'est que entier signé de l'addition est associative en C++. La raison à cela est la possibilité de dépassement de capacité, pour le dire crûment: (-1) + 1 + INT_MAX. Les règles de syntaxe, ou accumulate, le résultat est INT_MAX. Mais si vous utilisez reduce, ce peut être réécrit comme (-1) + (1 + INT_MAX) qui contient un débordement d'entier et donc un comportement indéfini. En fait, parce qu' reduce peut arbitrairement changer l'ordre des opérandes, c'est vrai même si les entrées sont { INT_MAX, -1, 1 }.

Ma recommandation est de veiller à ce que le rappel à l' reduce ne peut pas produire un dépassement de capacité. Cela pourrait être fait par la limitation de la gamme a permis d'intrants (par exemple, si vous ajoutez 1000 ints, assurez-vous qu'aucun d'entre eux est plus grand que INT_MAX / 1000 ou moins de la INT_MIN / 1000, arrondi à la hausse), par exemple, ou, de manière équivalente, en utilisant un grand nombre entier de type, ou, en tout dernier recours (parce que c'est à la fois coûteux et difficile à gérer correctement), mettre des contrôles supplémentaires dans l' reduce de rappel. Dans la plupart des cas pratiques, reduce n'est que légèrement moins sûr concernant le dépassement d'entier que accumulate, cependant.

Answer 2

std::accumulate itère sur le contenant dans l'ordre où qu' std:reduce peut pas. Parce que l'ordre n'est pas garanti, std::reduce introduit des exigences supplémentaires :

Le comportement est non-déterministe si binary_op n'est pas associatif ou non commutative. Le comportement est indéfini si binary_op modifie un élément ou invalide toute itérateur dans [première; dernière], y compris la fin de l'itérateur.

Toutefois, std::reduce fournit des surcharges qui prennent en charge la parallélisation qui ne sont pas disponibles avec std::accumulate. std::reduce automatique vous permet de paralléliser votre opération, à condition qu'elle respecte les exigences mentionnées ci-dessus.

Answer 3

• Permettant le parallélisme est la raison principale pour plus de std::réduire

• Également, on doit assurez-vous que l'opération que vous souhaitez utiliser avec std::réduire à la fois associatif et commutative.

  • Par exemple, l'Addition est associative et donne les mêmes résultats lorsque l'accumulation est fait en parallèle en utilisant std::réduire.
    100 + 50 + 40 + 10 = 200 (100 + 40) + (50 + 10) = 200

  • Mais la soustraction de ne pas être associatif, std::réduire peut donner de mauvais résultats.
    100 - 50 - 40 - 10 = 0 NOT SAME AS (100 - 40) - (50 - 10) = 20

• L'efficacité
  std::vector<double> v(100000, 0.1); double result = std::accumulate(v.begin(), v.end(), 0.0); double result = std::reduce(std::execution::par,v.begin(),v.end()) //Faster