From: Alinabi <alexander.the.average@gmail.com>
Subject: sub-optimal code for packed boolean arrays -- bug or inherent limitation
Date: Mon, 02 Jul 2007 19:34:16 -0000
Date: 2007-07-02T19:34:16+00:00 [thread overview]
Message-ID: <1183404856.375083.160890@q69g2000hsb.googlegroups.com> (raw)
Hello, everyone.
I am writing a chess program in Ada, using bitboards for position
representation. Bitboards are just 64 bit integers in which each bit
represents a predicate about a square of the board. For example, you
would have a bitboard called WhitePawns, which has a one for every
square that contains a white pawn, and zero for every other square. In
Ada, there are two possible implementations of a bitboard: using
Unsigned_64, which would closely mirror the way things are done in C,
and using packed arrays of booleans. The C-like version, using
Unsigned_64, leads to some rather obfuscated code, so I decided to
investigate the efficiency of the code that gnat generates for some
basic operations on packed arrays, which I implemented in the
following package:
package Test is
type Index_T is new Integer range 0..63;
type Bitboard_T is private;
procedure Set (B : in out Bitboard_T; I : in Index_T);
procedure Clear (B : in out Bitboard_T; I : in Index_T);
procedure Clear (B : in out Bitboard_T);
procedure Flip (B : in out Bitboard_T; I : in Index_T);
function Is_Set(B : in Bitboard_T; I : in Index_T)
return Boolean ;
private
type Bitboard_T is array(Index_T) of Boolean;
pragma Pack(Bitboard_T);
pragma Inline_Always(Set, Clear, Flip, Is_Set);
end Test;
package body Test is
pragma Optimize(Time);
procedure Set(B : in out Bitboard_T; I : in Index_T) is
begin
B(I) := True;
end;
procedure Clear(B : in out Bitboard_T; I : in Index_T) is
begin
B(I) := False;
end;
procedure Clear(B : in out Bitboard_T) is
begin
B := B xor B;
end;
procedure Flip(B : in out Bitboard_T; I : in Index_T) is
begin
B(i) := not B(i);
end;
function Is_Set(B : in Bitboard_T; I : in Index_T)
return Boolean is
begin
return B(I);
end;
end Test;
When compiled with
gnatmake -g -gnatp -gnatn -march=opteron -O3 -fdump-tree-optimized
test.adb
using the ada compiler in gcc 4.1.2, the code generated is generally
optimal, or close to optimal. For example, the code generated for Set
is
procedure Set(B : in out Bitboard_T; I : in Index_T) is
0: 89 f1 mov %esi,%ecx
begin
B(I) := True;
2: b8 01 00 00 00 mov $0x1,%eax
7: 48 d3 e0 shl %cl,%rax
a: 48 09 f8 or %rdi,%rax
end;
d: c3 retq
The only notable exception is procedure Flip, which becomes
procedure Flip(B : in out Bitboard_T; I : in Index_T) is
30: 89 f1 mov %esi,%ecx
begin
B(i) := not B(i);
32: 48 c7 c0 fe ff ff ff mov $0xfffffffffffffffe,%rax
39: 48 d3 c0 rol %cl,%rax
3c: 48 21 f8 and %rdi,%rax
3f: 48 d3 ef shr %cl,%rdi
42: 83 f7 01 xor $0x1,%edi
45: 83 e7 01 and $0x1,%edi
48: 48 d3 e7 shl %cl,%rdi
4b: 48 09 f8 or %rdi,%rax
end;
4e: c3 retq
instead of the shorter
mov %esi, %ecx
mov 0x1, %rax
shl %cl, %rax
xor % rax, %rdx
retq
I don't know much (if anything) about compiler internals, so I was
wondering if I should file a bug report. Is there some good
theoretical justification for all that extraneous shifts and
rotations? I would think that if the compiler can figure out the best
way to set or clear a bit in a register using shift and logical ops,
than it should also be able to negate it efficiently.
next reply other threads:[~2007-07-02 19:34 UTC|newest]
Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-07-02 19:34 Alinabi [this message]
2007-07-02 20:08 ` sub-optimal code for packed boolean arrays -- bug or inherent limitation Ludovic Brenta
2007-07-03 1:01 ` Jeffrey R. Carter
2007-07-03 7:22 ` Harald Korneliussen
2007-07-03 8:37 ` Georg Bauhaus
2007-07-03 7:59 ` gautier_niouzes
2007-07-03 9:25 ` Stefan Lucks
2007-07-03 12:40 ` Stefan Lucks
2007-07-03 15:42 ` Adam Beneschan
2007-07-03 18:04 ` Alinabi
2007-07-03 18:09 ` Alinabi
2007-07-03 18:17 ` Alinabi
2007-07-10 2:06 ` Randy Brukardt
2007-07-03 18:36 ` Jeffrey R. Carter
2007-07-03 19:42 ` Alinabi
2007-07-04 1:12 ` Jeffrey R. Carter
2007-07-04 10:15 ` Jeffrey Creem
2007-07-04 18:28 ` Jeffrey R. Carter
2007-07-04 3:22 ` Steve
2007-07-04 6:31 ` Harald Korneliussen
2007-07-08 22:53 ` Robert A Duff
2007-07-09 6:09 ` tmoran
2007-07-04 9:00 ` Jean-Pierre Rosen
2007-07-04 18:27 ` tmoran
2007-07-04 19:16 ` Pascal Obry
2007-07-05 1:45 ` tmoran
2007-07-05 4:53 ` Jeffrey R. Carter
2007-07-04 18:51 ` tmoran
2007-07-08 22:58 ` Robert A Duff
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox