removing a loop cause it to go at half the speed?
Web Server forum
Back To The Forum Home!Search!Private Messaging System

Web Server Talk Web Server Talk > Unix and Linux reviews > Free Unix support > Unix Programming > removing a loop cause it to go at half the speed?




Pages (2): [1] 2 »   Last Thread   Next Thread Next
  Show Printable Version Email this Page Subscribe to this Thread      Post New Thread    Post A Reply      

    removing a loop cause it to go at half the speed?  
tom fredriksen


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

Hi

I was doing a simple test of the speed of a "maths" operation and when I
tested it I found that removing the loop that initialises the data array
for the operation caused the whole program to spend twice the time to
complete. If the loop is included it takes about 7.48 seconds to
complete, but when removed it takes about 11.48 seconds.

Does anybody have a suggestion as to why this is so and whether I can
trust the results of the code as it is below?

(I tried declaring total and data as unsigned, because of time taken on
overflows as someone suggested, but it did not affect it)

/tom


The code was compiled on linux 2.6.3 with gcc 3.3.2 and glibc 2.2.3
compiler arguments are "-O2 -Wall -D_LARGEFILE64_SOURCE -std=gnu99"

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int main(int argc, char *argv[])
{
int total = 0;
int count = 65500;
signed int data[count];

/* Initialising array loop */
for(int c=0; c<count; c++) {
data[c]=1+(int) (2000000000.0*rand()/(RAND_MAX+1.0));
}

struct timeval start_time;
struct timeval end_time;

gettimeofday(&start_time, NULL);

for(int d=0; d<50000; d++) {
for(int c=0; c<count; c++) {
total += data[c];
}
}
gettimeofday(&end_time, NULL);

double t1=(start_time.tv_sec*1000)+(start_time.tv_usec/1000.0);
double t2=(end_time.tv_sec*1000)+(end_time.tv_usec/1000.0);

printf("Elapsed time (ms): %.6lf\n", t2-t1);
printf("Total: %u\n", total);

return(0);
}





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
Bjorn Reese


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

tom fredriksen wrote:

> tested it I found that removing the loop that initialises the data array
> for the operation caused the whole program to spend twice the time to
> complete. If the loop is included it takes about 7.48 seconds to
> complete, but when removed it takes about 11.48 seconds.
>
> Does anybody have a suggestion as to why this is so and whether I can
> trust the results of the code as it is below?
[...]
>     gettimeofday(&start_time, NULL);

You are measuring absolute time, not the time your program is using the
CPU, so everything else that is running while you measure is included in
the number; virtual memory swapping is also included.

Use getrusage() instead of gettimeofday().

--
mail1dotstofanetdotdk





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
tom fredriksen


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

Bjorn Reese wrote:
> tom fredriksen wrote:
> 
> [...] 
>
> You are measuring absolute time, not the time your program is using the
> CPU, so everything else that is running while you measure is included in
> the number; virtual memory swapping is also included.
>
> Use getrusage() instead of gettimeofday().

I see your point, but its not really a problem, even if I set the
priority to the highest the difference is almost the same.

/tom





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
moi


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

tom fredriksen wrote:
> Hi
>
> I was doing a simple test of the speed of a "maths" operation and when I
> tested it I found that removing the loop that initialises the data array
> for the operation caused the whole program to spend twice the time to
> complete. If the loop is included it takes about 7.48 seconds to
> complete, but when removed it takes about 11.48 seconds.
>
> Does anybody have a suggestion as to why this is so and whether I can
> trust the results of the code as it is below?
>

My guess would be: your initialisation fills the memory cache.
(all your data will probably fit into the L2 cache)
Without the initialisation, 1/4 (?) of the array-accesses will result in
a cache miss, and the processor will have to wait for the bus to grab
the data from RAM. (you could increase the arraysize to test this
hypothesis)

HTH,
AvK





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
tom fredriksen


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

moi wrote:
> tom fredriksen wrote: 
>
> My guess would be: your initialisation fills the memory cache.
> (all your data will probably fit into the L2 cache)
> Without the initialisation, 1/4 (?) of the array-accesses will result in
> a cache miss, and the processor will have to wait for the bus to grab
> the data from RAM. (you could increase the arraysize to test this
> hypothesis)

I think I figured it out, it seems that the array initialisation
statement contains float numbers, causing the entire program to be
optimised with float operations instead of integer operations as
in_cksum should be. I tested it with removing the offending statment,
ith then gave the same results as if I removed the loop.

Does anybody have a suggestion as to how to make the rand() statement
operate on integers only?

for(int c=0; c<count; c++) {
/* data[c]=1.0+(unsigned int) (2000000000.0*rand()/(RAND_MAX+1.0)); */
data2[c] = data[c];
}

(I used the data2 array at the end of the program to make usre it was
not optimised away.)

/tom





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
moi


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

moi wrote:

BTW: A similar effect could also be caused by the MMU, which has to
map in the pages (probably COW from /dev/zero)

BTW2: I would not allocate a big array like that on the stack, but
that's a matter of taste, I guess.

AvK





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
moi


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

tom fredriksen wrote:
> moi wrote:

>
> I think I figured it out, it seems that the array initialisation
> statement contains float numbers, causing the entire program to be
> optimised with float operations instead of integer operations as
> in_cksum should be. I tested it with removing the offending statment,
> ith then gave the same results as if I removed the loop.
>
> Does anybody have a suggestion as to how to make the rand() statement
> operate on integers only?

You are confused.
man 3 rand

AvK





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
tom fredriksen


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-15-06 10:55 PM

moi wrote:
> tom fredriksen wrote: 
> 
>
> You are confused.
> man 3 rand

I know, but gcc outputs code with 90% float instructions because of the
rand statement. Or is it just using integer instructions to do integer
operations?

/tom





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
tom fredriksen


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-16-06 12:51 PM

tom fredriksen wrote:
> moi wrote: 
>
> I know, but gcc outputs code with 90% float instructions because of the
> rand statement. Or is it just using integer instructions to do integer
> operations?

Sorry, meant float instructions to to integer operations

/tom





[ Post a follow-up to this message ]



    Re: removing a loop cause it to go at half the speed?  
Nils O. Selåsdal


View Ip Address Report This Message To A Moderator Edit/Delete Message


 
03-16-06 12:51 PM

tom fredriksen wrote:
> Bjorn Reese wrote: 
>
> I see your point, but its not really a problem, even if I set the
> priority to the highest the difference is almost the same.
Try measuring without compiling with optimizations. Who knows
what optimizations the compiler applies in the different
situations for the different code. It might eliminate loops
entierly in one of the situations, or unroll them.
Peek at the assembly.





[ Post a follow-up to this message ]



    Sponsored Links  




 





   All times are GMT. The time now is 03:09 AM.      Post New Thread    Post A Reply      
Pages (2): [1] 2 »   Last Thread   Next Thread Next


Most Popular forums 

Forum Jump:
Rate This Thread:

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is OFF
 
Medical and Health forum | Computer Games Reviews | Graphics design forum

Back To The Top
Home | Usercp | Faq | Register