Un cache template

**camboui** · 26/03/2009, 14h15

J'ai écrit un cache. Cela fait suite à cette discussion.

Je n'ai rien inventé, j'ai juste amélioré l'idée trouvée ici. Autant j'aime bien l'idée car simple, autant l'implémentation est assez lourde et peu pratique.

Voici une autre solution (pas encore de callback dont question dans l'autre discussion).

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
template <typename T>
struct cache_value
{
	T & s_value;
	bool s_created;
 
	cache_value(T & value,bool created):s_value(value),s_created(created) {}
};
 
 
#ifdef USE_UNORDERED_SET
template <typename K, typename T, typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
#else
template <typename K, typename T, typename PrLess = std::less<K> >
#endif
class cache
{
	//The cache organize a MRU/LRU collection of cells in a bidirectional circular list.
	//The MRU cell is stored in f_mru_cell, the LRU cell is thus f_mru_cell->s_prev.
	//The cells are also stored in a std::set for a fast key search.
	struct cell
	{
		cell *s_prev,*s_next;
		K s_key;
		T s_value;
 
		cell(K key):s_key(key) {s_next=s_prev=this;}
 
		void attach_before(const cell *p)
		{
			p=p->s_prev;
			s_prev=(s_next=p->s_next)->s_prev;
			s_next->s_prev=s_prev->s_next=this;
		}
		void detach()
		{
			s_next->s_prev=s_prev;
			s_prev->s_next=s_next;
		}
	};
#ifdef USE_UNORDERED_SET
	struct cell_predhash
	{
		std::size_t operator()(const cell *p) const
			{ return PrHash()(p->s_key); }
	};
	struct cell_predequal
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrEqual()(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrLess()(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell *,cell_predless> cell_set;
#endif
 
	unsigned f_maxCell;
 
	/* TODO: use my own allocator */
	cell *f_mru_cell;
	cell_set f_set;
 
public:
	cache(unsigned maxCell): f_maxCell(maxCell<1?1:maxCell),f_mru_cell((cell *)0)
#ifdef USE_UNORDERED_SET
		,f_set(maxCell<1?1:maxCell)
#endif
		{}
	//copy contructor, assign operator ?
	~cache() { clear(); }
 
	void clear()
	{
		if (f_mru_cell)
		{
			//delete cells from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				//cell deleted !!! caller MUST be informed
				delete p;
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		f_mru_cell=(cell *)0;
		f_set.clear();
	}
 
	void reset(unsigned maxCell)
	{
		clear();
		f_maxCell=(maxCell<1?1:maxCell);
#ifdef USE_UNORDERED_SET
		f_set.rehash(maxCell<1?1:maxCell);
#endif
	}
 
	cache_value<T> fetch(K key)
	{
		cell tmp(key);
		cell_set::iterator it=f_set.find(&tmp);
		if (it!=f_set.end())
		{
			//key is found
			//(f_mru_cell can't be NULL)
			cell *found_cell=*it;
			if (f_mru_cell!=found_cell)
			{
				//adjust cell list, found cell becomes MRU cell
				found_cell->detach();
				found_cell->attach_before(f_mru_cell);
				f_mru_cell=found_cell;
			}
 
			//return T and notify that key was already in cache
			return cache_value<T>(found_cell->s_value,false);
		}
		else
		{
			//key not found
			cell *new_cell;
 
            if (f_set.size()>=f_maxCell)
			{
				//cache size limit reached, remove LRU cell
				//(f_mru_cell can't be NULL)
				cell *lru_cell=f_mru_cell->s_prev;
				tmp.s_key=lru_cell->s_key;
				f_set.erase(&tmp);
				lru_cell->detach();
				//cell deleted !!! caller MUST be informed
				lru_cell->~cell();
 
				//create a new cell (actually reuse the just destroyed LRU cell)
				new_cell=new(lru_cell) cell(key);
			}
			else
			{
				//create a new cell
				new_cell=new cell(key);
			}
 
			//insert the new cell in list
			if (f_mru_cell!=(cell *)0)
				new_cell->attach_before(f_mru_cell);
 
			//set the new MRU cell
			f_mru_cell=new_cell;
 
			//insert also the new cell in the std::set
			f_set.insert(new_cell);
 
			//return the created T and notify that it wasn't yet in cache
			return cache_value<T>(new_cell->s_value,true);
		}
	}
 
	void display()
	{
		if (f_mru_cell)
		{
			//display cell key from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				std::cout << p->s_key << '"' << (p->s_value) << '"' << " - ";
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		std::cout << '(' << f_set.size() << ')' << std::endl;
	}
};

La méthode display() ne sert qu'à vérifier "l'âge" des clés. Voici un code de test:

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
void cachefetch(cache<unsigned,std::string> & c,unsigned key)
{
	char* HARD_DISK[] =
	{
		"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
	};
	cache_value<std::string> pair=c.fetch(key);
	if (pair.s_created)
		pair.s_value=HARD_DISK[key];
}
 
 
int main(int argc, char* argv[])
{
		cache<unsigned,std::string> c(5);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,2);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,3);
		c.display();
		cachefetch(c,4);
		c.display();
		cachefetch(c,1);
		c.display();
		cachefetch(c,5);
		c.display();
		cachefetch(c,8);
		c.display();
		c.reset(54);
		c.display();
return 0;
}

Le code utilise std::set<> de la STL uniquement, mais avec #define USE_UNORDERED_SET il utilise boost::unordered_set<>.

Vos avis ?
Merci.

screetch · 26/03/2009, 14h44

faire une allocation mémoire est assez lent, tu as essayé de voir le gain en performance lorsque le map original augmente ?
il me semble que ton cache ralentit plus qu'autre chose.

**3DArchi** · 27/03/2009, 10h43

Ta classe devrait être non copiable.
Si display ne te sert que pour les tests... sort là de ta classe.
Je trouve aussi que faire des allocations dynamiques au fur et à mesure que tu le remplis est plutôt étrange. J'aurais tout alloué d'un bloc au début.

**camboui** · 27/03/2009, 14h14

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
/* TODO: use my own allocator */
//copy contructor, assign operator ?

C'est comme si ne n'avais rien mis en commentaire...
Ceci dit, vous me direz comment imposer à std::set (ou à boost::unordered_set) de ne pas allouer ni désallouer de mémoire lors des insert et erase. Et puis, heureusement que je n'ai pas utilisé std::list pour gérer la p'tite liste de cellules.

Je m'attendais plutot à des commentaires sur le bon ou mauvais usage des template.

screetch · 27/03/2009, 16h43

ca ne me dit pas si tu as testé ton cache et si il est effectivement plus rapide.

**camboui** · 30/03/2009, 15h33

Plus "rapide" que quoi ?
Ta question sans un contexte d'utilisation est irrelevante (d'autant plus pour du code template).

Un cache sert à réduire les répétitions fréquentes de tâches lourdes. Dans ce genre de contexte je ne vois pas pourquoi ce ne serait pas "performant".

J'ai déjà écrit un cache d'accès fichiers avec succès. Pour info, il était intégré dans un plugin pour Acrobat Reader permettant de lire à distance et de manière sécurisée des fichiers PDF.

Mais c'était un cache dédié à cette tâche.
Là, j'en suis à généraliser le concept sous forme de template C++. Au moins à titre d'exercice.
Revoici le code, avec une allocation unique pour la gestion de 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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
template <typename T>
struct cache_value
{
	T & s_value;
	bool s_created;
 
	cache_value(T & value,bool created):s_value(value),s_created(created) {}
};
 
 
#ifdef USE_UNORDERED_SET
template <typename K, typename T, typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
#else
template <typename K, typename T, typename PrLess = std::less<K> >
#endif
class cache
{
	//The cache organize a MRU/LRU collection of cells in a bidirectional circular list.
	//The MRU cell is stored in f_mru_cell, the LRU cell is thus f_mru_cell->s_prev.
	//The cells are also stored in a std::set for a fast key search.
	struct cell
	{
		cell *s_prev,*s_next;
		K s_key;
		T s_value;
 
		cell(K key):s_key(key) {s_next=s_prev=this;}
 
		void attach_before(const cell *p)
		{
			p=p->s_prev;
			s_prev=(s_next=p->s_next)->s_prev;
			s_next->s_prev=s_prev->s_next=this;
		}
		void detach()
		{
			s_next->s_prev=s_prev;
			s_prev->s_next=s_next;
		}
	};
#ifdef USE_UNORDERED_SET
	struct cell_predhash
	{
		std::size_t operator()(const cell *p) const
			{ return PrHash()(p->s_key); }
	};
	struct cell_predequal
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrEqual()(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrLess()(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell *,cell_predless> cell_set;
#endif
 
	unsigned f_maxCell;
 
	cell *f_cell_pooler;
	cell *f_mru_cell;
	cell_set f_set;
 
	//don't allow copy or assign
	cache(cache const &);
	cache & operator=(cache const &);
public:
	cache(unsigned maxCell): f_maxCell(maxCell<1?1:maxCell),f_cell_pooler((cell *)0),f_mru_cell((cell *)0)
#ifdef USE_UNORDERED_SET
		,f_set(maxCell<1?1:maxCell)
#endif
		{ f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell)); }
	~cache()
	{
		clear();
		::operator delete(f_cell_pooler);
	}
 
	void clear()
	{
		if (f_mru_cell)
		{
			//delete cells from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				//cell deleted !!! caller MUST be informed
				p->~cell();
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		f_mru_cell=(cell *)0;
		f_set.clear();
	}
 
	void reset(unsigned maxCell)
	{
		clear();
		::operator delete(f_cell_pooler);
		f_cell_pooler=(cell *)0;
		f_maxCell=(maxCell<1?1:maxCell);
#ifdef USE_UNORDERED_SET
		f_set.rehash(f_maxCell);
#endif
		f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell));
	}
 
	cache_value<T> fetch(K key)
	{
		cell tmp(key);
		cell_set::iterator it=f_set.find(&tmp);
		if (it!=f_set.end())
		{
			//key is found
			//(f_mru_cell can't be NULL)
			cell *found_cell=*it;
			if (f_mru_cell!=found_cell)
			{
				//adjust cell list, found cell becomes MRU cell
				found_cell->detach();
				found_cell->attach_before(f_mru_cell);
				f_mru_cell=found_cell;
			}
 
			//return T and notify that key was already in cache
			return cache_value<T>(found_cell->s_value,false);
		}
		else
		{
			//key not found
			cell *new_cell;
 
			if (f_set.size()>=f_maxCell)
			{
				//cache size limit reached, remove LRU cell
				//(f_mru_cell can't be NULL)
				cell *lru_cell=f_mru_cell->s_prev;
				tmp.s_key=lru_cell->s_key;
				f_set.erase(&tmp);
				lru_cell->detach();
				//cell deleted !!! caller MUST be informed
				lru_cell->~cell();
 
				//create a new cell (actually reuse the just destroyed LRU cell)
				new_cell=new(lru_cell) cell(key);
			}
			else
			{
				//create a new cell (using a buffer from the pooler)
				new_cell=new(f_cell_pooler+f_set.size()) cell(key);
			}
 
			//insert the new cell in list
			if (f_mru_cell!=(cell *)0)
				new_cell->attach_before(f_mru_cell);
 
			//set the new MRU cell
			f_mru_cell=new_cell;
 
			//insert also the new cell in the std::set
			f_set.insert(new_cell);
 
			//return the created T and notify that it wasn't yet in cache
			return cache_value<T>(new_cell->s_value,true);
		}
	}
};

**Arzar** · 31/03/2009, 08h35

Envoyé par camboui

Je m'attendais plutot à des commentaires sur le bon ou mauvais usage des template.

Ben, je ne crois pas qu'il y ait grand chose à dire.

On est très loin du sac de nœud de la métaprog là. Tant que ça reste simple et clair comme ici, l'usage des template est assez direct en fait. Il y a quelque chose en particulier ?

Quelques commentaires sur le reste du code en vrac :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
cache_value
{
   T& value;
   bool created;
}

Le coup de renvoyer une référence sur un objet T du cache, c'est bien pour pouvoir le modifier immédiatement en sortit du fetch dans le cas ou il n'a pas été trouvé dans le cache c'est ça ? Mais après je suppose qu'il faut en faire une copie pour éviter les problèmes non ? Parce qu'il y a des commentaires troublant dans le code; des histoires pas très catholiques de callback avant destruction des cellules LRU.... "cell deleted !!! caller MUST be informed", pourquoi ça ?

Autre chose, un niveau design, si j'ai bien compris ce cache est surtout prévu pour stocker des objets assez léger, c'est ça ? En tout cas il est possible d'en faire une version adapté aux objets plus massif en remplaçant tous les T par des shared_ptr<T> dans cell et cache_value : j'ai essayé et ça marche impec. Y a même des fois ou ça va plus vite.

Et pour finir, très jolie l'utilisation de la liste intrusive pour stocker les cellules du cache. Élégant. J'ai tenté de pousser le bouchon encore plus loin en utilisant un set intrusif, mais ça n'a pas finalement pas donné changé grand chose de plus.

Mais bon c'était l'occasion pour s'amuser un peu avec boost::intrusive. Voilà le résultat + quelques benchs :

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
 
#include <time.h>
#include <windows.h>
struct Chrono
{
	LARGE_INTEGER liStart;
	LARGE_INTEGER liStop;
	void Start()
	{
		QueryPerformanceCounter(&liStart);
	}
	double Stop()
	{
	   QueryPerformanceCounter(&liStop);
	   LONGLONG llTimeDiff = liStop.QuadPart - liStart.QuadPart;
       // To get duration in milliseconds
	   LARGE_INTEGER Frequency;
	   QueryPerformanceFrequency(&Frequency);
       return llTimeDiff * 1000.0 / (double) Frequency.QuadPart;
	}
};
 
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <boost/functional/hash.hpp>
#include <boost/unordered_set.hpp>
 
#include <iostream>
#include <string>
#include <vector>
 
template <typename T>
struct cache_value
{
	T& value;
	bool created;
 
	cache_value<T>(T& value, bool created):value(value),created(created) {}
};
 
 
#define USE_UNORDERED_SET
 
#ifdef USE_UNORDERED_SET
template <typename K, typename T, typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
#else
template <typename K, typename T, typename PrLess = std::less<K> >
#endif
class cache
{
	//The cache organize a MRU/LRU collection of cells in a bidirectional circular list.
	//The MRU cell is stored in f_mru_cell, the LRU cell is thus f_mru_cell->s_prev.
	//The cells are also stored in a std::set for a fast key search.
	struct cell
	{
		cell *s_prev,*s_next;
		K s_key;
		T s_value;
 
		cell(K key):s_key(key) {s_next=s_prev=this;}
 
		void attach_before(const cell *p)
		{
			p=p->s_prev;
			s_prev=(s_next=p->s_next)->s_prev;
			s_next->s_prev=s_prev->s_next=this;
		}
		void detach()
		{
			s_next->s_prev=s_prev;
			s_prev->s_next=s_next;
		}
	};
#ifdef USE_UNORDERED_SET
	struct cell_predhash
	{
		std::size_t operator()(const cell *p) const
			{ return PrHash()(p->s_key); }
	};
	struct cell_predequal
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrEqual()(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		bool operator()(const cell *pl,const cell *pr) const
			{ return PrLess()(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell *,cell_predless> cell_set;
#endif
 
	unsigned f_maxCell;
 
	cell *f_cell_pooler;
	cell *f_mru_cell;
	cell_set f_set;
 
	//don't allow copy or assign
	cache(cache const &);
	cache & operator=(cache const &);
public:
	cache(unsigned maxCell): f_maxCell(maxCell<1?1:maxCell),f_cell_pooler((cell *)0),f_mru_cell((cell *)0)
#ifdef USE_UNORDERED_SET
		,f_set(maxCell<1?1:maxCell)
#endif
		{ f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell)); }
	~cache()
	{
		clear();
		::operator delete(f_cell_pooler);
	}
 
	void clear()
	{
		if (f_mru_cell)
		{
			//delete cells from LRU to MRU
			cell *lru_cell=f_mru_cell->s_prev;
			cell *p=lru_cell;
			do
			{
				cell *ptmp=p->s_prev;
				//cell deleted !!! caller MUST be informed
				p->~cell();
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		f_mru_cell=(cell *)0;
		f_set.clear();
	}
 
	void reset(unsigned maxCell)
	{
		clear();
		::operator delete(f_cell_pooler);
		f_cell_pooler=(cell *)0;
		f_maxCell=(maxCell<1?1:maxCell);
#ifdef USE_UNORDERED_SET
		f_set.rehash(f_maxCell);
#endif
		f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell));
	}
 
	cache_value<T> fetch(K key)
	{
		cell tmp(key);
		cell_set::iterator it=f_set.find(&tmp);
		if (it!=f_set.end())
		{
			//key is found
			//(f_mru_cell can't be NULL)
			cell *found_cell=*it;
			if (f_mru_cell!=found_cell)
			{
				//adjust cell list, found cell becomes MRU cell
				found_cell->detach();
				found_cell->attach_before(f_mru_cell);
				f_mru_cell=found_cell;
			}
 
			//return T and notify that key was already in cache
			return cache_value<T>(found_cell->s_value, false);
		}
		else
		{
			//key not found
			cell *new_cell;
 
			if (f_set.size()>=f_maxCell)
			{
				//cache size limit reached, remove LRU cell
				//(f_mru_cell can't be NULL)
				cell *lru_cell=f_mru_cell->s_prev;
				tmp.s_key=lru_cell->s_key;
				f_set.erase(&tmp);
				lru_cell->detach();
				//cell deleted !!! caller MUST be informed
				lru_cell->~cell();
 
				//create a new cell (actually reuse the just destroyed LRU cell)
				new_cell=new(lru_cell) cell(key);
			}
			else
			{
				//create a new cell (using a buffer from the pooler)
				new_cell=new(f_cell_pooler+f_set.size()) cell(key);
			}
 
			//insert the new cell in list
			if (f_mru_cell!=(cell *)0)
				new_cell->attach_before(f_mru_cell);
 
			//set the new MRU cell
			f_mru_cell=new_cell;
 
			//insert also the new cell in the std::set
			f_set.insert(new_cell);
 
			//return the created T and notify that it wasn't yet in cache
			return cache_value<T>(new_cell->s_value, true);
		}
	}
};
 
 
template <typename K, typename T , typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K>>
class cache2
{
private:
	//don't allow copy or assign
   cache2(const cache2&);
   cache2& operator=(const cache2&);
 
   struct Entry : public boost::intrusive::list_base_hook<>, boost::intrusive::unordered_set_base_hook<>
	{
		K key;
		T value;
 
		friend bool operator == (const Entry& e1, const Entry& e2)
		{ return PrEqual()(e1.key, e2.key);  }
 
		friend std::size_t hash_value(const Entry& e)
		{ return PrHash()(e.key);  }
   	};
 
   struct EntryKeyHash
	{
		std::size_t operator()(const K& key) const
		{ return PrHash()(key); }
	};
 
   struct EntryKeyEqual
	{
	   bool operator()(const K& key, const Entry& e) const
       { return PrEqual()(key, e.key); }
 
       bool operator()(const Entry& e, const K& key) const
       { return PrEqual()(e.key, key);  }
	};
 
   typedef boost::intrusive::list<Entry> EntryList;
   typedef boost::intrusive::unordered_set<Entry>  EntryHashSet;
   typedef typename EntryHashSet::bucket_type  BucketType;
   typedef typename EntryHashSet::bucket_traits  BucketTraits;
 
   std::vector<Entry> entryPool_;
   EntryList entryList_;
 
   // BE CAREFUL, the vector of bucket must be declared before the unordered set, 
   // in order to be initialized first in the constructor's initialization list
   std::vector<BucketType> buckets_; 
   EntryHashSet entryHashSet_;
 
   int maxsize_;
 
public:
	cache2(int maxsize): 
	maxsize_(maxsize<1?1:maxsize),
	buckets_(maxsize<1?1:maxsize),
	entryHashSet_(BucketTraits(&buckets_[0], maxsize<1?1:maxsize))
	{
		entryPool_.reserve(maxsize<1?1:maxsize);
	}
 
	void reset(int newMaxsize)
	{
       entryList_.clear();
	   entryHashSet_.clear();
	   entryPool_.clear();
	   maxsize_ = newMaxsize<1?1:newMaxsize;
	   buckets.resize(maxsize_);
	   entryHashSet_.rehash(maxsize_);
	}
 
 	cache_value<T> fetch(K key)
	{
		EntryHashSet::iterator found = entryHashSet_.find(key, EntryKeyHash(), EntryKeyEqual());
		if(found != entryHashSet_.end())
		{
			//key is found
			Entry& entry = *found;
			EntryList::iterator it = entryList_.iterator_to(entry);
 
			if(it != entryList_.begin())
			{
				//adjust entry list, found entry becomes MRU entry
				entryList_.erase(it);
				entryList_.push_front(entry);
			}
 
			//return T and notify that key was already in cache
			return cache_value<T>(entry.value, false);
		}
		else
		{
			Entry* entry;
			if(entryPool_.size() < (unsigned int)maxsize_)
			{
				//create a new entry
				Entry newEntry;
				newEntry.key = key; 
				entryPool_.push_back(newEntry);
 
				entry = &(entryPool_.back());
			}
			else
			{
				//cache size limit reached, destroy the lru entry
				entry = &(entryList_.back());
				entryHashSet_.erase(entryHashSet_.iterator_to(*entry));
				entryList_.erase(entryList_.iterator_to(*entry));
 
				//reuse the just destroyed LRU entry
				entry->key = key;
			}
			//insert the new entry in list
			entryList_.push_front(*entry);
 
			//insert also the new entry in the std::set
			entryHashSet_.insert(*entry);
 
			//return the created T and notify that it wasn't yet in cache
			return cache_value<T>(entry->value, true);
		}
	}
 
	void display()
	{
		//display cell key from LRU to MRU
		for(EntryList::const_reverse_iterator it = entryList_.crbegin() ; it != entryList_.crend() ;  ++it)
		{
    		std::cout << it->key << '"' << it->value << '"' << " - ";
		}
		std::cout << '(' << entrySet_.size() << ')' << std::endl;
	}
};
 
class HARD_DISK
{
public:
	HARD_DISK(){};
	HARD_DISK(int nbString, int lengthString):vec(nbString)
	{
	   std::string gabarit('a', lengthString);
       for(int i = 0 ; i < nbString ; i++)
		   vec[i] = gabarit;
	}
 
	void Resize(int nbString, int lengthString)
	{
		vec.resize(nbString);
		std::string gabarit('a', lengthString);
       for(int i = 0 ; i < nbString ; i++)
		   vec[i] = gabarit;
	}
	std::string Get(int num)
	{	
		return vec[num];
	}
private:
	std::vector<std::string> vec;
};
 
 
void cachefetch(HARD_DISK& hdd, cache<unsigned,std::string> & c,unsigned key)
{
	cache_value<std::string> cv = c.fetch(key);
	if (cv.created)
		cv.value = hdd.Get(key);
}
 
void cachefetch(HARD_DISK& hdd, cache2<unsigned,std::string> & c,unsigned key)
{
	cache_value<std::string> cv = c.fetch(key);
	if (cv.created)
		cv.value = hdd.Get(key);
}
 
void Test(HARD_DISK& hdd, int numIteration, int sizecache, int numString, int lengthString)
{
	srand(time(NULL));
	hdd.Resize(numString, lengthString);
	Chrono chrono;
	double time;
 
	std::cout << "Iteration "<< numIteration << " sizecache " << sizecache << " numString " << numString << " lengthString " << lengthString << std::endl;
 
	chrono.Start();
	{
		cache<unsigned,std::string> c(sizecache);
		for(int i = 0 ; i < numIteration ; i++)
		{
			cachefetch(hdd, c, rand() % numString);
		}
	}
	time = chrono.Stop();
	std::cout << time << std::endl;
 
	chrono.Start();
	{
		cache2<unsigned,std::string> c2(sizecache);
		for(int i = 0 ; i < numIteration ; i++)
		{
			cachefetch(hdd, c2, rand() % numString);
		}
	}
	time = chrono.Stop();
	std::cout << time << std::endl;
}
 
 
int main(int argc, char* argv[])
{
	HARD_DISK hdd;
 
	// numIteration, sizecache, numString, lengthString
	Test(hdd, 1000000, 1000, 100, 20);
	Test(hdd, 1000000, 10000, 10000, 20);
	Test(hdd, 1000000, 100000, 100000, 20);
	Test(hdd, 1000000, 1000, 10, 10000);
 
	std::cout << "\nlot of small object (100000 objects, 100 byte each), size of cache is small" << std::endl;
	Test(hdd, 1000000, 10000, 100000, 20);
 
	std::cout << "\nlot of small object (100000 objects, 100 byte each), size of cache is good" << std::endl;
	Test(hdd, 1000000, 100000, 100000, 20);
 
	std::cout << "\nfew but BIG object (100 objects, 100000 byte each)" << std::endl;
	Test(hdd, 1000000, 1000, 100, 100000);
 
	std::cout << "\nLOT of BIG object (100000 objects, 100000 byte each), size of cache is small" << std::endl;
	Test(hdd, 1000000, 10000, 100000, 100000);
 
	std::cout << "\nLOT of BIG object (100000 objects, 100000 byte each), size of cache is good" << std::endl;
	Test(hdd, 1000000, 100000, 100000, 100000);
 
return 0;
}

**camboui** · 31/03/2009, 10h38

Envoyé par Arzar

Ben, je ne crois pas qu'il y ait grand chose à dire.

On est très loin du sac de nœud de la métaprog là. Tant que ça reste simple et clair comme ici, l'usage des template est assez direct en fait. Il y a quelque chose en particulier ?

Ah ben voilà, mon égo est quelque peu regonfflé

Envoyé par Arzar

Quelques commentaires sur le reste du code en vrac :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
cache_value
{
   T& value;
   bool created;
}

Le coup de renvoyer une référence sur un objet T du cache, c'est bien pour pouvoir le modifier immédiatement en sortit du fetch dans le cas ou il n'a pas été trouvé dans le cache c'est ça ?

"Modifier", oui. Je dirais même "remplir" car la cellule est vide quand elle vient d'être crée par le cache.

Envoyé par Arzar

Mais après je suppose qu'il faut en faire une copie pour éviter les problèmes non ? Parce qu'il y a des commentaires troublant dans le code; des histoires pas très catholiques de callback avant destruction des cellules LRU.... "cell deleted !!! caller MUST be informed", pourquoi ça ?

Non, il n'y a pas de copie à faire, sauf éventuellement juste avant qu'une cellule ne soit détruite. Cela dépend de l'usage qui est fait du cache.
Imaginons un cache en écriture sur disque. Si une cellule devait être supprimée, il faut que l'utilisateur en soit averti à temps afin de transférer son contenu sur disque.
Dans le cas d'un cache en lecture ce n'est pas nécessaire.
Je pensais notifier l'utilisateur via un callback, d'où le commentaire.

Envoyé par Arzar

Autre chose, un niveau design, si j'ai bien compris ce cache est surtout prévu pour stocker des objets assez léger, c'est ça ?

Là tu soulignes un point qui m'embête un peu. Je le souhaite générique, mais la première ligne de code de fetch(), la variable tmp créée sur le stack, peut être "lourde" si T est "lourd" (cell tmp(key);).

Envoyé par Arzar

En tout cas il est possible d'en faire une version adapté aux objets plus massif en remplaçant tous les T par des shared_ptr<T> dans cell et cache_value : j'ai essayé et ça marche impec. Y a même des fois ou ça va plus vite.

En changeant le set par un map on peut aussi utiliser des objets plus lourds sans la contrainte de la variable locale tmp. J'ai fait cette adaptation hier PM.
Mais la nuit a porté conseil et je pense qu'il y a "mieux". J'y reviendrai.

Envoyé par Arzar

Et pour finir, très jolie l'utilisation de la liste intrusive pour stocker les cellules du cache. Élégant. J'ai tenté de pousser le bouchon encore plus loin en utilisant un set intrusif, mais ça n'a pas finalement pas donné changé grand chose de plus.

Mais bon c'était l'occasion pour s'amuser un peu avec boost::intrusive. Voilà le résultat + quelques benchs :

Joli

.
Je te remercie pour ton intervention et ton l'analyse poussée. L'adaptation avec les ficelles de boost m'épate aussi, chapeau. Mais c'est moins lisible je trouve, en tout cas pour moi qui n'en suis qu'à balbutier avec boost. Je ne suis pas sûr que j'aurais le courage ou même le capacité d'en percevoir toutes les possibilités.

Un cache template

Langage C++

Vue hybride

Discussions similaires

Partager

Partager