Discussion :

[camboui]

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]

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]

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]

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]

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

[camboui]

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]

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]

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é

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.

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.

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

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.

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.

[camboui]

Bon, voici le "mieux" dont je parlais tout à l'heure. Il s'agit tout simplement de faire un (tout petit) peu de polymorphisme afin d'éviter de créer inutilement une cellule complète sur le stack. Au fait, Arzar, c'était bien pour cela que tu disais que les objet devaient être "légers", ou pour une autre raison ?

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
#ifdef USE_UNORDERED
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_key
	{
		K s_key;
 
		cell_key(K key):s_key(key) {}
	};
 
	struct cell: cell_key
	{
		cell *s_prev,*s_next;
		T s_value;
 
		cell(K key):cell_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
	struct cell_predhash
	{
		std::size_t operator()(const cell_key *p) const
			{ return PrHash()(p->s_key); }
	};
	struct cell_predequal
	{
		bool operator()(const cell_key *pl,const cell_key *pr) const
			{ return PrEqual()(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell_key *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		bool operator()(const cell_key *pl,const cell_key *pr) const
			{ return PrLess()(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell_key *,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
		,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
		f_set.rehash(f_maxCell);
#endif
		f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell));
	}
 
	cache_value<T> fetch(K key)
	{
		cell_key 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=(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;
				f_set.erase(lru_cell);
				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);
		}
	}
};

Maintenant je souhaite comprendre le intrusive set, connaitre ses avantages, inconvénients, etc. Permet-il d'éviter les allocations internes à la gestion du set ?

[Arzar]

Au fait, Arzar, c'était bien pour cela que tu disais que les objet devaient être "légers", ou pour une autre raison ?

Non, désolé c'était une erreur de ma part en fait.
Après tout, si l'objet à manipuler dans le cache devient assez lourd il est tout à fait possible de faire :

Code :

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

1
2
typedef shared_ptr<Objet> ObjetPtr;
cache<int, ObjetPtr> cache;

Maintenant je souhaite comprendre le intrusive set, connaitre ses avantages, inconvénients, etc.

C'est assez simple en fait. (enfin, le concept, parce que l'implémentation )
L'idée c'est de rajouter les données nécessaires à la création de liste, set etc. directement dans nos classes, par le biais de "hook" fournis par boost::intrusive. Le hook implémente la machinerie nécessaire plus une interface similaire à celle de la STL.

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
 
//std::list classique : quelque part dans le code de la STL
// on trouve une classe node, plus ou moins comme ceci :
class Node
{
   Node* next;
   Node* prev;
   T value
} ;
 
// liste intrusive
// Cell est une de nos propre classe, dans notre code
class cell : public boost::intrusive::list_base_hook<>
{
// other data
}
 
// le hook permet de rajouter les données nécessaires de manière
// transparente. On obtient l'équivalent de :
class cell
{
   cell* prev;
   cell* next;
   // other data
}

Dans le cas du set intrusif, la doc indique que le hook ajoute trois pointeurs à notre classe. Je suppose qu'il y a un left, right et parent.

Permet-il d'éviter les allocations internes à la gestion du set ?

Oui, absolument, en fait un conteneur intrusif ne gère pas du tout les allocations mémoires qui sont laissés à l'utilisateur. (on ne passe d'ailleurs pas d'allocator au conteneur). Le conteneur intrusif se contente de manipuler les pointeurs fournis par le hook.

L'usage le plus intéressant (et mentionné tel quel par la doc) c'est d'avoir un std::vector qui se charge de la gestion de nos objets en les maintenant bien compact en mémoire, puis de construire par dessus des conteneurs intrusifs. Cela permet de résoudre le problème n° 1 des std::set classiques par exemple : le fait que les nœuds soient alloués un par un donc peuvent être assez dispersés en mémoire.

L'écriture est aussi un peu plus simple, car on obtient l'équivalent naturel d'un vector<T> + std::conteneur<T*>.sans se cogner des tas de foncteur à écrire.

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
 
class cell : public boost::intrusive::list_base_hook <>
{
// other data
};
 
std::vector<Cell> v;
typedef boost::intrusive::list<Cell> CellList;
CellList l;
 
v.push_back(Cell());
Cell& cell = v.back();
 
l.push_back(cell); // pas de copie !
l.clear(); // le destructeur de Cell n'est pas appelé
l.push_back(cell); // pas de copie !
 
// récupère l'itérateur à partir de la référence en O(1).
CellList::iterator it = l.iterator_to(cell) 
 
// le destructeur de Cell est appelé. 
// La prochaine fois qu'on essayera d'accéder au vecteur... BOUM . 
// Il faut donc faire très attention à ce que l'on fait.
l.erase_and_dispose(it);

Avantage :
* Améliore la localité des données. (ceci dit pour le cache, ça n'a pas changé grand chose, c'est assez décevant)
* Utilisation naturelle de l'équivalent sémantique à un std::conteneur<T*>
* Permet de convertir une référence en itérateur en O(1)
* L'auteur de la librairie en a profité pour rajouter quelques fonctions assez utiles, par exemple pour les set un find(Key K, CompareKey)

Inconvénient :
* Les conteneurs intrusifs sont... intrusifs ! Il faut modifier sa classe de base en rajoutant un hook propre à chaque nouveau conteneur.
* La gestion de la mémoire n'est plus automatique -> il faut faire attention.
* Pour les boost::intrusive::unordered_set uniquement : Les buckets pour la table de hashage doivent être gérés par l'utilisateur, ce qui alourdit un peu le code.

Ah oui, et j'ajoute que je me suis intéressé à boost:intrusive que depuis quelques jours. Il y a peut être des difficultés que je n'ai pas vu.

[camboui]

Permettez-moi de revenir sur ce cache, il est "terminé"

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
template<typename T>
struct param_call
{
private:
	template <bool B>
	struct selector
	{
		typedef T const & type;
	};
 
	template <>
	struct selector<false>
	{
		typedef T type;
	};
public:
	typedef typename selector< (sizeof(T) > sizeof(void *)) >::type type;
};
 
 
template <typename T>
struct cache_value
{
	T & s_value;
	bool s_created;
 
	cache_value(T & value,bool created):s_value(value),s_created(created) {}
};
 
 
 
template <typename T>
struct cache_dummy_callback: std::unary_function<T, void>
{
	void operator()(T &) const
		{}
};
 
 
 
#ifdef USE_UNORDERED
template <typename K, typename T, typename CB = cache_dummy_callback<T>,
	typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
#else
template <typename K, typename T, typename CB = cache_dummy_callback<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.
public:
	typedef typename param_call<K>::type param_key_type;
	typedef size_t size_type;
	typedef CB callback_type;
 
private:
	struct cell_key
	{
		K s_key;
 
		cell_key(param_key_type key):s_key(key) {}
	};
 
	struct cell: cell_key
	{
		cell *s_prev,*s_next;
		T s_value;
 
		cell(param_key_type key):cell_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
	struct cell_predhash
	{
		PrHash f_hash;
		cell_predhash(PrHash const & hash):f_hash(hash) {}
		std::size_t operator()(const cell_key *p) const
			{ return f_hash(p->s_key); }
	};
	struct cell_predequal
	{
		PrEqual f_equal;
		cell_predequal(PrEqual const & equal):f_equal(equal) {}
		bool operator()(const cell_key *pl,const cell_key *pr) const
			{ return f_equal(pl->s_key,pr->s_key); }
	};
	typedef boost::unordered_set<cell_key *,cell_predhash,cell_predequal> cell_set;
#else
	struct cell_predless
	{
		PrLess f_pred;
		cell_predless(PrLess const & pred):f_pred(pred) {}
		bool operator()(const cell_key *pl,const cell_key *pr) const
			{ return f_pred(pl->s_key,pr->s_key); }
	};
	typedef std::set<cell_key *,cell_predless> cell_set;
#endif
 
	size_type f_maxCell;
 
	cell *f_cell_pooler;
	cell *f_mru_cell;
	cell_set f_set;
	callback_type f_callback;
 
	//don't allow copy or assign
	cache(cache const &);
	cache & operator=(cache const &);
public:
	explicit cache(size_type maxCell, CB const & callback = CB(),
#ifdef USE_UNORDERED
			PrHash const & hash=PrHash(), PrEqual const & equal=PrEqual()):
		f_maxCell(maxCell<1?1:maxCell),f_cell_pooler((cell *)0),f_mru_cell((cell *)0),
		f_set(maxCell<1?1:maxCell,cell_predhash(hash),cell_predequal(equal)),
#else
			PrLess const & pred=PrLess()):
		f_maxCell(maxCell<1?1:maxCell),f_cell_pooler((cell *)0),f_mru_cell((cell *)0),
		f_set(cell_predless(pred)),
#endif
		f_callback(callback)
		{ f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell)); }
	~cache()
	{
		clear();
		::operator delete(f_cell_pooler);
	}
 
	size_type use_cell()
		{ return f_set.size(); }
	size_type max_cell()
		{ return f_maxCell; }
 
	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 to be deleted, trigger the callback functor
				f_callback(p->s_value);
				p->~cell();
				p=ptmp;
			}
			while (p!=lru_cell);
		}
		f_mru_cell=(cell *)0;
		f_set.clear();
	}
 
	void reset(size_type maxCell)
	{
		clear();
		::operator delete(f_cell_pooler);
		f_cell_pooler=(cell *)0;
		f_maxCell=(maxCell<1?1:maxCell);
#ifdef USE_UNORDERED
		f_set.rehash(f_maxCell);
#endif
		f_cell_pooler=(cell *)::operator new(f_maxCell*sizeof(cell));
	}
 
	cache_value<T> fetch(param_key_type key)
	{
		cell_key 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=(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;
				f_set.erase(lru_cell);
				lru_cell->detach();
				//cell to be deleted, trigger the callback functor
				f_callback(lru_cell->s_value);
				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);
		}
	}
 
};

Deux versions, une avec std::set<> et l'autre avec boost::unordered_set<>. On peut spécifier les predicats/foncteurs souhaités pour les set<>. On peut aussi préciser un foncteur "callback" qui sera appelé juste avant la destruction d'une cellule (ou page) du cache. Cela permet à l'appelant de faire un flush ou autre si besoin est.

Dans le cache il y a deux conteneurs: une liste (auto-intrusive à la "bonne vieille méthode" C) et un conteneur à recherche rapide (un set<>). Ce conteneur contient des pointeurs vers les éléments de la liste (et non pas une copie de ceux-ci). Il n'y a aucune allocation de mémoire en cours d'utilisation du cache sauf... dans la popotte interne des set<>.
Il n'y a qu'un seul moyen d'empêcher cela: écrire un allocator que l'on passe en paramètre du set<> en lieu et place du std:allocator<> (c'est le dernier paramètre par défaut). J'ai déjà demandé sur le forum si quelqu'un s'était lancé dans ce genre de tâche sans succès... (je crois qu'il y a ça dans loki, un SmallObjectAllocator qui devrait bien convenir)

Je pourrais m'en tenir là, mais arzar m'a fait découvrir les intrusives

Ainsi, au lieu d'écrire un allocator<> (qui serait un memory pooler personalisé) on pourrait écrire un set<> personnalisé qui n'alloue pas de mémoire. Et c'est à peu près ce que propose boost::intrusive. Merci arzar

Mais je n'ai pas repris le code de arzar pour deux raisons.
D'abord je ne comprend pas où sont spécifiés les prédicats/foncteurs utilisés par unordered_set<> ? (rien dans le constructeur). Il y a bien des paramètres pour find() mais aucun pour erase() ni insert().
Et ensuite le set<> contient des instances de cellules/pages "complètes" et non pas un pointeur vers celles se trouvant déjà dans la liste: l'info est dédoublée. Ceci explique d'ailleurs peut-être pourquoi arzar avait constaté des performances décevantes de intrusive_set par rapport à set.
J'en suis donc à faire des essais avec intrusive_unordered_set<cell *> mais ce n'est pas trivial car "cell *" doit dériver d'un boost::hook_truc_machin, ce qui est impossible sans enrober "cell *" dans une classe.

[camboui]

Suite à ma compréhension incomplète des intrusives, le post précédant peut être entièrement barré avec la balise "strike" ... lorsqu'elle sera supportée par le forum

Revoici donc ma copie revue et corrigée, en partant du code de arzar

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
template<typename T>
struct param_call
{
private:
	template <bool B>
	struct selector
	{
		typedef T const & type;
	};
 
	template <>
	struct selector<false>
	{
		typedef T type;
	};
public:
	typedef typename selector< (sizeof(T) > sizeof(void *))
#if !defined(IS_MSVC_6)
		|| (__is_class(T)==true && __is_pod(T)==false)
#endif
		>::type type;
};
 
template <typename K, typename T>
struct cache_callback_traits: std::binary_function<typename param_call<K>::type, T &, void>
{
};
 
template <typename K, typename T>
struct cache_dummy_callback: cache_callback_traits<K, T>
{
	result_type operator()(first_argument_type, second_argument_type) const
		{}
};
 
template <typename K, typename T, typename CB = cache_dummy_callback<K, T>,
	typename PrHash = boost::hash<K>, typename PrEqual = std::equal_to<K> >
class cache2: private CB
{
public:
	typedef K key_type;
	typedef T value_type;
	typedef typename param_call<K>::type param_key_type;
	typedef size_t size_type;
	typedef CB callback_type;
 
private:
	struct Entry:
		boost::intrusive::list_base_hook<>,
		boost::intrusive::unordered_set_base_hook<>
	{
		K key_;
		boost::optional<T> value_;
		Entry(param_key_type key): key_(key) {}
	};
 
	struct EntryKeyHash: private PrHash
	{
		EntryKeyHash(PrHash const & hash): PrHash(hash) {}
		std::size_t operator()(const Entry & e) const
			{ return PrHash::operator()(e.key_); }
		std::size_t operator()(const K & key) const
			{ return PrHash::operator()(key); }
	};
 
	struct EntryKeyEqual: private PrEqual
	{
		EntryKeyEqual(PrEqual const & equal): PrEqual(equal) {}
		bool operator()(const Entry & el, const Entry & er) const
			{ return PrEqual::operator()(el.key_, er.key_); }
		bool operator()(const K & key, const Entry & e) const
			{ return PrEqual::operator()(key, e.key_); }
	};
 
	typedef boost::intrusive::list<Entry> EntryList;
	typedef boost::intrusive::unordered_set<Entry,
		boost::intrusive::hash<EntryKeyHash>,
		boost::intrusive::equal<EntryKeyEqual> > EntryHashSet;
	typedef typename EntryHashSet::bucket_type BucketType;
	typedef typename EntryHashSet::bucket_traits BucketTraits;
 
	size_type maxsize_;
 
	Entry *entry_pooler_;
 
	EntryList entry_list_;
	// 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 entry_hashset_;
 
	//don't allow copy nor assign
	cache2(cache2 const &);
	cache2 & operator=(cache2 const &);
public:
	explicit cache2(size_type maxsize, CB const & callback = CB(),
			PrHash const & hash=PrHash(), PrEqual const & equal=PrEqual()):
		callback_type(callback),
		maxsize_(maxsize<1?1:maxsize), entry_pooler_((Entry *)0),
		entry_list_(),
		buckets_(EntryHashSet::suggested_lower_bucket_count(maxsize_)),
		entry_hashset_(BucketTraits(&buckets_[0], buckets_.size()), EntryKeyHash(hash), EntryKeyEqual(equal))
		{ entry_pooler_=(Entry *)::operator new(maxsize_*sizeof(Entry)); }
	~cache2()
	{
		clear();
		::operator delete(entry_pooler_);
	}
 
	size_type use_cell()
		{ return entry_hashset_.size(); }
	size_type max_cell()
		{ return maxsize_; }
 
	void clear()
	{
		size_type count=entry_hashset_.size();
		entry_hashset_.clear();
		entry_list_.clear();
		//delete entries from LRU to MRU
		for (Entry *entry=(entry_pooler_+count-1); !(entry<entry_pooler_); --entry)
		{
			//entry to be deleted, trigger the callback functor
			(*this)(entry->key_, *entry->value_);
			entry->~Entry();
		}
	}
	void reset(size_type newMaxsize)
	{
		clear();
		::operator delete(entry_pooler_);
		entry_pooler_=(Entry *)0;
		maxsize_=(newMaxsize<1?1:newMaxsize);
		//From boost doc:
		// The bucket array must be destroyed after the container using it is destroyed,
		// otherwise, the result is undefined.
		BucketType dummy_bucket;
		entry_hashset_.rehash(BucketTraits(&dummy_bucket, 1));
		buckets_.resize(EntryHashSet::suggested_lower_bucket_count(maxsize_));
		entry_hashset_.rehash(BucketTraits(&buckets_[0], buckets_.size()));
 
		entry_pooler_=(Entry *)::operator new(maxsize_*sizeof(Entry));
	}
 
	boost::optional<T> & fetch(param_key_type key)
	{
		EntryHashSet::iterator found=entry_hashset_.find(key, entry_hashset_.hash_function(), entry_hashset_.key_eq());
		if (found!=entry_hashset_.end())
		{
			//key is found
			Entry & entry = *found;
			EntryList::iterator it=entry_list_.iterator_to(entry);
 
			if (it!=entry_list_.begin())
			{
				//adjust entry list, found entry becomes MRU entry
				entry_list_.erase(it);
				entry_list_.push_front(entry);
			}
 
			//return boost::optional<T>: it is initialized !
			return entry.value_;
		}
		else
		{
			Entry *entryp;
 
			if (entry_hashset_.size()<maxsize_)
			{
				//create a new entry (using a buffer from the pooler)
				entryp=new(entry_pooler_+entry_hashset_.size()) Entry(key);
			}
			else
			{
				//cache size limit reached, remove LRU cell
				entryp=&(entry_list_.back());
				entry_hashset_.erase(entry_hashset_.iterator_to(*entryp));
				entry_list_.erase(entry_list_.iterator_to(*entryp));
				//entry to be deleted, trigger the callback functor
				(*this)(entryp->key_, *entryp->value_);
				entryp->~Entry();
 
				//reuse the just destroyed LRU entry
				new(entryp) Entry(key);
			}
 
			//insert the new entry in list
			entry_list_.push_front(*entryp);
 
			//insert also the new entry in the std::set
			entry_hashset_.insert(*entryp);
 
			//return boost::optional<T>: it is uninitialized !
			return entryp->value_;
		}
	}
 
	void display()
	{
		//display cell key from LRU to MRU
		for (EntryList::const_reverse_iterator it=entry_list_.crbegin(); it!=entry_list_.crend(); ++it)
		{
			std::cout << it->key_ << '"' << (*it->value_) << '"' << " - ";
		}
		std::cout << '(' << entry_hashset_.size() << ')' << std::endl;
	}
};

Evolution remarquable, la valeur retour de fetch() est désormais une référence sur boost::optional<T>. Il n'y a ainsi plus aucune contrainte sur T qui ne subit aucune copie, il faut juste l'initializer avec un boost::in_place_factory au retour de fetch(), si nécessaire.
Il n'y a d'ailleurs aucune copie d'objet ni d'allocation de mémoire lors des appels de fetch().

L'exercice était intéressant avec un usage combiné de foncteurs (à presque s'en arracher les cheveux ), intrusive, optional, in_place, et la particularité de intrusive::unordered_set permettant de faire un find() sur une valeur tierce et des foncteurs associés.

Note: boost::unordered_set::suggested_lower_bucket_count() est buggé ! (version 1.41)

Voilà, merci de votre attention