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

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?

--
http://kaba.hilvi.org

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

From: johncruise on 31 Dec 2009 22:54
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_...(a)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
> ...


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

From: pedro on 2 Jan 2010 23:55
On Jan 1, 11:54 pm, johncruise <johncru...(a)gmail.com> wrote:
> 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_...(a)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 get a vast improvement in
the iterator version

sum = 0;
vector<int>::iterator j = num.begin();
for(int i = 0; i < iter; ++i)
for(; j != num.end(); ++j)
sum += *j;


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

From: pedro on 2 Jan 2010 23:59
On Jan 1, 11:54 pm, johncruise <johncru...(a)gmail.com> wrote:
> 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_...(a)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;


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

From: MiB on 3 Jan 2010 22:19
On Jan 3, 5:59 pm, pedro <pedroke...(a)gmail.com> wrote:
[..]
> 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.


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

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