Hi everyone ,
I need to implement cacheing in my EGTB probe code and before anyone says "why not use existing (Nalimov, scorpio bitbases) implementations?", I simply want to do it because it is to be used in a checkers engine.
I haven't yet implemented LRU, because I don't want to make conceptual mistakes.
Has anyone sucessfully implemented a multithreaded LRU cache for probing the EGTBs?
The way I see it we should lock inserting, reading and deleting, but this seems to me a slow solution to use in a multithreaded engine.
Any thoughts and advices on this?
That multi-threaded LRU is a 'conceptual problem' for EGTBs is a mole invented by those who don't use it to badmouth those who do. Infact I , myself, pointed this out in a discussion just to be honest and now used against me Well one can just ..ahm... disable it ... if it is not wanted! The system will take care of it as much as it can but I have always found even a small cache of 16MB helped. In my experience up to 8 cpus it was never a problem, but if you don't feel comfortable with it there are lockless ways to traverse a double-linked list as mentioned here http://www.ebaytechblog.com/2011/08/30/ ... u-caching/ . But first try the simpler version , which fortunately I have in a ready to use form here https://github.com/dshawul/egbbdll/blob/master/cache.h. Include cache.h and cache.cpp in your project and cache a block of data whose size you can adjust.
Cardoso wrote:Hi everyone ,
I need to implement cacheing in my EGTB probe code and before anyone says "why not use existing (Nalimov, scorpio bitbases) implementations?", I simply want to do it because it is to be used in a checkers engine.
I haven't yet implemented LRU, because I don't want to make conceptual mistakes.
Has anyone sucessfully implemented a multithreaded LRU cache for probing the EGTBs?
The way I see it we should lock inserting, reading and deleting, but this seems to me a slow solution to use in a multithreaded engine.
Any thoughts and advices on this?
best regards,
Alvaro
You could look at Eugene's egtb.cpp code for ideas. It uses a LRU chain, and it is thread safe (uses locks to that the cache is shared correctly).
Cardoso wrote:Hi everyone ,
I need to implement cacheing in my EGTB probe code and before anyone says "why not use existing (Nalimov, scorpio bitbases) implementations?", I simply want to do it because it is to be used in a checkers engine.
I haven't yet implemented LRU, because I don't want to make conceptual mistakes.
Has anyone sucessfully implemented a multithreaded LRU cache for probing the EGTBs?
The way I see it we should lock inserting, reading and deleting, but this seems to me a slow solution to use in a multithreaded engine.
Any thoughts and advices on this?
Alvaro, the amount of misinformation that has been spread is unbelievable, solely due to total butchering of scorpio egbb code by Houdini everywhere.
The problem is this; Houdini searches with 32 threads but does so only with 8 threads for egbbs!! Then he thought multi-threaded probe locks and stuff, when in reality he generated the contention itself. The LRU cache had _nothing_ to do with this. This is what I have been saying and infact is very efficient. First of all each EGBB file bascially gets its own LRU cache, that means like 300 LRU caches for 5 men alone. They share the same resource memory but to check if there is a hit, would take very fast because two threads would first have to probe the same egbb file to even have to contend. Note that a 16MB cache with 8kb blocks is 2024 elements, and if you divide uniformly it means 2024/300= 8 elements per EGBB!! So how can scanning 8 elements cause any problems? Ofcourse as the game moves to the final endgame only specific EGBB files would be probed more so the resources shift to say KRPkp by the LRU scheme. Infact the more and more I look at the code, I realize how I went to a great length to get an efficient cache! (Just forgot about it since it has been long)
If you really think scanning such small number of cache elements to check for a cache hit is expensive, then you can use a HashMap+DoublyLinkedList structure to have get() and put() both in O(1) time (see YAGNI). But the hash table wastes resources which are expensive since each block is 8kb. I use one big doubly linked list to maintain LRU order, and a number of (about 300) doubly linked lists for each EGBB.
Don't believe a word coming out of that group who never produces DATA to back up claims. I lost the number of times how fabricated stories such as this have a simple and dumb explanation like stupid implementation.
,