Multithreaded LRU

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Cardoso
Posts: 313
Joined: Thu Mar 16, 2006 6:39 pm
Location: Portugal
Full name: Alvaro Cardoso
Contact:

Multithreaded LRU

Post by Cardoso » Sun Oct 06, 2013 12:01 am

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

Daniel Shawul
Posts: 3980
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Multithreaded LRU

Post by Daniel Shawul » Sun Oct 06, 2013 3:57 am

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.

Daniel

[ignore]EnCt29957f4dc7c500045a2e9c562c24901245f3bd6c69957f4dc7c500045a2e9c562eKA2uUuqnwOAu1PfUFKiBoCApQu9vwPIx7dMV1MZojpVIkIVFqo2pdhK2bRRtVW0NVNkBbmjeVT3SoI2IwEmS[/ignore]

bob
Posts: 20916
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Multithreaded LRU

Post by bob » Sun Oct 06, 2013 3:59 am

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
Posts: 313
Joined: Thu Mar 16, 2006 6:39 pm
Location: Portugal
Full name: Alvaro Cardoso
Contact:

Re:Many thanks to you both (NT)

Post by Cardoso » Sun Oct 06, 2013 12:07 pm

NT

Rein Halbersma
Posts: 688
Joined: Tue May 22, 2007 9:13 am

Re: Multithreaded LRU

Post by Rein Halbersma » Sun Oct 06, 2013 12:15 pm

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 ask Ed Gilbert (author of the Kingsrow checkers program) over on the computer draughts forum http://laatste.info/bb3/viewforum.php?f=53&start=0

Daniel Shawul
Posts: 3980
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Multithreaded LRU

Post by Daniel Shawul » Thu Oct 24, 2013 12:12 pm

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.

Cardoso
Posts: 313
Joined: Thu Mar 16, 2006 6:39 pm
Location: Portugal
Full name: Alvaro Cardoso
Contact:

Re: Multithreaded LRU

Post by Cardoso » Thu Oct 24, 2013 4:16 pm

This is worth gold, many thanks for your excellent work and sharing.

best regards,
Alvaro

Post Reply