ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

PEXT Bitboards
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Ronald de Man



Joined: 28 Feb 2012
Posts: 3684

PostPost subject: Re: PEXT Bitboards    Posted: Fri Jun 07, 2013 9:57 pm Reply to topic Reply with quote

Gerd Isenberg wrote:
Haswell BMI2 PEXT replacement for Fancy Magic Bitboards with variable shift comes real now. PEXT r64, r64, r64 has latency of 3 and reciprocal throughput of 1 cycle (like imul r64,r64):
Code:
U64 arrAttacks  [...]; // ~840 KByte all rook and bishop attacks
U64 arrRookBase  [64]; // arrAttacks base offset per rook square
U64 arrRookMask  [64]; // 10..12 relevant occupancy bits per rook square
U64 arrBishopBase[64]; // arrAttacks base offset per bishop square
U64 arrBishopMask[64]; //  5.. 9 relevant occupancy bits per bishop square

U64 rookAttack(U64 occ, enumSquare sq) {
  return arrAttacks[arrRookBase[sq] + _pext_u64(occ, arrRookMask[sq])];
}

U64 bishopAttack(U64 occ, enumSquare sq) {
  return arrAttacks[arrBishopBase[sq] + _pext_u64(occ, arrBishopMask[sq])];
}

http://users.atw.hu/instlatx64/GenuineIntel00306C3_Haswell_InstLatX64.txt

My tablebase generator (when compiled with -DBMI2) in addition uses pdep to reduce the table to 210.25 KB (a bit smaller is possible by reusing entries, but I haven't yet looked at that very well).

I haven't tested on a Haswell processor, but it works correctly with my own implementation of pext and pdep:
Code:
uint64 bit[64]; // bit[i] = 1ULL << i;

uint64 _pext_u64(uint64 val, uint64 mask)
{
  uint64 res = 0;
  int i = 0;

  val &= mask;
  while (val) {
    uint64 p = val & -val;
    uint64 q = mask & -mask;
    while (q != p) {
      i++;
      mask &= mask - 1;
      q = mask & -mask;
    }
    mask &= mask - 1;
    res |= bit[i++];
    val &= val - 1;
  }

  return res;
}

uint64 _pdep_u64(long64 val, long64 mask)
{
  uint64 res = 0;
  int i = 0;

  while (mask) {
    if (val & bit[i++])
      res |= mask & -mask;
    mask &= mask - 1;
  }

  return res;
}

I couldn't easily get it faster (on my i7 in combination with my generator), but maybe someone has a better implementation.
Taking bit[i] and incrementing i surprisingly was faster than uint64 bb = 1 and bb <<= 1 at each iteration.
_________________
https://github.com/syzygy1/tb
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
PEXT Bitboards Gerd Isenberg Fri Jun 07, 2013 2:09 pm
      Re: PEXT Bitboards Ronald de Man Fri Jun 07, 2013 9:57 pm
            Re: PEXT Bitboards Gerd Isenberg Fri Jun 07, 2013 10:52 pm
                  Re: PEXT Bitboards Ronald de Man Fri Jun 07, 2013 11:49 pm
                        Re: PEXT Bitboards Jhor A. Vi Thu Jun 13, 2013 12:12 pm
                              Re: PEXT Bitboards Gerd Isenberg Thu Jun 13, 2013 1:53 pm
                                    Re: PEXT Bitboards Jhor A. Vi Mon Mar 24, 2014 5:37 am
                                          Re: PEXT Bitboards Paul Henri Mon Mar 24, 2014 6:10 am
                                          Re: PEXT Bitboards Gerd Isenberg Mon Mar 24, 2014 4:07 pm
                  Re: PEXT Bitboards Rein Halbersma Sun Jul 16, 2017 8:00 pm
                        Re: PEXT Bitboards Lucas Braesch Mon Jul 17, 2017 5:02 am
                              Re: PEXT Bitboards Rein Halbersma Mon Jul 17, 2017 5:44 am
                                    Re: PEXT Bitboards Gerd Isenberg Mon Jul 17, 2017 2:48 pm
                                    Re: PEXT Bitboards Ronald de Man Mon Jul 17, 2017 8:08 pm
                                          Re: PEXT Bitboards Rein Halbersma Mon Jul 17, 2017 8:22 pm
                                                Re: PEXT Bitboards Ronald de Man Mon Jul 17, 2017 10:54 pm
                              Re: PEXT Bitboards J. Wesley Cleveland Mon Jul 17, 2017 3:04 pm
                                    Re: PEXT Bitboards Lucas Braesch Tue Jul 18, 2017 7:39 am
                                          Re: PEXT Bitboards J. Wesley Cleveland Tue Jul 18, 2017 4:16 pm
                        Re: PEXT Bitboards Rein Halbersma Mon Jul 17, 2017 8:13 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads