Comment améliorer l'accès multi-thread au cache (implémentation personnalisée)

Question

J'ai une implémentation de cache personnalisée, qui permet de mettre en cache les descendants TCacheable<TKey> en utilisant l'algorithme de remplacement de cache LRU (les moins récemment utilisés).

Chaque fois qu'un élément est accessible, il est fait barboter jusqu'à la partie supérieure de la file d'attente LRU utilisant la fonction synchronisée suivante:

// a single instance is created to handle all TCacheable<T> elements 
public class Cache() 
{ 
    private TCacheable<T> oldest, newest; 

    private object syncQueue = new object(); 
    private void topQueue(TCacheable<T> el) 
    { 
     lock (syncQueue) 
     if (newest != el) 
     { 
      if (el.elder != null) el.elder.newer = el.newer; 
      if (el.newer != null) el.newer.elder = el.elder; 

      if (oldest == el) oldest = el.newer; 
      if (oldest == null) oldest = el; 

      if (newest != null) newest.newer = el; 
      el.newer = null; 
      el.elder = newest; 
      newest = el; 
     } 
    } 
} 

Le goulot d'étranglement dans cette fonction est l'opérateur lock(), ce qui limite l'accès de la mémoire cache à juste un fil à la fois.

Question: Est-il possible de se débarrasser de lock(syncQueue) dans cette fonction tout en préservant l'intégrité de la file d'attente?

Answer 1

La première étape la plus facile serait de déplacer l'instruction de verrouillage à l'intérieur du bloc if (le plus récent! = El), puisque vous n'avez pas du tout à attendre sur le verrou si le plus récent == el. En dehors de cela, vous faites des affectations conditionnelles. Avez-vous vraiment des informations de profilage qui vous amènent à croire que cette section est problématique en termes de performance?

Si vous êtes vraiment sûr que l'optimisation de cette classe est la meilleure utilisation de votre temps, here's a PDF of the paper "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms". Here's an excellent blog post that might be a little bit more straightforward.

Answer 2

L'astuce pour un cache LRU concurrent n'est pas d'enlever le verrou - c'est un trou de lapin - mais d'amortir le besoin de l'acquérir. La file d'attente peut éventuellement être cohérente avec la table pendant les lectures, mais elle doit être cohérente après une écriture pour choisir correctement une victime à expulser. Ainsi, vous pouvez tamponner les réorganisations et éviter les conflits de verrouillage. J'ai prouvé la validité de cette approche dans mon implémentation Java: http://code.google.com/p/concurrentlinkedhashmap/

Alors même que je peux offrir des solutions pour répondre «Oui» à votre question, une meilleure réponse est que vous n'avez pas besoin d'enlever le verrou mais de comprendre quand c'est vraiment nécessaire.