Initializing Arrays at compile time with macros... fun!!!

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
vittyvirus
Posts: 646
Joined: Wed Jun 18, 2014 2:30 pm
Full name: Fahad Syed

Initializing Arrays at compile time with macros... fun!!!

Post by vittyvirus »

Honestly, I think it is an art to initialize an array at compile time, although I don't think it'll give any noticeable speed-ups compared to initializing at start of the program (you can try anyway ;) ). Here are some of the few arrays that are initialized at compile time in Yaka:
#1: The SquareMask array, (1ULL << sq)

Code: Select all

#define A&#40;s&#41; &#40;1ULL << &#40;s&#41;), &#40;1ULL << &#40;s+1&#41;), &#40;1ULL << &#40;s+2&#41;), &#40;1ULL << &#40;s+3&#41;)
#define S&#40;s&#41; A&#40;s&#41;, A&#40;s+4&#41;, A&#40;s+8&#41;, A&#40;s+12&#41;
  // SquareMask&#91;64&#93; stores the Bitboard square masks. It's only a faster
  // alternative to 1ULL << square

  const Bitboard SquareMask&#91;Square&#58;&#58;SQ_NB&#93; = &#123;
    S&#40;0&#41;, S&#40;16&#41;, S&#40;32&#41;, S&#40;48&#41;
  &#125;;

#undef A
#undef S
#2: AdjacentFileMask array

Code: Select all

#define F&#40;f&#41; (&#40;FileAMask << (&#40;f&#41; - 1&#41;) | &#40;FileAMask << (&#40;f&#41; + 1&#41;))
  // AdjacentFileMask&#91;8&#93; stores the masks of the adjacent files of the index

  const Bitboard AdjacentFilesMask&#91;Square&#58;&#58;FILE_NB&#93; = &#123;
    FileBMask, F&#40;1&#41;, F&#40;2&#41;, F&#40;3&#41;, F&#40;4&#41;, F&#40;5&#41;, F&#40;6&#41;, FileGMask
  &#125;;

#3: ForwardMasks

Code: Select all

#define X&#40;s&#41; (&#40;1ULL << (&#40;s&#41; * 8&#41;) - 1&#41;
#define A&#40;s&#41; &#40;X&#40;&#40;s&#41;>>3&#41; & &#40;FileAMask << (&#40;s&#41;&7&#41;))
#define B&#40;s&#41; A&#40;s&#41;, A&#40;s+1&#41;, A&#40;s+2&#41;, A&#40;s+3&#41;
#define S&#40;s&#41; B&#40;s&#41;, B&#40;s+4&#41;, B&#40;s+8&#41;, B&#40;s+12&#41;

  const Bitboard ForwardBlackMask&#91;Square&#58;&#58;SQ_NB&#93; = &#123;
    S&#40;0&#41;, S&#40;16&#41;, S&#40;32&#41;, S&#40;48&#41;
  &#125;;

#undef A
#define A&#40;s&#41; ((~X&#40;(&#40;s&#41;>>3&#41;+1&#41;) & &#40;FileAMask << (&#40;s&#41;&7&#41;))

  const Bitboard ForwardWhiteMask&#91;Square&#58;&#58;SQ_NB&#93; = &#123;
    S&#40;0&#41;, S&#40;16&#41;, S&#40;32&#41;, B&#40;48&#41;, B&#40;52&#41;
  &#125;;

#undef A
#4: The bit count table

Code: Select all

// Not my code, see https&#58;//graphics.stanford.edu/~seander/bithacks.html
  // This array stores the number of bits set in an integer from 0 to 255.
  const uint8_t BitCountTable&#91;&#93; = &#123;
#define B2&#40;n&#41;    n,     n+1,     n+1,     n+2
#define B4&#40;n&#41; B2&#40;n&#41;, B2&#40;n+1&#41;, B2&#40;n+1&#41;, B2&#40;n+2&#41;
#define B6&#40;n&#41; B4&#40;n&#41;, B4&#40;n+1&#41;, B4&#40;n+1&#41;, B4&#40;n+2&#41;
              B6&#40;0&#41;, B6&#40;0+1&#41;, B6&#40;0+1&#41;, B6&#40;0+2&#41;
  &#125;;
#5: The SquareDistance Table!!!

Code: Select all


  // Max&#40;x, y&#41;
#define M&#40;x, y&#41; ((&#40;x&#41; > &#40;y&#41;) ? &#40;x&#41; &#58; &#40;y&#41;)
  // A&#40;x, y&#41; returns the distance between files and ranks
#define A&#40;x, y&#41; ((&#40;x&#41; < &#40;y&#41;) ? (&#40;y&#41; - &#40;x&#41;) &#58; (&#40;x&#41; - &#40;y&#41;))
#define F&#40;x, y&#41; &#40;A&#40;&#40;x&7&#41;, &#40;y&7&#41;))
#define R&#40;x, y&#41; A&#40;&#40;x>>3&#41;, &#40;y>>3&#41;)
  // D&#40;x, y&#41; returns the distance between two squares
#define D&#40;x, y&#41; M&#40;F&#40;x, y&#41;, R&#40;x, y&#41;)
#define X&#40;x, y&#41; D&#40;x, y&#41;, D&#40;x, y+1&#41;, D&#40;x, y+2&#41;, D&#40;x, y+3&#41;
#define X1&#40;x, y&#41; X&#40;x, y&#41;, X&#40;x, y+4&#41;, X&#40;x, y+8&#41;, X&#40;x, y+12&#41;
#define X2&#40;x&#41; &#123; X1&#40;x, 0&#41;, X1&#40;x, 16&#41;, X1&#40;x, 32&#41;, X1&#40;x, 48&#41; &#125;
#define X3&#40;x&#41; X2&#40;x&#41;, X2&#40;x+1&#41;, X2&#40;x+2&#41;, X2&#40;x+3&#41;
#define X4&#40;x&#41; X3&#40;x&#41;, X3&#40;x+4&#41;, X3&#40;x+8&#41;, X3&#40;x+12&#41;

  const unsigned Distance&#91;SQ_NB&#93;&#91;SQ_NB&#93; = &#123;
    X4&#40;0&#41;, X4&#40;16&#41;, X4&#40;32&#41;, X4&#40;48&#41;
  &#125;;

#undef M
#undef A
#undef F
#undef R
#undef D
#undef X
#undef X1
#undef X2
#undef X3
#undef X4
Yes, the code is gets almost unreadable but I don't think any one would have an interest in reading code of array initialization, as long as the DEFINITION and the USE of the array remains clear. However, there are exception such as Magic BB arrays etc.
Also, I'll keep this forum updated whenever I find more ways to initialize more arrays at compile time.
User avatar
cdani
Posts: 2204
Joined: Sat Jan 18, 2014 10:24 am
Location: Andorra

Re: Initializing Arrays at compile time with macros... fun!!

Post by cdani »

Nice! :-)
zamar
Posts: 613
Joined: Sun Jan 18, 2009 7:03 am

Re: Initializing Arrays at compile time with macros... fun!!

Post by zamar »

:shock:

Ever considered writing a simple C code generator which would just generate the code for constant arrays? You can do it in less than 30 lines of code...

I tried this in the past to see if it would give any performance boost, but at least for SF there was no measurable difference in speed, so we still initialize arrays dynamically...
Joona Kiiski
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Initializing Arrays at compile time with macros... fun!!

Post by bob »

zamar wrote::shock:

Ever considered writing a simple C code generator which would just generate the code for constant arrays? You can do it in less than 30 lines of code...

I tried this in the past to see if it would give any performance boost, but at least for SF there was no measurable difference in speed, so we still initialize arrays dynamically...
There's only one place where it might help. If you refer to specific elements of such an array by using a constant subscript, such as a[1]. If you declare that as a const int array, the compiler can fold that constant during optimizing. Otherwise it has to go to memory every time, even with a constant subscript.
User avatar
vittyvirus
Posts: 646
Joined: Wed Jun 18, 2014 2:30 pm
Full name: Fahad Syed

Re: Initializing Arrays at compile time with macros... fun!!

Post by vittyvirus »

zamar wrote::shock:

Ever considered writing a simple C code generator which would just generate the code for constant arrays? You can do it in less than 30 lines of code...

I tried this in the past to see if it would give any performance boost, but at least for SF there was no measurable difference in speed, so we still initialize arrays dynamically...
Yes. I see in Stockfish you've done the same (Bitboards::init()). Infact, it's very concise, especially this one:

Code: Select all

for &#40;Color c = WHITE; c <= BLACK; ++c&#41;
      for &#40;PieceType pt = PAWN; pt <= KING; ++pt&#41;
          for &#40;Square s = SQ_A1; s <= SQ_H8; ++s&#41;
              for &#40;int i = 0; steps&#91;pt&#93;&#91;i&#93;; ++i&#41;
              &#123;
                  Square to = s + Square&#40;c == WHITE ? steps&#91;pt&#93;&#91;i&#93; &#58; -steps&#91;pt&#93;&#91;i&#93;);

                  if &#40;is_ok&#40;to&#41; && distance&#40;s, to&#41; < 3&#41;
                      StepAttacksBB&#91;make_piece&#40;c, pt&#41;&#93;&#91;s&#93; |= to;
              &#125;
for &#40;Square s1 = SQ_A1; s1 <= SQ_H8; ++s1&#41;
  &#123;
      PseudoAttacks&#91;QUEEN&#93;&#91;s1&#93;  = PseudoAttacks&#91;BISHOP&#93;&#91;s1&#93; = attacks_bb<BISHOP>&#40;s1, 0&#41;;
      PseudoAttacks&#91;QUEEN&#93;&#91;s1&#93; |= PseudoAttacks&#91;  ROOK&#93;&#91;s1&#93; = attacks_bb<  ROOK>&#40;s1, 0&#41;;

      for &#40;Square s2 = SQ_A1; s2 <= SQ_H8; ++s2&#41;
      &#123;
          Piece pc = &#40;PseudoAttacks&#91;BISHOP&#93;&#91;s1&#93; & s2&#41; ? W_BISHOP &#58;
                     &#40;PseudoAttacks&#91;ROOK&#93;&#91;s1&#93;   & s2&#41; ? W_ROOK   &#58; NO_PIECE;

          if &#40;pc == NO_PIECE&#41;
              continue;

          LineBB&#91;s1&#93;&#91;s2&#93; = &#40;attacks_bb&#40;pc, s1, 0&#41; & attacks_bb&#40;pc, s2, 0&#41;) | s1 | s2;
          BetweenBB&#91;s1&#93;&#91;s2&#93; = attacks_bb&#40;pc, s1, SquareBB&#91;s2&#93;) & attacks_bb&#40;pc, s2, SquareBB&#91;s1&#93;);
      &#125;
  steal_BetweenBB&#40;);
  &#125;
There are absolutely very few arrays (I haven't yet found one) that are compile time constants in Stockfish. And doing almost the same thing in Yaka:

Code: Select all

 // Now we'll initialize AttacksFrom array.
      // We'll start by initializing the array for knight and king
      for &#40;sq = Square&#58;&#58;A1; sq < Square&#58;&#58;SQ_NB; ++sq&#41;
      &#123;
        AttacksFrom&#91;Piece&#58;&#58;KNIGHT&#93;&#91;sq&#93; = knight_attacks&#40;SquareMask&#91;sq&#93;);
        AttacksFrom&#91;Piece&#58;&#58;KING&#93;&#91;sq&#93; = king_attacks&#40;SquareMask&#91;sq&#93;);
        for &#40;square_t sq2 = Square&#58;&#58;A1; sq2 < Square&#58;&#58;SQ_NB; ++sq2&#41; &#123;
          if &#40;bishop_attacks&#40;sq, 0&#41; & SquareMask&#91;sq2&#93;) &#123;
            SquaresBetween&#91;sq&#93;&#91;sq2&#93; = bishop_attacks&#40;sq, SquareMask&#91;sq2&#93;);
            SquaresBetween&#91;sq&#93;&#91;sq2&#93; &= bishop_attacks&#40;sq2, SquareMask&#91;sq&#93;);
          &#125; else if &#40;rook_attacks&#40;sq, 0&#41; & SquareMask&#91;sq2&#93;) &#123;
            SquaresBetween&#91;sq&#93;&#91;sq2&#93; = rook_attacks&#40;sq, SquareMask&#91;sq2&#93;);
            SquaresBetween&#91;sq&#93;&#91;sq2&#93; &= rook_attacks&#40;sq2, SquareMask&#91;sq&#93;);
          &#125;
        &#125;
      &#125;

      // Now, we need to store generate attacks for sliders. As we're
      // storing attacks on a otherwise empty board, we simply call
      // the attack mask generator with zero occupancy.
      for &#40;piece_type_t pt = Piece&#58;&#58;BISHOP; pt <= Piece&#58;&#58;QUEEN; ++pt&#41;
        for &#40;sq = Square&#58;&#58;A1; sq < Square&#58;&#58;SQ_NB; ++sq&#41;
          AttacksFrom&#91;pt&#93;&#91;sq&#93; = attacks_by&#40;pt, sq, 0&#41;;
Aleks Peshkov
Posts: 892
Joined: Sun Nov 19, 2006 9:16 pm
Location: Russia

Re: Initializing Arrays at compile time with macros... fun!!

Post by Aleks Peshkov »

Code: Select all

class Bb &#58; public BitSet<Bb, Square, std&#58;&#58;uint64_t> &#123;
...
    //bidirectional signed shift
    constexpr Bb (_t v, signed offset&#41; &#58; Bb&#40; &#40;offset >= 0&#41;? &#40;v << offset&#41;&#58;&#40;v >> -offset&#41; ) &#123;&#125;

    constexpr explicit Bb &#40;Rank&#58;&#58;_t r&#41; &#58; Bb&#123;BB&#40;0xff&#41; << 8*r&#125; &#123;&#125;
    constexpr explicit Bb &#40;File&#58;&#58;_t f&#41; &#58; Bb&#123;BB&#40;0x0101010101010101&#41; << f&#125; &#123;&#125;
...
    constexpr static Bb horizont&#40;Square sq&#41; &#123; return Bb&#123;Rank&#40;sq&#41;&#125; - sq; &#125;
    constexpr static Bb vertical&#40;Square sq&#41; &#123; return Bb&#123;File&#40;sq&#41;&#125; - sq; &#125;
    constexpr static Bb diagonal&#40;Square sq&#41; &#123; return Bb&#123;BB&#40;0x0102040810204080&#41;, 8*&#40;Rank&#40;sq&#41; + File&#40;sq&#41; - 7&#41;&#125; - sq; &#125;
    constexpr static Bb antidiag&#40;Square sq&#41; &#123; return Bb&#123;BB&#40;0x8040201008040201&#41;, 8*&#40;Rank&#40;sq&#41; - File&#40;sq&#41;)&#125; - sq; &#125;
...
&#125;;

constexpr signed Square&#58;&#58;x88&#40;signed d_file, signed d_rank&#41; const &#123;
    return this->_v + &#40;this->_v & 070&#41; + d_file + 16*d_rank;
&#125;

constexpr Bb Square&#58;&#58;operator&#40;) &#40;signed d_file, signed d_rank&#41; const &#123;
    return &#40;x88&#40;d_file, d_rank&#41; & 0x88&#41;? Bb&#58;&#58;empty&#40;) &#58; Bb&#40;static_cast<_t>(&#40;x88&#40;d_file, d_rank&#41; + &#40;x88&#40;d_file, d_rank&#41; & 7&#41;) >> 1&#41;);
&#125;

PieceTypeAttack&#58;&#58;PieceTypeAttack () &#123;
    FOR_INDEX&#40;Square, sq&#41; &#123;
        attack&#91;Rook&#93;&#91;sq&#93; = Bb&#58;&#58;vertical&#40;sq&#41; + Bb&#58;&#58;horizont&#40;sq&#41;;
        attack&#91;Bishop&#93;&#91;sq&#93; = Bb&#58;&#58;diagonal&#40;sq&#41; + Bb&#58;&#58;antidiag&#40;sq&#41;;
        attack&#91;Queen&#93;&#91;sq&#93; = attack&#91;Rook&#93;&#91;sq&#93; + attack&#91;Bishop&#93;&#91;sq&#93;;

        attack&#91;Pawn&#93;&#91;sq&#93; = sq&#40;-1, -1&#41; + sq&#40;+1, -1&#41;;

        attack&#91;Knight&#93;&#91;sq&#93; =
               sq&#40;-2, -1&#41; + sq&#40;-2, +1&#41; + sq&#40;-1, -2&#41; + sq&#40;-1, +2&#41;
             + sq&#40;+2, +1&#41; + sq&#40;+2, -1&#41; + sq&#40;+1, +2&#41; + sq&#40;+1, -2&#41;;

        attack&#91;King&#93;&#91;sq&#93; =
               sq&#40;-1, -1&#41; + sq&#40;-1, 0&#41; + sq&#40;-1, +1&#41; + sq&#40;0, -1&#41;
             + sq&#40;+1, +1&#41; + sq&#40;+1, 0&#41; + sq&#40;+1, -1&#41; + sq&#40;0, +1&#41;;
    &#125;
&#125;
jordanbray
Posts: 52
Joined: Mon Aug 11, 2014 3:01 am

Re: Initializing Arrays at compile time with macros... fun!!

Post by jordanbray »

bob wrote:
zamar wrote::shock:

Ever considered writing a simple C code generator which would just generate the code for constant arrays? You can do it in less than 30 lines of code...

I tried this in the past to see if it would give any performance boost, but at least for SF there was no measurable difference in speed, so we still initialize arrays dynamically...
There's only one place where it might help. If you refer to specific elements of such an array by using a constant subscript, such as a[1]. If you declare that as a const int array, the compiler can fold that constant during optimizing. Otherwise it has to go to memory every time, even with a constant subscript.
This is exactly why I generate this C code. It had a (very minor) performance improvement switching to 'const' memory. However, I never thought of using macros for it. I prefer simply auto-generating the arrays.