Luis Babboni wrote:Sven Schüle wrote:Luis Babboni wrote:If I´m understanding the things right, in the way I think I´ll do my TT (give 4 bytes for the position key and use 256MB for TT that is the rule for CCRL 40/4 rank), I have the option to choice between this two possibilities:
a) Have 25,165,824 entries with 1 "bucket" for each one.
b) Have 8,388,608 entries with 3 "buckets" for each one
The question is:
Is known wich posibilitie is better?
With wich possibilitie I´ll need to delete less amount of entries cause I have no place to store a new one?
Thanks.
Some remarks.
1) I am not sure whether it is common wording for everyone but for me a "bucket", in the context of a hash table in a chess engine, is the unit of information that is found by using the hash key (a part of it), and it can contain one or more hash table entries, depending on the overall hashing strategy. So I would swap the two words "bucket" and "entry" in your description above. "Bucket" is sometimes also called "cluster".
2) The total number of addressable buckets (according to #1) should be a power of two, since you want to use a certain number of bits from the hash key for your hash index. With 8,388,608 buckets that would be 23 index bits, the other number is not a power of two.
3) If I assume that you plan a hash table entry with a size of 10 bytes and you want to implement a strategy that uses more than one entry per index then you could either think about a slightly faster solution (considering cache issues already), or ignore that for a while. Ignoring would lead to defining "1 bucket = 3 entries = 3*10 bytes" while optimizing would mean "1 bucket = 3 entries + 2 padding bytes = 3*10+2 bytes" (so that two buckets fit exactly into one memory cache line).
4) Apart from these basic considerations, the answer to your question would clearly be "b". With "a" you will always store new data in the entry that is given by the index bits. With "b" you have three entries for one index. Either one or more of them are still unused, or otherwise you can decide which of these entries has the lowest benefit for you and can be overwritten (btw. not "deleted", just overwritten).
Thanks Sven!
In fact I quoted "buckets" cause I not sure about the word, I took it from here:
http://mediocrechess.blogspot.com.ar/20 ... ables.html (little below mid page talking about collisions).
[...]
I simply think in use 10 bytes per TT entry and 3 entries ("buckets"/"custers") per index so I did this calculus: 10bytes/entrie x 3 entries / index x 8,388,608 indexes = 251,658,240 bytes = 240MB that gives me extra 16MB for all other engine memory stuff in the 256MB CCRL rules.
I did not know why the number of "buckets"/"clusters" must be a power of 2. For index I think in use the last 4 bytes of the number I use to identify a position.
The wording may differ. What I call "buckets" is called differently by others, e.g. "cluster", it could also be called "group". Common language is that a transposition table (TT) consists of TT entries (or TT elements) which may or may not be grouped; in your case the plan is to have three entries per group. Let's use "bucket" for a group from now on. You access buckets through their table index which you obtain from the TT hash key. Since the complete TT hash key is too large to serve as the table index itself (typically the hash key has a size of 64 bit), and even four of those eight bytes are too large for that purpose, you need to define a mapping "TT hash key => table index". The typical, and most simple, mapping is to take the lowest N bits of the hash key as the index. And that is already the reason why your table should have a size of 2^N "buckets". It would also be possible to use an "arbitrary" size but then the mapping would be slightly more difficult (essentially it is always "hash key" modulo "table size"). 8,388,608 buckets means N=23, so you calculate the table index from the hash key by simply taking the lower 23 bits of it, and there you are. If you want to reserve the double size for your hash table then you increase N by one, and so on.
Now you have the index for a bucket consisting of, in your case, three TT entries. You need two operations, where each one starts by extracting the index from the hash key and then doing something with those three entries found there:
- "probe" => input is the hash key, the current depth, alpha and beta, and output is either a "matching" TT entry or the information that there is none; a TT entry is "matching" if the part of the hash key that you have stored in the entry is identical to the corresponding part of the hash key given as input, and if other conditions are matching as well (e.g. stored depth >= current depth, but there is more);
- "store" => input is again the hash key, the current depth, the score, the type of score (exact/lower bound/upper bound), and maybe more; the data will always be stored, either in an entry that was unused so far, or (usually) by overwriting an entry that previously contained data for a position for which its hash key has the same lower N index bits.
"probe" will simply loop over the three entries, compare the stored key part to the corresponding hash key part (to reduce the chance that the stored information actually belongs to a different position - but you can't perfectly exclude that), stop at the first matching entry, do the other comparisons for that entry (depth etc.), and return a result. "store" will loop over the entries as well, stop at the first entry that is unused (usually determined as "stored key part == 0"), and store the data there; or, if all three entries of the bucket are already in use, decide which one shall be replaced.
"Power of 2" is mainly for the number of table indices (2^N, in your case 2^23). If the number of bytes per table index is a power of 2 as well (e.g. 32) then of course the whole table size in bytes is a power of 2, but that is not a "hard requirement". It will only improve performance.
But you can forget about the "padding" for now, and simply have buckets of 3 entries = 3*10 = 30 bytes.