Re: 10 rules for benchmarking (was Re: Teaching new tricks to an old dog (C++ -->Ada))

["Aslan Kral" <aslanski2002@yahoo.com>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4163 bytes --]


"Aslan Kral" <aslanski2002@yahoo.com>, haber iletisinde �unlar�
yazd�:39fr2iF5uq3mvU1@individual.net...
> > 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.
> >
>

Oops! I failed to read the -O2 part. It makes sense now. And your code
doesn't use any lookup table that is why it is slower than Willem's. Anyway
the version with lookup table is quite close to "bsr" version. So yours also
can get faster with the addition of lookup table. It would be interesting to
see how much Ada can get close to "bsr" version below! (By adding a lookup
table, I mean.)

__inline unsigned FindHighestBit(unsigned n)
{
   __asm
   {
      bsr eax, n
   }
}
.

> OK. I adjusted the code to run in your loop.
>
> Your score is a bit strange to me?! It may be the compiler that makes the
> difference.
> I timed your code in my P4 1.4GHz NT4.0 SP6 (MSVC6) and my result is ~2100
> ms for your code while the best version suggested by Williem finishes in
> ~650 ms (which is slightly better than 1-opcode "bsr" inline assembly
> version). I guess it is because you use a 5-bit lookup table.
Unfortunately
> I couldn't test the Ada version.
>
> And I tried to run the loops twice in a row and they seem linear except
for
> the assembly version which seems to get slightly better.
> Yours: 4200 ms
> Williem's: 1300 ms
> "bsr": 1280 ms
>
>
>
>
> > 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
> > >
> > >
> > >
>
>