c++ boost cache

Bonjour à tous,


Avant de créer le sujet, j'ai pu faire des recherches via les documentations officielles, les forums (connus) mais malheureusement, je n'ai pas ou très pu eu de réponse.

Contexte :

J'essaye de concevoir un cache pour stocker certaines données liées à des paramètres qui sont très souvent demandées. Le but est d'éviter de toujours rechercher la même chose sachant que juste avant j'ai dû sortir les mêmes données en réponse.

L'idée a été de développer un cache LRU. J’utiliserais ce cache à divers endroits de mon code dans différentes fonctions de différentes classes ; le but est d’attraper les valeurs entrantes et sortantes de certaines fonctions pour les stocker dans mon cache.

Donc il y a aussi un souci que mon cache ne doit pas être créé et détruit à chaque processus, cela perdrait de son sens.

Âpres avoir fait un prototype en c++ sans librairie (pour ne pas se perdre dans plein de documents, je ne posterais pas ce code-ci, car ce n'est pas le sujet principal de mon poste.), je me suis intéressé à la libraire Boost pour trouver des ajouts et optimiser certains cas. Idée très plaisante, car j'ai pu trouver dans la documentation un point hyper intéressant à utiliser :

https://www.boost.org/doc/libs/1_34_....html#example9 .

Suite à cela, j'ai recherché à droite à gauche et trouver un exemple qui me paraissait assez simple et possible à utiliser.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

#include <boost/multi_index_container.hpp> #include <boost/multi_index/sequenced_index.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/key.hpp>   template<typename Tkey, typename Tval> class CacheWeb{ private: using value_type = std::pair<Tkey, Tval>;   unsigned int capacity; boost::multi_index_container< value_type, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::hashed_unique<boost::multi_index::key<&value_type::first>> > > container;   CacheWeb(const CacheWeb&) = delete; CacheWeb& operator=(const CacheWeb&) = delete;   int capacityOut(){ if( capacity == 0 || container.size() < capacity ) { return 0; } int cnt = 0; while(container.size() > capacity) { container.pop_back(); ++cnt; } return cnt; };   public: CacheWeb(int icapacity) : capacity(icapacity){}; virtual ~CacheWeb() = default;     int size(){ return container.size(); }; bool empty(){ return container.empty(); }; void clear(){ container.clear(); };   bool contains(const Tkey& key){ const auto& lookup = container.template get<1>(); return lookup.find(key) != container.template get<1>().end(); };   void remove(const Tkey& key){ container.erase(key); };   void put(const Tkey& key, const Tval& val){ auto& lookup = container.template get<1>(); auto it = lookup.find(key); if( it != lookup.end() ) { lookup.modify(it,[&](value_type& x){ x.second = val; }); } else{ it=lookup.emplace(key, val).first; } container.relocate(container.begin(),container.template project<0>(it)); capacityOut(); };   std::list<std::pair<Tkey, Tval>>getItems(){ return {container.begin(), container.end()}; };   const Tval& get(const Tkey& key){ const auto& lookup = container.template get<1>(); const auto it = lookup.find(key); if( it == lookup.end() ) { throw std::invalid_argument("Key does not exist"); } return it->second; } };   #include <iostream>   int main() { CacheWeb<int,int> c(10); for(int i=0;i<11;++i)c.put(i,i);   for(const auto& x:c.getItems()){ std::cout<<"("<<x.first<<","<<x.second<<")"; } std::cout<<"\n";   for(int i=1;i<11;++i){ std::cout<<i<<"->"<<c.get(i)<<" "; } std::cout<<"\n"; }

---

Malheureusement, plusieurs questions me viennent à l’esprit et aussi quelques problématiques :

1- A cette ligne-là :

Code:

---

boost::multi_index_container<value_type,boost::multi_index::indexed_by<boost::multi_index::sequenced<>,boost::multi_index::hashed_unique<boost::multi_index::key<&value_type::first>>>> container;

---

Je ne comprends pas trop le concept derrière ceci ? J’ai un container avec deux paramètres, ok, mais on souhaite créer quoi en fait comme container ? D’après les recherche, c’est un type vector...


2 – Par rapport à la ligne de code précédente, donc celle-ci :

Code:

---

boost::multi_index_container<value_type,boost::multi_index::indexed_by<boost::multi_index::sequenced<>,boost::multi_index::hashed_unique<boost::multi_index::key<&value_type::first>>>> container;

---

J’ai exporté le code et builder un peu pour mieux comprendre ce qu’il faisait, mais j’obtiens quelques erreurs :

2.1: Too few template arguments for class template 'sequenced'clang(template_arg_list_different_arity)


2.2: No member named 'key' in namespace 'boost::multi_index'clang(no_member)

J’ai essayé de régler le problème en modifiant le container

Code:

---

boost::multi_index::key<&value_type::first>

---

Par ceci :

Code:

---

boost::multi_index::member<value_type,Tkey,&value_type::first>

---

Malheureusement, j’obtiens cette erreur : error: template argument 2 is invalid


3 – Dernière question, je comprends mal certains fonctions liée a boost :

3.1 template get<1>();
3.2 emplace

J’ai trifouillé dans la documents boost, mais soit j’ai louper la page ou je ne sais pas.

Voilà, je vous remercie de lire mon poste ! Je souhaite bien sur avancer dans ce projet et mes connaissances, et je suis arrivé au moment ou je viens à la recherche d’aide.


Je vous souhaite une bonne journée ou soirée.

Je ne suis pas certain que d'utiliser un algo de cache LRU soit très intéressant en software.

Je ne comprend pas l’intérêt de faire ça , sauf si c'est pour une "analyse" , mais même là , si on met des caches , c'est parce que les données sont dynamique , si on savaità l'avance ce qu’on aurait besoin , on aurait pas de cache mais un SPM.

Et justement je ne comprend pas ce que ton code apporterait de plus : " J'essaye de concevoir un cache pour stocker certaines données liées à des paramètres qui sont très souvent demandées. Le but est d'éviter de toujours rechercher la même chose sachant que juste avant j'ai dû sortir les mêmes données en réponse."
si vraiment ton but et de recherché des données rapidement , le cache LRU n'est vraiment pas le plus efficace pour ça.

Bonjour, je te remercie de ta réponse. Très content de voir ce genre de réponse, car ça me fait penser peut-être à une erreur de ma part :)

Bref, pour venir au sujet. J'ai recherché le principe de cache si dans le cas présent, on connaît déjà la quasi-totalité des paramètres entrants et que seules les données sortantes auront quelques valeurs différentes. Je place le contexte : je suis un voyageur et j'ai des paramètres en entrée qui eux sont toujours les mêmes, par exemple : Paris, Toulouse, Dijon etc..(des noms de villes), la dates etc...

Pourquoi LRU cache, âpres différentes recherches, je suis pratiquement toujours tombé sur un LRU cache comme réponse à mon problème

Globalement, je choisis Paris -> Toulouse et je veux qu'en sortit, il me dise juste la meilleure façon de parcourir cette distance, quel transport, etc....


On peut dire qu'à chaque recherche d'un client pour le même parcours, certains points peuvent changer, mais d'autres pas du tout. Mon but est juste qu'en voyant les paramètres entrant comme Paris -> Toulouse, je me dis "Ha tiens, j'ai déjà sorti une réponse pour ce même parcours il y à 1 heure" donc je peux reprendre la réponse stockée dans un cache et sortir ceci plus rapidement que tout refaire à zéro. Bien sur le cache sera actualiser a certain moment, mais c'est une autre question.

ps: un SPM ?


Je me suis déjà mis dans le LRU cache donc j'essaye de pas tout lâcher avant de changer de solution, ça me permettra au pire de découvrir le principe du cache et LRU :) bien sûr je suis preneur, absolument preneur de toute solution/idée qui pourrait m'aide à résoudre ce petit casse-tête de cache, le but est tout de même de trouver une solution

Ok , merci pour ta réponse enfin détaillé , je comprend mieux.

J'ai une question , comment tu compte ressortir les derniers valeurs ? comment fonctionne ton cache LRU ? un cache regarde l'adresse ,toi tu regarde quoi ? Les premières lettres ?

Sinon , je te conseille de faire un Direct Mapped , il faut savoir que les CPU font du cache LRU parce qu'ils sont limité en mémoire cache (un cache L1 c'est 32 Ko donc il a intérêt d’être efficace).
Un cache Direct Mapped peut être aussi performant qu'un LRU , si il est plus gros ( a taille égal le DM est beaucoup moins performant) , mais normalement sur PC , tu n'as pas ce genre de contrainte, à toi de voir, mais je pose la solution ici , surtout qu'un Direct Mapped est facile à implémenter (quelque ligne littéralement ) :p
Mais ça dépend comment ton "cache" fonctionne aussi.
Et si on parle de cache , tu sais combien de "way" tu ferra ? (pour le LRU , le DM , par définition c'est du 1 way) en général on conseille 4 mini , normalement à 16 way , c'est aussi efficace que du full associative (c'est ce qu’utilise les cache L3 d'AMD ou d'Intel).

Pour le SPM , ça veut dire ScratchPad Memory , en gros tu peux écrire dessus comme sur la RAM ,juste que c'est intégrer au cores. , donc c'est bien plus rapide , et comme ce n'est pas un cache, il est bien plus rapide d’accès en lecture/écriture, par contre ,c'est au programmeur de" décider" de savoir ce qu'il y stocke dedans.
Pour cela que le SPM n'existe pas sur les ordinateurs grand public (mais certaine console les intégrer comme la Playstation 2 et Playstation 3 ).

Dans un premier temps, le but de mon sujet est de faire des prototypes de plusieurs solutions et de trouver la meilleure. Dans ce cas-là, tu devines que le LRU est le premier. Faisant ce projet en groupe, je m'occupe de la partie code. Ce que j'essaye de concevoir fonctionne avec un serveur distant qui fonctionne 7/7 h24. (Merci à un ami :) )

C'est comme si je simuler une solution réel et moi je dois implémenter mon algo dans une solution de voyage déjà conçu


Pour répondre à tes questions, je vais faire une liste et mixer certaines questions ensemble. J'excuse d'avance si vous trouvez que j'ai soit mal où peut comprise certaine chose. J'essaie par ce type de projet de m'améliorer et découvrir d'autre chose. Ce projet me tient a cœur


Comment fonctionne ton cache LRU ? + comment tu comptes ressortir les dernières valeurs ?

D'après ce que j'ai compris du LRU.

Lorsqu'une page est référencée, la page requise peut être en mémoire. S'il est dans la mémoire, on détache le nœud de la liste et on l'amenait au début de la file d'attente pour le sortir plus rapidement.

Un cache regarde l'adresse ,toi, tu regardes quoi ?

Je comptais créer un pair de clé: la clé serait les lettres ville + la date. Exemple: PRS-TS-1211202


tu sais combien de "way" tu ferra ?

Bonne question, j'avais pris connaissance du concep de way (via cette page https://www.quora.com/What-does-L1-c...ine-8-way-mean), mais j'ai du mal à le concevoir

je réitère mais merci pour tes réponse.

Ok je pense avoir mieux compris.

Je ne pense pas que le way te servira (en tout cas 8 way et son concept ) , si je comprend ,tu vas gérer un nombre de valeur je pense assez conséquent (un tableau de 128 ou 256 par exemple) et tu as besoin d'un algo pour savoir lequel tu vas virer ou garder.

Le LRU est un algo qu'on utilise sur des adresses un peu random , mais surtout parce qu'on est assez faible en way ( par exemple sur 4 valeurs à garder, l'algo à intérêt d’être assez bon ).

Si tu fait un tableau de 128 ou 256 , c'est un peu comme si tu faisais du 128 ou 256 way , ce qui du coup change beaucoup de chose :mrgreen:
En soit j'ai aucune idée de l'efficacité du LRU quand tu as autant de "way" , mais ce qui est sur c'est que peu importe l'algo , plus tu as de way, plus le "miss cache" tente de disparaître.

Donc si je stocke un certain nombre de données et que je les actualise par exemple, toutes les heures, je peux éviter le miss cache alors.

Pour revenir aussi aux premières questions, tu as peut-être des idées ou réponses qui peuvent m'aider ?

Citation:

---

Envoyé par nansty

Donc si je stocke un certain nombre de données et que je les actualise par exemple, toutes les heures, je peux éviter le miss cache alors.

Pour revenir aussi aux premières questions, tu as peut-être des idées ou réponses qui peuvent m'aider ?

---

Euh , je vais pas te répondre, je vais juste t'expliquer comment ça marche.
Tu comprendra pourquoi "je ne sais pas quoi te répondre".
Un CPU comme ça doit être rapide pour accéder aux caches , il ne stocke qu'une partie de l'adresse , mais forcément en faisant cela , il va se trouver avec les même adresses .
Alors , c'est pas grave , sur 4 way , il peut stocker 4 adresses "pareil" , mais forcément si un nouveau arrive, il faut en éjecter un , la question est "lequel ?" , et c'est là que différent algo existe (notamment le LRU).

Alors tu as forcément des miss cache obligatoire et c'est les premiers accès et bien sur si ta donnée n'existe pas sur ton cache.
L'autre cache miss ,et celle des conflits de cache, donc que tu as deux adresses identique (je le rappel on ne prend qu'une partie de l'adresse) , forcément , plus en grossis le way , plus les chances que deux adresses identique soit en conflit diminue , et c'est en général sur ceux là qu'on "bosse" à améliorer, et le LRU est une des réponses (parmi en d'autre).
Les premiers cache miss étant obligatoire, y'a pas de solution possible pour les éviter.

Voilà donc tu comprends que toi tu n'es pas dans ce cas de figure pour ça que faudra plutôt customiser par rapport à ton besoin.

Citation:

---

Envoyé par nansty

Pour revenir aussi aux premières questions, tu as peut-être des idées ou réponses qui peuvent m'aider ?

---

Lesquels plus exactement ?
Moi je t'ai répondu sur l'algo que tu viserai.

Pour expliquer encore les caches , admettons que tu fais un tableau de 256 , j'imagine que tu vas comparer les 256 adresses ?
Mais ce n'est pas ce que fait un cache , il va prendre une partie de l'adresse et ensuite il va comparer que 4 adresses (4 way ).

Mais si dans ton cas, cela pose pas de soucis de comparer les 256 , le way n'a plus d'importance , et comme tu as un nombre assez conséquent, tu peux te permettre de faire du une pile , ce qui est le plus "logique".
Après j’imagine que tu veux savoir que le premier pourrait être très utilisé donc dommage de le virer du cache ?
Mais c'est un soucis qui existe sur le cache , donc en général , quand c'est réutilisé, il est "réinitialiser" , c'est un algo parmi en d'autre, mais ça serait le plus logique, vu que tu n'as pas les autres contrainte matériel d'un cache.

Bonjour,

Je vais mettre sur papiers (enfin un word je veux dire :D) tes réponses pour bien comprendre le principe. C'est une notion forte intéressante que tu m'as donnée.

Pour revenir à ta dernière question et à la mienne. Je parlais du fonctionnement de ma classe, les questions 1,2, 3 qui sont liées à la lib Boost en autres. Je suis perdu, à savoir pourquoi ma classe ne fonctionne pas (faut bien que je la fasse fonctionner).

Je ne copie pas les questions dans ce message sinon ça fera un gros doublon (surtout que je dois aussi copier le code), et pas très agréable à lire comme fil conducteur pour les personnes qui s'intéresse à cette question.

Ah pour le code ,n'étant pas expert en C++ , et vu que je n'utilise pas boost, je préfère laisser quelqu'un d'autre y répondre :p

Je répondais aux caches LRU vu que c'est un peu plus mon domaine de compétence ,le C++ moins ^^'

Je n'utilise pas Boost, mais un cache ça peut être un simple std::map.

Sinon il y a Memcached, je l'avais utilisé il y a plusieurs années sur un serveur Python. Il semblerait qu'ils aient une libMemcached en C++.
Si ton serveur de cache est externe, faut voir si la requête est pas plus lente que de toujours calculer le résultat je suppose. J'imagine que ça va dépendre si ton objectif est de limiter l'utilisation CPU, la bande-passante, le temps de réponse, ...

Bonjour Bousk, je te remercie de ta réponse, je vais regarder ceci aussi !

Une petite question pour toi. Je vois que tu es modérateur, je me suis aperçue qu'il existait un sous-forum dédie à boost et ne voulant pas supprimer ce sujet, car il correspond aussi à une question cache et dispose de plusieurs réponses très intéressantes, je me trouve embêter, car j'ai aussi des questions liées à Boost.

Je sais que normalement des doublons de sujet ne sont pas autorisés, mais dans ce cas-là, il serait autorisé de créer une autre discussion tout en gardant celui-ci ?

Je te souhaite une bonne journée.