CODEWITHSUNDEEP
c++vector
24n8
24n8

Reputation: 2236

Why does switching the order of for loops significantly change the execution time?

In the following code, I have 2 nested for loops. The second one swaps the order of the for loops, and runs significantly faster.

Is this purely a cache locality issue (the first code loops over a vector many times, whereas the second code loops over the vector once), or is there something else that I'm not understanding? 

int main() 
{ 
  using namespace std::chrono;
  auto n = 1 << 12;
  vector<int> v(n);

  high_resolution_clock::time_point t1 = high_resolution_clock::now();
  for(int i = 0; i < (1 << 16); ++i)
  {
    for(const auto val : v) i & val;
  }
  high_resolution_clock::time_point t2 = high_resolution_clock::now();
  duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
  std::cout << "It took me " << time_span.count() << " seconds.";
  std::cout << std::endl;

  t1 = high_resolution_clock::now();
  for(const auto val : v)
  {
     for(int i = 0; i < (1 << 16); ++i) i & val;
  }
  t2 = high_resolution_clock::now();
  time_span = duration_cast<duration<double>>(t2 - t1);
  std::cout << "It took me " << time_span.count() << " seconds.";
  std::cout << std::endl;
}

Upvotes: 0

Views: 279

Answers (1)

gnasher729
gnasher729

Reputation: 52612

As written, the second loop needs to read each val from vector v only once. The first version needs to read each val from vector v once in the inner loop for every i, so in total 65536 times.

So without any optimisation, this will make the second loop several times faster. With optimisation turned on high enough, the compiler will figure out that all these calculations achieve nothing, and are unnecessary, and throw them all away. Your execution times will then go down to zero.

If you change the code to do something with the results (like adding up all values i & val, then printing the total), a really good compiler may figure out that both pieces of code produce the same result and use the faster method for both cases.

Upvotes: 1

Related Questions