benchmarking std::vector
January 12th, 2010
No comments
so i always wondered whats the fastest way is to iterate over a vector. So with this little snippet you can find out for yourself:
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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 | // some simple std::vector benchmark tool // Jan 2010, thomas{AT}thomasfischer{DOT}biz // also see http://stackoverflow.com/questions/776624/whats-faster-iterating-an-stl-vector-with-vectoriterator-or-with-at #include <stdio.h> #include <vector> #include "Timer.h" #define VECSIZE 500000 typedef struct foo_t { char tmp[2]; } foo_t; int main(int argc, char **argv) { int amount = VECSIZE; int tests = 10; printf("testing with %d elements a %d bytes (%0.2f MB) and %d runs per test\n", amount, sizeof(foo_t), (amount*sizeof(foo_t))/1024.0f/1024.0f, tests); double time = 0.0f; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; vec.reserve(amount); foo_t f; // with random data in it Timer *t = new Timer(); for(int i=0;i<amount;i++) vec.push_back(f); time += t->elapsed(); } printf("add time (resized before): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; foo_t f; // with random data in it Timer *t = new Timer(); for(int i=0;i<amount;i++) vec.push_back(f); time += t->elapsed(); } printf("add time (dynamic resize): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; foo_t f; // with random data in it for(int i=0;i<amount;i++) vec.push_back(f); Timer *t = new Timer(); for(std::vector<foo_t>::iterator it=vec.begin(); it!=vec.end(); it++) { // some example usage it->tmp[1] = 0; } time += t->elapsed(); } printf("iterate time (version #1): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; foo_t f; // with random data in it for(int i=0;i<amount;i++) vec.push_back(f); Timer *t = new Timer(); std::vector<foo_t>::iterator vecEnd = vec.end(); for(std::vector<foo_t>::iterator it=vec.begin(); it!=vecEnd; ++it) { // some example usage it->tmp[1] = 0; } time += t->elapsed(); } printf("iterate time (version #2): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; foo_t f; // with random data in it for(int i=0;i<amount;i++) vec.push_back(f); Timer *t = new Timer(); for(int i=0; i<amount; i++) { // some example usage vec[i].tmp[1] = 0; } time += t->elapsed(); } printf("iterate time (version #3): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { std::vector<foo_t> vec; foo_t f; // with random data in it for(int i=0;i<amount;i++) vec.push_back(f); Timer *t = new Timer(); for(unsigned int i=0; i<vec.size(); ++i) { // some example usage vec.at(i).tmp[1] = 0; } time += t->elapsed(); } printf("iterate time (version #4): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { foo_t vec[VECSIZE]; Timer *t = new Timer(); for(int i=0; i<amount; ++i) { // some example usage vec[i].tmp[1] = 0; } time += t->elapsed(); } printf("iterate over array (version #1): %f\n", time/tests); time=0; for(int i=0;i<tests;i++) { foo_t *vec = (foo_t *)malloc(sizeof(foo_t) * amount); Timer *t = new Timer(); for(int i=0; i<amount; ++i) { // some example usage vec[i].tmp[1] = 0; } time += t->elapsed(); free(vec); } printf("iterate over array (version #2): %f\n", time/tests); return 0; } |
to compile, add the Timer.h from my previous post 
which results in the following output on my windows machine (/Oi /O2)
testing with 500000 elements a 2 bytes (0.95 MB) and 10 runs per test add time (resized before): 0.005281 add time (dynamic resize): 0.007693 iterate time (version #1): 0.004180 iterate time (version #2): 0.004107 iterate time (version #3): 0.000903 iterate time (version #4): 0.004891 iterate over array (version #1): 0.000277 iterate over array (version #2): 0.000773
what are your results?
