Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Random access iteration benchmark  (Read 8643 times)

0 Members and 1 Guest are viewing this topic.

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Random access iteration benchmark
« on: December 25, 2012, 01:05:48 pm »
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. :)
« Last Edit: December 25, 2012, 01:09:33 pm by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 10930
    • View Profile
    • development blog
    • Email
Re: Random access iteration benchmark
« Reply #1 on: December 25, 2012, 02:42:38 pm »
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
 
« Last Edit: December 25, 2012, 03:11:52 pm by eXpl0it3r »
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

FRex

  • Hero Member
  • *****
  • Posts: 1848
  • Back to C++ gamedev with SFML in May 2023
    • View Profile
    • Email
Re: Random access iteration benchmark
« Reply #2 on: December 25, 2012, 02:48:44 pm »
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.
Back to C++ gamedev with SFML in May 2023

eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 10930
    • View Profile
    • development blog
    • Email
Re: Random access iteration benchmark
« Reply #3 on: December 25, 2012, 02:56:39 pm »
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... ;)
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Random access iteration benchmark
« Reply #4 on: December 25, 2012, 03:15:19 pm »
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.
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

FRex

  • Hero Member
  • *****
  • Posts: 1848
  • Back to C++ gamedev with SFML in May 2023
    • View Profile
    • Email
Re: Random access iteration benchmark
« Reply #5 on: December 25, 2012, 03:26:17 pm »
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
}
 
Back to C++ gamedev with SFML in May 2023

binary1248

  • SFML Team
  • Hero Member
  • *****
  • Posts: 1405
  • I am awesome.
    • View Profile
    • The server that really shouldn't be running
Re: Random access iteration benchmark
« Reply #6 on: December 25, 2012, 05:18:05 pm »
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.
SFGUI # SFNUL # GLS # Wyrm <- Why do I waste my time on such a useless project? Because I am awesome (first meaning).

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Random access iteration benchmark
« Reply #7 on: December 26, 2012, 10:45:48 am »
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.
« Last Edit: December 26, 2012, 12:46:26 pm by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Random access iteration benchmark
« Reply #8 on: December 26, 2012, 11:02:58 am »
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 ;)
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

FRex

  • Hero Member
  • *****
  • Posts: 1848
  • Back to C++ gamedev with SFML in May 2023
    • View Profile
    • Email
Re: Random access iteration benchmark
« Reply #9 on: December 26, 2012, 11:59:11 am »
Quote
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
« Last Edit: December 26, 2012, 05:51:58 pm by FRex »
Back to C++ gamedev with SFML in May 2023

binary1248

  • SFML Team
  • Hero Member
  • *****
  • Posts: 1405
  • I am awesome.
    • View Profile
    • The server that really shouldn't be running
Re: Random access iteration benchmark
« Reply #10 on: December 26, 2012, 04:39:49 pm »
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 ;).
SFGUI # SFNUL # GLS # Wyrm <- Why do I waste my time on such a useless project? Because I am awesome (first meaning).

cire

  • Full Member
  • ***
  • Posts: 138
    • View Profile
Re: Random access iteration benchmark
« Reply #11 on: December 27, 2012, 12:21:16 am »
Quote
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.


eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 10930
    • View Profile
    • development blog
    • Email
Re: Random access iteration benchmark
« Reply #12 on: December 27, 2012, 12:45:39 am »
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
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: Random access iteration benchmark
« Reply #13 on: January 03, 2013, 01:03:02 am »
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*.
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

toulis9999

  • Newbie
  • *
  • Posts: 11
    • View Profile
Re: Random access iteration benchmark
« Reply #14 on: January 03, 2013, 01:42:11 am »
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).

 

anything