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 

pawn enumeration
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 12753
Location: Amsterdam
PostPost subject: Re: price of complex indexing    Posted: Fri Jul 27, 2012 4:06 pm Reply to topic Reply with quote
Daniel Shawul wrote:
You make so many random access to RAM (pretty much like a hash table in chess engines) that will eventually be your bottleneck.


The trick is to localize the accesses, and do as much as you can in cache. Like bringing a slice with fixed constellation of all black pieces, but containing all possible white piece constellations of white pieces in cache when you are making a pass for doing white moves. Then all accesses will be in that slice, until you start processing the next black constellation, after which you are completely done with the slice until the next (black) pass.

And if that does not fit, split the pass in two, where you do moves of two white pieces during one pass, and those of the other two white pieces in the other pass, so you can also freeze the white pieces whose moves you are not handling in that pass. Note that there always is one piece that you cannot freeze, but have to be cached in all possible locations even when you are not moving it, because cache lines are 64 byte. Usually I take this the black King. So slices with two movable white pieces in fact are 3-men slices, containing 256K positions.

Kings can also help in slicing: although slices with fixed King position wil not be invariant under King moving, the Kings move pretty locally, so you can treat their moves in an order that never requires you to have more than 4 King slices in cache at any time, when you do half the King moves in one white pass, and the other half in the other white pass.

syzygy wrote:
(There might be a problem though with such cache lines mapping to the same cache entry, since they are at distances (a mutiple of) a power of two.)


This can be avoided by using 64-byte spacer regions in between the higher slices. If you don't want to do that in the index, (e.g. to keep it easy to mirror the board by bit-manipulation on the index), you can use an index->address translation just before every access, like

address = index*01000101 >> 18;

This is still much faster than the access itself, so it will not cause a noticeable slowdown. (As it will be computed in parallel.)

Last edited by H.G.Muller on Fri Jul 27, 2012 4:23 pm; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
pawn enumeration Daniel Shawul Tue Jul 24, 2012 1:23 am
      Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 1:36 am
            Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 2:06 am
                  Re: pawn enumeration Kevin Hearn Tue Jul 24, 2012 2:35 am
                        Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 3:01 am
                              Re: pawn enumeration Kevin Hearn Tue Jul 24, 2012 3:28 am
                                    Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 3:48 am
                                          Re: pawn enumeration Kevin Hearn Tue Jul 24, 2012 4:06 am
                                                Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 4:57 am
                  Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 4:57 pm
                        Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 6:55 pm
                  Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 7:01 pm
                        Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 9:47 pm
                              Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 10:47 pm
                                    Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 10:51 pm
                                          Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 11:00 pm
                                                Re: pawn enumeration Wylie Garvin Wed Jul 25, 2012 6:40 pm
                                                      Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 6:59 pm
                                                            Re: pawn enumeration Ronald de Man Wed Jul 25, 2012 7:22 pm
                                                                  Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 7:27 pm
                                                            Re: pawn enumeration Wylie Garvin Wed Jul 25, 2012 11:41 pm
                                                                  Re: pawn enumeration Ronald de Man Thu Jul 26, 2012 12:19 am
                                                                  Re: pawn enumeration Vincent Diepeveen Fri Jul 27, 2012 12:48 pm
                                                                        Re: pawn enumeration Ronald de Man Fri Jul 27, 2012 2:42 pm
                                                      Re: pawn enumeration Ronald de Man Wed Jul 25, 2012 7:21 pm
                                          Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 11:08 pm
                                                Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 11:22 pm
                                                      Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 11:39 pm
                                                      Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 11:39 pm
                                                            Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 12:08 am
      Related: malloc virtual Daniel Shawul Tue Jul 24, 2012 2:29 am
            Re: Related: malloc virtual Jon Dart Tue Jul 24, 2012 2:50 pm
                  Re: Related: malloc virtual Daniel Shawul Tue Jul 24, 2012 6:39 pm
                        Re: Related: malloc virtual Vincent Diepeveen Tue Jul 24, 2012 10:38 pm
                              Re: Related: malloc virtual Daniel Shawul Wed Jul 25, 2012 11:56 am
                                    Re: Related: malloc virtual Vincent Diepeveen Wed Jul 25, 2012 12:00 pm
                                          Re: Related: malloc virtual Daniel Shawul Wed Jul 25, 2012 12:06 pm
                                                Re: Related: malloc virtual Vincent Diepeveen Wed Jul 25, 2012 12:21 pm
                                                      Re: Related: malloc virtual Daniel Shawul Wed Jul 25, 2012 12:34 pm
                                                            Re: Related: malloc virtual Vincent Diepeveen Wed Jul 25, 2012 12:51 pm
      Re: pawn enumeration H.G.Muller Tue Jul 24, 2012 6:32 am
            Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 12:34 pm
            Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 4:31 pm
                  Re: pawn enumeration Daniel Shawul Tue Jul 24, 2012 9:29 pm
                        Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 10:22 pm
                              Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 11:01 pm
                                    Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 11:12 pm
                                          Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 11:32 pm
                                                Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 11:58 pm
                                                      Re: pawn enumeration Ronald de Man Wed Jul 25, 2012 1:04 am
                                                            Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 1:19 am
                        Re: pawn enumeration Ronald de Man Tue Jul 24, 2012 10:25 pm
                              Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 10:44 pm
                                    Re: pawn enumeration Daniel Shawul Wed Jul 25, 2012 12:08 pm
                                          Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 12:18 pm
                                                Re: pawn enumeration Daniel Shawul Wed Jul 25, 2012 12:30 pm
                                                      Re: pawn enumeration Vincent Diepeveen Wed Jul 25, 2012 12:43 pm
                                    Re: pawn enumeration Ronald de Man Wed Jul 25, 2012 6:58 pm
      Re: pawn enumeration Wylie Garvin Tue Jul 24, 2012 5:21 pm
            Re: pawn enumeration Vincent Diepeveen Tue Jul 24, 2012 5:26 pm
      price of complex indexing Daniel Shawul Fri Jul 27, 2012 1:24 pm
            Re: price of complex indexing Vincent Diepeveen Fri Jul 27, 2012 2:01 pm
                  Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 3:04 pm
                        Re: price of complex indexing Vincent Diepeveen Sun Jul 29, 2012 10:15 pm
                              Re: price of complex indexing Daniel Shawul Mon Jul 30, 2012 12:09 am
                                    Re: price of complex indexing Vincent Diepeveen Mon Jul 30, 2012 1:06 pm
                                          Re: price of complex indexing Daniel Shawul Mon Jul 30, 2012 1:45 pm
            Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 2:03 pm
                  Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 2:52 pm
                        Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 3:18 pm
                              Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 4:13 pm
                                    Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 9:46 pm
                                          Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 10:40 pm
                                                Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 10:52 pm
                                                      Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 11:10 pm
                                                            Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 11:53 pm
                                                                  Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 12:31 am
                                                                  Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 10:15 pm
                        Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 4:00 pm
                              Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 6:16 pm
                                    Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 9:47 pm
                                          Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 11:02 pm
                                                Re: price of complex indexing Ronald de Man Fri Jul 27, 2012 11:29 pm
                                                      Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 12:04 am
                                                            Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 1:00 am
                                                                  Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 1:15 am
                                                                  Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 1:30 am
                                                                  Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 1:59 am
                                                                        Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 2:48 am
                                                                              Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 3:21 am
                                                                                    Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 4:05 am
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 2:43 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 3:02 pm
                                                                  Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 2:39 am
                                                                        Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 3:37 am
                                                                              Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 2:49 pm
                        Re: price of complex indexing H.G.Muller Fri Jul 27, 2012 4:06 pm
                              Re: price of complex indexing Daniel Shawul Fri Jul 27, 2012 7:37 pm
                                    Re: price of complex indexing H.G.Muller Sat Jul 28, 2012 8:32 am
                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 1:20 pm
                                                Re: price of complex indexing H.G.Muller Sat Jul 28, 2012 1:40 pm
                                                      Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 2:10 pm
                              Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 12:27 am
                                    Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 11:42 am
                                          Re: price of complex indexing H.G.Muller Sat Jul 28, 2012 12:19 pm
                                                Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 1:39 pm
                                                      Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 2:04 pm
                                                            Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 3:11 pm
                                                                  Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 3:42 pm
                                                                  Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 3:46 pm
                                                                        Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 5:19 pm
                                                                              Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 5:22 pm
                                                                                    Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 5:34 pm
                                                                                          Cutoff rates Daniel Shawul Sat Jul 28, 2012 6:09 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 6:13 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 6:18 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 6:53 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 7:04 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 7:11 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 7:16 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 7:45 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 8:10 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 10:24 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 10:31 pm
                                                                                          Re: price of complex indexing Sven Schüle Sat Jul 28, 2012 10:46 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 10:53 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 11:23 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 11:39 pm
                                                                                          Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 11:50 pm
                                                                                          Re: price of complex indexing Daniel Shawul Sat Jul 28, 2012 11:54 pm
                                                      Re: price of complex indexing Ronald de Man Sat Jul 28, 2012 5:15 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