Can someone explain what advantage there is to...

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Can someone explain what advantage there is to...

Post by Zenmastur » Mon Oct 06, 2014 10:44 pm

... saving the entire hash key in each entry of TT.

Seems like a waste of memory or am I missing something?

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Can someone explain what advantage there is to...

Post by AlvaroBegue » Tue Oct 07, 2014 12:32 am

The bits of the key that were used to determine what entry (or bin) to use don't need to be stored, sure. But if you are really afraid of collisions, you may want to store a 64-bit hash key and use a separate one to index into the table.

Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Re: Can someone explain what advantage there is to...

Post by Zenmastur » Tue Oct 07, 2014 2:01 am

AlvaroBegue wrote:The bits of the key that were used to determine what entry (or bin) to use don't need to be stored, sure. But if you are really afraid of collisions, you may want to store a 64-bit hash key and use a separate one to index into the table.
So what you are saying is, if I'm superstitious I should waste memory in my TT other wise it's OK not to waste space. Does this accurately sum up your response ?

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Can someone explain what advantage there is to...

Post by AlvaroBegue » Tue Oct 07, 2014 2:03 am

Zenmastur wrote:
AlvaroBegue wrote:The bits of the key that were used to determine what entry (or bin) to use don't need to be stored, sure. But if you are really afraid of collisions, you may want to store a 64-bit hash key and use a separate one to index into the table.
So what you are saying is, if I'm superstitious I should waste memory in my TT other wise it's OK not to waste space. Does this accurately sum up your response ?

Regards,

Forrest
No, I don't think that's what I said. It is always wasteful to store bits that are encoded in the index of the entry (or bin).

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

When the whole key is stored

Post by sje » Tue Oct 07, 2014 2:10 am

When the whole key is stored in a transposition table entry, then it's simple to create a new table with a different size and initialize it with entries from the old table.

This is the technique used in Common Lisp which includes a hash table type as a standard type. There, a table starts small and grows only on demand. A Common Lisp hash table can also be explicitly resized with a simple loop if needed.

Zenmastur
Posts: 487
Joined: Sat May 31, 2014 6:28 am

Re: When the whole key is stored

Post by Zenmastur » Tue Oct 07, 2014 4:52 am

sje wrote:When the whole key is stored in a transposition table entry, then it's simple to create a new table with a different size and initialize it with entries from the old table.

This is the technique used in Common Lisp which includes a hash table type as a standard type. There, a table starts small and grows only on demand. A Common Lisp hash table can also be explicitly resized with a simple loop if needed.
That I could understand if most chess programs were written in Lisp OR they had dynamically re-sizeable TT. Most don't. So I'm still left wondering why they choose to waste memory?

Lets suppose I have a system with 64 Gib of memory with 60 Gib available to a chess program. Most programs require a power of 2 for the number of TT entries. With this restriction and a 16-byte entry size 2^31 entries is all you can squeeze into the available memory. This leaves about 28 Gib for the rest of the program which is probably over-kill.

On the other hand, if I only store 4 bytes of the key and squeeze the rest of the TT information into 6 bytes (e.g. 9 bits for the move etc.) then in a 64 byte cache line I can store 6 TT entries with some room left over for book-keeping if needed or wanted). Now, 2^32 entries occupy just 42.7 Gib. This leaves 17.3 Gib for the rest of the program/data. ( Note that this works with much smaller memory sizes although the raw numbers will be different. i.e. this will work on a 8, 16, or 32 Gib system.). Doubling your TT size with out adding memory to your system is significant.

Regards,

Forrest
Only 2 defining forces have ever offered to die for you.....Jesus Christ and the American Soldier. One died for your soul, the other for your freedom.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Can someone explain what advantage there is to...

Post by hgm » Tue Oct 07, 2014 5:28 am

None of my engines stores more than 32 bits of the hash key. Joker uses 9-byte hash entries, 7 per bucket.

5 entries of 12 bytes each is also a nice design, if you want to store dual bounds + depth (2x 2-byte score, 2x 1-byte depth, 2-byte move, 4-byte key). Then you have 4 bytes left in a 64-byte bucket, which can be used for 4 aging fields (while the 5th entry is always-replace, and so does not need an aging field).

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: When the whole key is stored

Post by sje » Tue Oct 07, 2014 5:44 am

Zenmastur wrote:That I could understand if most chess programs were written in Lisp OR they had dynamically re-sizeable TT. Most don't.
"Most" ≠ "All"

The number of signature bits recoverable from a table entry given its contents and its address governs the false positive rate when all other factors are held equal.

40 bits will be enough for storing a moderately sized opening book.
64 bits will not be enough for calculating perft(13) and higher.

It's not necessary that the length of a transposition table be a power of two. Another approach is to have the entry count of the table be some prime p and the address of an entry given by the value key mod p. For some years now, the cost of a division isn't much different than the cost of a mask and shift; using key mod p can be an improvement because it allows for better utilization of available memory. After all, there are many primes from which to choose.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: When the whole key is stored

Post by syzygy » Tue Oct 07, 2014 8:42 am

Zenmastur wrote:So I'm still left wondering why they choose to waste memory?
The easy answer is that they do that because it's easy.

Hash entries have a fixed size indepedent of the size of the hash table (i.e. independent of the number of bits used for indexing). So it does not make sense to eliminate exactly those bits that are used for indexing, unless the size of your hash table is fixed. Also keep in mind that most want hash entries to be 16 bytes, so that 4 entries fit exactly in a cacheline. Hash entries of 12 bytes are less efficient to access.

Storing 32 bits of the key in the hash entry and using the rest for indexing into the table seems to be the best compromise to me, also because nowadays you probably use most of the other 32 bits for indexing into the table anyway.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: When the whole key is stored

Post by syzygy » Tue Oct 07, 2014 8:44 am

sje wrote:It's not necessary that the length of a transposition table be a power of two. Another approach is to have the entry count of the table be some prime p and the address of an entry given by the value key mod p. For some years now, the cost of a division isn't much different than the cost of a mask and shift; using key mod p can be an improvement because it allows for better utilization of available memory. After all, there are many primes from which to choose.
No added benefit in requiring p to be prime.

Post Reply