Cache

Olá pessoal, aqui é o Lince. Bem vindos de volta.
Como vocês estão?

Suponhamos que você seja o processador de um computador. Cá está você isolado na sua sala de trabalho, processando tudo que o escalonador te manda.

Pra fazer seu trabalho você precisa de instruções, e essas instruções estão guardadas na memória. Você não tem acesso direto à memória, mas tem um empregado que pode acessá-la e trazer o que você pedir.

As instruções e os dados estão em formato de livros, todos eles guardados na imensa biblioteca que é a memória; na sua sala você tem suas próprias estantes para guardar os livros com instruções e os dados, você pode ter acesso a estes livros rapidamente, mas com uma capacidade de armazenamento bem menor que a memória. Este é seu cache.

O empregado que acessa a memória, vamos chamá-lo de ARM, tem um protocolo muito especifico de trabalho:

• Ele fica à sua porta esperando instruções sempre que não houver o que fazer;
• Você pede para que ele busque um livro em especifico, os quais são identificados por um código único que representa sua localização na memória (um endereço);
• Ao receber a ordem de busca, o ARM primeiramente verifica se o livro já está em uma de suas prateleiras. Se não estiver, ele pega seu carrinho de mão e vai até a memória (que é moderadamente longe);
• Na memória, ele procura o livro requerido para tirar uma cópia e, além deste, vários outros a sua volta;
• Com as cópias no carrinho de mão ele volta para sua sala e as coloca em uma de suas estantes pessoais;
• Se não houver estantes disponíveis existem formas de decidir quais livros serão descartados para dar lugar aos novos:
• Substituir os livros que já não são usados há mais tempo; ou
• Substituir os livros que foram menos usados; ou
• Substituir os livros que chegaram há mais tempo.
• A partir daqui o ARM ainda tem uma ultima tarefa: verificar se o conteúdo dos livros descartados foi modificado por você. Caso positivo, ele precisa atualizar os livros da memória com o novo conteúdo.

Talvez você esteja se perguntando: “Por que diabos o ARM me trouxe esse monte de livro quando eu o pedi apenas um?”, e a resposta chama-se “Principio de Localidade”.

O Principio de Localidade diz que se você, como processador, acabou de ler as instruções do livro X, é bem provável que logo em seguida queira ler as instruções do livro X+1. O ARM se poupou ao trabalho de fazer várias viagens até a memória trazendo esse livro pra você no primeiro pedido. Também existe a possibilidade de você precisar de um livro e o ARM não estar disponível; ele pode ter ido buscar outro livro ou estar atualizando a memória.

Existem dois cenários que devem ser considerados aqui: o Cache Hit e o Cache Miss;

O Cache Hit é quando o livro requerido por você já está em uma de suas prateleiras, em seu cache, quando você o solicita;

O Cache Miss é quando o livro requerido não está em uma de suas prateleiras e precisa ser buscado na memória.

E porque isso é importante?

Digamos que o ARM leva 10 segundos para vasculhar suas estantes e procurar um livro, e leva 500 segundos para buscar um livro na memória. Então, se seu cache não existisse, seriam 500 segundos toda vez que precisasse de um livro diferente. Existe, portanto, um ganho significativo sempre que o livro estiver no cache, mas quando o livro não está o ARM “perde tempo” procurando o livro lá em vez de ir direto para a memória.

Mas e os dados? Eles funcionam assim também?

Para você - o Processador - tudo na memória são livros, independente se são instruções ou dados. Se os dados serão afetados pelo Principio de Localidade, e trarão mais Cache Hit que Cache Miss, depende fundamentalmente do programador. Este pode ter um papel fundamental na hora de organizar os dados do programa de forma a influenciar positivamente o desempenho do cache.

Com isso tudo não estou dizendo que se deve sempre programar com o medo do desempenho do cache assombrando seu código. Muitas vezes o ganho fornecido por tais práticas é irrisório, mas diversos Cache Miss sequenciais podem significar uma falha evitável que é capaz de diminuir o desempenho geral do seu programa. Portanto, talvez valha à pena passar uma fração do tempo de programação otimizando a organização dos dados do programa.

Fontes:

Para ler mais sobre Memória e Cache (em inglês):
Introduction to Caches - Computer Science University of Maryland

Para ler mais sobre Design Orientado a Dados (em inglês):
Data-Oriented Design (Or Why You Might Be Shooting Yourself in The Foot With OOP) - Games from Within

Um agradecimento especial para Priscila Braga por ter me ajudado muito com a revisão deste artigo.

Então é isso, espera que tenham gostado e aprendido alguma coisa, deixa um comentário aí. E como sempre vocês podem me encontrar no tuiter @LinceAssassino ou no email emailDoLince(arroba)gmail(ponto)com para qualquer dúvida, sugestão, crítica ou simplesmente se quiser trocar uma ideia.
Abraços do Lince.

Tweetar