Qual estrutura de dados devo usar para esta estratégia de cache?

11

Estou trabalhando em um aplicativo .NET 4.0, que executa um cálculo bastante caro em duas duplas retornando uma dupla. Este cálculo é realizado para cada um dos vários milhares de itens . Esses cálculos são realizados em um Taskencadeamento em um conjunto de encadeamentos.

Alguns testes preliminares mostraram que os mesmos cálculos são realizados repetidamente, então eu gostaria de armazenar n resultados em cache . Quando o cache está cheio, eu gostaria de jogar fora os menos frequentemente artigo recentemente utilizado. ( Editar: percebi que com menos frequência não faz sentido, porque quando o cache está cheio e eu substituía um resultado por um recém-calculado, esse seria menos usado e substituído imediatamente na próxima vez que um novo resultado fosse calculado e adicionado ao cache)

Para implementar isso, eu estava pensando em usar um Dictionary<Input, double>(onde Inputseria uma mini-classe armazenando os dois valores duplos de entrada) para armazenar as entradas e os resultados armazenados em cache. No entanto, eu também precisaria acompanhar quando um resultado foi usado pela última vez. Para isso, acho que precisaria de uma segunda coleção para armazenar as informações necessárias para remover um resultado do dictonário quando o cache estivesse ficando cheio. Preocupa-me que a manutenção constante dessa lista tenha um impacto negativo no desempenho.

Existe uma maneira melhor (ou seja, mais eficiente) de fazer isso, ou talvez até uma estrutura de dados comum que eu desconheça? Que tipos de coisas devo analisar / medir para determinar a otimização da minha solução?

PersonalNexus
fonte

Respostas:

12

Se você deseja usar um cache de remoção de LRU (remoção menos usada recentemente), provavelmente uma boa combinação de estruturas de dados a ser usada é:

  • Lista vinculada circular (como uma fila prioritária)
  • Dicionário

Isso é por que:

  • A lista vinculada tem um tempo de inserção e remoção de O (1)
  • Os nós da lista podem ser reutilizados quando a lista estiver cheia e nenhuma alocação extra precisar ser executada.

É assim que o algoritmo básico deve funcionar:

As estruturas de dados

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

  1. Entrada recebida
  2. Se o dicionário contiver a chave
    • retorne o valor armazenado no nó e mova o nó para o início da lista
  3. Se o dicionário não contiver a chave
    • calcular o valor
    • armazene o valor no último nó da lista
    • se o último não tiver um valor, remova a chave anterior do dicionário
    • mova o último nó para a primeira posição.
    • armazene no dicionário o par de valores de chave (entrada, nó).

Alguns benefícios dessa abordagem são: ler e definir um valor de dicionário se aproxima de O (1), inserir e remover um nó em uma lista vinculada é O (1), o que significa que o algoritmo está se aproximando de O (1) para leitura e gravação de valores no cache e evita alocações de memória e bloqueia operações de cópia de memória, tornando-o estável do ponto de vista da memória.

Pop Catalin
fonte
Bons pontos, a melhor idéia até agora, IMHO. Eu implementei um cache com base nisso hoje e terá que criar um perfil e ver como ele se sai amanhã.
PersonalNexus
3

Parece muito esforço para um único cálculo, considerando o poder de processamento que você tem à disposição no PC comum. Além disso, você ainda terá as despesas da primeira chamada do seu cálculo para cada par de valores exclusivo; portanto, 100.000 pares de valores únicos ainda custarão o tempo n * 100.000, no mínimo. Considere que o acesso a valores no seu dicionário provavelmente se tornará mais lento à medida que o dicionário aumentar. Você pode garantir que a velocidade de acesso ao seu dicionário compense o suficiente para fornecer um retorno razoável em relação à velocidade do seu cálculo?

Independentemente disso, parece que você provavelmente precisará considerar um meio de otimizar seu algoritmo. Para isso, você precisará de uma ferramenta de criação de perfil, como o Redgate Ants , para ver onde estão os gargalos e para ajudá-lo a determinar se existem maneiras de reduzir algumas das despesas gerais que você possa ter em relação às instanciações de classe, percursos de lista, banco de dados acessos ou o que quer que esteja custando tanto tempo.

S.Robins
fonte
1
Infelizmente, por enquanto, o algoritmo de cálculo não pode ser alterado, pois é uma biblioteca de terceiros que usa matemática avançada que consome muita CPU. Se em um momento posterior que for reformulado, definitivamente irei verificar as ferramentas de criação de perfil sugeridas. Além disso, o cálculo será realizado com bastante frequência, às vezes com entradas idênticas; portanto, o perfil preliminar mostrou um benefício claro, mesmo com uma estratégia de cache muito ingênua.
PersonalNexus
0

Um pensamento é por que apenas cache n resulta? Mesmo que n seja 300.000, você usaria apenas 7,2 MB de memória (mais qualquer valor extra para a estrutura da tabela). Isso pressupõe três duplos de 64 bits, é claro. Você pode simplesmente aplicar a memorização à própria rotina de cálculo complexa se não estiver preocupado com a falta de espaço na memória.

Peter Smith
fonte
Não haverá apenas um cache, mas um por "item" que estou analisando, e pode haver várias centenas de milhares desses itens.
PersonalNexus
De que maneira importa de qual 'Item' é proveniente a entrada? existem efeitos colaterais?
jk.
@jk. Itens diferentes produzirão entradas muito diferentes para o cálculo. Como isso significa que haverá pouca sobreposição, não acho que mantê-los em um único cache faz sentido. Além disso, itens diferentes podem viver em threads diferentes, portanto, para evitar o estado compartilhado, eu gostaria de manter os caches separados.
PersonalNexus
@PersonalNexus Entendo que isso implica que há mais de 2 parâmetros envolvidos no cálculo? Caso contrário, você ainda terá basicamente f (x, y) = fazer algumas coisas. Além disso, o estado compartilhado parece que ajudaria o desempenho ao invés de dificultar?
Peter Smith
@ PeterSmith Os dois parâmetros são as principais entradas. Existem outros, mas eles raramente mudam. Se o fizerem, eu jogaria fora o cache inteiro. Por "estado compartilhado", quis dizer um cache compartilhado para todos ou um grupo de itens. Como isso precisaria ser bloqueado ou sincronizado de outra maneira, isso prejudicaria o desempenho. Mais sobre as implicações de desempenho do estado compartilhado .
PersonalNexus
0

A abordagem com a segunda coleção é boa. Deve ser uma fila de prioridades que permita localizar / excluir valores mínimos rapidamente e também alterar (aumentar) prioridades dentro da fila (a última parte é difícil, não suportada pela maioria das implementações simples de fila de espera). A biblioteca C5 tem essa coleção, é chamada IntervalHeap.

Ou, é claro, você pode tentar criar sua própria coleção, algo como a SortedDictionary<int, List<InputCount>>. ( InputCountdeve ser uma classe que combina seus Inputdados com seu Countvalor)

A atualização dessa coleção ao alterar seu valor de contagem pode ser implementada removendo e reinserindo um elemento.

Doc Brown
fonte
0

Conforme apontado na resposta de Peter Smith, o padrão que você está tentando implementar é chamado de memorização . No C #, é muito difícil implementar a memorização de maneira transparente, sem efeitos colaterais. O livro de Oliver Sturm sobre programação funcional em C # fornece uma solução (o código está disponível para download, capítulo 10).

Em F #, seria muito mais fácil. Obviamente, é uma grande decisão começar a usar outra linguagem de programação, mas pode valer a pena considerar. Especialmente em cálculos complexos, é mais fácil programar do que memorizar.

Gert Arnold
fonte