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 

Hash table division
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Robert Hyatt



Joined: 27 Feb 2006
Posts: 15814
Location: Birmingham, AL
PostPost subject: Re: Hash table division    Posted: Sat Apr 07, 2012 4:16 pm Reply to topic Reply with quote
diep wrote:
bob wrote:
diep wrote:
bob wrote:
sje wrote:
Symbolic has always done this with one table for WTM and one for BTM.


I simply xor a STM value. I'm not sure I'd want two different tables. What happens in positions where one side has lots of mobility and one side is very restricted? One table fills up, the other is barely used...

I've never thought, in any scenario, that two separate tables works, unless you talk about two tables in the Belle sense, where one is a depth-preferred replacement strategy while the other is an always-store table. But for Belle, both store both WTM/BTM entries, so there is no "side-to-move boundary".


Actually Bob you were doing 2 total different lookup until start of this century. Even some years after i noticed it and wrote about it several times in the forum, Crafty kept losing system time to 2 random probes.


I already mentioned that as the "Belle approach" in my post above. But the table was not divided into a black and a white part. Never done that. What I do today, I did in Cray Blitz back in the 80's as anyone can check (we used 8-entry buckets on the Cray since vector loads made that a "for free" operation, as opposed to 4-entry buckets today). And we never had a separate table for black and white, because nothing makes those positions balance evenly.


Quote:


Now i say this in my own words: when it was convenient to wintel programmer Eugene Nalimov, to change that, he did do so.
Of course not for his employer, it was done well in time before AMD had a faster latency to the RAM with opteron and built in memory controller in k8, so we can't prove any relationship there. Sincethen you're also doing sequential probes Bob Smile
And not a day before until Eugene modified that... Smile

Vincent

p.s. normally spoken specint2004 would have released in 2004 and crafty also was a candidate for specint2004. Intel didn't have an on die memory controller until years later, so that Nalimov changed that, despite me writing it for years into the forum, was a most lucky change for wintel, which the years before that, despite mewriting it regurary in the CCC, wasn't convenient for them as during the on die memory controllers, intel had the fastest random latency. That changed to AMD's advantage when april 2003 they released the opteron that had an on die memory controller.
Interesting to see how $100 billion companies still are dependant there upon lucky coincidences... ...delaying this change that long really was lucky for them....


Of course all is correct what you write - you were doing 2 random probes. 2 sequential probes is a lot faster though. That's the change i am speaking about.


The belle approach had two advantages:

(1) two tables, one could be 2x the other, letting you use 3/4 of memory for hash, as opposed to just 1/2.

(2) simple to do replacement. Depth in one, just overwrite the other.

When the PC went to 64 byte cache lines, the 4-bucket approach made more sense. This would be two cache line files on a 32 byte cache line machine, which is about as bad as two random probes.. Today I get the entire bucket in one line and avoid that.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
Hash table division Ed Schroder Thu Apr 05, 2012 8:30 am
      Re: Hash table division H.G.Muller Thu Apr 05, 2012 9:47 am
      Re: Hash table division Steven Edwards Thu Apr 05, 2012 6:11 pm
            Re: Hash table division Robert Hyatt Thu Apr 05, 2012 6:58 pm
                  Re: Hash table division Vincent Diepeveen Thu Apr 05, 2012 11:36 pm
                        Re: Hash table division Robert Hyatt Fri Apr 06, 2012 6:58 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 8:37 pm
                                    Re: Hash table division Robert Hyatt Sat Apr 07, 2012 4:16 pm
                                          Re: Hash table division Vincent Diepeveen Sat Apr 07, 2012 4:27 pm
      Re: Hash table division Robert Hyatt Thu Apr 05, 2012 7:00 pm
            Re: Hash table division Sam Hamilton Thu Apr 05, 2012 8:39 pm
                  Re: Hash table division Robert Hyatt Fri Apr 06, 2012 7:01 pm
            Re: Hash table division Ed Schroder Fri Apr 06, 2012 1:29 pm
                  Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:33 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:22 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:29 pm
                  Re: Hash table division H.G.Muller Fri Apr 06, 2012 1:35 pm
                        Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:37 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:06 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:15 pm
                              Re: Hash table division Robert Houdart Fri Apr 06, 2012 2:24 pm
                                    Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:47 pm
                                    Re: Hash table division Ed Schroder Fri Apr 06, 2012 4:53 pm
                                          Re: Hash table division Robert Houdart Fri Apr 06, 2012 5:24 pm
                                                Re: Hash table division Sam Hamilton Fri Apr 06, 2012 5:29 pm
                                                      Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 8:33 pm
                                                            Re: Hash table division Sam Hamilton Sat Apr 07, 2012 1:39 am
                                                                  Re: Hash table division Vincent Diepeveen Sat Apr 07, 2012 8:42 am
                                                                        Re: Hash table division Sam Hamilton Sat Apr 07, 2012 3:11 pm
                                                Re: Hash table division Ed Schroder Fri Apr 06, 2012 9:55 pm
                                                      Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 10:25 pm
                                                      Re: Hash table division Robert Houdart Fri Apr 06, 2012 10:27 pm
                                                            Re: Hash table division Ed Schroder Sat Apr 07, 2012 3:27 pm
                              Re: Hash table division H.G.Muller Fri Apr 06, 2012 4:24 pm
                                    Re: Hash table division Ed Schroder Fri Apr 06, 2012 5:05 pm
                                          Re: Hash table division H.G.Muller Sat Apr 07, 2012 12:43 pm
                                    Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 5:14 pm
                  Re: Hash table division Robert Hyatt Fri Apr 06, 2012 8:44 pm
      Re: Hash table division Vincent Diepeveen Thu Apr 05, 2012 11:15 pm
            Re: Hash table division Ed Schroder Fri Apr 06, 2012 1:53 pm
                  Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:58 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:10 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:23 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