Wikipedia répertorie 11 algorithmes de remplacement de cache . En supposant que je ne sache presque rien sur l'application que je vais développer, que dois-je utiliser comme algorithme de remplacement de cache "par défaut"?
Si je me souviens bien de mon cours sur le système d'exploitation, LRU est le meilleur algorithme général de remplacement de cache. Mais je me trompe peut-être.
En outre, c'est un peu une question académique, car, généralement, la mémoire principale est bon marché et abondante et je n'ai pas vraiment à me soucier de la taille du cache.
algorithms
caching
cendres999
la source
la source
Réponses:
Je suppose que la meilleure réponse est que cela dépend. D'après mon expérience, de nombreux facteurs entrent en jeu dans le choix des algorithmes de mise en cache.
Facteurs à considérer
Une fois que vous avez pris en compte tous les différents facteurs, vous devez alors trouver un algorithme de cache qui gère le mieux. Par exemple, disons que vous avez une application où il y a beaucoup d'écritures, de réécritures, de lectures de données récemment écrites et d'une sorte de support tournant. Dans ce cas, vous voudriez une sorte d'algorithme de mise en cache hybride. Pour gérer les données d'écriture, vous souhaiterez peut-être quelque chose comme Wise order of Writes (WOW) et un algorithme LRU pour les données qui ont été lues sur le disque. La raison en est que les accès au disque sont très chers et l'algorithme WOW rendra l'écriture des données plus efficace et la LRU gardera toujours les données fréquemment consultées dans le cache.
Supposons que vous ayez des disques SSD, qui ont un temps d'accès très rapide, vous voudrez peut-être orienter votre choix vers l'algorithme LRU car les accès aux disques sont relativement peu coûteux.
Donc, vraiment, ce que je veux dire, c'est qu'il n'y a pas de «meilleure» réponse. La meilleure réponse est de connaître les facteurs qui s'appliquent à vous et de choisir un algorithme qui les gère le mieux.
Comment trouver l'algorithme pour vous
Profilez votre système. Cela implique généralement l'ajout de code pour conserver les statistiques d'accès à la mémoire. En profilant, vous pouvez voir quels facteurs sont les plus importants pour vous.
Dans le passé, j'ai ajouté du code pour suivre tous les accès à la mémoire sur une période de temps. Plus tard, je cherche des motifs. Je recherche des relectures, des réécritures, des accès séquentiels, des accès aléatoires, etc.
Une fois que vous avez identifié les éléments importants, vous devez examiner tous les différents types d'algorithmes de mise en cache pour voir quels sont les meilleurs éléments.
la source
En supposant que vous ne savez presque rien de l'application que vous allez développer, vous devez en savoir plus avant de choisir et de mettre en œuvre un système de cache. En d'autres termes, il n'y a pas d'implémentations par défaut: certaines sont bonnes à certaines fins et totalement mauvaises à d'autres .
Par exemple, prenez seulement deux implémentations: le moins récemment utilisé et le moins fréquemment utilisé. Comment décider lequel utiliser avant l'autre?
LRU est bon lorsque vous êtes presque sûr que l'utilisateur accédera plus souvent aux éléments les plus récents et ne reviendra jamais ou rarement aux anciens. Un exemple: une utilisation générale d'un client de messagerie. Dans la plupart des cas, les utilisateurs accèdent constamment aux mails les plus récents. Ils les lisent, les reportent, reviennent dans quelques minutes, heures ou jours, etc. Ils peuvent se retrouver à chercher un courrier qu'ils ont reçu il y a deux ans, mais cela arrive moins fréquemment que d'accéder aux courriers qu'ils ont reçus au cours des deux dernières heures.
D'un autre côté, LRU n'a aucun sens dans le contexte où l'utilisateur accédera à certains éléments beaucoup plus fréquemment que d'autres. Un exemple: j'écoute fréquemment de la musique que j'aime, et il peut arriver que sur 400 chansons, j'écoute les mêmes cinq au moins une fois par semaine, alors que j'écoute au maximum une fois par an 100 chansons que je n'aime pas trop beaucoup. Dans ce cas, LFU est beaucoup plus approprié.
En prenant seulement deux des implémentations, vous voyez qu'il n'y a pas d'algorithme "par défaut" que vous pouvez utiliser lorsque vous ne voulez pas penser à laquelle est le meilleur ou que vous n'avez pas assez d'informations sur l'application. C'est, eh bien, comme demander si par défaut, vous devez ajouter, soustraire, multiplier ou diviser deux nombres pour trouver le résultat d'un calcul lorsque vous n'en savez rien.
la source
Pourquoi limiter vos choix uniquement à Wikipedia? Si vous avez accès à une base de données de recherche comme la bibliothèque numérique ACM, vous trouverez encore plus d'algorithmes. Soyez également conscient de jouer avec les brevets. Par exemple, ARC est un bon algorithme mais malheureusement il est breveté.
la source
Vous pourriez passer beaucoup de temps à agoniser sur le «meilleur» algorithme, ou vous pourriez simplement implémenter un algorithme simple et GET ON AVEC LE RESTE DU SYSTÈME. Lorsque vous avez testable quelque chose alors vous soucier de l'algorithme.
Optimisation prématurée ...
la source
Il n'y a pas d'algorithme de cache parfait - vous pouvez toujours trouver un cas qui se comporte très mal.
Par conséquent, il est important de connaître le problème mis en cache afin de déterminer celui qui se comportera le moins mal.
En outre, vous devriez considérer combien de temps vous devez mettre en cache les choses et combien de temps vous pouvez mettre en cache les choses ...
la source