IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Modéliser un cache LRU : l'erreur la plus inexplicable


Sujet :

C++

  1. #1
    Rédacteur
    Avatar de Bakura
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2005
    Messages
    1 386
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 386
    Par défaut Modéliser un cache LRU : l'erreur la plus inexplicable
    Bonsoir à tous,

    Cela fait maintenant 5 jours que je planche sur un programme destiné à améliorer l'indicage d'un tableau d'indices d'un modèle 3D afin d'en accélerer l'affichage, et je me heurte à un problème, que je viens d'identifier à l'instant.

    L'algorithme en question utilise un cache LRU, dont j'ai créé une classe afin de me simplifier le travail, en utilisant un deque (la rapidité n'est pas très importante pour l'instant, étant donné que je ne travaille que sur de très petits caches (32), et que le container deque a tout ce que je recherche).

    Elle devait remplir quelques critères : pouvoir contenir n'importe quelle valeur, ne pas autoriser de valeurs dupliquées (comme pour un map ou un set), mais ne pas être ordonné (contrairement à un map ou un set).

    Chaque élément que j'ajoute dans mon cache se placera à la tête automatiquement et me renvoit la valeur ajoutée, et si la taille maximale a été atteinte, me renvoit la valeur qui vient d'être supprimée. Si j'ajoute un élément qui est déjà présent dans le cache, cet élément est replacé au début du cache (et me renvoit cette valeur), et ne supprime donc rien.

    Voici comment j'ai codé ça :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
     
    // Pour un cache de type deque
    template <typename Value_Type>
    class LRUCacheDeq
    {
    	public:
    		LRUCacheDeq (const std::size_t maxSize)
    			: maxSize (maxSize)
    		{
    		}
     
    	private:
    		// Quelques typedefs pour faciliter le travail...
    		typedef typename std::deque<Value_Type>::iterator deq_iterator;
    		typedef typename std::deque<Value_Type>::const_iterator deq_const_iterator;
     
    		// Taille maximale du cache
    		std::size_t maxSize;
     
    		// Les données en elle-même
    		std::deque<Value_Type> LRUList;
     
    	public:
    		// On cherche un élément
    		deq_iterator find (const Value_Type & value)
    		{
    			// On recherche l'élément
    			deq_iterator deq_iter = std::find (LRUList.begin(), LRUList.end(),
    														  value);
     
    			// Si aucun élément n'a été trouvé, on retourne l'itérateur vers la fin
    			if (deq_iter == LRUList.end())
    				return deq_iter;
     
    			// Sinon, on replace l'élément au début de la liste
    			LRUList.push_front (*deq_iter);
    			LRUList.erase (deq_iter);
     
    			// On renvoit l'élément
    			return (LRUList.begin());
    		}
     
    		// Fonction pour insérer un élément
    		Value_Type & insert (const Value_Type & value)
    		{
    			// On recherche si l'élément est déjà dans la liste
    			deq_iterator deq_iter = find (value);
     
    			// Si l'élément n'est pas encore présent, on l'ajoute à la fin de la liste.
    			// S'il est présent, il sera automatiquement ajouté au début (MRU)
    			if (deq_iter == LRUList.end())
    				LRUList.push_front (value);
     
    			// On vérifie si on ne dépasse pas la taille maximale du cache
    			if (LRUList.size() > maxSize)
    			{
    				// On récupère la valeur de l'élément qui va être supprimé
    				Value_Type & val = LRUList.back();
     
    				// On supprime le dernier élément
    				LRUList.pop_back();
     
    				// On renvoit l'élément
    				return val;
    			}
     
    			// Sinon, on retourne l'élément qui vient d'être ajouté
    			return (LRUList.front());
    		}
     
    		Value_Type & operator[] (const std::size_t idx)
    		{
    			assert (idx < maxSize);
     
    			return LRUList[idx];
    		}
     
    		// On affiche les éléments dans l'ordre, du plus récent au plus ancien
    		void Write () const
    		{
    			for (deq_const_iterator deq_const_iter = LRUList.begin() ; 
    				  deq_const_iter != LRUList.end() ; ++deq_const_iter)
    			{
    				std::cout << *deq_const_iter << std::endl;
    			}
    		}			
    };
    J'ai eu beau relire ce code 5-6 fois, il me paraît totalement bien et sans aucune erreur... Toutefois, je me suis aperçu dans mon code bien long que le problème venait du cache, et j'ai donc créé un code minimale qui reproduit l'erreur et, vous allez voir, c'est l'erreur la plus incompréhensible que je n'ai jamais vu... Voici en tout cas un cas dans lequel ça fonctionne, avec une taille de cache de 31 :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    LRUCacheDeq<std::size_t> cache (31);
     
    for (std::size_t i = 0 ; i != 31 ; ++i)
    	cache.insert (i);
     
    cache.insert (30);
    J'obtient donc bien 30, 29, 28, 27, 26... 0

    Avec un cache de 33 :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    LRUCacheDeq<std::size_t> cache (33);
     
    for (std::size_t i = 0 ; i != 33 ; ++i)
    	cache.insert (i);
     
    cache.insert (32);
    Aucun soucis non plus...

    Par contre, avec un cache de 32...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    LRUCacheDeq<std::size_t> cache (32);
     
    for (std::size_t i = 0 ; i != 32 ; ++i)
       cache.insert (i);
     
    cache.insert (31);
    Et bien... ça plante . Je dois avouer que je n'y comprends rien du tout, mon ordinateur a failli se prendre plusieurs coups de pieds, tellement c'est complètement illogique que ça fonctionne pour une taille de 31, de 33, mais pa s de 32... J'ai essayé, dans le doute, avec un autre nombre pair, 30, mais ça fonctionne.

    Je m'en remet donc à vos conseils avisés, car là je commence à m'énerver.

    Merci à vous.

  2. #2
    Rédacteur
    Avatar de Bakura
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2005
    Messages
    1 386
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 386
    Par défaut
    Bon... Pour une raison que j'ignore complètement, en remplaçant le deque par une liste, ça marche bien... Alors je comprends pas du tout, je vois pas pourquoi le code ne fonctionne pas avec un deque... Voici le code pour la liste :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    // Pour un cache en utilisant une liste
    template <typename Value_Type>
    class LRUCacheDeq
    {
    	public:
    		LRUCacheDeq (const std::size_t maxSize)
    			: maxSize (maxSize)
    		{
    		}
     
    	private:
    		// Quelques typedefs pour faciliter le travail...
    		typedef typename std::list<Value_Type>::iterator list_iterator;
    		typedef typename std::list<Value_Type>::const_iterator list_const_iterator;
     
    		// Taille maximale du cache
    		std::size_t maxSize;
     
    		// Les données en elle-même
    		std::list<Value_Type> LRUList;
     
    	public:
    		// On cherche un élément
    		list_iterator find (const Value_Type & value)
    		{			
    			// On recherche l'élément
    			list_iterator list_iter = std::find (LRUList.begin(), LRUList.end(),
    														    value);
     
    			// Si aucun élément n'a été trouvé, on retourne l'itérateur vers la fin
    			if (list_iter == LRUList.end())
    				return list_iter;
     
    			// Sinon, on replace l'élément au début de la liste
    			LRUList.push_front (value);
    			LRUList.erase (list_iter);
     
    			// On renvoit l'élément
    			return (LRUList.begin());
    		}
     
    		// Fonction pour insérer un élément
    		Value_Type & insert (const Value_Type & value)
    		{
    			// On recherche si l'élément est déjà dans la liste
    			list_iterator list_iter = find (value);
     
    			// Si l'élément n'est pas encore présent, on l'ajoute à la fin de la liste.
    			// S'il est présent, il sera automatiquement ajouté au début (MRU)
    			if (list_iter == LRUList.end())
    				LRUList.push_front (value);
     
    			// On vérifie si on ne dépasse pas la taille maximale du cache
    			if (LRUList.size() > maxSize)
    			{
    				// On récupère la valeur de l'élément qui va être supprimé
    				Value_Type & val = LRUList.back();
     
    				// On supprime le dernier élément
    				LRUList.pop_back();
     
    				// On renvoit l'élément
    				return val;
    			}
     
    			// Sinon, on retourne l'élément qui vient d'être ajouté
    			return (LRUList.front());
    		}
     
    		Value_Type operator[] (const std::size_t idx)
    		{
    			assert (idx < maxSize);
     
    			std::size_t i = 0;
     
    			for (list_iterator list_iter = LRUList.begin() ;
    				  list_iter != LRUList.end() ; ++list_iter)
    			{
    				if (i == idx)
    					return *list_iter;
    				++i;
    			}
    		}
     
    		// On affiche les éléments dans l'ordre, du plus récent au plus ancien
    		void Write () const
    		{
    			for (list_const_iterator list_const_iter = LRUList.begin() ; 
    				  list_const_iter != LRUList.end() ; ++list_const_iter)
    			{
    				std::cout << *list_const_iter << std::endl;
    			}
    		}			
    };

  3. #3
    screetch
    Invité(e)
    Par défaut
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    			LRUList.push_front (*deq_iter);
    			LRUList.erase (deq_iter);
    push_front invalide l'iterateur puis tu fais erase dessus, KABOOM.

    ca marche en remplacant ce code par :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    			Value_type val = *deq_iter;
    			LRUList.erase (deq_iter);
    			LRUList.push_front (val);

  4. #4
    Rédacteur
    Avatar de Bakura
    Homme Profil pro
    Étudiant
    Inscrit en
    Septembre 2005
    Messages
    1 386
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Septembre 2005
    Messages : 1 386
    Par défaut
    Merci, ça marche . Ca va bien plus vite avec un deque et l'opérateur [] que la méthode vaseuse qu'on peut faire avec une liste .

    Merci beaucoup !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Les 10 erreurs les plus stupides faites par les admin réseau ?
    Par Community Management dans le forum Sécurité
    Réponses: 87
    Dernier message: 28/09/2020, 16h18
  2. Trie dans un cache LRU
    Par Kromagg dans le forum C++
    Réponses: 8
    Dernier message: 09/11/2008, 21h21
  3. Réponses: 9
    Dernier message: 30/10/2008, 12h10
  4. erreur étrange : plus d'accès à this
    Par DEVfan dans le forum C++
    Réponses: 4
    Dernier message: 21/07/2008, 22h47
  5. [SOURCE][CPP] Cache LRU
    Par Bakura dans le forum Contribuez
    Réponses: 0
    Dernier message: 23/10/2007, 10h48

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo