Why is C array so much faster than std::array? [duplicate]

Question

We are currently writing some performance critical code in C++ that operates on many large matrices and vectors. Regarding to our research, there should be no major performance difference between std::array and standard C arrays (See This question or this). However, while testing we experienced a huge performance improvement by using C arrays over std::array. This is our demo code:

#include <iostream>
#include <array>
#include <sys/time.h>

#define ROWS 784
#define COLS 100
#define RUNS 50

using std::array;

void DotPComplex(array<double, ROWS> &result, array<double, ROWS> &vec1, array<double, ROWS> &vec2){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void DotPSimple(double result[ROWS], double vec1[ROWS], double vec2[ROWS]){
  for(int i = 0; i < ROWS; i++){
    result[i] = vec1[i] * vec2[i];
  }
}

void MatMultComplex(array<double, ROWS> &result, array<array<double, COLS>, ROWS> &mat, array<double, ROWS> &vec){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

void MatMultSimple(double result[ROWS], double mat[ROWS][COLS], double vec[ROWS]){
  for (int i = 0; i < COLS; ++i) {
      for (int j = 0; j < ROWS; ++j) {
        result[i] += mat[i][j] * vec[j];
      }
  }
}

double getTime(){
    struct timeval currentTime;
    gettimeofday(&currentTime, NULL);
    double tmp = (double)currentTime.tv_sec * 1000.0 + (double)currentTime.tv_usec/1000.0;
    return tmp;
}

array<double, ROWS> inputVectorComplex = {{ 0 }};
array<double, ROWS> resultVectorComplex = {{ 0 }};
double inputVectorSimple[ROWS] = { 0 };
double resultVectorSimple[ROWS] = { 0 };

array<array<double, COLS>, ROWS> inputMatrixComplex = {{0}};
double inputMatrixSimple[ROWS][COLS] = { 0 };

int main(){
  double start;
  std::cout << "DotP test with C array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPSimple(resultVectorSimple, inputVectorSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "DotP test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    DotPComplex(resultVectorComplex, inputVectorComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C array : " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultSimple(resultVectorSimple, inputMatrixSimple, inputVectorSimple);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;

  std::cout << "MatMult test with C++ array: " << std::endl;
  start = getTime();
  for(int i = 0; i < RUNS; i++){
    MatMultComplex(resultVectorComplex, inputMatrixComplex, inputVectorComplex);
  }
  std::cout << "Duration: " << getTime() - start << std::endl;
}

Compiled with: icpc demo.cpp -std=c++11 -O0 This is the result:

DotP test with C array: 
Duration: 0.289795 ms
DotP test with C++ array: 
Duration: 1.98413 ms
MatMult test with C array : 
Duration: 28.3459 ms
MatMult test with C++ array: 
Duration: 175.15 ms

With -O3 flag:

DotP test with C array: 
Duration: 0.0280762 ms
DotP test with C++ array: 
Duration: 0.0288086 ms
MatMult test with C array : 
Duration: 1.78296 ms
MatMult test with C++ array: 
Duration: 4.90991 ms

The C array implementation is much faster without compiler optimization. Why? Using compiler optimizations the dot products are equally fast. But for the matrix multiplication there is still a significant speedup when using C arrays. Is there a way to achieve equal performance when using std::array?

Update:

The compiler used: icpc 17.0.0

With gcc 4.8.5 our code runs much slower than with the intel compiler using any optimization level. Therefore we are mainly interested in the behaviour of the intel compiler.

As suggested by Jonas we adjusted RUNS 50.000 with the following results (intel compiler):

With -O0 flag:

DotP test with C array: 
Duration: 201.764 ms
DotP test with C++ array: 
Duration: 1020.67 ms
MatMult test with C array : 
Duration: 15069.2 ms
MatMult test with C++ array: 
Duration: 123826 ms

With -O3 flag:

DotP test with C array: 
Duration: 16.583 ms
DotP test with C++ array: 
Duration: 15.635 ms
MatMult test with C array : 
Duration: 980.582 ms
MatMult test with C++ array: 
Duration: 2344.46 ms

Also, you synthetic benchmark is not really useful. You are mostly measuring if the compiler can figure out that the result will unused (in which case all the computations can be left out) or constant (in which case the compilter could just do all the computations at compile time). In both cases, you aren't measuring anything useful. — Uli Schlachter
– Uli Schlachter, Commented Apr 3, 2017 at 11:11
Because you are paying an abstraction penalty because of function calls which aren't being inlined because you've disabled optimisation? — davmac
– davmac, Commented Apr 3, 2017 at 11:15
Enable optimisation if you want the compiler to optimise away abstractions. — Uli Schlachter
– Uli Schlachter, Commented Apr 3, 2017 at 11:16
On godbolt.org/g/9MnTLs, both MatMultComplex and MatMultSimple appear to produce identical assembly — eerorika
– eerorika, Commented Apr 3, 2017 at 11:16

Community · Accepted Answer · 2020-06-20 09:12:55Z

22

First up, the amount of runs you are using is simply too few. Personally, I did not realize (before running the code) that your "Duration" measurements are in miliseconds

By increasing the RUNS to 5,000,000 for DotPSimple and DotPComplex the timing are something like:

DotP test with C array:

Duration: 1074.89

DotP test with C++ array:

Duration: 1085.34

That is, they are very close to being equally fast. In fact, which ever was the fastest differed from test to test, due to the stochastic nature of a benchmark. The same was true for MatMultSimple and MatMultComplex, though they only needed 50,000 runs.

If you really want to measure and know more, you should embrace the stochastic nature of this benchmark and approximate the distributions of the "Duration" measurements. Including a random order of the functions, to remove any ordering bias.

EDIT: The assembly code (from user2079303's answer) prove outright that there are no differences with optimization enabled. Thus, the zero-cost abstractions are in fact zero-cost with optimization enabled, which is a reasonable requirement.

UPDATE:

The compiler I used:

g++ (Debian 6.3.0-6) 6.3.0 20170205

With the following command:

g++ -Wall -Wextra -pedantic -O3 test.cpp

Using this processor:

Intel(R) Core(TM) i5-4300U CPU @ 1.90GHz

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Apr 3, 2017 at 11:31

Jonas

7,0498 gold badges39 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

The Floe Over a year ago

Which compiler do you use and which optimization level. Increasing RUNS does not change the ratio at all in my case.

Jonas Over a year ago

@TheFloe I've updated my answer

eerorika · Accepted Answer · 2017-04-03 12:04:58Z

13

why ... is much faster without compiler optimization. Why?

For whatever reason the compiler chooses. If you don't let the compiler optimize, then you cannot expect two different pieces of code to have similar performance, even if they have identical behaviour. When optimization is enabled, the compiler may be able to transform the abstracted code into the efficient one, and the performance should be comparable.

The use of std::array involves function calls where the use of a pointer does not. For example, std::array::operator[] is a function, while the subscript operator of a pointer is not. Making a function call is potentially slower than not making a function call. All those function calls can be optimized away (expanded inline), but if you choose to not enable optimization, then the function calls remain.

But for the matrix multiplication there is still a significant speedup when using C arrays.

Probably a quirk in your benchmark, or the compiler. Here both functions have identical assembly, and so have identical performance

EDIT: I concur with Jonas' answer. The benchmark has way too few iterations. Also, it is not possible to say whether the difference between two measurements is significant without repeating the benchmark, and analysing the deviation.

The conclusios are:

The C array is not faster than std::array when optimization is enabled. At least not when compiling with clang 3.9.1 as demonstrated by the link. Perhaps your compiler produces different assembly, but I see no reason why it should.
The zero cost abstractions of C++ are zero cost only after optimization.
Writing meaningful micro benchmarks is not trivial.

edited Apr 3, 2017 at 12:04

answered Apr 3, 2017 at 11:21

eerorika

240k13 gold badges212 silver badges354 bronze badges

4 Comments

JeremyP Over a year ago

The C version of the matrix is not the same as the std::array version. The C array is simply a block of ROWS * COLS doubles. The std::array version is, at least conceptually an array of arrays. That means to fully dereference it requires two subscripting operations whereas the C version is one calculation. I am impressed that some modern C++ compilers are able to optimise the abstraction overhead away almost completely.

eerorika Over a year ago

@JeremyP surely a 2D array is also conceptually an array of arrays. The only difference that I see is the fact that the two dereferences of std::array are within separate (inline) function calls, so it might be sensitive to order of optimization passes. The functions must be expanded before the dereferences can be merged, while the two dereferences of the pointer are there even before inlining. Frankly, I would have been disappointed if the assembly output wasn't (at least almost) identical.

The Floe Over a year ago

@user2079303 I partially agree with your answer. Increasing RUNS doesn't change the behavior with our compiler. The ratio remains the same. I figured that there is a "quirck in benchmark" after following Uli Schlachters comment: If the results from the functions are actually used after calculating, both implementation perform approximately equal.

eerorika Over a year ago

@TheFloe I recommend to compare the assembly output given by your compiler and see how they differ.

Collectives™ on Stack Overflow

Why is C array so much faster than std::array? [duplicate]

2 Answers 2

2 Comments

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Linked

Related