c++ - ¿Por qué es std:: acumular tan lento?

performance optimization

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Por qué acumular es más rápido que un ciclo simple? 3 respuestas

Estoy tratando de sumar elementos de matriz utilizando un bucle for simple, un std::accumulate y un bucle enrollado manualmente para. Como es de esperar, el bucle desenrollado manualmente es el más rápido, pero más interesante es que std :: acumulación es mucho más lento que el bucle simple. Este es mi código, lo compilé con gcc 4.7 con el indicador -O3. Visual Studio necesitará una implementación diferente de la función rdtsc.

#include <iostream>
#include <algorithm>
#include <numeric>
#include <stdint.h>


using namespace std;

__inline__ uint64_t rdtsc() {
  uint64_t a, d;
  __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
  return (d<<32) | a;
}

class mytimer
{
 public:
  mytimer() { _start_time = rdtsc(); }
  void   restart() { _start_time = rdtsc(); }
  uint64_t elapsed() const
  { return  rdtsc() - _start_time; }

 private:
  uint64_t _start_time;
}; // timer

int main()
{
    const int num_samples = 1000;
    float* samples = new float[num_samples];
    mytimer timer;
    for (int i = 0; i < num_samples; i++) {
        samples[i] = 1.f;
    }
    double result = timer.elapsed();
    std::cout << "rewrite of " << (num_samples*sizeof(float)/(1024*1024)) << " Mb takes " << result << std::endl;

    timer.restart();
    float sum = 0;
    for (int i = 0; i < num_samples; i++) {
        sum += samples[i];
    }
    result = timer.elapsed();
    std::cout << "naive:/t/t" << result << ", sum = " << sum << std::endl;

    timer.restart();
    float* end = samples + num_samples;
    sum = 0;
    for(float* i = samples; i < end; i++) {
        sum += *i;
    }
    result = timer.elapsed();
    std::cout << "pointers:/t/t" << result << ", sum = " << sum << std::endl;

    timer.restart();
    sum = 0;
    sum = std::accumulate(samples, end, 0);
    result = timer.elapsed();
    std::cout << "algorithm:/t" << result << ", sum = " << sum << std::endl;

    // With ILP
    timer.restart();
    float sum0 = 0, sum1 = 0;
    sum = 0;
    for (int i = 0; i < num_samples; i+=2) {
        sum0 += samples[i];
        sum1 += samples[i+1];
    }
    sum = sum0 + sum1;
    result = timer.elapsed();
    std::cout << "ILP:/t/t" << result << ", sum = " << sum << std::endl;
}

Answer 1

Como a usted (aparentemente) le importa hacer esto rápido, también podría considerar tratar de multiprocilar el cálculo para aprovechar todos los núcleos disponibles. Hice una reescritura bastante trivial de tu bucle ingenuo para usar OpenMP, dando esto:

timer.restart();
sum = 0;

// only real change is adding the following line:
#pragma omp parallel for schedule(dynamic, 4096), reduction(+:sum)
for (int i = 0; i < num_samples; i++) {
    sum += samples[i];
}
result = timer.elapsed();
std::cout << "OMP:/t/t" << result << ", sum = " << sum << std::endl;

Solo para sonreír, también reescribí un poco en su bucle desenrollado para permitir el desenrollamiento semi-arbitrario, y también agregué OpenMP:

static const int unroll = 32;
real total = real();
timer.restart();
double sum[unroll] = { 0.0f };
#pragma omp parallel for reduction(+:total) schedule(dynamic, 4096)
for (int i = 0; i < num_samples; i += unroll) {
    for (int j = 0; j < unroll; j++)
        total += samples[i + j];
}
result = timer.elapsed();
std::cout << "ILP+OMP:/t" << result << ", sum = " << total << std::endl;

También aumenté el tamaño de la matriz (sustancialmente) para obtener números un tanto más significativos. Los resultados fueron los siguientes. Primero para un AMD de doble núcleo:

rewrite of 4096 Mb takes 8269023193
naive:          3336194526, sum = 536870912
pointers:       3348790101, sum = 536870912
algorithm:      3293786903, sum = 536870912
ILP:            2713824079, sum = 536870912
OMP:            1885895124, sum = 536870912
ILP+OMP:        1618134382, sum = 536870912

Entonces para un quad-core (Intel i7):

rewrite of 4096 Mb takes 2415836465
naive:          1382962075, sum = 536870912
pointers:       1675826109, sum = 536870912
algorithm:      1748990122, sum = 536870912
ILP:            751649497, sum = 536870912
OMP:            575595251, sum = 536870912
ILP+OMP:        450832023, sum = 536870912

Desde el punto de vista de las cosas, las versiones de OpenMP probablemente tienen limitaciones en el ancho de banda de la memoria; las versiones de OpenMP hacen más uso de la CPU que las versiones sin subprocesos, pero aún así alcanzan alrededor del 70% aproximadamente, lo que indica otras La CPU está actuando como un cuello de botella.

Answer 2

Para empezar, su uso de std::accumulate es sumar enteros. Por lo tanto, es probable que esté pagando el costo de convertir cada punto flotante en entero antes de agregarlo. Tratar:

sum = std::accumulate( samples, end, 0.f );

y ver si eso no hace una diferencia.