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=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no 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!postnews.google.com!k29g2000hsd.googlegroups.com!not-for-mail From: Alinabi Newsgroups: comp.lang.ada Subject: Re: sub-optimal code for packed boolean arrays -- bug or inherent limitation Date: Tue, 03 Jul 2007 19:42:30 -0000 Organization: http://groups.google.com Message-ID: <1183491750.177186.154490@k29g2000hsd.googlegroups.com> References: <1183404856.375083.160890@q69g2000hsb.googlegroups.com> <1183485842.725620.199490@w5g2000hsg.googlegroups.com> NNTP-Posting-Host: 75.75.8.72 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" X-Trace: posting.google.com 1183491750 23019 127.0.0.1 (3 Jul 2007 19:42:30 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 3 Jul 2007 19:42:30 +0000 (UTC) In-Reply-To: User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.8.1.4) Gecko/20061201 Firefox/2.0.0.4 (Ubuntu-feisty),gzip(gfe),gzip(gfe) Complaints-To: groups-abuse@google.com Injection-Info: k29g2000hsd.googlegroups.com; posting-host=75.75.8.72; posting-account=gD74RA0AAABm9rsBG7oeOmJ-iO5c3KUQ Xref: g2news1.google.com comp.lang.ada:16401 Date: 2007-07-03T19:42:30+00:00 List-Id: 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. 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. 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. On Jul 3, 2:36 pm, "Jeffrey R. Carter" wrote: > Alinabi wrote: > > > Now, concerning efficiency: these basic operations on bitboards > > are used 1e8 to 1e9 times every time the program tries to decide > > what to move next. Even the smallest improvement in speed can > > mean the difference between searching 10 or 11 ply deep, which > > can mean an improvement of over 50 Elo points in strength. > > I'm sure that's true. However, you have not demonstrated that there's a > speed difference between the 2 versions. Even if there is, it doesn't > necessarily mean that there will be a difference in the # of plys that > can be searched. The old rule, "1st get it right, then make it fast," > still applies. Once you have it finished you can easily see if modifying > this single procedure actually makes a difference. Until then, you're > wasting a lot of effort on something you don't know is important. > > You should also be aware that you're sending the compiler conflicting > messages. Packing the array indicates that you want the compiler to > minimize storage, even at the expense of speed, while "pragma Optimize > (Time);" indicates that you want to minimize time, even at the expense > of storage. Obtaining speed often requires wasting storage; the fastest > implementation might be to not pack the array. I don't know how many of > these you have, but with the large memories on modern machines, you > might be better off with the additional 56 bytes per array. Again, you > won't know for sure until you have a working version you can measure. > > -- > Jeff Carter > "Gentlemen, you can't fight in here. This is the War Room!" > Dr. Strangelove > 30