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

[Alinabi <alexander.the.average@gmail.com>]

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"
<spam.jrcarter....@acm.nospam.org> 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