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.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,5ff6e0c3de8331c0 X-Google-Attributes: gid103376,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!feeder1-2.proxad.net!proxad.net!feeder1-1.proxad.net!club-internet.fr!feedme-small.clubint.net!news.ecp.fr!news.jacob-sparre.dk!pnx.dk!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: sub-optimal code for packed boolean arrays -- bug or inherent limitation Date: Mon, 9 Jul 2007 21:06:34 -0500 Organization: Jacob's private Usenet server Message-ID: References: <1183404856.375083.160890@q69g2000hsb.googlegroups.com> <1183485842.725620.199490@w5g2000hsg.googlegroups.com> <1183486195.764567.297420@k29g2000hsd.googlegroups.com> <1183486662.806585.71680@q69g2000hsb.googlegroups.com> NNTP-Posting-Host: static-69-95-181-76.mad.choiceone.net X-Trace: jacob-sparre.dk 1184033059 28219 69.95.181.76 (10 Jul 2007 02:04:19 GMT) X-Complaints-To: news@jacob-sparre.dk NNTP-Posting-Date: Tue, 10 Jul 2007 02:04:19 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1807 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2800.1896 Xref: g2news1.google.com comp.lang.ada:16444 Date: 2007-07-09T21:06:34-05:00 List-Id: "Alinabi" wrote in message news:1183486662.806585.71680@q69g2000hsb.googlegroups.com... > One more thing: some inline assembly is unavoidable. There are two > other bitboard operations that are required: First_One(Bitboard_T) > returns Natural and Last_One(Bitboard_T) returns Natural; They return > the position of the least significant and most significant set bit > respectively. On x86 processors you can do this with one instruction > BSF (bit scan forward) and BSR (bit scan reverse), and you cannot > expect a compiler to generate them. There's a reason for that: Intel recommended to compiler writers to not use "complex" instructions, as sets of simple instructions are often supposed to be faster. The "complex" instructions were implemented essentially as "macros" of simple instructions. (This is information is somewhat old, so it may vary on the most recent processors.) My point is that it might not actually be faster to use those instructions than to use a loop of your own design (and there is a small chance that they'd be slower). As suggested elsewhere, you need to test that in a suitable benchmark. The number of instructions has had no real bearing on the execution time since the 486 came out (and indeed, given that some instructions are much slower than others, it never had much bearing on Intel's x86 processors). Randy.