Pourquoi Range-v3 est-il plus lent que la STL dans cet exemple ?

Question

Je m'amuse avec la bibliothèque Range-v3 pour effectuer un glorifié find_if et je suis curieux de savoir pourquoi google-benchmark classe systématiquement mon code Range-v3 moins bien que mon code Range-v3. std::find_if approche. g++ et clang donnent tous deux le même schéma avec -O3 y #define NDEBUG .

L'exemple spécifique que j'ai en tête est le suivant, qui utilise la STL :

std::vector<int> lengths(large_number, random_number);

auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
auto accumulated_length = 0l;
auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
                              accumulated_length += val;
                              return to_find < accumulated_length;
                          });
auto found_index = std::distance(lengths.begin(), found);    

C'est un peu artificiel pour les besoins de cette illustration, mais il y aurait normalement un générateur aléatoire pour l'adresse de l'utilisateur. to_find et des valeurs aléatoires dans la lengths vecteur.

En utilisant la bibliothèque Range-v3, j'obtiens le code suivant

using namespace ranges;    

std::vector<int> lengths(large_number, random_number);

auto const to_find = accumulate(lengths, 0l) / 2;

auto found_index = distance(lengths | view::partial_sum()
                                    | view::take_while([=](auto const i) {
                                         return i < to_find;
                                      }));

Ma question est de savoir pourquoi la Range-v3 est plus lente que l'implémentation STL. Je comprends qu'il s'agit encore d'une bibliothèque expérimentale, mais peut-être y a-t-il quelque chose qui ne va pas dans l'exemple de code ou est-ce que j'utilise mal les concepts de Range ?

Editar

Un exemple de pilote google-bench (pas sûr qu'il soit correct)

#define NDEBUG

#include <numeric>
#include <vector>

#include <benchmark/benchmark.h>

#include <range/v3/all.hpp>

static void stl_search(benchmark::State &state) {

    using namespace ranges;

    std::vector<long> lengths(state.range(0), 1l);

    auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;

    while (state.KeepRunning()) {

        auto accumulated_length = 0l;
        auto const found = std::find_if(lengths.begin(), lengths.end(), [&](auto const& val) {
                               accumulated_length += val;
                               return to_find < accumulated_length;
                           });
        volatile long val = std::distance(lengths.begin(), found);
    }
    state.SetBytesProcessed(int64_t(state.iterations()) *
                            int64_t(state.range(0)) * sizeof(long));
}

static void ranges_search(benchmark::State &state) {

    using namespace ranges;

    std::vector<long> lengths(state.range(0), 1l);

    auto const to_find = accumulate(lengths, 0l) / 2;

    while (state.KeepRunning())
    {
        volatile long val = distance(lengths | view::partial_sum()
                                             | view::take_while([=](auto const& i) {
                                                   return i <= to_find;
                                               }));
    }
    state.SetBytesProcessed(int64_t(state.iterations()) *
                            int64_t(state.range(0)) * sizeof(long));
}

BENCHMARK(ranges_search)->Range(8 << 8, 8 << 16);
BENCHMARK(stl_search)->Range(8 << 8, 8 << 16);

BENCHMARK_MAIN();

Donne

ranges_search/2048          756 ns        756 ns     902091   20.1892GB/s
ranges_search/4096         1495 ns       1494 ns     466681   20.4285GB/s
ranges_search/32768       11872 ns      11863 ns      58902   20.5801GB/s
ranges_search/262144      94982 ns      94892 ns       7364   20.5825GB/s
ranges_search/524288     189870 ns     189691 ns       3688   20.5927GB/s
stl_search/2048             348 ns        348 ns    2000964   43.8336GB/s
stl_search/4096             690 ns        689 ns    1008295   44.2751GB/s
stl_search/32768           5497 ns       5492 ns     126097    44.452GB/s
stl_search/262144         44725 ns      44681 ns      15882   43.7122GB/s
stl_search/524288         91027 ns      90936 ns       7616   42.9563GB/s

avec clang 4.0.1 et

ranges_search/2048         2309 ns       2307 ns     298507   6.61496GB/s
ranges_search/4096         4558 ns       4554 ns     154520   6.70161GB/s
ranges_search/32768       36482 ns      36454 ns      19191   6.69726GB/s
ranges_search/262144     287072 ns     286801 ns       2438   6.81004GB/s
ranges_search/524288     574230 ns     573665 ns       1209   6.80928GB/s
stl_search/2048             299 ns        298 ns    2340691   51.1437GB/s
stl_search/4096             592 ns        591 ns    1176783   51.6363GB/s
stl_search/32768           4692 ns       4689 ns     149460   52.0711GB/s
stl_search/262144         37718 ns      37679 ns      18611   51.8358GB/s
stl_search/524288         75247 ns      75173 ns       9244   51.9633GB/s

avec gcc 6.3.1. Ma machine a un processeur de la génération Haswell. Les deux ont été compilés et exécutés avec

g++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out
clang++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out

Answer 1

view::partial_sum sur une gamme de int produit une gamme de int . Si to_find > INT_MAX l'accumulateur interne débordera, ce qui donnera lieu à UB. En pratique, l'algorithme parcourt probablement toute l'entrée et renvoie l'itérateur de fin.

À l'inverse, votre accumulated_length dans l'approche hors gamme-v3 est un long . Il ne déborde pas, et a donc un comportement défini / retourne avant de traiter la totalité de l'entrée.

L'approche range-v3 aura un comportement correct si vous transform la gamme d'entrée en une gamme de long avant de le faire passer par partial_sum :

auto found_index = distance(lengths
  | view::transform(convert_to<long>{}) | view::partial_sum()
  | view::take_while([=](auto const i) { return i < to_find; }));

Même avec ce correctif, il est toujours remarquablement plus lent que l'utilisation des algorithmes standards dans mes tests. Compilation de ce programme de test :

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#ifdef USE_RV3
#include <range/v3/core.hpp>
#include <range/v3/algorithm.hpp>
#include <range/v3/numeric.hpp>
#include <range/v3/view.hpp>

#else
#include <algorithm>
#include <numeric>
#endif

int main() {
    constexpr size_t large_number = 1UL << 30;

    int random_number = 42;

    std::vector<int> const lengths(large_number, random_number);

    using clock_t = std::chrono::steady_clock;
    auto const start = clock_t::now();

#ifdef USE_RV3
    auto const to_find = ranges::accumulate(lengths, 0l) / 2;
#else
    auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
#endif

    auto const elapsed1 = clock_t::now() - start;

#ifdef USE_RV3
    auto const found_index = ranges::distance(lengths
            | ranges::view::transform(ranges::convert_to<long>{})
            | ranges::view::partial_sum()
            | ranges::view::take_while([=](auto const i) { return !(to_find < i); }));
#else
    auto accumulated_length = 0l;
    auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
                                accumulated_length += val;
                                return to_find < accumulated_length;
                            });
    auto const found_index = std::distance(lengths.begin(), found);
#endif

    auto const elapsed2 = clock_t::now() - start;

    std::cout << "elapsed1: "
        << std::chrono::duration<double, std::milli>(elapsed1).count()
        << " ms, to_find: " << to_find << "\n"
           "elapsed2: "
        << std::chrono::duration<double, std::milli>(elapsed2).count()
        << " ms, result: " << found_index << '\n';
}

avec

g++-6 -std=c++14 -Ofast -march=native -DNDEBUG rv3.cpp -I ~/dev/range-v3/include -S -o -

à la fois sans et avec -DUSE_RV3 et différencier la sortie de l'assemblage est intéressant. Le code généré jusqu'à l'initialisation de elapsed1 est identique dans les deux cas. Il existe des différences notables dans la section intermédiaire entre les initialisations de elapsed1 y elapsed2 . gcc fait un bien meilleur travail d'optimisation de la version std : la boucle chaude est regroupée en un seul passage de code avec des branches pour les conditions de terminaison. La version range-v3 est plus moche et saute un peu partout ; je suppose que nous devons modifier les détails de l'implémentation de la fonction partial_sum pour le rendre plus transparent pour les optimiseurs.