-
Continued from http://en.sfml-dev.org/forums/index.php?topic=10046.msg69235#msg69235
I have written a benchmark to compare iteration through random access containers. The code is rather complex, because I tried to make the comparison as fair as possible. Every iteration is executed multiple times, and the different iterations are executed in random order to reduce uneven conditions.
Comparison
Iterations: iterator, operator[]
Containers: std::vector, std::deque
Element types: int, std::string
Code
#include <SFML/System/Clock.hpp>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <array>
#include <functional>
#include <algorithm>
#include <cstdlib>
inline void compute(int& v) { v = (v + 25) % 13; }
inline void compute(std::string& v) { v = "x"; }
template <typename Container>
sf::Time testIterator(Container& c)
{
sf::Clock clock;
for (auto itr = c.begin(), end = c.end(); itr != end; ++itr)
compute(*itr);
return clock.getElapsedTime();
}
template <typename Container>
sf::Time testIndex(Container& c)
{
sf::Clock clock;
for (std::size_t i = 0, size = c.size(); i != size; ++i)
compute(c[i]);
return clock.getElapsedTime();
}
template <typename T>
void benchmark(std::map<std::string, sf::Time>& times, const std::string& type, std::size_t elements)
{
std::vector<T> vector(elements);
std::deque<T> deque(elements);
std::array<std::function<void()>, 4> array =
{
[&] () { times["vector<" + type + "> iterator"] += testIterator(vector); },
[&] () { times[" deque<" + type + "> iterator"] += testIterator(deque); },
[&] () { times["vector<" + type + "> index "] += testIndex(vector); },
[&] () { times[" deque<" + type + "> index "] += testIndex(deque); },
};
// Make sure the single tests are executed in random order
std::random_shuffle(array.begin(), array.end());
std::for_each(array.begin(), array.end(), [] (std::function<void()>& fn) { fn(); });
// Prevent optimization of unused containers
if (std::rand() < 0)
std::cout << vector[std::rand() % vector.size()] << deque[std::rand() % deque.size()];
}
int main()
{
std::map<std::string, sf::Time> times;
const std::size_t outer = 10000;
const std::size_t inner = 100000;
for (std::size_t m = 0; m < outer; ++m)
{
benchmark<int> (times, "int ", inner);
benchmark<std::string>(times, "string", inner);
}
for (auto itr = times.begin(); itr != times.end(); ++itr)
std::cout << itr->first << " " << std::setw(6) << std::right << itr->second.asMilliseconds() << "\n";
std::cin.get();
}
Results
VC++ 10, Release mode, without debugger, NDEBUG defined
deque<int > index 10779
deque<int > iterator 4884
deque<string> index 20268
deque<string> iterator 14991
vector<int > index 4711
vector<int > iterator 4764
vector<string> index 13953
vector<string> iterator 13459
g++ 4.6.2 (MinGW), -std=c++0x -O2 -DNDEBUG
deque<int > index 5456
deque<int > iterator 4914
deque<string> index 45758
deque<string> iterator 42905
vector<int > index 4896
vector<int > iterator 4908
vector<string> index 42874
vector<string> iterator 42547
Conclusions
For std::vector, both index operator and iterator take more or less the same execution time.
For std::deque, iterator is a clear winner, especially on VC++.
Tell me when you see any flaws in the code or the compiler flags. Of course, the rather simple operations in the loop are not representative of every possible iteration use case. However, the more complex the loop body becomes, the more time it takes to execute, while iteration itself becomes more negligible.
Since iterators are not slower, I suggest to follow the simple rule:
Use iterators when you iterate and index operator when you need random access. :)
-
I 'quickly' ran the benchmark first on GCC and then on VC++. With GCC I really started to wonder if it would ever finish...
Does anyone have an explanation, why GCC needs 170 seconds to run the string tests, while VC++ manages it in 13-26 seconds? ???
Does the static linkage of sfml-system have an influence on the performance?
VC++ 11, Release mode, /O2, without debugger, NDEBUG & SFML_STATIC defined
deque<int > index 15328
deque<int > iterator 4823
deque<string> index 26747
deque<string> iterator 15815
vector<int > index 4524
vector<int > iterator 4515
vector<string> index 13540
vector<string> iterator 13539
VC++ 11, Release mode, /O2, without debugger, NDEBUG & SFML_STATIC defined, static runtime lib
deque<int > index 15071
deque<int > iterator 4869
deque<string> index 24463
deque<string> iterator 14498
vector<int > index 4540
vector<int > iterator 4513
vector<string> index 12050
vector<string> iterator 12301
GCC 4.7.2 (MinGW), -std=c++11 -O2 -DNDEBUG -DSFML_STATIC
deque<int > index 4592
deque<int > iterator 4401
deque<string> index 171719
deque<string> iterator 171166
vector<int > index 4428
vector<int > iterator 4441
vector<string> index 170266
vector<string> iterator 170240
GCC 4.7.2 (MinGW), -std=c++11 -O2 -DNDEBUG -DSFML_STATIC, static runtime lib
deque<int > index 4682
deque<int > iterator 4488
deque<string> index 174566
deque<string> iterator 173684
vector<int > index 4451
vector<int > iterator 4459
vector<string> index 172912
vector<string> iterator 173383
-
What about adding iteration over a vector with pointer to test? Yes, I know, pointers are evil, but vector iterators behave a lot like them.
-
What about adding iteration over a vector with pointer to test? Yes, I know, pointers are evil, but vector iterators behave a lot like them.
I'm not sure if there's a defined/safe way to do it.
I guess you could simply get the address of the first element and then add the wanted offset. Maybe for comparison one could use it, but for all the rest it's not really important... ;)
-
I'm not sure if there's a defined/safe way to do it.
Yes, the memory in std::vector is contiguous.
But I would be surprised if there were a difference to iterators. Actually, an implementation may even take pointers as iterators.
-
Sure you can, pointer arithmetics inside array and one element past it are well defined(I actually used to think they always are, but that is good enough). And that's how you should work with C-ish code that requires const char * and takes first element pointer and count for arrays(like Box2D does...).
std::string line;
//fill line however..
someCishStringFun(line.c_str());
std::vector<int> vec;
//fill vec
someCishArrayFun(vec.empty()?0x0:&vec[0],vec.size());
And iteration:
for(int * it,* end=(it=vec.empty()?0x0:&vec[0])+vec.size();it!=end;++it)
{
//whatever operations with iterator syntax
}
-
Since iterators are not slower, I suggest to follow the simple rule:
Use iterators when you iterate and index operator when you need random access. :)
Actually since std::vector's iterator is a Random Access Iterator, I wouldn't be surprised if doing iterator arithmetic would be just as fast/faster than indexing in some implementations. If so then using those implementations, iterators would always be faster than indexing no matter what your access patterns are.
-
What about adding iteration over a vector with pointer to test? Yes, I know, pointers are evil, but vector iterators behave a lot like them.
Following changes:
// added function template
template <typename Container>
sf::Time testPointer(Container& c)
{
sf::Clock clock;
for (auto ptr = c.data(), end = c.data() + c.size(); ptr != end; ++ptr)
compute(*ptr);
return clock.getElapsedTime();
}
// modified inside benchmark()
std::vector<T> vector(elements);
std::array<std::function<void()>, 3> array =
{
[&] () { times["vector<" + type + "> iterator"] += testIterator(vector); },
[&] () { times["vector<" + type + "> index "] += testIndex(vector); },
[&] () { times["vector<" + type + "> pointer "] += testPointer(vector); },
};
VC++ 10, Release mode, /O2, without debugger, NDEBUG defined
vector<int > index 4718
vector<int > iterator 4722
vector<int > pointer 4699
vector<string> index 13421
vector<string> iterator 13697
vector<string> pointer 13738
g++ 4.6.2 (MinGW), -std=c++0x -O2 -DNDEBUG
vector<int > index 4854
vector<int > iterator 4833
vector<int > pointer 4811
vector<string> index 30756
vector<string> iterator 29864
vector<string> pointer 29959
As expected, pointer iteration has the same performance. Therefore one should prefer iterators, since they can be used for all containers and they provide helpful checks in debug mode.
By the way, the range [vector.data(), vector.data() + vector.size()[ is always a valid iterator range, there is no need to check for empty(). I think your code would be ill-formed anyway, because the 2nd and 3rd operand of operator?: must have the same type.
-
Actually since std::vector's iterator is a Random Access Iterator, I wouldn't be surprised if doing iterator arithmetic would be just as fast/faster than indexing in some implementations.
We only consider containers with random access iterators, because they are the only ones who provide the index operator. And yes, in these cases, iterators are as fast or faster than operator[] for iteration :) In fact it would be surprising if the standard library writers implemented iterators slower than index access. Because in the worst case, they could still implement iterators via indices without loss of performance -- but not necessarily the other way around.
What I wanted to show is that your statement "Traversing a container with an iterator is more expensive than using direct array indexing if you don't intend to modify the container" does not hold, instead even the opposite may be true ;)
-
I think your code would be ill-formed anyway, because the 2nd and 3rd operand of operator?: must have the same type.
second is 0x0, which is what NULL is in c++98 and can be implicitly casted to any pointer, just like nullptr in 11
third is &vec[0], which is pointer to int
Maybe visual decided to compile code that isn't strictly standard conforming(WHY would it do that.. right? ;)).
But yes, that's not optimal, I always use iterators so I didn't know about data() and adding 0 to NULL pointer might be undefined, I'm not sure.
@Edit: Well, data seems to be c++11 addition, so no wonder I didn't encounter it in c++98. ;D
-
What I wanted to show is that your statement "Traversing a container with an iterator is more expensive than using direct array indexing if you don't intend to modify the container" does not hold, instead even the opposite may be true ;)
I think we can agree that theoretically and from a syntactic point of view indexing shouldn't be slower than iterators. It is non-intuitive that creating an object just to iterate over a serial container is less costly than just using an index to address its elements. This comes from the fact that iterators have been subject to so many different optimizations over the past generations of compilers whereas normal indexing probably produces the same code as it did 14 years ago. From a technological standpoint this is probably also a good thing because in C++11 I use range based for all the time and they expand to iterator access.
Maybe my statements have to be signed with "this applies to pre C++0x compilers" but if you ask me, "simple indexing" has been neglected by the optimization teams in the recent years ;).
-
Does anyone have an explanation, why GCC needs 170 seconds to run the string tests, while VC++ manages it in 13-26 seconds? ???
I'm not entirely sure if it's still the case, but VC++ has always used SSO, so this type of operation on a very small string is cheap. GCC, on the other hand, has traditionally used a reference-counted copy-on-write implementation. I would assume that's the difference you're seeing here.
If that is the case,
inline void compute(std::string& v) { v = "x"; }
being changed to:
std::string x("x");
inline void compute(std::string& v) { v = x; }
might be a better measure of iteration performance.
-
I'm not entirely sure if it's still the case, but VC++ has always used SSO, so this type of operation on a very small string is cheap. GCC, on the other hand, has traditionally used a reference-counted copy-on-write implementation. I would assume that's the difference you're seeing here.
Thanks for the information! :)
The given modification really makes quite a big difference:
vector<int > index 4469
vector<int > iterator 4528
vector<int > pointer 4506
vector<string> index 157884
vector<string> iterator 157176
vector<string> pointer 157706
vs.vector<int > index 4449
vector<int > iterator 4438
vector<int > pointer 4440
vector<string> index 39906
vector<string> iterator 39463
vector<string> pointer 39637
-
I think we can agree that theoretically and from a syntactic point of view indexing shouldn't be slower than iterators. It is non-intuitive that creating an object just to iterate over a serial container is less costly than just using an index to address its elements.
No -- the notion "object" may imply something heavy, which is misleading. An iterator can use specific knowledge about the container to its advantage. It can exploit implementation details. An index operator only gets a generic integer, it has to compute a way to access elements from it. For every single access, independent of the underlying container's complexity.
For example, an iterator could store a direct pointer to the element, for fast access (and possibly slower increment) -- a design option an index operator never has.
This comes from the fact that iterators have been subject to so many different optimizations over the past generations of compilers whereas normal indexing probably produces the same code as it did 14 years ago.
Especially the optimizers have become really good in the past years, as a result of which std::vector<T>::iterator can be treated like a T*.
-
I really felt I should log in just because I had a similar kind of optimisation concern just today!
Would you mind trying to ad another random access test using the ::at() member function on both containers?
My bet is that this is where the difference lies... since .at() and [] operator have different rules for bounds checking on different containers.
Hope my thinking is communicated and I would appreciate it if any1 could try this (I wish I could but I am hard pressed at this point..sorry).