Rein Halbersma wrote:syzygy wrote:koedem wrote:However if you have to put the TB on a HDD the much larger lookup times probably make it too slow to being offset by the gain from using TBs. (though I am just speculating of course)
It will depend on the probing depth. Doing a TB probe allows the search to cut the whole subtree, so if the subtree is large enough (remaining depth is high enough) the probe will be worth it already for that reason. The improved accuracy is then an added bonus.
IIRC, you still do memory-mapped IO with unconditional probing?
Yes, it's so much easier. Of course probing can be limited to a particular remaining search depth and above.
In checkers/draughts, where the dbs are adding quite a bit of playing strength, people write their own caching and conditionally probe the dbs. Typically they keep 4K (or whatever size the disk controller nowadays uses) blocks in an LRU-cache.
But how are you going to do that efficiently in user space if you have 32 threads or so trying to access the TBs at the same time? I prefer to leave all the locking logic to the kernel, which can probably do it more efficiently anyway.
When the search encounters an endgame, first the cache is being probed (unconditionally), if there is a cache miss, then some tunable function of search depth and search bound is being used to decide whether a disk read should be done. If so, a new block is being loaded and overwrites the LRU block in the cache. This disk read could also be done asynchronously in a separate thread, so that if a re-search is done the block is in cache.
But the block to be read from disk might already/still be in the disk cache without the program knowing it.
On Linux it is possible (with mincore()) to check whether a particular virtual-memory address corresponds to an existing physical page. In theory that could be used to implement "smart" probing, but I don't know how efficient it would be.
With 6-piece TBs on SSD and a decent amount of RAM, there is no real probing overhead. With 7-piece TBs on HDD that will of course be different.