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!news2.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!wns13feed!worldnet.att.net!attbi_s21.POSTED!53ab2750!not-for-mail From: "Jeffrey R. Carter" User-Agent: Thunderbird 1.5.0.12 (Windows/20070509) MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: sub-optimal code for packed boolean arrays -- bug or inherent limitation References: <1183404856.375083.160890@q69g2000hsb.googlegroups.com> <1183485842.725620.199490@w5g2000hsg.googlegroups.com> <1183491750.177186.154490@k29g2000hsd.googlegroups.com> In-Reply-To: <1183491750.177186.154490@k29g2000hsd.googlegroups.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: NNTP-Posting-Host: 12.201.97.213 X-Complaints-To: abuse@mchsi.com X-Trace: attbi_s21 1183511565 12.201.97.213 (Wed, 04 Jul 2007 01:12:45 GMT) NNTP-Posting-Date: Wed, 04 Jul 2007 01:12:45 GMT Organization: AT&T ASP.att.net Date: Wed, 04 Jul 2007 01:12:45 GMT Xref: g2news1.google.com comp.lang.ada:16402 Date: 2007-07-04T01:12:45+00:00 List-Id: Alinabi wrote: > The bitboard representation does not to save space. In fact it is > quite wasteful, which is why it is not used in embedded devices, like > cell phones. If you wonder how can this save time, here is an example: > suppose that you have a white pawn on c4 and you want to determine if > it is a passed pawn. That means that the pawn can no longer be blocked > or attacked by a black pawn, and therefore it threatens to advance and > get promoted. You would have to check if there are any black pawns at > b5, b6, b7, c5, c6, c7, d5, d6, d7. In the bitboard representation, > you would have a bitboard called BlackPawns which has a one for every > square occupied by a black pawn and than you would keep an array of > bitboard masks BlackBlockers : array(a1..h8) of Bitboard, such that, > for example, BlackBlockers(c4) has 1's at b5, b6, b7, c5, c6, c7, d5, > d6, d7, and 0's everywhere else. Then the white pawn at c4 is passed > if BlackPawns and BlackBlockers(c4) = 0, which is two machine > instruction, one for indexing and one for the logical operator. Zero is not an array of Boolean. You'd have to compare against (others => False). That the compiler recognizes this as 0 might be something else you'll want to check. > As for the proof that the hand coded version is faster, here it is: > > Hand coded: 2 MOV, 1 SHL, 1 XOR > Compiler: 2 MOV, 1 SHL, 1 XOR, 1 SHR, 1 ROL, 2 AND, 1 OR > --------------------- > 5 extraneous instructions, Q.E.D. This demonstrates only that the hand-coded version has fewer instructions. To prove that it's faster, you have to time them both. However, granting that the hand-coded version is faster, you haven't demonstrated that it makes an actual difference. > As I mentioned in a previous post, I already implemented all these > bitboard operations the usual way, using Unsigned_64, shifts, masks > and even some inline assembly. I am not opposed to that. I was just > wondering if I could use packed arrays of booleans to make the code > more legible and delegate the low level work to the compiler. I did > not expect the compiler to perform as well as it did. Since it only > failed far off the mark in one case, I was wondering if that would be > considered a bug. That question was answered in the negative. You are > getting way to defensive about this. I don't have a gnat bashing > agenda. My reaction is due to an allergy to premature optimization, the root of all evil. -- Jeff Carter "Gentlemen, you can't fight in here. This is the War Room!" Dr. Strangelove 30