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:
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:
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:
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:
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 8O. 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.
