|
| Jim Rogers wrote:
> CTips <ctips@bestweb.net> wrote in
> news:11329cb96h2p19f@corp.supernews.com:
>
>
>
> [snip advice]
>
>
>
> Let's see if this helps.
> I have adjusted my program to meet some of your advice.
> The I/O at the end is not included in the reported timing.
> The program now runs for > 1 second.
Close, but still has one problem. You're using Ada.Calendar.Clock,
which, IIRC, returns the actual wall-clock time. So, if you were swapped
out in the middle, you would be over-reporting the time. Isn't there
some Ada call that is the equivalent of POSIX clock() [or, better,
times()]?
If I look at your numbers, it seems that you using 2e-7 seconds per
call. On a 2GHz AMD, that translates to 388 cycles per call.
IIRC, the C codes that were posted to find the highest bit set thread
were about 1/10th of that number. Just to double check, I wrote and
measured some C code. On my 3GHz Xeon running with cygwin on WinXP, when
compiled with gcc3.3.3 using -mpcu=i686 -O0, I got a total run-time of
2.3s, for about 69 cycles/iteration, and with -O2 I get 0.94s for about
28 cycles/iteration.
We're comparing a Xeon with a AMD so its not apples to apples, but
still, it suggests that either your timing methodology could use some
work, or that the code generated is quite bad.
unsigned
FindHighestBit(unsigned n)
{
unsigned d = 0;
if( n > 0xffff ) {
d += 16;
n >>= 16;
}
if( n > 0xff ) {
d += 8;
n >>= 8;
}
if( n > 0xf ) {
d += 4;
n >>= 4;
}
if( n > 0x3 ) {
d += 2;
n >>= 2;
}
if( n > 0x1 ) {
d += 1;
n >>= 1;
}
if( n > 0x0 ) {
d += 1;
}
return d;
}
main(void)
{
unsigned i;
unsigned j;
unsigned s= 0;
unsigned val[32];
for( i = 0; i < 32; i+= 2 ) {
val[i] = (1U<<i)-1;
val[i+1] = 1U<<(31-i);
}
for( i = 0; i < 3125000; i++ ) {
for( j = 0; j < 32; j++ ) {
s += FindHighestBit(val[j]);
}
}
return s;
}
>
> Time run: 1.94 seconds
> Hardware: 2.0GHz AMD 64 processor with 512 Mb memory
> System :
> OS : WIN XP Service Pack 1
> compiler: GNAT v3.15p
> Compiler flags: none (-O2 was tried but appeared to remove too much)
>
> Program: Performs bit search 10,000,000 times
>
> -- Highest bit set
> with Ada.Text_Io;
> with Ada.Calendar; use Ada.Calendar;
>
> procedure Highest_Bit_Set is
> Num : Integer;
> type Index_Type is mod 32;
> type Bit_Array is array(Index_Type) of Boolean;
> pragma Pack(Bit_Array);
> Overlay : Bit_Array;
> for Overlay'Address use Num'Address;
> Start, Stop : Time;
> Bit_Num : Index_Type := 0;
> begin
> Start := Clock;
> Num := 1;
> for X in 1..10_000_000 loop
> for I in reverse Overlay'range loop
> if Overlay(I) then
> Bit_Num := I;
> exit;
> end if;
> end loop;
> end loop;
> Stop := Clock;
> Ada.Text_IO.Put_Line("High bit :" & Index_Type'Image(Bit_Num));
> Ada.Text_IO.Put_Line("Execution time: " &
> Duration'Image(Stop - Start));
> end Highest_Bit_Set;
>
> Program output:
> High bit : 0
> Execution time: 1.950221327
>
> Jim Rogers
>
>
>
|
|