Re: number of machine instructions - for algorithm measuring
From: Mark F. Haigh (mfhaigh_at_sbcglobal.net)
Date: 02/22/05
- Next message: Mark McIntyre: "Re: Converting seconds to (Days, Hours, Minutes, seconds)"
- Previous message: Eric Sosman: "Re: FAQ 4.9 and void**"
- In reply to: ben: "number of machine instructions - for algorithm measuring"
- Next in thread: ben: "Re: number of machine instructions - for algorithm measuring"
- Reply: ben: "Re: number of machine instructions - for algorithm measuring"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 22 Feb 2005 14:30:07 -0800
ben wrote:
<snip>
>
>
> Prove an upper bound on the number of machine instructions required
to
> process N objects using the below programme. You may
> assume, for example, that any C assignment statement always requires
> less than c instructions, for some fixed constant c.
>
> /* a very simple and silly example "algorithm" */
> #include <stdio.h>
> #define N 10000
>
> int main(void)
> {
> int n = 0;
> int x[3] = { 1, 4, 9 };
> long unsigned total = 0;
>
> while( n < N ) {
> total += x[ n % 3 ];
> n++;
> }
>
> printf("%lu\n", total);
> return 0;
> }
>
In my opinion, this is a waste of time. Instruction count no longer
has much of a bearing on how much time a program takes to execute. To
use your example program, with N set to 0x4FFFFFFFu:
[mark@icepick ~]$ gcc -save-temps -Wall -O3 -o bar bar.c && time ./bar
&& wc -l bar.s
1968526669
real 0m16.683s
user 0m16.682s
sys 0m0.002s
44 bar.s <- lines of assembly
[mark@icepick ~]$ gcc -save-temps -Wall -O3 -march=pentium4 -o bar
bar.c && time ./bar && wc -l bar.s
1968526669
real 0m4.313s
user 0m4.312s
sys 0m0.001s
78 bar.s <- lines of assembly
As you can see, a change in an optimization setting roughly doubled the
assembly output, but resulted in a 4x speed improvement. I picked the
quickest of 3 trials each, for the record.
It may be an interesting academic exercise, but its real world
applicability is questionable. Probably not the answer you wanted, but
an answer nonetheless.
Mark F. Haigh
mfhaigh@sbcglobal.net
- Next message: Mark McIntyre: "Re: Converting seconds to (Days, Hours, Minutes, seconds)"
- Previous message: Eric Sosman: "Re: FAQ 4.9 and void**"
- In reply to: ben: "number of machine instructions - for algorithm measuring"
- Next in thread: ben: "Re: number of machine instructions - for algorithm measuring"
- Reply: ben: "Re: number of machine instructions - for algorithm measuring"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
