algorithme de remplacement d'entrée de cache

Question

J'ai un projet logiciel qui crée une série de valeurs d'empreinte digitale (hash) à partir d'objets de taille variable. Plus la taille de l'objet est grande, plus le calcul du hachage est coûteux. Les hachages sont utilisés à des fins de comparaison. Je souhaite maintenant mettre en cache les valeurs de hachage afin d'améliorer les performances des comparaisons suivantes. Pour toute entrée donnée dans le cache, je les disponibles métriques suivantes:

• nombre de succès
• date de dernière modification/heure
• taille de l'objet haché

donc à ma question. Étant donné le besoin de restreindre la taille du cache (en le limitant à un nombre spécifique d'entrées), qu'est-ce qu'une approche équilibrée pour remplacer les éléments du cache? De toute évidence, les objets plus gros coûtent plus cher au hachage et doivent donc être conservés aussi longtemps que possible. Cependant, je veux éviter une situation où peupler le cache avec une grande quantité d'objets volumineux empêchera les éléments futurs (plus petits) d'être mis en cache. Donc, en me basant sur les métriques disponibles (voir ci-dessus), je cherche une bonne "formule" générale pour expirer (enlever) les entrées de cache quand le cache est plein.

Toutes les pensées, commentaires sont appréciés.

Answer 1

Vous devez réfléchir à la nature des objets. Pensez à la probabilité que les objets soient appelés à nouveau bientôt. Et supprimez l'objet le moins probable.

Ceci est très spécifique au logiciel que vous utilisez et à la nature des objets.
S'ils sont utilisés en continu dans le programme, ils respecteront probablement le principe Locality of reference. Vous devriez donc utiliser l'algorithme LRU (Least récemment utilisé).

Si les objets avec un nombre d'accès plus élevé sont plus susceptibles d'être appelés à nouveau, utilisez-le (et supprimez le plus bas).

Jetez un oeil à Cache Algorithms

En principe, vous devez calculer:

min (p * coût)

p = probabilité d'être appelé à nouveau.
coût = Le coût de mise en cache de cet objet à nouveau.

Answer 2

En supposant la possibilité d'enregistrer quand une entrée a été accédée pour la dernière fois, j'irais avec un "Coût" pour chaque entrée, où vous pouvez à tout moment supprimer l'entrée la moins chère.

Cost = Size * N - TimeSinceLastUse * M 

présumant vous supprimer complètement les entrées du cache (et non garder les anciennes données HitCount autour) J'éviter d'utiliser hitcount comme une métrique, vous finiriez avec une entrée qui a une forte hitcount parce qu'il a été il y a longtemps, et il sera là encore plus longtemps car il a un nombre de hits élevé.

Answer 3

J'utilise généralement un schéma strictement utilisé (LRU) strict pour éliminer des choses du cache, à moins que ce soit énormément plus cher de reconstruire certains éléments. LRU a l'avantage d'être trivialement simple à mettre en œuvre, et il fonctionne très bien pour un large éventail d'applications. Il conserve également les éléments les plus fréquemment utilisés dans le cache.

En substance, je crée une liste liée qui est également indexée par un dictionnaire. Quand un client veut un article, je le cherche dans le dictionnaire. S'il est trouvé, je dissocie le noeud de la liste chaînée et le déplace en tête de liste. Si l'élément n'est pas dans le cache, je le construis (charge à partir du disque, ou autre), le place en tête de la liste, l'insère dans le dictionnaire, puis supprime l'élément qui est en queue de liste .

Answer 4

Vous pouvez essayer un style de cache à plusieurs niveaux. Consacrer un certain pourcentage du cache à Expensive pour créer des éléments et une partie facile à créer, mais des éléments plus fortement sollicités. Vous pouvez ensuite utiliser différentes stratégies pour maintenir le cache coûteux que vous le feriez le moins cher.

Answer 5

L'algorithme pourrait prendre en compte le coût de reproduction d'un élément manquant. De cette façon, vous conserverez les éléments les plus précieux dans le cache.