Prev: Tricky declarators
Next: How to create a shallow copy without calling a constructor?
From: Arijit on 31 Dec 2009 02:06
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 ?

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! ]

From: Paul Carter on 31 Dec 2009 04:46
On Dec 31, 2:06 pm, Arijit <pal_...(a)yahoo.co.in> 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.
>

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


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jeff Flinn on 31 Dec 2009 04:46
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

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Dave Harris on 31 Dec 2009 22:54
pal_ari(a)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

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.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: nabulke on 31 Dec 2009 22:58
On 31 Dez. 2009, 22:46, Jeff Flinn <TriumphSprint2...(a)hotmail.com>
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


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2 3
Prev: Tricky declarators
Next: How to create a shallow copy without calling a constructor?