c++ - ¿Por qué es Range-v3 más lento que el STL en este ejemplo?

performance

Question

Estoy jugando con la biblioteca Range-v3 para realizar un find_if glorificado y tenía curiosidad por la razón por la cual google-benchmark siempre califica mi código Range-v3 peor que mi enfoque std::find_if . Tanto g ++ como clang dan el mismo patrón con -O3 y #define NDEBUG .

El ejemplo específico que tengo en mente es el siguiente usando el 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);

Esto es algo artificial para el propósito de esta ilustración, pero generalmente habría un generador aleatorio para la variable to_find y valores aleatorios en el vector de lengths .

Usando la librería Range-v3, obtengo el siguiente código

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

Mi pregunta es por qué el Range-v3 es más lento que la implementación de STL. Entiendo que esto todavía es una biblioteca experimental, pero tal vez haya algún problema con el ejemplo del código o ¿estoy haciendo un mal uso de los conceptos de rango?

Editar

Un ejemplo de controlador de google-bench (no estoy seguro si es correcto)

#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();

Da

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

con clang 4.0.1 y

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

con gcc 6.3.1. Mi máquina tiene un procesador de generación Haswell. Ambos fueron compilados y ejecutados con

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 sobre un rango de int produce un rango de int . Si to_find > INT_MAX , el acumulador interno se desbordará dando como resultado UB. En la práctica, lo más probable es que el algoritmo recorra toda la entrada y devuelva el iterador final.

A la inversa, su long accumulated_length en el enfoque sin rango-v3 es long . No se desborda y, por lo tanto, ha definido el comportamiento / las devoluciones antes de procesar toda la entrada.

El enfoque de rango v3 tendrá un comportamiento correcto si transform el rango de entrada en un rango de long antes de pasarlo a través de 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; }));

Incluso con esta corrección de corrección, sigue siendo notablemente más lento que el uso de los algoritmos estándar en mis pruebas. Compilando este programa de prueba:

#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'';
}

con

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

Tanto sin como con -DUSE_RV3 y diferenciar la salida del ensamblaje es interesante. El código generado hasta la inicialización de elapsed1 es idéntico para ambos casos. Existen diferencias notables en la sección intermedia entre las inicializaciones de elapsed1 y elapsed2 . gcc hace un trabajo mucho mejor de optimización de la versión estándar: el bucle caliente está todo junto en un solo código ejecutado con sucursales para condiciones de terminación. La versión de range-v3 es más fea y salta un poco; Especulo que necesitamos cambiar los detalles de la implementación de partial_sum para que sea más transparente para los optimizadores.