A Wikipedia lista 11 algoritmos de substituição de cache . Supondo que não saiba quase nada sobre o aplicativo que vou desenvolver, o que devo usar como um algoritmo de substituição de cache "padrão"?
Se bem me lembro do curso do SO, o LRU é o melhor algoritmo geral de substituição de cache. Mas talvez eu esteja enganado.
Além disso, essa é uma questão acadêmica, já que, geralmente, a memória principal é barata e abundante e não preciso me preocupar muito com o tamanho do cache.
algorithms
caching
ashes999
fonte
fonte
Respostas:
Eu acho que a melhor resposta é que depende. Na minha experiência, existem muitos fatores na escolha de algoritmos de cache.
Fatores a considerar
Depois de considerar todos os fatores diferentes, você precisará encontrar um algoritmo de cache que lide melhor com isso. Por exemplo, digamos que você tenha um aplicativo em que haja muitas gravações, algumas reescritas, leituras de dados gravados recentemente e algum tipo de mídia rotativa. Nesse caso, você deseja um tipo de algoritmo de cache híbrido. Para manipular os dados de gravação, convém algo como Wise order of Writes (WOW) e um algoritmo LRU para dados que foram lidos a partir do disco. A razão para isso é que os acessos ao disco são muito caros e o algoritmo WOW tornará mais eficiente a gravação de dados e a LRU manterá os dados acessados com frequência sempre em cache.
Digamos que você tenha discos SSD, com tempo de acesso muito rápido, convém escolher o algoritmo LRU, já que os acessos a disco são relativamente baratos.
Então, realmente, o que eu quero dizer é que não há uma "melhor" resposta. A melhor resposta é conhecer os fatores que se aplicam a você e escolher um algoritmo que melhor lide com eles.
Como encontrar o algoritmo para você
Perfile seu sistema. Isso geralmente envolve adicionar código para manter as estatísticas dos acessos à memória. Ao criar um perfil, você pode ver quais fatores são mais importantes para você.
No passado, eu adicionei código para rastrear todos os acessos à memória durante um período de tempo. Depois, procuro padrões. Eu procuro releituras, reescritas, acesso seqüencial, acesso aleatório, etc.
Depois de identificar as coisas importantes, é necessário examinar todos os diferentes tipos de algoritmos de armazenamento em cache para ver qual manipula quais são as melhores.
fonte
Supondo que você não saiba quase nada sobre o aplicativo que irá desenvolver, saiba mais sobre ele antes de realmente escolher e implementar um sistema de cache. Em outras palavras, não há implementações padrão: algumas são boas para alguns propósitos e totalmente ruins para outros .
Por exemplo, faça apenas duas implementações: Menos Usado Recentemente e Menos Usado com Freqüência. Como decidir qual usar antes da outra?
O LRU é bom quando você tem certeza de que o usuário acessará com mais frequência os itens mais recentes e nunca ou raramente retornará aos antigos. Um exemplo: um uso geral de um cliente de email. Na maioria dos casos, os usuários acessam constantemente os e-mails mais recentes. Eles os leem, adiam, retornam em alguns minutos, horas ou dias etc. Eles podem procurar uma mensagem que receberam dois anos atrás, mas isso acontece com menos frequência do que acessar os emails que receberam nas últimas duas horas.
Por outro lado, o LRU não faz sentido no contexto em que o usuário acessará alguns itens com muito mais frequência do que outros. Um exemplo: eu frequentemente ouço a música que gosto, e pode acontecer que em 400 músicas eu ouça as mesmas cinco pelo menos uma vez por semana, enquanto eu ouço no máximo uma vez por ano 100 músicas que não gosto muito Muito de. Nesse caso, o LFU é muito mais apropriado.
Ao tomar apenas duas das implementações, você vê que não há algoritmo "padrão" que pode ser usado quando não deseja pensar em qual é o melhor ou se não possui informações suficientes sobre o aplicativo. É como perguntar se, por padrão, você deve adicionar, subtrair, multiplicar ou dividir dois números para encontrar o resultado de um cálculo quando não sabe nada sobre ele.
fonte
Por que limitar suas escolhas apenas à Wikipedia? Se você tiver acesso a um banco de dados de pesquisa como a Biblioteca Digital ACM, encontrará ainda mais algoritmos. Também esteja ciente de mexer com patentes. Por exemplo, o ARC é um bom algoritmo, mas infelizmente é patenteado.
fonte
Você pode gastar muito tempo agonizando sobre o 'melhor' algoritmo, ou pode simplesmente implementar um algoritmo simples e seguir em frente com o descanso do sistema. Quando você tem algo testável, então se preocupe com o algoritmo.
Otimização prematura ...
fonte
Não existe um algoritmo de cache perfeito - você sempre pode encontrar um caso que se comporte muito mal.
Portanto, é importante conhecer o problema que está sendo armazenado em cache para determinar o que se comportará menos mal.
Além disso, você deve considerar por quanto tempo precisa armazenar em cache e por quanto tempo pode armazenar em cache ...
fonte