c++arraysperformanceoptimizationinner-product

std::inner_product 4x faster than manual but no SIMD being used?


I was interested how std::inner_product() performs compared with a manual dot-product calculation, so I did a test.

std::inner_product() was 4x faster than the manual implementation. I find this odd because there aren't really that many ways to calculate it, surely?! I also cannot see any SSE/AVX registers being used at the point of calculation.

Setup: VS2013/MSVC(12?), Haswell i7 4770 CPU, 64-bit compilation, release mode.

Here is the C++ test code:

#include <iostream>
#include <functional>
#include <numeric>
#include <cstdint>

int main() {
   const int arraySize = 1000;
   const int numTests = 500;
   unsigned int x, y = 0;
   unsigned long long* array1 = new unsigned long long[arraySize];
   unsigned long long* array2 = new unsigned long long[arraySize];

   //Initialise arrays
   for (int i = 0; i < arraySize; i++){
      unsigned long long val = __rdtsc();
      array1[i] = val;
      array2[i] = val;
   }

   //std::inner_product test
   unsigned long long timingBegin1 = __rdtscp(&s);
   for (int i = 0; i < numTests; i++){
      volatile unsigned long long result = std::inner_product(array1, array1 + arraySize, array2, static_cast<uint64_t>(0));
   }
   unsigned long long timingEnd1 = __rdtscp(&s);

   f, s = 0;

   //Manual Dot Product test
   unsigned long long timingBegin2 = __rdtscp(&f);
   for (int i = 0; i < numTests; i++){
      volatile unsigned long long result = 0;

      for (int i = 0; i < arraySize; i++){
         result += (array1[i] * array2[i]);
      }
   }
   unsigned long long timeEnd2 = __rdtscp(&f);


   std::cout << "STL:     :  " << static_cast<double>(finish1 - start1) / numTests << " CPU cycles per dot product" << std::endl;
   std::cout << "Manually :  " << static_cast<double>(finish2 - start2) / numTests << " CPU cycles per dot product" << std::endl;

Solution

  • Your test is bad, and this is likely to make a big difference.

    volatile uint64_t result = 0;
    
    for (int i = 0; i < arraySize; i++){
       result += (array1[i] * array2[i]);
    

    Note how you're continually using the volatile-qualified variable here. This forces the compiler to write the temporary results to memory.

    In contrast, your inner_product version:

    volatile uint64_t result = std::inner_product(array1, array1 + arraySize, array2, static_cast<uint64_t>(0));
    

    first calculates the inner product, allowing optimisations, and only then assigns the result to a volatile-qualfied variable.