Can someone explain what advantage there is to...

[Zenmastur]

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

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

Regards,

Forrest

[AlvaroBegue]

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]

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

[AlvaroBegue]

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).

[sje]

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]

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

[hgm]

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).

[sje]

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]

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]

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.