Pourquoi avons-nous besoin de plages de C ++ 20 dans un simple broyeur?

Récemment, les plages qui devraient être incluses dans la norme C ++ 20 ont été assez discutées, y compris sur Habré ( un exemple où il existe de nombreux exemples ). Il y a suffisamment de critiques des intervalles, ils disent que

• ils sont trop abstraits et ne sont nécessaires que pour un code très abstrait
• la lisibilité du code avec eux ne fait qu'empirer
• intervalles ralentissent le code

Voyons voir complètement ouvrier-paysan tâche pratique, afin de comprendre si cette critique est valable et est-il vrai qu'Eric Nibler a été mordu par Bartosz Milewski et n'écrit range-v3 qu'avec la pleine lune .

Nous intégrerons la fonction suivante en utilisant la méthode trapézoïdale:$$ $ inline $ f (t) = 3 t ^ 2 \ sin t ^ 3 $ inline $ allant de zéro à$$ $ inline $ \ tau $ inline $ . Si$$ $ inline $ \ tau ^ 3 / \ pi $ inline $ est égal à un nombre impair, alors l'intégrale est 2.

Donc, le problème: nous écrivons un prototype d'une fonction qui calcule l'intégrale par la méthode trapézoïdale . Il semble, à première vue, que les abstractions ne sont pas nécessaires ici, mais la vitesse est importante. En fait, ce n'est pas entièrement vrai. Pour le travail, je dois souvent écrire des "concasseurs de nombres", dont l'utilisateur principal est moi-même. Je dois donc aussi supporter et gérer leurs bugs (malheureusement mes collègues - pas toujours juste moi). Et il arrive aussi qu'un certain code ne soit pas utilisé, disons un an, et puis ... En général, la documentation et les tests doivent également être écrits.

Quels arguments une fonction d'intégrateur doit-elle avoir? Fonction et grille intégrables (ensemble de points$$ $ en ligne $ t_1, t_2, t_3 ... $ en ligne $ utilisé pour calculer l'intégrale). Et si tout est clair avec la fonction intégrée ( std::function sera juste ici), alors sous quelle forme la grille doit-elle être transmise? Voyons voir.

Les options

Pour commencer - afin qu'il y ait quelque chose à comparer avec les performances - nous allons écrire une boucle for simple avec un pas de temps constant:

 // trapezoidal rule of integration with fixed time step; // dt_fixed is the timestep; n_fixed is the number of steps double integrate() { double acc = 0; for(long long i = 1; i < n_fixed - 1; ++i) { double t = dt_fixed * static_cast<double>(i); acc += dt_fixed * f(t); } acc += 0.5 * dt_fixed * f(0); acc += 0.5 * dt_fixed * f(tau); return acc; } 

Lorsque vous utilisez ce cycle, vous pouvez passer comme arguments à la fonction le début et la fin de l'intervalle d'intégration, ainsi que le nombre de points pour cette intégration elle-même. Stop - la méthode trapézoïdale se produit également avec un pas variable, et notre fonction intégrable demande simplement d'utiliser un pas variable! Qu'il en soit ainsi, ayons un paramètre de plus ($$ $ en ligne $ b $ en ligne $ ) pour contrôler la "non-linéarité" et laisser nos étapes être, par exemple, comme suit:$$ $ inline $ \ Delta t (t) = \ Delta t_0 + bt $ inline $ . Cette approche (introduire un paramètre numérique supplémentaire) est probablement utilisée dans un million d'endroits, même si, semble-t-il, son défaut devrait être évident pour tout le monde. Et si nous avons une fonction différente? Et si nous avons besoin d'un petit pas quelque part au milieu de notre intervalle numérique? Mais que se passe-t-il si une fonction intégrable possède quelques fonctionnalités? En général, nous devons être capables de transporter n'importe quelle grille. (Néanmoins, dans les exemples, jusqu'à la toute fin, nous «oublierons» la vraie méthode trapézoïdale et pour simplifier nous considérerons sa version avec un pas constant, en gardant à l'esprit que la grille peut être arbitraire).

Comme la grille peut être quelconque, passons ses valeurs$$ $ en ligne $ t_1, t_2, ... $ en ligne $ enveloppé dans std::vector .

 // trapezoidal rule of integration with fixed time step double integrate(vector<double> t_nodes) { double acc = 0; for(auto t: t_nodes) { acc += dt_fixed * f(t); } acc -= 0.5 * dt_fixed * f(0); acc -= 0.5 * dt_fixed * f(tau); return acc; } 

Il y a plus qu'assez de communautés dans cette approche, mais qu'en est-il de la performance? Avec une consommation de mémoire? Si auparavant tout était résumé sur le processeur, nous devons maintenant d'abord remplir la zone mémoire, puis lire à partir de celle-ci. Et la communication avec la mémoire est une chose assez lente. Et la mémoire n'est toujours pas en caoutchouc ( et silicone )

Regardons la racine du problème. De quoi une personne a-t-elle besoin pour être heureuse? Plus précisément, de quoi a besoin notre cycle (basé sur la plage pour la boucle)? Tout conteneur avec les itérateurs begin() et end() , et ++ , * et != Opérateurs pour les itérateurs. Nous allons donc écrire.

 //   ,    ,      template <typename T> double integrate(T t_nodes) { double acc = 0; for(auto t: t_nodes) { acc += dt_fixed * f(t); } acc -= 0.5 * dt_fixed * f(0); acc -= 0.5 * dt_fixed * f(tau); return acc; } // ... //      class lazy_container { public: long long int n_nodes; lazy_container() { n_nodes = n_fixed; } ~lazy_container() {} class iterator { public: long long int i; // index of the current node iterator() { i = 0; } ~iterator() {} iterator& operator++() { i+= 1; return *this; } // ! bool operator!=(const iterator& rhs) const { return i != rhs.i; } double operator* () const { return dt_fixed * static_cast<double>(i); } }; iterator begin() { return iterator(); } iterator end() { iterator it; it.i = n_nodes; return it; } }; // ... //      lazy_container t_nodes; double res = integrate(t_nodes); 

Nous calculons ici une nouvelle valeur.$$ $ inline $ t_i $ inline $ à la demande, comme nous l'avons fait dans une boucle for simple. Il n'y a pas d'accès à la mémoire et nous espérons que les compilateurs modernes simplifieront le code très efficacement. Dans le même temps, le code de la fonction d'intégration n'a pas beaucoup changé et il peut encore digérer std::vector .

Où est la flexibilité? En fait, nous pouvons maintenant écrire n'importe quelle fonction dans l'opérateur ++ . Autrement dit, cette approche permet, en fait, de transférer une fonction au lieu d'un seul paramètre numérique. La grille générée à la volée peut être quelconque, et nous ne perdons pas (probablement) non plus de performances. Cependant, écrire un nouveau lazy_container chaque fois juste pour déformer d'une manière ou d'une autre la grille d'une manière complètement nouvelle ne semble pas (c'est autant que 27 lignes!). Bien sûr, vous pouvez faire de la fonction responsable de la génération de la grille un paramètre de notre fonction d'intégration, et lazy_container aussi, c'est-à-dire, excusez-moi, encapsulez-le.

Vous demandez - alors quelque chose ne va plus? Oui! Premièrement, il sera nécessaire de transmettre séparément le nombre de points à intégrer, ce qui peut provoquer une erreur. Deuxièmement, le vélo non standard créé devra être pris en charge et éventuellement développé par quelqu'un. Par exemple, pouvez-vous imaginer immédiatement comment, avec cette approche, composer un combinateur de fonctions dans l'opérateur ++ ?

C ++ depuis plus de 30 ans. Beaucoup à cet âge ont déjà des enfants, et C ++ n'a même pas de conteneurs / itérateurs paresseux standard. Un cauchemar! Mais tout (dans le sens des itérateurs, pas des enfants) changera dès l'année prochaine - la norme (peut-être partiellement) inclura la bibliothèque range-v3 , qui a été développée par Eric Nibler depuis plusieurs années. Nous utiliserons les œuvres de ses fruits. Le code dit tout pour lui:

 #include <range/v3/view/iota.hpp> #include <range/v3/view/transform.hpp> //... auto t_nodes = ranges::v3::iota_view(0, n_fixed) | ranges::v3::views::transform( [](long long i){ return dt_fixed * static_cast<double>(i); } ); double res = integrate(t_nodes); 

La fonction d'intégration reste la même. Autrement dit, seulement 3 lignes pour résoudre notre problème! Ici, iota_view(0, n) génère un intervalle paresseux (plage, un objet qui encapsule le début et la fin généralisés; une plage paresseuse est une vue), qui, lors de l'itération à chaque étape, calcule le nombre suivant dans la plage [0, n). C'est drôle que le nom ι (la lettre grecque iota) se réfère il y a 50 ans à la langue APL. Stick | vous permet d'écrire des pipelines de modificateurs d'intervalle et de transform , en fait, est un tel modificateur qui, en utilisant une simple fonction lambda, transforme une séquence d'entiers en une série$$ $ en ligne $ t_1, t_2, ... $ en ligne $ . Tout est simple, comme dans un conte de fées Haskell.

Mais comment faire un pas variable? Tout est aussi simple:

 #include <range/v3/view/drop.hpp> #include <range/v3/view/iota.hpp> #include <range/v3/view/transform.hpp> //... // trapezoidal rule of integration; step size is not fixed template <typename T> double integrate(T t_nodes) { double acc = 0; double t_prev = *(t_nodes.begin()); double f_prev = f(t_prev); for (auto t: t_nodes | ranges::v3::views::drop(1)) { double f_curr = f(t); acc += 0.5 * (t - t_prev) * (f_curr + f_prev); t_prev = t; f_prev = f_curr; } return acc; } //... auto step_f = [](long long i) { if (static_cast<double>(i) <= 1 / a) { return pow(2 * M_PI, 1/3.0) * a * static_cast<double>(i); } else { return tau * pow(static_cast<double>(i) / static_cast<double>(n), 1/3.0); } }; auto t_nodes = ranges::v3::iota_view(0, n) | ranges::v3::views::transform(step_f); double res = integrate(t_nodes); 

Un lecteur attentif a noté que dans notre exemple, le pas variable nous a permis de réduire le nombre de points de grille d'un facteur trois, alors qu'il y a des dépenses supplémentaires pour le calcul$$ $ inline $ t_i $ inline $ . Mais si nous prenons un autre$$ $ en ligne $ f (t) $ en ligne $ , le nombre de points peut changer beaucoup plus ... (mais ici l'auteur devient déjà paresseux).

Donc, les horaires

Nous avons les options suivantes:

• v1 - boucle simple
• v2 -$$ $ inline $ t_i $ inline $ se trouver dans std::vector
• v3 - fortune lazy_container avec itérateur de fortune
• v4 - intervalles de C ++ 20 (plages)
• v5 - étend à nouveau, mais seulement ici la méthode trapézoïdale est écrite en utilisant un pas variable

Voici ce qu'il s'avère (en secondes) pour$$ $ inline $ \ tau = (10 \, 000 \, 001 \ times \ pi) ^ {1/3} $ inline $ , pour g ++ 8.3.0 et clang ++ 8.0.0 sur Intel® Xeon® CPU® X5550 (nombre d'étapes$$ $ en ligne $ 1,5 \ fois 10 ^ 8 $ en ligne $ , sauf pour la v5, où les étapes sont trois fois moins (le résultat des calculs par toutes les méthodes ne diffère pas des deux de plus de 0,07):

En général, la mouche a traversé le champ, la mouche a trouvé une pièce!

Résumé

Même dans une tâche très simple, les plages se sont avérées très utiles: au lieu de code avec des itérateurs self-made sur 20+ lignes, nous avons écrit 3 lignes, sans avoir de problème avec la lisibilité du code ou ses performances.

Bien sûr, si nous avions besoin (pour) les performances ultimes de ces tests, nous devrions tirer le meilleur parti du processeur et de la mémoire en écrivant du code parallèle (ou en écrivant une version pour OpenCL) ... De plus, je n'ai aucune idée de ce qui se passera si j'écris très longues chaînes de modificateurs. Est-il facile de déboguer et de lire les messages du compilateur lors de l'utilisation de plages dans des projets complexes. Compilera l'augmentation du temps. J'espère que quelqu'un écrit jamais sur cet article.

Quand j'ai écrit ces tests, je ne savais pas moi-même ce qui allait se passer. Maintenant, je sais - les gammes méritent certainement d'être testées dans un vrai projet, dans les conditions dans lesquelles vous comptez les utiliser.

Je suis allé au bazar pour acheter un samovar.

Liens utiles

gamme-v3 maison

Documentation et études de cas v3

code de cet article sur github

listes en haskell, pour comparaison

Remerciements

Merci fadey d' avoir aidé à écrire tout cela!

PS

J'espère que quelqu'un commentera de telles bizarreries: i) Si vous prenez un intervalle d'intégration 10 fois plus court, alors sur mon exemple Xeon v2 est 10% plus rapide que v1, et v4 est trois fois plus rapide que v1. ii) Le compilateur Intel (icc 2019) produit parfois dans ces exemples du code deux fois plus rapide que g ++ compilé. La vectorisation est-elle à blâmer? G ++ peut-il être obligé de faire de même?