Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > which loop is faster

Reply
Thread Tools

which loop is faster

 
 
petermcmillan_uk@yahoo.com
Guest
Posts: n/a
 
      01-04-2005

Jack Klein wrote:
> On 3 Jan 2005 04:11:39 -0800, "EventHelix.com" <(E-Mail Removed)>
> wrote in comp.lang.c:
>
> Either figure out how to do one of the following:
>
> 1. Get the new Google groups reply to quote context.
>
> 2. Quote the context yourself.
>
> 3. If you can't do either of the above, use a real newsreader. Free
> Agent, Mozilla Thunderbird, and Gravity are all free and quite good.
>
> > It will really depend upon "some code".
> > If "some code" just fits into the cache but the outer loop doesn't:
> > (2) would be faster.
> >
> > If the inner and the outer loop fit into the cache, I don't expect

to
> > see
> > a large difference in performance.
> >
> > Deepa

>
> What's a 'cache'? Where is it defined in the C standard? I write C
> code for quite a few platforms that don't have any such thing.
>
> So what's your answer if the OP is writing code for a platform

without
> a cache?
>


Hmm, I dunno whether you're joking? The cache is a type of memory,
there are quite a few caches within the computer. In this case the
important caches are the ones CPU caches. Have a look at
http://www.pantherproducts.co.uk/Art...%20Cache.shtml for
more info.

 
Reply With Quote
 
 
 
 
Mike Wahler
Guest
Posts: n/a
 
      01-04-2005

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
>
> Jack Klein wrote:
> > On 3 Jan 2005 04:11:39 -0800, "EventHelix.com" <(E-Mail Removed)>
> > wrote in comp.lang.c:
> >
> > Either figure out how to do one of the following:
> >
> > 1. Get the new Google groups reply to quote context.
> >
> > 2. Quote the context yourself.
> >
> > 3. If you can't do either of the above, use a real newsreader. Free
> > Agent, Mozilla Thunderbird, and Gravity are all free and quite good.
> >
> > > It will really depend upon "some code".
> > > If "some code" just fits into the cache but the outer loop doesn't:
> > > (2) would be faster.
> > >
> > > If the inner and the outer loop fit into the cache, I don't expect

> to
> > > see
> > > a large difference in performance.
> > >
> > > Deepa

> >
> > What's a 'cache'? Where is it defined in the C standard? I write C
> > code for quite a few platforms that don't have any such thing.
> >
> > So what's your answer if the OP is writing code for a platform

> without
> > a cache?
> >

>
> Hmm, I dunno whether you're joking?


He's not.

> The cache is a type of memory,
> there are quite a few caches within the computer.


1. The topic here is the C language, not computers.
2. The C language has no notion of 'cache'
2. Not all computers use 'caches'

>In this case the
> important caches are the ones CPU caches. Have a look at
> http://www.pantherproducts.co.uk/Art...%20Cache.shtml for
> more info.


No need. The hardware described there might include
'caches', but that's nothing to do with C.

-Mike


 
Reply With Quote
 
 
 
 
Mike Wahler
Guest
Posts: n/a
 
      01-04-2005

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
>
> Neo wrote:
> > "Stan Milam" <(E-Mail Removed)> wrote in message
> > news:q%oCd.6935$(E-Mail Removed) m...
> >
> > Yes, mathematically dis is true.
> >
> > When it comes to relams of C compilers its totally up to the compiler

> how it
> > generates the machine instructions to do the same. and dat also

> depends on,
> > for which target machine you are going to generate dat code. Its

> properties
> > affect the binary code generation like : word length, chache - if any

> the
> > processor has, address n data buses (von newman vs. harvard

> architecture) n
> > of couse, how compiler optimize the code while exploiting all these
> > available facilites.
> >
> > One important thing - Standard doesn't make any assumptions about it.
> >
> > It is obvious by closely analysing the two loops that memory access

> will be
> > more in first case
> > [100]
> > ...[10]
> >
> > as compared to
> > [10]
> > ...[100]
> >
> > 'coz inner loop breaks 10 times more and intialization has to be

> performed
> > for loop control variable 10 times more, assuming, all other things

> being
> > constant.
> >
> > Is that make sense?
> >
> > -Neo

>
> OK, I just had to find out the truth,


The truth for your particular platform, implementation,
and current configuration of such.

> so I compiled the program and
> looked at the disassemly. The results seem to be pretty much the same.


For your current setup.

> Take a look :


No need.

[snip]
>
> That's one way, and if it's done the other way then the only difference
> will be the parameters used for the for looping.


On your system.

>The thing that makes
> it loop is jmp, and in both cases it will jmp the same number of times.
> The other parts of the for loops have exactly the same instructions,
> but with different parameters.
> I think we can conclude that neither of these loops will be faster.


On your system. On others, the results could be completely different.

-Mike


 
Reply With Quote
 
Neo
Guest
Posts: n/a
 
      01-05-2005

"sushant" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> hi all,
>
> suppose i have 2 loops one inside the other, like this
>
> 1) for(i=0;i<=100;i++)
> {
> for(j=0;j<=10;j++)
> {
> some code;
> }
> }
>
> 2) for(i=0;i<=10;i++)
> {
> for(j=0;j<=100;j++)
> {
> some code;
> }
> }
>
> so which loops will work faster the 1st one or the 2nd one.
>
> thnx in advance
> sushant


2nd will be faster.
O'kay lets try to analyze it.

As per K&R2 (Page 60):
"The for statement
for(expr1; expr2; expr3)
statement
is equivalent to
expr1;
while(expr2) {
statement
expr3;
}

Grammatically, the three components of a for loop are expressions. Most
commonly, expr1 and expr3 are assignment or function calls and expr2 is a
relational expression."

In 1st one "expr1" will be executed 100 times, because inner loop breaks
more frequently. In 2nd case "expr1" will be executed 10 times only. So, all
things being equal (like generated target code) execution time will be more
in 1st case.

O'kay What about
for(i=0; i<1000; i++)
{
some code;
}
Will it run faster then any of the above versions?

Does it make sense, its all Standard C...

-Neo


 
Reply With Quote
 
Derrick Coetzee
Guest
Posts: n/a
 
      01-05-2005
sushant wrote:
> suppose i have 2 loops one inside the other, like this
>
> [ snipped: two nested loops, same with loops reversed ]
>
> so which loops will work faster the 1st one or the 2nd one.


A good compiler will perform loop exchange where it's possibly and
beneficial on that platform. In other words, both run just as quickly
with a good compiler (because it transforms one into the other).
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.
 
Reply With Quote
 
Mark McIntyre
Guest
Posts: n/a
 
      01-05-2005
On Wed, 5 Jan 2005 09:30:57 +0530, in comp.lang.c , "Neo"
<(E-Mail Removed)> wrote:

>
>"sushant" <(E-Mail Removed)> wrote in message
>news:(E-Mail Removed) om...
>> hi all,
>>
>> suppose i have 2 loops one inside the other, like this


(snip example of nested loops)

>2nd will be faster.


There's no way to say that.

>O'kay lets try to analyze it.


You can't, unless you know what "some code" inside the inner loop is. A
modern optimising compiler can optimise both these to be identical, if it
can determine there are no side-effects of the inner code. Many compilers
might even unroll both loops entirely and execute 1000 evaluations of 'some
code'.

And then of course modern CPUs can often run such loops as parallel
processes in different pipelines. Again this might (or might not) mean that
version X was faster than version Y.

This is all in concordance with the 'as if' principle which allows the
compiler and/or hardware to rearrange your code how it likes, as long as
the result is the same as if it hadn't.

(of a once-unrolled loop)

>Will it run faster then any of the above versions?


Yes. No. Sometimes. Never.




--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
 
Reply With Quote
 
Neo
Guest
Posts: n/a
 
      01-06-2005

"Mark McIntyre" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Wed, 5 Jan 2005 09:30:57 +0530, in comp.lang.c , "Neo"
> <(E-Mail Removed)> wrote:
>
>>
>>"sushant" <(E-Mail Removed)> wrote in message
>>news:(E-Mail Removed). com...
>>> hi all,
>>>
>>> suppose i have 2 loops one inside the other, like this

>
> (snip example of nested loops)
>
>>2nd will be faster.

>
> There's no way to say that.
>
>>O'kay lets try to analyze it.

>
> You can't, unless you know what "some code" inside the inner loop is. A
> modern optimising compiler can optimise both these to be identical, if it
> can determine there are no side-effects of the inner code. Many compilers
> might even unroll both loops entirely and execute 1000 evaluations of
> 'some
> code'.
>
> And then of course modern CPUs can often run such loops as parallel
> processes in different pipelines. Again this might (or might not) mean
> that
> version X was faster than version Y.
>
> This is all in concordance with the 'as if' principle which allows the
> compiler and/or hardware to rearrange your code how it likes, as long as
> the result is the same as if it hadn't.
>
> (of a once-unrolled loop)
>
>>Will it run faster then any of the above versions?

>
> Yes. No. Sometimes. Never.
>


O'kay! that may be, or may not be TRUE, for generated code
or a particular implementation/hardware combinattion.

Also as per C Standard -
5.1.2.3 Program execution
1 The semantic descriptions in this International Standard describe the
behavior of an
abstract machine in which issues of optimization are irrelevant.
[-snip-]
3 In the abstract machine, all expressions are evaluated as specified by the
semantics.
An actual implementation need not evaluate part of an expression if it can
deduce that
its value is not used and that no needed side effects are produced
(including any
caused by calling a function or accessing a volatile object).

But as per language semantics, as also abstract machine states (for loop)
6.6.5.3 The for statement
1 Except for the behavior of a continue statement in the loop body, the
statement
for ( clause*1 ; expression*2 ; expression*3 ) statement
and the sequence of statements
{
clause*1 ;
while ( expression*2 ) {
statement
expression*3 ;
}
}
are equivalent (where clause*1 can be an expression or a declaration). 114
2 Both clause*1 and expression*3 can be omitted. If either or both are an
expression,
they are evaluated as a void expression. An omitted expression*2 is replaced
by a
nonzero constant.

"clause 1" will make the difference, becase it will be evaluated every time
loop is entered.

-Neo


>
>
>
> --
> Mark McIntyre
> CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
> CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>



 
Reply With Quote
 
infobahn
Guest
Posts: n/a
 
      01-06-2005
Neo wrote:
>


<snip>

> 2 Both clause*1 and expression*3 can be omitted. If either or
> both are an expression, they are evaluated as a void expression.
> An omitted expression*2 is replaced by a nonzero constant.
>
> "clause 1" will make the difference, becase it will be evaluated every time
> loop is entered.


It needn't be, for the reasons you pointed out. If it can be
optimised out legally, then it won't make any difference at all.
 
Reply With Quote
 
Thomas Matthews
Guest
Posts: n/a
 
      01-09-2005
Lawrence Kirby wrote:
> On Mon, 03 Jan 2005 03:58:19 -0800, sushant wrote:
>
>
>>hi all,
>>
>>suppose i have 2 loops one inside the other, like this
>>
>>1) for(i=0;i<=100;i++)

>
>
> This is suspicious because it will loop 101 times,
>
>
>> {
>> for(j=0;j<=10;j++)

>
>
> and this will loop 11 times. If you expected 100 and 10 then make the
> comparison a < rather than a <= . That's common and normal in C as we tend
> to count from 0 a lot especially when array indexing is concerned. A 100
> element array has elements indexed from 0 to 99 and trying to access an
> element at position 100 would be an error.
>
>
>> {
>> some code;
>> }
>> }
>> }
>>2) for(i=0;i<=10;i++)
>> {
>> for(j=0;j<=100;j++)
>> {
>> some code;
>> }
>> }
>> }
>>so which loops will work faster the 1st one or the 2nd one.

>
>
> It is impossible to say. It will depend on your compiler (and the options
> you use with it), the processor used to run the code and not least on what
> exactly "some code" is. If "some code" uses i and/or j then the two
> samples are not equivalent and it doesn't make much sense to talk about
> which is faster. That's also the case if i and/or j are used after the
> loops.
>
> Lawrence


Hi, nice to see you back, if you are the real "god".

Is the compiler allowed to optimize the two loops into one?
Given: (Example 1)
unsigned int i, j;
for (i = 0; i < 10; ++i)
{
for (j = 0; j < 100; ++j)
{
Some_Code();
}
}

According to my elementary computer science knowledge, the
statement:
Some_Code();
is executed 1000 times. I believe this would be the same
as: (Example 2)
unsigned int k;
for (k = 0; k < 1000; ++k)
{
Some_Code();
}

Is there any rule in the standard preventing the compiler from
converting Example 1 to Example 2 (i.e. factoring out the
nested loop to just one loop)?

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 
Reply With Quote
 
Joona I Palaste
Guest
Posts: n/a
 
      01-09-2005
Thomas Matthews <(E-Mail Removed)> scribbled the following:
> Lawrence Kirby wrote:


(snip)

>> Lawrence


> Hi, nice to see you back, if you are the real "god".


Lawrence, next time someone asks you if you're a god, you say yes!

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"The day Microsoft makes something that doesn't suck is probably the day they
start making vacuum cleaners."
- Ernst Jan Plugge
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Memset is faster than simple loop? AndersWang@gmail.com C Programming 24 03-12-2013 09:42 PM
Triple nested loop python (While loop insde of for loop inside ofwhile loop) Isaac Won Python 9 03-04-2013 10:08 AM
Re: Why is my code faster with append() in a loop than with a largelist? Dave Angel Python 4 07-06-2009 10:51 PM
method calls faster than a loop? tom fredriksen Java 42 03-20-2006 08:06 PM
Microcontrollers: which one ? which language ? which compiler ? The Jesus of Suburbia NZ Computing 2 02-11-2006 06:53 PM



Advertisments