Nous avons une application C ++ pour laquelle nous essayons d'améliorer les performances. Nous avons identifié que la récupération de données prend beaucoup de temps et que vous souhaitez cacher des données. Nous ne pouvons pas stocker toutes les données en mémoire car elle est énorme. Nous voulons stocker jusqu'à 1000 articles en mémoire. Ces éléments peuvent être indexés par une touche Pouvez-vous suggérer un moyen de le mettre en œuvre?
Ma mise en œuvre initiale consistait à avoir une carte Une autre idée était de contenir une liste de Pouvez-vous suggérer une meilleure approche?
Merci Long . Cependant, lorsque la taille du cache dépasse 1000, nous souhaitons supprimer l'élément qui n'a pas été accédé au plus longtemps, car nous supposons une sorte de "localité de référence", c'est que nous supposons que les éléments du cache récemment consulté sera probablement accessible à nouveau.
accessampstamp membre sur cacheenry qui sera défini sur un compteur croissant chaque fois qu'une entrée est créée ou accessible. Lorsque le cache est plein et qu'une nouvelle entrée est nécessaire, le code numérisera la carte de cache entière et trouvera l'entrée avec le accessampstamp et le supprimer.
Le problème avec ceci est qu'une fois le cache plein, chaque insertion nécessite une analyse complète du cache.
cacheentries en plus de la carte de cache, et sur chaque accès déplacez l'entrée accessible en haut de la liste, mais le problème était de savoir comment trouver rapidement cela Entrée dans la liste.
Splintor
10 Réponses :
Numérisation d'une carte de 1000 éléments prendra très peu de temps et la numérisation ne sera effectuée que lorsque l'article n'est pas dans le cache qui, si votre localité d'idées de référence est correcte, devrait être une faible proportion du temps. Bien sûr, si vos idées ont tort, le cache est probablement une perte de temps de toute façon.
Et comme cela venait de moi et que j'ai dit dans ma réponse: Si vous pouvez faire des E / S asynchrones, vous pouvez numériser le cache pour quelque chose à supprimer pendant que vous attendez que votre nouvel objet arrive. Donc, c'est effectivement libre tant que cela prend moins de temps que les E / S, et vous n'êtes pas également lié à la CPU. Il pourrait donc accomplir jusqu'à autant d'articles que vous pouvez visiter au moment de la prise d'E / S. Si vous ne pouvez pas faire ASYNC E / S, vous n'avez probablement aucune entreprise optimisant le cache ;-)
Sauf que la mise en place et la manipulation de l'ASYNCH E / S coûte du temps à l'exécution et à l'effort de temps de conception et de mise en œuvre. Rien n'est "efficacement libre" dans ce monde. Et je suis convaincu assez fort avec votre dernière phrase - le cache peut être utile même dans un cadre purement synchrone.
Je suis d'accord que le cache peut être utile. Je veux juste dire que si votre cache est sous-performant, vous n'avez pas de cycle économique - comptant le code de maintenance du cache avant que vous ayez au moins essayé de paralliser l'E / S. Ce dont je parle dans ce cas, cependant, n'est que quelque chose comme "Démarrer les E / S ASYNC; expulser quelque chose du cache; bloc sur les E / S;". C'est un peu plus de travail de conception que de bloquer les E / S, mais avec une bonne API ASYNC, pas beaucoup plus. Et ce n'est peut-être pas plus de travail d'exécution, car il n'est pas inhabituel que les systèmes de mise en oeuvre de blocage d'E / S au-dessus de l'ASYNC: l'autre solution est plus difficile.
... Le point global étant que vous avez probablement raison que la numérisation de 1000 articles soit triviale, mais même si ce n'est pas trivial, par exemple si la taille du cache est augmentée à l'avenir, il sera souvent possible d'organiser pour que cela ne soit pas important. . En termes de performance, l'éléphant dans la pièce que le questionneur ignore, est que la récupération de données dans le cache est presque certainement lente et non liée à la CPU.
Je pense que je vais aller avec vos conseils. À l'aide d'ASYNC E / S pourrait être un mal de tête ici, car nous compilons à l'aide du compilateur SAS / C et copiez-le sur Z / OS Mainframe, et je ne suis pas sûr que nous avons une bibliothèque d'E / S ASYNC décente pour cela.
Mise à jour: je l'ai maintenant ...
Cela devrait être raisonnablement rapide. AVERTISSEMENT, un peu pseudo-code à venir. P>
// accesses contains a list of id's. The latest used id is in front(),
// the oldest id is in back().
std::vector<id> accesses;
std::map<id, CachedItem*> cache;
CachedItem* get(long id) {
if (cache.has_key(id)) {
// In cache.
// Move id to front of accesses.
std::vector<id>::iterator pos = find(accesses.begin(), accesses.end(), id);
if (pos != accesses.begin()) {
accesses.erase(pos);
accesses.insert(0, id);
}
return cache[id];
}
// Not in cache, fetch and add it.
CachedItem* item = noncached_fetch(id);
accesses.insert(0, id);
cache[id] = item;
if (accesses.size() > 1000)
{
// Remove dead item.
std::vector<id>::iterator back_it = accesses.back();
cache.erase(*back_it);
accesses.pop_back();
}
return item;
}
Il est index par la touche longue, pas l'heure d'accès.
La carte n'est pas clatée sur la valeur qu'il souhaite supprimer.
Je pense que ce code est essentiellement correct. C'est une pseudo-implémentation de l'autre idée que j'ai mentionnée dans le poste. J'ai peur que la recherche des éléments consultés dans la liste des accès à chaque accès prendra trop de temps, bien que la localité soit effectivement réduire ce temps.
comme une alternative plus simple, vous pouvez créer une carte qui se développe indéfiniment et s'efforce toutes les 10 minutes environ (régler la durée du trafic attendu).
Vous pouvez également enregistrer des statistiques très intéressantes de cette façon.
Ajout d'un fil d'arrière-plan et des serrures multi-threading pour gérer ce problème semble être une overcilleuse.
J'ai supposé que votre cache devrait être le fil de sécurité, sans distinction.
Non pas du tout. L'application est actuellement insuffisante, désolé.
Créer un std: priority_queue
Cela ne fonctionne pas lorsque les comptes d'accès sont incrémentés. Les files d'attente prioritaires ne peuvent pas ajuster leur évolution si les choses à l'intérieur peuvent changer.
Je suis d'accord avec Neil, numériser 1000 éléments ne prend pas de temps du tout.
Mais si vous voulez le faire quand même, vous pouvez simplement utiliser la liste supplémentaire que vous proposez et, afin d'éviter de numériser toute la liste à chaque fois, au lieu de stocker uniquement la cachetry dans votre carte, vous pouvez stocker la cachetry et un pointeur à l'élément de votre liste correspondant à cette entrée.
Mais alors je devrai traiter avec une itératrice invalidante (en supposant que je utilise STD: liste), car la liste change constamment lorsque des entrées de cache sont en cours d'accès.
Hmm, oui tu as raison, je n'y ai pas pensé! Mais vous pouvez toujours créer votre propre liste double liée, ce qui serait facile car les seules opérations dont vous avez besoin sont assez faciles. De cette façon, vous ne perdrez aucune référence que vous avez. Donc, ce qui se passe est ce qui se passe: lorsque une nouvelle entrée arrive, créez un nouveau nœud à la tête de la liste. Ajouter dans la carte la cachetry avec un pointeur sur ce nœud. Lorsqu'une entrée est réoplacée, trouvez le nœud de la liste (à l'aide de la touche pour obtenir le bon élément sur la carte, puis le pointeur qui pointe sur le nœud de la liste) et déplacez cet élément à la tête de la liste.
C'est fondamentalement ce que JK a suggéré, et nous avons tous deux convenu que le maintien de ma propre liste liée, tout en étant amusant, pourrait être trop risqué, en particulier pour l'étape actuelle et la condition de notre projet.
Une mise en œuvre alternative susceptible de rendre le «vieillissement» des éléments plus facilement, mais au prix de la performance de la recherche inférieure serait de conserver vos éléments de la cachetry dans une marque STD :: Liste (ou d'utiliser un std :: paire < long, cachetryry> . L'élément le plus récent est ajouté à l'avant de la liste afin qu'ils «migrent» vers la fin de la liste comme ils vieillissent. Lorsque vous vérifiez si un élément est déjà présent dans le cache, vous numérisez. la liste (qui est certes une opération O (n) par opposition à être une opération O (log n) sur une carte). Si vous le trouvez, vous le supprimez de son emplacement actuel et de l'insérer au début de la Liste. Si la longueur de la liste s'étend sur plus de 1000 éléments, vous supprimez le nombre requis d'éléments de la fin de la liste pour la couper en dessous de 1000 éléments.
L'âge n'est pas le problème. C'est le nombre d'accès à un objet mis en cache qui correspond aux critères de la conserver.
Hmmm ... op semble-au contraire de soi. "... Nous supposons que les articles dans le cache qui ont été récemment accessibles seront probablement accessibles à nouveau."
Je pense que par "sera défini sur un comptoir croissant", le PO signifie qu'il a un compteur croissant global et définira l'accès à l'accès à la valeur de ce comptoir. Il ne dis pas, "Access Stamp est un comptoir croissant".
L'OP a dit: "Nous voulons éliminer l'article qui n'a pas été accédé pour la plus longue période", ce qui m'a semblé être après une sorte d'algorithme de moins récemment utilisé. D'où la suggestion de conserver les entrées récemment utilisées au début de la liste et supprimez les entrées «trop anciennes» de la fin de la liste.
J'ai pensé à cette solution, mais comme vous l'avez dit, l'action de recherche, que je m'attends à survenir beaucoup plus que de supprimer l'article d'un cache complet, prendra plus de temps. C'est pourquoi j'ai rejeté cette option.
Cela pourrait encore être digne d'essayer - 1000 éléments n'est pas si nombreux et je m'attendais même à une recherche linéaire assez rapide.
avoir votre carte cacheenry , mettez deux liens vers un autre cacheenry objets Pour que les entrées forment une liste doublement liée. Chaque fois qu'une entrée est accessible, déplacez-la à la tête de la liste (il s'agit d'une opération de temps constante). De cette façon, vous trouverez facilement l'entrée de cache facilement, car elle est accessible à partir de la carte et vous permettra de supprimer l'entrée utilisée la moins récemment utilisée, car elle est à la fin de la liste (ma préférence est de créer des listes doublement liées circulaires, Donc, un pointeur de la tête suffit pour obtenir un accès rapide à la queue aussi). N'oubliez pas non plus de mettre dans la clé que vous avez utilisée dans la carte dans la cacheentry de sorte que vous pouvez supprimer la saisie de la carte lorsqu'il est expulsé du cache.
J'aime ça - probablement la meilleure solution qui utilise deux collections. Je voudrais faire des tests pour prouver que cela est en réalité plus rapide que la mise en œuvre de la numérisation de carte naïve, cependant.
Odd, j'ai raté cette réponse avant d'écrire le mien, ce qui est identique. +1, alors.
Cela ressemble en effet à la bonne réponse pour le problème. Toutefois, compte tenu de la planification serrée et de la capacité de débogage limitée (nous compilons le code à l'aide de SAS /, C compilateur et copiez-le sur Z / OS Mainframe), il semble trop risqué de gérer notre propre liste liée. Par conséquent, je pense que je vais coller avec mon design original et utiliser les conseils de Neil Butterworth qui scannant une carte de 1000 articles prend peu de temps.
Il est difficile de dire - comme je l'ai dit, la "réponse correcte" à ma question semble être cette réponse, mais que je compte, votre réponse me convient mieux. J'aimerais pouvoir marquer les deux réponses. Cependant, depuis que je compte sur Oyur Répondre, je suppose que vous méritez que ce soit une réponse ...
J'étais juste en train de blaguer! Donnez à JK les points - il a besoin de eux plus que moi!
Splitrice, assez juste: obtenir une liste liée complètement correcte peut être délicate. Et Neil, si vous êtes si inquiet pour que je reçoive des points, pourquoi ne vous précipitez pas certaines de mes autres réponses? ;-)
Je crois que c'est un bon candidat pour Treaps . La priorité serait l'heure (virtuelle ou autre), dans l'ordre croissant (plus vieux à la racine) et le Il y a aussi le algorithme de deuxième chance , c'est bon pour les caches. Bien que vous perdiez la capacité de recherche, cela ne sera pas un impact important si vous n'avez que 1000 articles.
La méthode naïve serait d'avoir une carte associée à une file d'attente prioritaire, enveloppée dans une classe. Vous utilisez la carte pour rechercher et la file d'attente à retirer (enlevez d'abord de la file d'attente, en saisissant l'élément, puis retirez la touche de la carte). long comme clé.
Je vais y examiner, mais cela semble trop complexe pour la tâche à un premier coup d'œil.
Une autre option peut être d'utiliser Boost :: Multi_index . Il est conçu pour séparer l'index des données et permettant de permettre à plusieurs index sur les mêmes données.
Je ne suis pas sûr que cela serait vraiment plus rapide alors de numériser 1000 articles. Cela pourrait utiliser plus de mémoire alors bon. Ou ralentir la recherche et / ou insérer / supprimer.
L'index multiples nécessitera de suppression et de l'ajout d'un élément sur chaque accès, car chaque clé d'index est constante et accès à l'accès, que je devrais indexer, changements sur chaque accès. Je suppose donc que je n'aurai aucun temps de bénéficier de ce soluion.
Dans mon approche, il est nécessaire d'avoir une table HASH pour rechercher des objets stockés rapidement et une liste liée pour maintenir la séquence de la dernière utilisation.
Lorsqu'un objet est demandé. 1) Essayez de trouver un objet de la table de hachage 2.Oui) Si trouvé (la valeur a un pointeur de l'objet dans la liste liée), déplacez l'objet dans la liste liée en haut de la liste liée. 2.no) Sinon, supprimez le dernier objet de la liste liée et retirez également les données de la table HASH, puis mettez l'objet dans la table HASH et le haut de la liste liée.
Par exemple Disons que nous avons une mémoire cache uniquement pour 3 objets.
La séquence de la demande est 1 3 2 1 4.
1) Tableau de hachage: [1] Liste liée: [1]
2) Tableau de hachage: [1, 3] Liste liée: [3, 1]
3) Tableau de hachage: [1,2,3] Liste liée: [2,3,1]
4) Tableau de hachage: [1,2,3] Liste liée: [1,2,3]
5) Tableau de hachage: [1,2,4] Liste liée: [4,1,2] => 3 out
@Neil n'a pas pu
AccessStamp être utilisé dans ce cas?Non, parce que cela change. Une clé doit être constante.
@Niel merci, pour la réponse. C'est mon mauvais que je ne pensais pas soigneusement.
Je préfère l'accèstamp. Je pense que cela peut être compris qu'un "horodatage" pourrait être tout ce qui augmente avec le temps, pas nécessairement la date / heure réelle d'accès. Je trouverais un accès confusant, car je me demandais s'il s'agit du nombre de tous les accès à toutes les entrées de cache (cache la plus récente) ou d'un nombre de seuls accès à cette entrée (cache la plus utilisée).
@Steve Je ne comprends vraiment pas ce que vous dites. Si vous voulez un cache MRU, vous devez utiliser un horodatage. Si vous voulez un MFU, vous devez utiliser un compte. Dans le premier cas, j'appellerais IT Accessampstamp, dans ce dernier AccessCount.
Je pense que l'affiche veut un cache mru (parce qu'il le dit), et que lorsqu'il dit "AccessStamp est défini sur un comptoir croissant", il signifie quelque chose comme
AccessStamp = ++ my_global_counter; , pas quelque chose comme++ accèstamp; comme vous semblez avoir lu.@Steve Vous pourriez bien avoir raison - je dois dire que j'ignore normalement le titre de la question actuelle et ne lisez que le texte. Heureusement, ma propre réponse est applicable dans les deux cas :-)