Kindergarten Bitboard density of array.

[OliverBr]

Since over 20 years, OliThink used a readable and symmetry array u64 rays[0x8000] for the Kindergarten Move Generator, which implements like this (and for XRays needing second half):

Code: Select all

#define RATT1(f) rays[(f << 6) | key000(BOARD, f)]
#define RATT2(f) rays[(f << 6) | key090(BOARD, f) | 0x1000]
#define BATT3(f) rays[(f << 6) | key045(BOARD, f) | 0x2000]
#define BATT4(f) rays[(f << 6) | key135(BOARD, f) | 0x3000]

Of course, an array u64 rays[0x8000] needs 256 Kbyte memory and it is the most used array (move generator and evaluation)
In very modern CPUs the first Level Cache may have place for all the data, but it is not guaranteed.
So, in order to squeeze the array into a more manageable size like u64 rays[0x800] = 16 Kbyte there has to be additional operations and breaking of symmetry:

Code: Select all

#define RATT1(f) rays[((f&7) << 6) | key000(BOARD, f)] & rmask0[f]
#define RATT2(f) (rays[((f>>3) << 6) | key090(BOARD, f) | 0x200]) << (f&7)
#define BATT3(f) rays[((f&7) << 6) | key045(BOARD, f)] & bmask45[f]
#define BATT4(f) rays[((f&7) << 6) | key135(BOARD, f)] & bmask135[f]

For big CPUs the ELO gain is minimal (under 10 ELO), but there is the educated guess, that in CPUs with less CPU Cache this could be much bigger.

Now what is here the best way to go?
Maintain readability and symmetry?
Or catch those few ELO points, and perform better on tourney with lesser CPUs?

Another observation: Splitting an array into smaller arrays seems to change the performance. Is this a known feature of CPU Cache?

[OliverBr]

I have changed it now for the newest 5.11.5.
Here are the new rays for the Kindergarten implemention of year 2004 (before it was even called so).
Symmetry is broken for the (vertical) 90-Attack, but it needs much less memory than before, which can be important for CPU Level 1 Cache.

Code: Select all

#define RATT1(f) raysRank[f&7][key000(BOARD, f)] & rmask0[f]
#define RATT2(f) raysAFile[f>>3][key090(BOARD, f)] << (f&7)
#define BATT3(f) raysRank[f&7][key045(BOARD, f)] & bmask45[f]
#define BATT4(f) raysRank[f&7][key135(BOARD, f)] & bmask135[f]
#define RXRAY1(f) (xrayRank[f&7][key000(BOARD, f)] & rmask0[f])
#define RXRAY2(f) (xrayAFile[f>>3][key090(BOARD, f)] << (f&7))
#define BXRAY3(f) (xrayRank[f&7][key045(BOARD, f)] & bmask45[f])
#define BXRAY4(f) (xrayRank[f&7][key135(BOARD, f)] & bmask135[f])