Iterating over vectors - speed difference
Arijit
I am comparing the runtime of iterating through a vector using 3
different approaches -
1) Indexing -> i = 0; i < vec.size();
2) Iterator -> i = vec.begin(), i != vec.end()
3) Summing using Accumulate
Here are the runtimes on my computer. I am compiling using VC++ 2008,
Release mode build. Runtimes are pretty stable from run to run.
1) Indexing -> 1.884 s
2) Iterator -> 8.725 s
3) Accumulate -> 1.8 s
As expected, accumulate is the fastest of them all, but only by a
narrow margin. The shocker is using iterators is nearly 5 times slower
than indexing, whereas I expected the two to be nearly at par. I don't
understand why this should happen.
Is this a case specific to VC++ / Dinkumware libraries ? Or is this
expected based on the C++ standard ? Or have I made an error in my
benchmarking ?
Thanks for your responses!
-Arijit
#include <iostream>
#include <vector>
#include <numeric>
#include <ctime>
using namespace std;
int main()
{
const int maxnum = 1000000;
const int iter = 1000;
vector<int> num;
num.reserve(maxnum);
for(int i = 0; i < maxnum; ++i)
num.push_back(i);
clock_t start = clock();
long long sum = 0;
for(int i = 0; i < iter; ++i)
for(unsigned int j = 0; j < num.size(); ++j)
sum += num[j];
cout << sum << endl;
clock_t mid = clock();
sum = 0;
for(int i = 0; i < iter; ++i)
for(vector<int>::iterator j = num.begin(); j != num.end(); ++j)
sum += *j;
cout << sum << endl;
clock_t late = clock();
sum = 0;
for(int i = 0; i < iter; ++i)
sum += accumulate(num.begin(), num.end(), 0ll);
cout << sum << endl;
clock_t end = clock();
cout << endl << static_cast<double>(mid - start) / CLOCKS_PER_SEC;
cout << endl << static_cast<double>(late - mid) / CLOCKS_PER_SEC;
cout << endl << static_cast<double>(end - late) / CLOCKS_PER_SEC <<
endl << endl;
return 0;
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Paul Carter
> Hi
>
> I am comparing the runtime of iterating through a vector using 3
> different approaches -
> 1) Indexing -> i = 0; i < vec.size();
> 2) Iterator -> i = vec.begin(), i != vec.end()
> 3) Summing using Accumulate
>
> Here are the runtimes on my computer. I am compiling using VC++ 2008,
> Release mode build. Runtimes are pretty stable from run to run.
>
> 1) Indexing -> 1.884 s
> 2) Iterator -> 8.725 s
> 3) Accumulate -> 1.8 s
>
> As expected, accumulate is the fastest of them all, but only by a
> narrow margin. The shocker is using iterators is nearly 5 times slower
> than indexing, whereas I expected the two to be nearly at par. I don't
> understand why this should happen.
>
What compiler flags are you using?
With VS 2005's cl command with no flags (in 32-bit Windows XP), I got:
13.469
53.484
4.078
But when I recompile adding -O2 I got:
4.093
2.344
1.094
Using gcc 4.2.4 on a 64-bit Linux box with no optimization, I got:
10.32
28.11
18.3
Recompiling with -O3 gave this results:
1.71
1.27
1.26
So the results depend on the optimizations.
--
Paul
Jeff Flinn
> Hi
>
> I am comparing the runtime of iterating through a vector using 3
> different approaches -
> 1) Indexing -> i = 0; i < vec.size();
> 2) Iterator -> i = vec.begin(), i != vec.end()
> 3) Summing using Accumulate
>
> Here are the runtimes on my computer. I am compiling using VC++ 2008,
> Release mode build. Runtimes are pretty stable from run to run.
>
> 1) Indexing -> 1.884 s
> 2) Iterator -> 8.725 s
> 3) Accumulate -> 1.8 s
>
> As expected, accumulate is the fastest of them all, but only by a
> narrow margin. The shocker is using iterators is nearly 5 times slower
> than indexing, whereas I expected the two to be nearly at par. I don't
> understand why this should happen.
>
> Is this a case specific to VC++ / Dinkumware libraries ? Or is this
> expected based on the C++ standard ? Or have I made an error in my
> benchmarking ?
For certain(most) versions of VC++ you need to turn off all iterator
debugging facilities. And of course you'll want to ensure that you are
timing an optimized build.
Jeff
Dave Harris
> As expected, accumulate is the fastest of them all, but only by a
> narrow margin. The shocker is using iterators is nearly 5 times
> slower than indexing, whereas I expected the two to be nearly at
> par. I don't understand why this should happen.
Perhaps you have VC++'s checked iterators enabled. They are enabled by
default even in release builds. Try adding:
#define _SECURE_SCL=0
before first #include. (Incidentally, your code doesn't just measure the
iteration time. It includes the time to print the final sum as well.)
-- Dave Harris, Nottingham, UK.
nabulke
wrote:
> Arijit wrote:
> > Hi
>
> > I am comparing the runtime of iterating through a vector using 3
> > different approaches -
> > 1) Indexing -> i = 0; i < vec.size();
> > 2) Iterator -> i = vec.begin(), i != vec.end()
> > 3) Summing using Accumulate
>
> > Here are the runtimes on my computer. I am compiling using VC++ 2008,
> > Release mode build. Runtimes are pretty stable from run to run.
>
> > 1) Indexing -> 1.884 s
> > 2) Iterator -> 8.725 s
> > 3) Accumulate -> 1.8 s
>
> > As expected, accumulate is the fastest of them all, but only by a
> > narrow margin. The shocker is using iterators is nearly 5 times slower
> > than indexing, whereas I expected the two to be nearly at par. I don't
> > understand why this should happen.
>
> > Is this a case specific to VC++ / Dinkumware libraries ? Or is this
> > expected based on the C++ standard ? Or have I made an error in my
> > benchmarking ?
>
> For certain(most) versions of VC++ you need to turn off all iterator
> debugging facilities. And of course you'll want to ensure that you are
> timing an optimized build.
>
> Jeff
Hi,
after disabling iterator range checks and enabling optimizations I get
the same timing for 2) and 3):
1) 2,7 s
2) 1,15 s
3) 1,14 s
use define _SECURE_SCL=0 (for Visual Studio 2008) and compiler
switches /O2 /Ot.
Here is the part of the manual:
_SECURE_SCL
If defined as 1, unsafe iterator use causes a runtime error. If
defined as 0, checked iterators are disabled. The exact behavior of
the runtime error depends on the value of _SECURE_SCL_THROWS. The
default value for _SECURE_SCL is 1, meaning checked iterators are
enabled by default.
Horst
Kaba
> Hi
>
> I am comparing the runtime of iterating through a vector using 3
> different approaches -
> 1) Indexing -> i = 0; i < vec.size();
> 2) Iterator -> i = vec.begin(), i != vec.end()
> 3) Summing using Accumulate
>
> Here are the runtimes on my computer. I am compiling using VC++ 2008,
> Release mode build. Runtimes are pretty stable from run to run.
>
> 1) Indexing -> 1.884 s
> 2) Iterator -> 8.725 s
> 3) Accumulate -> 1.8 s
>
> As expected, accumulate is the fastest of them all, but only by a
> narrow margin. The shocker is using iterators is nearly 5 times slower
> than indexing, whereas I expected the two to be nearly at par. I don't
> understand why this should happen.
>
> Is this a case specific to VC++ / Dinkumware libraries ? Or is this
> expected based on the C++ standard ? Or have I made an error in my
> benchmarking ?
Fortunately the last one must be the case:)
Here's a check list:
1) Use the Release configuration.
2) Run the program with Ctrl+F5 (without debugger), not F5 (with
debugger).
3) Turn of iterator debugging: Add to Configuration Properties->
C/C++->"Command Line" -> Additional options:
/D "_SECURE_SCL=0" /D "_HAS_ITERATOR_DEBUGGING=0"
Do these changes change your iterator timings?
johncruise
same speed as it basically have very similar implementations.
I think the reason why your iterator method is slower is because of
the time (p)added when the local-scope variable j is being created and
release at each loop. It would be interesting to see the result if
the iterator variable is declared outside the for(int i...) loop
(my thoughts are just pure speculation at this point)
JC
On Dec 31, 11:06 am, Arijit <pal_...@yahoo.co.in> wrote:
> ...
> I am comparing the runtime of iterating through a vector using 3
> different approaches -
> 1) Indexing -> i = 0; i < vec.size();
> 2) Iterator -> i = vec.begin(), i != vec.end()
> 3) Summing using Accumulate
> ...
pedro
> In theory, accumulate() and your iterator method should almost be the
> same speed as it basically have very similar implementations.
>
> I think the reason why your iterator method is slower is because of
> the time (p)added when the local-scope variable j is being created and
> release at each loop. It would be interesting to see the result if
> the iterator variable is declared outside the for(int i...) loop
>
> (my thoughts are just pure speculation at this point)
>
> JC
>
> On Dec 31, 11:06 am, Arijit <pal_...@yahoo.co.in> wrote:
>
> > ...
> > I am comparing the runtime of iterating through a vector using 3
> > different approaches -
> > 1) Indexing -> i = 0; i < vec.size();
> > 2) Iterator -> i = vec.begin(), i != vec.end()
> > 3) Summing using Accumulate
> > ...
I just tried the suggestion from JC and I got a vast improvement from
the iterator version:
499999500000000
499999500000
499999500000000
3.543
0.002
1.58
This is my iterator version:
sum = 0;
vector<int>::iterator j = num.begin();
for(int i = 0; i < iter; ++i)
for(; j != num.end(); ++j)
sum += *j;
MiB
[..]
> 3.543
> 0.002
> 1.58
>
> This is my iterator version:
>
> sum = 0;
> vector<int>::iterator j = num.begin();
> for(int i = 0; i < iter; ++i)
> for(; j != num.end(); ++j)
> sum += *j;
I don't want to be picky, but the "improvement" is based on running
the inner loop properly only once (on i = 0). It immediately fails its
termination test on each subsequent run since j is not reset to
reference the sequence start again.
MiB.
Seungbeom Kim
>
> I just tried the suggestion from JC and I got a vast improvement from
> the iterator version:
>
> 499999500000000
> 499999500000
> 499999500000000
>
> 3.543
> 0.002
> 1.58
>
> This is my iterator version:
>
> sum = 0;
> vector<int>::iterator j = num.begin();
> for(int i = 0; i < iter; ++i)
> for(; j != num.end(); ++j)
> sum += *j;
>
Don't you have to initialize j in each iteration?
--
Seungbeom Kim
Chris Uzdavinis
> I just tried the suggestion from JC and I got a vast improvement from
> the iterator version:
>
> 499999500000000
> 499999500000
> 499999500000000
>
> 3.543
> 0.002
> 1.58
Something seems fishy about a result being "that" much better. Try
switching the order of your tests, so that the for loop is done in the
middle and the iterators are done first. Or do each test twice
(individually timed.) Might be interesting.
Chris
Matthias Kluwe
On 1 Jan., 16:54, brang...@cix.co.uk (Dave Harris) wrote:
> pal_...@yahoo.co.in (Arijit) wrote (abridged):
>
> > As expected, accumulate is the fastest of them all, but only by a
> > narrow margin. The shocker is using iterators is nearly 5 times
> > slower than indexing, whereas I expected the two to be nearly at
> > par. I don't understand why this should happen.
>
> Perhaps you have VC++'s checked iterators enabled. They are enabled by
> default even in release builds. Try adding:
> #define _SECURE_SCL=0
Annoying. Please forgive the platform specific question:
Does anynone know of any other "assistance" MS has thought of that I'd
have to #define away if I do not want to pay for them?
Regards,
Matthias
ThosRTanner
>
> This is my iterator version:
>
> sum = 0;
> vector<int>::iterator j = num.begin();
> for(int i = 0; i < iter; ++i)
> for(; j != num.end(); ++j)
> sum += *j;
Thats because your 2nd loop now only does stuff the first time. It'd
be (slightly) more productive to leave the declaration of j in the for
loop and stash the value of num.end()