Discussion :

[Bakura]

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.

[Bakura]

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;
			}
		}			
};

[screetch]

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);

[Bakura]

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 !