From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.1 required=5.0 tests=BAYES_00,FREEMAIL_FROM, PP_MIME_FAKE_ASCII_TEXT autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,703c4f68db81387d X-Google-Thread: 115aec,703c4f68db81387d X-Google-Thread: 108717,a7c8692cac750b5e X-Google-Thread: f43e6,703c4f68db81387d X-Google-Attributes: gid103376,gid115aec,gid108717,gidf43e6,public X-Google-Language: ENGLISH,ASCII Path: g2news1.google.com!news3.google.com!news.glorb.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Aslan Kral" Newsgroups: comp.lang.ada,comp.realtime,comp.programming,comp.software-eng Subject: Re: 10 rules for benchmarking (was Re: Teaching new tricks to an old dog (C++ -->Ada)) Date: Sat, 12 Mar 2005 14:47:09 +0200 Message-ID: <39g6jbF62g4qjU1@individual.net> References: <4229bad9$0$1019$afc38c87@news.optusnet.com.au> <1110032222.447846.167060@g14g2000cwa.googlegroups.com> <871xau9nlh.fsf@insalien.org> <3SjWd.103128$Vf.3969241@news000.worldonline.dk> <87r7iu85lf.fsf@insalien.org> <1110052142.832650@athnrd02> <1110284070.410136.205090@o13g2000cwo.googlegroups.com> <395uqaF5rhu2mU1@individual.net> <112rs0bdr2aftdf@corp.supernews.com> <1inxxr988rxgg$.1w9dedak41k89.dlg@40tude.net> <112s1r0rf0o8nca@corp.supernews.com> <112sonip5v4dca6@corp.supernews.com> <112t3de6fu04f38@corp.supernews.com> <1110396477.596174.285520@o13g2000cwo.googlegroups.com> <112vb2t8eonuhed@corp.supernews.com> <1110422108.925127.54110@o13g2000cwo.googlegroups.com> <11329cb96h2p19f@corp.supernews.com> <1134l90ja5sqm73@corp.supernews.com> <39fr2iF5uq3mvU1@individual.net> X-Trace: individual.net us8XV3Gz0tNT5dBaOJK0BwmiKSSXF14cPA6OPJUnoorD1lJeMQ X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Xref: g2news1.google.com comp.lang.ada:9224 comp.realtime:1356 comp.programming:17863 comp.software-eng:4919 Date: 2005-03-12T14:47:09+02:00 List-Id: "Aslan Kral" , 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< > 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 > > > > > > > > > > >