Re: sub-optimal code for packed boolean arrays -- bug or inherent limitation

["Jeffrey R. Carter" <spam.jrcarter.not@acm.nospam.org>]

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