C++

Forum

 
Differences in iteration speed

JayhawkZombie (738)
I never thought about it until recently, but what might cause the overhead of iterating through std::vector?

TestItem.h
1
2
3
4
5
6
7
8
9
10
11
 
class TestItem
{
public:
  TestItem() = default;
  ~TestItem() = default;

  void update();

private:

};


TestItem.cpp
1
2
3
4
5
6
7
8
9
10
 
void TestItem::update()
{
  //Some somewhat compelx calculations go here
  //Just whatever
  for (int i = 0; i < 1000; i++) {
    i += i;
  }

  return;
}


main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include "TestItem.h"

#include <string>
#include <vector>
#include <chrono>
#include <iostream>


int main()
{
  float VecDeltaAverage = 0, VecDeltaIteratorAverage = 0, ArrDeltaAverage = 0;
  std::uint32_t count = 0;

  std::chrono::duration<float, std::milli> VecDelta(0);
  std::chrono::system_clock::time_point VecTimeBegin;
  std::chrono::system_clock::time_point VecTimeEnd;

  std::chrono::duration<float, std::milli> VecIteratorDelta(0);
  std::chrono::system_clock::time_point VecIteratorTimeBegin;
  std::chrono::system_clock::time_point VecIteratorTimeEnd;

  std::chrono::duration<float, std::milli> ArrDelta(0);
  std::chrono::system_clock::time_point ArrTimeBegin;
  std::chrono::system_clock::time_point ArrTimeEnd;

  std::vector<TestItem> ItemVector(400);
  TestItem item;
  for (int i = 0; i < 400; i++) {
    ItemVector.push_back(item);
  }

  TestItem *ItemArray = new TestItem[400];

  while (count < 10) {
  //Test vector using iterator
    VecIteratorTimeBegin = std::chrono::system_clock::now();
    for (auto & item : ItemVector)
      item.update();
    VecIteratorTimeEnd = std::chrono::system_clock::now();
    VecIteratorDelta = VecIteratorTimeEnd - VecIteratorTimeBegin;

    //Test vector using regular iteration
    VecTimeBegin = std::chrono::system_clock::now();
    for (int i = 0; i < 400; i++) {
      ItemVector[i].update();
    }
    VecTimeEnd = std::chrono::system_clock::now();
    VecDelta = VecTimeEnd - VecTimeBegin;

    ArrTimeBegin = std::chrono::system_clock::now();
    for (int i = 0; i < 400; i++) {
      ItemArray[i].update();
    }
    ArrTimeEnd = std::chrono::system_clock::now();
    ArrDelta = ArrTimeEnd - ArrTimeBegin;

    std::cout << "-----Iteration: " << count << "------------------" << std::endl;
    std::cout << "Time for vector iterator : " << VecIteratorDelta.count() << std::endl;
    std::cout << "Time for vector int count: " << VecDelta.count() << std::endl;
    std::cout << "Time for array           : " << ArrDelta.count() << std::endl;

    VecDeltaAverage += VecDelta.count();
    VecDeltaIteratorAverage += VecIteratorDelta.count();
    ArrDeltaAverage += ArrDelta.count();

    count++;
  }

  VecDeltaAverage /= count;
  VecDeltaIteratorAverage /= count;
  ArrDeltaAverage /= count;

  std::cout << "\nAverage over " << count << " runs -----------------" << std::endl;
  std::cout << "Vector iterator : " << VecDeltaIteratorAverage << std::endl;
  std::cout << "Vector int count: " << VecDeltaAverage << std::endl;
  std::cout << "Array iteration : " << ArrDeltaAverage << std::endl;

  delete[] ItemArray;

  return 0;
}


Running it many times, it outputs times similar to:
-----Iteration: 0------------------
Time for vector iterator : 0.2557
Time for vector int count: 0.1166
Time for array           : 0.0232
-----Iteration: 1------------------
Time for vector iterator : 0.2443
Time for vector int count: 0.1159
Time for array           : 0.0236
-----Iteration: 2------------------
Time for vector iterator : 0.244
Time for vector int count: 0.1154
Time for array           : 0.0233
-----Iteration: 3------------------
Time for vector iterator : 0.2436
Time for vector int count: 0.1154
Time for array           : 0.0249
-----Iteration: 4------------------
Time for vector iterator : 0.2436
Time for vector int count: 0.1166
Time for array           : 0.0233
-----Iteration: 5------------------
Time for vector iterator : 0.2443
Time for vector int count: 0.1151
Time for array           : 0.0232
-----Iteration: 6------------------
Time for vector iterator : 0.2455
Time for vector int count: 0.1158
Time for array           : 0.0233
-----Iteration: 7------------------
Time for vector iterator : 0.2491
Time for vector int count: 0.1155
Time for array           : 0.0233
-----Iteration: 8------------------
Time for vector iterator : 0.2557
Time for vector int count: 0.1151
Time for array           : 0.0236
-----Iteration: 9------------------
Time for vector iterator : 0.2439
Time for vector int count: 0.1183
Time for array           : 0.0236

Average over 10 runs -----------------
Vector iterator : 0.24697
Vector int count: 0.11597
Array iteration : 0.02353


Iterating through a vector rather an a raw array takes... 10 times as long?! I knew there would be a time difference, but I don't really understand why it would be so much slower. It seems using a range-based for loop is was the slowest, iterating through using [] was the middle guy, but iterating through a raw array was the fastest, 1/10th the time of using iterators and 1/5th the time of iterating through a vector using [].

I don't think I understand enough about how C++ works under the hood to really understand why there's such a massive time difference. Can anyone perhaps enlighten me? Clearly this doesn't make much of a difference for a small number of elements, but can for a very large number of elements.
Using std::chrono::system_clock instead of std::chrono::high_resolution_clock to only include time spent inside the program's execution.
helios (17575)
Your code contains bugs. The loop starting at line 28 doubles the size of the vector, so the ranged for performs twice as much work as the array loop.

Average over 50 runs -----------------
Vector iterator : 6.37506
Vector int count: 6.574
Array iteration : 6.52352

The code generated by ranged for is generally the most optimal because the compiler can make stronger assumptions.
If you are seeing huge performance differences when using std::vector vs. raw arrays, turn on optimizations.
Last edited on
JayhawkZombie (738)
Well, pardon my stupid mistake.
I did still see some big differences after fixing that, but turning on optimizations fixed it. Regular iteration in the array was then the slowest.
My computer gives everything as 0ms, but shows ranged for loop as faster if I slow it down.
Thanks for pointing that out :)
*facepalm*
Last edited on
Topic archived. No new replies allowed.