Otimização de uso de memória usando Cache - Conceitos / Teoria - Artigos - Articles - Fórum

Jump to content

Bem vindo à Unidev
Registre para ter acesso a todos os recursos do site. Uma vez registrado e logado, você poderá criar tópicos, postar em tópicos já existentes, gerenciar seu perfil e muito mais. Se você já tem uma conta, faça login aqui - ou então crie aqui uma conta agora mesmo!
- - - - -
Photo

Otimização de uso de memória usando Cache


por Issam Lahlali

Quando os processos em execução no seu computador tentam alocar mais memória do que o sistema tem disponível, o kernel começa a trocar páginas de memória de e para o disco. Isto é feito a fim de liberar memória física suficiente para satisfazer as exigências de alocação de memória RAM do solicitante.

O uso excessivo de troca é chamado de thrashing e é indesejável, pois reduz o desempenho geral do sistema, principalmente porque os discos rígidos são muito mais lentos do que a RAM.

Se seu aplicativo precisa usar uma grande quantidade de dados, você será exposto ao thrashing e sua aplicação pode perder desempenho drasticamente. Existem duas soluções: ou otimizar seus aplicativos para usar a memória de forma mais eficiente, ou adicionar mais memória RAM física para o sistema.

Usando um cache é uma maneira popular para otimizar seu uso de memória. A idéia é armazenar em cache os dados carregados a partir do disco, este cache irá conter muitos slots, cada um contendo um pedaço específico de dados, e alguns slots serão liberados se o tamanho do cache for superior a um determinado valor.

O desempenho do cache depende:

- O container: pode ser uma fila, uma matriz, uma lista ou talvez um container personalizado. A escolha de um desses containers poderia impactar muito o desempenho de cache.

- O tamanho máximo do cache.

- O algoritmo utilizado para liberar entradas do cache: Quando o cache atinge o seu máximo, você tem que decidir quais entradas liberar, por exemplo, você pode:

- Liberar os primeiros slots carregados.
- Liberar os últimos slots carregados.
- Liberar os slots menos usados.


Vamos descobrir as vantagens de usar cache estudando estes dois cenários:

CENÁRIO 1: A APLICAÇÃO USA GRANDE QUANTIDADE DE DADOS ARMAZENADOS EM DISCO (IRRLICHT ENGINE)

Este cenário ocorre quando você usa uma grande quantidade de dados armazenados no disco, e quando você carrega esses dados na memória, o aplicativo se torna

lento. Quando você procurar a causa, você descobre que seu aplicativo consome muita memória. Você decide liberar os dados assim que você terminar de usá-lo, mas o aplicativo ainda é lento, e desta vez é devido ao thrashing. Na verdade você precisa muitas vezes para recarregar os dados liberados.

Vamos dar uma olhada na Irrlicht Engine usando CppDepend e descobrir alguns fatos sobre a cache usada.

O Irrlicht Engine é uma engine open-source 3D em tempo real de alto desempenho escrito em C++. E, como todos as game engines, ela consegue gerenciar classes de meshs.

Um mesh é um conjunto de polígonos. Cada polígono é armazenado na memória como uma lista ordenada de pontos 3D. A fim de criar um mesh de cubo 3D seria preciso especificar os oito pontos de canto do cubo no espaço 3D. Cada polígono poderia, então, ser definido usando quatro de oito pontos.

Os meshs são armazenados no disco, e tem de ser carregado para a memória para trabalhar. Irrlicht fornece a interface IMeshCache para definir o contrato de cache, e o CMeshCache implementá-lo.

Posted Image
[Figura 1]

Esta interface nos dá muitos métodos úteis para lidar com o cache, e para descobrir que container é usado vamos procurar por métodos chamados pelo método AddMesh:

Posted Image
[Figura 2]

Irrlicht usa o container de modelo personalizado irr::core::array<t,talloc>, este container é projetado para ter melhor performance para armazenar e procurar meshs pelo índice e nome.

Aqui está, por exemplo, os métodos invocados por getMeshByName

Posted Image
[Figura 3]

O cache usa o algoritmo de busca binária, para melhorar a performance do cache na busca de mesh pelo nome.

E sobre o algoritmo usado para liberar meshs?

Nenhum algoritmo é fornecido na Irrelicht engine para liberar o cache, na verdade, depende da lógica do jogo usando a engine, e é responsabilidade do usuário da Irrlicht engine para decidir quando para liberar um mesh.

CENÁRIO 2: A APLICAÇÃO USA GRANDE QUANTIDADE DE DADOS CALCULADOS NA MEMÓRIA (DOXYGEN)

Neste caso, os dados utilizados não são armazenados no disco, mas que são calculados após alguns tratamentos de processo.

Tomemos como exemplo a ferramenta Doxygen, que é uma ferramenta útil para a geração de documentação a partir de fontes C++ anotadas.

Doxygen toma como entrada arquivos fonte para analisar, e depois de uma análise léxica, muitos dados são extraídos esses arquivos para serem armazenados na memória para tratá-los e gerar a documentação.

Se você analisar um grande projeto, os dados extraídos das fontes tornam-se muito grande, e que consomem muita memória, e para resolver esse problema Doxygen usa um cache para armazenar esses dados.

Doxygen recebe o tamanho máximo do cache do arquivo de configuração:


int cacheSize = Config_getInt("SYMBOL_CACHE_SIZE");


É uma boa idéia deixar este parâmetro ser configurável, para que possa aumentar o cache, se você tem uma máquina com um tamanho grande memória física para aumentar a performance cache. No entanto, para os mais recentes lançamentos Doxygen este parâmetro é removido do arquivo de configuração, e um valor padrão é usado.

E aqui está o container usado por Doxygen:

Doxygen::symbolCache = new ObjCache(16+cacheSize); // 16 -> room for 65536 elements,


E sobre o algoritmo para liberar entradas de cache?

Os desenvolvedores Doxygen poderiam decidir o algoritmo otimizado para liberar o cache, isso depende de como eles implementaram o analisador, aqui está um trecho de código a partir do código fonte do Doxygen responsável por liberar o cache quando ele atinge o seu máximo:

void MemberDef::makeResident() const
{
  if (m_cacheHandle==-1) // not yet in cache
  {
    MemberDef *victim = 0;
    MemberDef *that = (MemberDef*)this; // fake method constness
    that->m_cacheHandle = Doxygen::symbolCache->add(that,(void **)&victim);
//printf("adding %s to cache, handle=%d\n",m_impl->name.data(),that->m_cacheHandle);
if (victim) // cache was full, victim was the least recently used item and has to go
{
  victim->m_cacheHandle=-1; // invalidate cache handle
  victim->saveToDisk(); // store the item on disk
}
else // cache not yet full
{
  //printf("Adding %s to cache, handle=%d\n",m_impl->name.data(),m_cacheHandle);
}
if (m_storagePos!=-1) // already been written to disk
{
  if (isLocked()) // locked in memory
  {
    assert(m_impl!=0);
    that->m_flushPending=FALSE; // no need to flush anymore
  }
  else // not locked in memory
  {
    assert(m_impl==0);
    loadFromDisk();
  }
}
}
else // already cached, make this object the most recently used.
{
  assert(m_impl!=0);
  //printf("Touching symbol %s\n",m_impl->name.data());
  Doxygen::symbolCache->use(m_cacheHandle);
}
}


Conforme especificado no código do método makeResident, o item menos usado recentemente é removido se o cache está cheio.

Vamos descobrir onde este método é invocado:

Posted Image
[Figura 4]

Este método é chamado para quase todos os métodos MemberDef, ele é chamado cada vez que você tem para acessar o estado MemberDef para verificar se este membro está carregado ou não. Carregá-lo, se não é o caso e remover o membro menos usado recentemente a partir do cache.

O IMPACTO DE USAR O CACHE

Usando o cache pode aumentar a performance de sua aplicação, mas se o cache de trazer uma grande otimização ou apenas uma otimização de micro e não vale a pena adicioná-lo em seu aplicativo?

Vamos tomar como exemplo o projeto Doxygen, eu modifiquei o código para não usar o cache e analisei alguns projetos em C++ com esta versão modificada. E, surpreendentemente o tempo de análise foi muito aumentada, por vezes, de 5 min a 25 min.

CONCLUSÃO

Usando o cache é uma técnica poderosa para aumentar o desempenho se você usar uma grande quantidade de dados. Descobrir como projetos open-source implementam o cache pode ser muito útil para entender como implementá-lo em suas aplicações.

Este artigo foi originalmente postado em Gamedev.net
http://www.gamedev.n...ing-cache-r3531


Links Úteis

Irrlicht Engine - http://irrlicht.sourceforge.net/
CppDepend - http://www.cppdepend.com/
Doxygen - http://www.stack.nl/~dimitri/Doxygen/



0 Comments