Quelle structure de données dois-je utiliser pour cette stratégie de mise en cache?

11

Je travaille sur une application .NET 4.0, qui effectue un calcul assez cher sur deux doubles retournant un double. Ce calcul est effectué pour chacun de plusieurs milliers d' articles . Ces calculs sont effectués dans un Tasksur un thread threadpool.

Certains tests préliminaires ont montré que les mêmes calculs sont effectués encore et encore, donc je voudrais mettre en cache n résultats. Lorsque le cache est plein, je voudrais jeter l' élément le moins souvent utilisé récemment. ( Edit: je me suis rendu compte que le moins souvent n'a pas de sens, car lorsque le cache est plein et que je remplacerais un résultat par un nouveau calculé, celui-ci serait le moins souvent utilisé et immédiatement remplacé la prochaine fois qu'un nouveau résultat est calculé et ajouté au cache)

Afin de mettre en œuvre cela, je pensais à utiliser un Dictionary<Input, double>(où Inputserait une mini-classe stockant les deux valeurs doubles d'entrée) pour stocker les entrées et les résultats mis en cache. Cependant, je devrais également garder une trace du moment où un résultat a été utilisé la dernière fois. Pour cela, je pense que j'aurais besoin d'une deuxième collection stockant les informations dont j'avais besoin pour supprimer un résultat du dicton lorsque le cache était plein. Je crains que le fait de conserver constamment cette liste triée ait un impact négatif sur les performances.

Y a-t-il une meilleure façon (c'est-à-dire plus performante) de faire cela, ou peut-être même une structure de données commune que je ne connais pas? Quels types de choses dois-je profiler / mesurer pour déterminer l'optimalité de ma solution?

PersonalNexus
la source

Réponses:

12

Si vous souhaitez utiliser un cache d'expulsion LRU (expulsion la moins récemment utilisée), alors une bonne combinaison de structures de données à utiliser est probablement:

  • Liste liée circulaire (comme file d'attente prioritaire)
  • dictionnaire

C'est pourquoi:

  • La liste chaînée a un temps d'insertion et de retrait O (1)
  • Les nœuds de liste peuvent être réutilisés lorsque la liste est pleine et qu'aucune allocation supplémentaire ne doit être effectuée.

Voici comment l'algorithme de base devrait fonctionner:

Les structures de données

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

  1. L'entrée est reçue
  2. Si le dictionnaire contient la clé
    • renvoyer la valeur stockée dans le nœud et déplacer le nœud au début de la liste
  3. Si le dictionnaire ne contient pas la clé
    • calculer la valeur
    • stocker la valeur dans le dernier nœud de la liste
    • si le dernier n'a pas de valeur, supprimez la clé précédente du dictionnaire
    • déplacer le dernier nœud à la première position.
    • stocker dans le dictionnaire la paire de valeurs de clé (entrée, nœud).

Certains avantages de cette approche sont, la lecture et la définition d'une valeur de dictionnaire approche O (1), l'insertion et la suppression d'un nœud dans une liste chaînée est O (1), ce qui signifie que l'algorithme approche O (1) pour la lecture et l'écriture de valeurs vers le cache, et évite les allocations de mémoire et les opérations de copie de mémoire de bloc, ce qui le rend stable d'un point de vue mémoire.

Pop Catalin
la source
Bons points, la meilleure idée à ce jour, à mon humble avis. J'ai implémenté un cache basé sur cela aujourd'hui et devra profiler et voir comment il fonctionne demain.
PersonalNexus
3

Cela semble demander beaucoup d'efforts pour un seul calcul étant donné la puissance de traitement dont vous disposez sur le PC moyen. En outre, vous aurez toujours les frais du premier appel à votre calcul pour chaque paire de valeurs uniques, donc 100 000 paires de valeurs uniques vous coûteront toujours le temps n * 100 000 au minimum. Considérez que l'accès aux valeurs dans votre dictionnaire deviendra probablement plus lent à mesure que le dictionnaire s'agrandit. Pouvez-vous garantir que la vitesse d'accès à votre dictionnaire compensera suffisamment pour fournir un rendement raisonnable par rapport à la vitesse de votre calcul?

Quoi qu'il en soit, il semble que vous devrez probablement envisager de trouver un moyen d'optimiser votre algorithme. Pour cela, vous aurez besoin d'un outil de profilage, tel que Redgate Ants, pour voir où se trouvent les goulots d'étranglement et pour vous aider à déterminer s'il existe des moyens de réduire certains des frais généraux que vous pourriez avoir concernant les instanciations de classe, les traversées de liste, la base de données accès, ou quoi que ce soit qui vous coûte tellement de temps.

S.Robins
la source
1
Malheureusement, pour l'instant, l'algorithme de calcul ne peut pas être modifié, car il s'agit d'une bibliothèque tierce qui utilise des mathématiques avancées qui sont naturellement gourmandes en CPU. Si à un moment ultérieur cela sera retravaillé, je vais certainement vérifier les outils de profilage proposés. En outre, le calcul sera effectué assez souvent, parfois avec des entrées identiques, donc le profilage préliminaire a montré un avantage clair même avec une stratégie de mise en cache très naïve.
PersonalNexus
0

Une pensée est pourquoi ne mettre en cache que les résultats n? Même si n est 300 000, vous n'utiliserez que 7,2 Mo de mémoire (plus tout ce qui est supplémentaire pour la structure de la table). Cela suppose bien sûr trois doubles 64 bits. Vous pouvez simplement appliquer la mémorisation à la routine de calcul complexe elle-même si vous ne craignez pas de manquer d'espace mémoire.

Peter Smith
la source
Il n'y aura pas qu'un seul cache, mais un par "élément" que j'analyse, et il peut y avoir plusieurs centaines de milliers de ces éléments.
PersonalNexus
De quelle manière est-il important de savoir de quel «article» provient l'entrée? y a-t-il des effets secondaires?
jk.
@jk. Différents éléments produiront des entrées très différentes pour le calcul. Comme cela signifie qu'il y aura peu de chevauchement, je ne pense pas que les conserver dans un seul cache soit logique. De plus, différents éléments peuvent vivre dans différents threads, donc afin d'éviter un état partagé, je voudrais garder les caches séparés.
PersonalNexus
@PersonalNexus Je suppose que cela implique qu'il y a plus de 2 paramètres impliqués dans le calcul? Sinon, vous avez toujours fondamentalement f (x, y) = faites quelques trucs. De plus, l'état partagé semble aider les performances plutôt que les entraver?
Peter Smith
@PeterSmith Les deux paramètres sont les entrées principales. Il y en a d'autres, mais ils changent rarement. S'ils le font, je jetterais la cache entière. Par «état partagé», j'entendais un cache partagé pour tout ou un groupe d'éléments. Étant donné que cela devrait être verrouillé ou synchronisé d'une autre manière, cela nuirait aux performances. En savoir plus sur les implications en termes de performances d'un état partagé .
PersonalNexus
0

L'approche avec la deuxième collection est très bien. Il doit s'agir d'une file d'attente prioritaire qui permet de trouver / supprimer rapidement des valeurs min et également de modifier (augmenter) les priorités dans la file d'attente (cette dernière partie est la plus difficile, non prise en charge par la plupart des implémentations de file d'attente prio simples). La bibliothèque C5 possède une telle collection, on l'appelle IntervalHeap.

Ou bien sûr, vous pouvez essayer de créer votre propre collection, quelque chose comme a SortedDictionary<int, List<InputCount>>. ( InputCountdoit être une classe combinant vos Inputdonnées avec votre Countvaleur)

La mise à jour de cette collection lors de la modification de votre valeur de comptage peut être implémentée en supprimant et en réinsérant un élément.

Doc Brown
la source
0

Comme indiqué dans la réponse de Peter Smith, le modèle que vous essayez de mettre en œuvre s'appelle la mémorisation . En C #, il est assez difficile d'implémenter la mémorisation de manière transparente sans effets secondaires. Le livre d'Oliver Sturm sur la programmation fonctionnelle en C # donne une solution (le code est disponible en téléchargement, chapitre 10).

En F #, ce serait beaucoup plus facile. Bien sûr, c'est une grande décision de commencer à utiliser un autre langage de programmation, mais cela peut valoir la peine d'être considéré. Surtout dans les calculs complexes, cela rendra plus de choses plus faciles à programmer que la mémorisation.

Gert Arnold
la source