Wikipedia enumera 11 algoritmos de reemplazo de caché . Suponiendo que no sé casi nada acerca de la aplicación que voy a desarrollar, ¿qué debo usar como algoritmo de reemplazo de caché "predeterminado"?
Si recuerdo correctamente de mi curso de sistema operativo, LRU es el mejor algoritmo general de reemplazo de caché. Pero tal vez estoy equivocado.
Además, esta es una pregunta académica, ya que, en general, la memoria principal es barata y abundante y realmente no necesito preocuparme demasiado por el tamaño de la memoria caché.
algorithms
caching
cenizas999
fuente
fuente
Respuestas:
Supongo que la mejor respuesta es que depende. En mi experiencia, hay muchos factores que intervienen en la elección de algoritmos de almacenamiento en caché.
Factores a considerar
Una vez que considera todos los factores diferentes, necesita encontrar un algoritmo de caché que maneje mejor. Por ejemplo, supongamos que tiene una aplicación donde hay muchas escrituras, algunas reescrituras, lecturas de datos escritos recientemente y algún tipo de medio giratorio. En este caso, desearía una especie de algoritmo de almacenamiento en caché híbrido. Para manejar los datos de escritura, es posible que desee algo como Wise order of Writes (WOW) y un algoritmo LRU para los datos que se han leído del disco. La razón de esto es que los accesos al disco son muy caros y el algoritmo WOW hará que sea más eficiente escribir datos y la LRU mantendrá los datos de acceso frecuente siempre en caché.
Supongamos que tiene discos SSD, que tienen un tiempo de acceso muy rápido, es posible que desee adaptar su elección al algoritmo LRU, ya que los accesos a disco son relativamente económicos.
Así que realmente lo que quiero decir es que no hay una "mejor" respuesta. La mejor respuesta es conocer los factores que se aplican a usted y elegir el algoritmo que mejor los maneje.
Cómo encontrar el algoritmo para ti
Perfile su sistema. Esto generalmente implica agregar código para mantener estadísticas para los accesos a la memoria. Al hacer un perfil puede ver qué factores son más importantes para usted.
En el pasado, agregué código para rastrear todos los accesos a la memoria durante un período de tiempo. Luego busco patrones. Busco relecturas, reescrituras, acceso secuencial, acceso aleatorio, etc.
Una vez que haya identificado las cosas importantes, debe observar todos los diferentes tipos de algoritmos de almacenamiento en caché para ver cuál maneja qué cosas son las mejores.
fuente
Suponiendo que no sabe casi nada acerca de la aplicación que va a desarrollar, debe saber más antes de elegir e implementar un sistema de caché. En otras palabras, no hay implementaciones predeterminadas: algunas son buenas para algunos propósitos y son totalmente malas para otros .
Por ejemplo, tome solo dos implementaciones: Menos utilizadas recientemente y Menos utilizadas frecuentemente. ¿Cómo decidir cuál usar antes que otro?
LRU es bueno cuando está bastante seguro de que el usuario accederá con mayor frecuencia a los elementos más recientes y nunca o rara vez volverá a los anteriores. Un ejemplo: un uso general de un cliente de correo electrónico. En la mayoría de los casos, los usuarios acceden constantemente a los correos más recientes. Los leen, los posponen, regresan en unos minutos, horas o días, etc. Pueden encontrarse buscando un correo que recibieron hace dos años, pero ocurre con menos frecuencia que acceder a los correos que recibieron en las últimas dos horas.
Por otro lado, LRU no tiene sentido en el contexto donde el usuario accederá a algunos elementos con mucha más frecuencia que otros. Un ejemplo: con frecuencia escucho la música que me gusta, y puede suceder que en 400 canciones, escuche las mismas cinco al menos una vez por semana, mientras que escucharé como máximo una vez al año 100 canciones que no me gustan también mucho. En este caso, LFU es mucho más apropiado.
Al tomar solo dos de las implementaciones, verá que no hay un algoritmo "predeterminado" que pueda usar cuando no quiera pensar cuál es mejor o no tiene suficiente información sobre la aplicación. Es, bueno, como preguntar si, por defecto, debe sumar, restar, multiplicar o dividir dos números para encontrar el resultado de un cálculo cuando no sabe nada al respecto.
fuente
¿Por qué limitar sus opciones solo a Wikipedia? Si tiene acceso a una base de datos de investigación como la Biblioteca Digital ACM , encontrará aún más algoritmos. También tenga en cuenta acerca de jugar con las patentes. Por ejemplo, ARC es un buen algoritmo pero desafortunadamente está patentado.
fuente
Podría pasar mucho tiempo agonizando sobre el "mejor" algoritmo, o simplemente podría implementar un algoritmo simple y COMENZAR CON EL RESTO DEL SISTEMA. Cuando tengas algo comprobable, entonces preocúpate por el algoritmo.
Optimización prematura ...
fuente
No existe un algoritmo de caché perfecto: siempre puede encontrar un caso que se comporte muy mal.
Por lo tanto, es importante conocer el problema que se está almacenando en caché para determinar cuál se comportará menos mal.
Además, debe considerar cuánto tiempo necesita almacenar en caché las cosas y cuánto tiempo puede almacenarlas ...
fuente