syzygy wrote: ↑Sun Jun 03, 2018 6:01 pm
To play it safe, one could make the hash table array 1 entry larger. Then probes of arbitrary keys are guaranteed to stay within the allocated array. This could also solve your current problem:
I guess this is the most elegant solution; one can even do it runtime, adding more elements as needed.
To do it at runtime you would have to resize the array at runtime, which would need some more changes.
The array is accessed on every TB probe. Since its content is static (all material signature keys corresponding to all 7-men material combinations), the optimal size can easily be determined once and for all. We don't need to have the TB files available to do that; we can simply temporarily remove the check in lines 439 and 440.
Nordlandia wrote: ↑Sun Jun 03, 2018 5:14 pm
Question for Seese: do you use some of the already generated 7-men sets for live website or wait until complete set is finished?
I use what is available. At some point, I will run out of disk space, though.
Do you notice any significant slowdown caused by 7-men compared to 6-men?
We're worried that the speed penalty is considerable more than 6-men.
Probing 7-men inflict higher knps penalty. Probing algorithm of Houdini suits 7-men bases as tb hits flow can be adjusted to prevent excessive tablebase consulting, simply for avoiding wasting engine speed.
Nordlandia wrote: ↑Sun Jun 03, 2018 6:41 pm
Do you notice any significant slowdown caused by 7-men compared to 6-men?
We're worried that the speed penalty is considerable more than 6-men.
I haven't done extensive testing on this. I do have SSDs that cache in front of the disks (a fairly fast RAID), but probably nowhere near enough.
Probing 7-men inflict higher knps penalty. Probing algorithm of Houdini suits 7-men bases as tb hits flow can be adjusted to prevent excessive tablebase consulting.
Based on the (lack of) information in the thread so far, I don't think we can say much about how Houdini's selective probing will behave wrt. 7-men tablebases.
Sesse wrote: ↑Sun Jun 03, 2018 10:21 pm
One overflow element in the hash table was enough, even for the full set of 1311 tables.
I suppose you meant to type 1511.
It would be interesting to know the total number of times the hash insertion loop ran. Dividing this number by 2*1511-20 = 3002 would give us the average number of times the hash lookup loop runs for each probe.
I don't know where your subtraction of 20 comes from, but I did some experiments based on number of probes on lookup (which is very similar to insert probe numbers, but not identical). Going from 4K to 8K entries reduces average probe length from 2.06 to 1.30 and worst from 68 to 9.
However, I also implemented Robin Hood hashing (which is like three lines of code). Barring bugs, it seems to have taken 4K average probe length from 2.06 to 2.05 and worst from 68 to 11 (!). 8K with RH goes to average 1.29 and worst 4, which is great. So it gives a pretty good boost to the worst case at these medium-high load factors. The Robin Hood hashing is pretty much a free lunch for reducing the worst case—4K versus 8K is a matter of taste, I guess. I'd probably stay with 4K, but I'm not the expert here.
The minus 20 comes from 5 symmetric 2v2 and 15 symmetric 3v3 tables. For those tables key2 == key: https://github.com/official-stockfish/S ... #L450-L451
It seems insert() reinserts key2 in the same slot as key, so it's probably OK.
I think the Robin Hood trick should leave the average exactly unchanged. (I am guessing that the double counting of symmetric tables somehow explains the change from 2.06 to 2.05.) Reducing the worst case length is probably a good thing.
If the average is just above 2, there is probably not much to gain compared to the time the rest of the probe takes. And doubling the size of the table also increases cache pressure.
According to this page, the average number of probes for successful find is estimated to be
For alpha = 3002/4096, this gives 2.372. So what you measured is better than expected.
For alpha = 3002/8192, we get 1.289, which is slightly better than what you measured.
