Download

Reference Manual

Navigation

← Previous Changeset
Next Changeset →

Changeset 5416

Timestamp:

03/21/10 14:15:40 (2 years ago)

Author:

kris

Message:

made the default allocator faster, and hid the implementation from the containers. Use the new cache() method instead for configuring how containers pre-allocate.

Files:

trunk/tango/util/container/CircularList.d (modified) (3 diffs)
trunk/tango/util/container/Container.d (modified) (16 diffs)
trunk/tango/util/container/HashMap.d (modified) (8 diffs)
trunk/tango/util/container/HashSet.d (modified) (5 diffs)
trunk/tango/util/container/LinkedList.d (modified) (3 diffs)
trunk/tango/util/container/SortedMap.d (modified) (3 diffs)

Legend:

: Unmodified
: Added
: Removed
: Modified
: Copied
: Moved

trunk/tango/util/container/CircularList.d

r5131	r5416
131	131	/***********************************************************************
132	132
133		~~Return the configured allocator~~
134
135		***********************************************************************/
136
137		~~final Alloc allocator ()~~
138		{
139		~~return heap;~~
140		}
141
142		/***********************************************************************
143
144	133	Return a generic iterator for contained elements
145	134
…	…
157	146	i.index = 0;
158	147	return i;
	148	}
	149
	150	/***********************************************************************
	151
	152	Configure the assigned allocator with the size of each
	153	allocation block (number of nodes allocated at one time)
	154	and the number of nodes to pre-populate the cache with.
	155
	156	Time complexity: O(n)
	157
	158	***********************************************************************/
	159
	160	final CircularList cache (size_t chunk, size_t count=0)
	161	{
	162	heap.config (chunk, count);
	163	return this;
159	164	}
160	165
…	…
1187	1192	// use a chunk allocator, and presize the bucket[]
1188	1193	auto test = new CircularList!(uint, Container.reap, Container.Chunk);
1189		test.~~allocator.config (1000, 1~~000);
	1194	test.cache (1000, 1_000_000);
1190	1195	const count = 1_000_000;
1191	1196	StopWatch w;

trunk/tango/util/container/Container.d

r5064	r5416
72	72	static size_t hash(K) (K k, size_t length)
73	73	{
74		static if (is(K : int) ~~\|\| is(K : uint)~~ \|\|
75		is(K : long) ~~\|\| is(K : ulong)~~ \|\|
	74	static if (is(K : int) \|\| is(K : uint) \|\|
	75	is(K : long) \|\| is(K : ulong) \|\|
76	76	is(K : short) \|\| is(K : ushort) \|\|
77		is(K : byte) ~~\|\| is(K : ubyte)~~ \|\|
78		is(K : char) ~~\|\| is(K : wchar)~~ \|\| is (K : dchar))
	77	is(K : byte) \|\| is(K : ubyte) \|\|
	78	is(K : char) \|\| is(K : wchar) \|\| is (K : dchar))
79	79	return cast(size_t) (k % length);
80	80	else
…	…
82	82	}
83	83
84		/***********************************************************************
85
86		generic GC allocation manager
87
88		***********************************************************************/
89
90		struct Collect(T)
	84
	85	/***********************************************************************
	86
	87	GC Chunk allocator
	88
	89	Can save approximately 30% memory for small elements (tested
	90	with integer elements and a chunk size of 1000), and is at
	91	least twice as fast at adding elements when compared to the
	92	generic allocator (approximately 50x faster with LinkedList)
	93
	94	Operates safely with GC managed entities
	95
	96	***********************************************************************/
	97
	98	struct ChunkGC(T)
91	99	{
92		/***************************************************************
93
94		allocate a T sized memory chunk
95
96		***************************************************************/
97
	100	static assert (T.sizeof >= (T).sizeof, "The ChunkGC allocator can only be used for data sizes of at least " ~ ((T).sizeof).stringof[0..$-1] ~ " bytes!");
	101
	102	private struct Cache {Cache* next;}
	103
	104	private Cache* cache;
	105	private T[][] lists;
	106	private size_t chunks = 256;
	107
	108	/***************************************************************
	109
	110	allocate a T-sized memory chunk
	111
	112	***************************************************************/
	113
98	114	T* allocate ()
99		{
100		return cast(T*) GC.calloc (T.sizeof);
101		}
102
103		/***************************************************************
104
105		allocate an array of T sized memory chunks
	115	{
	116	if (cache is null)
	117	newlist;
	118	auto p = cache;
	119	cache = p.next;
	120	return cast(T*) p;
	121	}
	122
	123	/***************************************************************
	124
	125	allocate an array of T* sized memory chunks
106	126
107	127	***************************************************************/
…	…
109	129	T*[] allocate (size_t count)
110	130	{
111		return new T*[count];
112		}
113
114		/***************************************************************
115
116		Invoked when a specific T[] is discarded
117
118		***************************************************************/
119
120		void collect (T* p)
121		{
122		if (p)
123		delete p;
124		}
125
126		/***************************************************************
127
128		Invoked when a specific T[] is discarded
	131	auto p = (cast(T*) calloc(count, (T).sizeof)) [0 .. count];
	132	GC.addRoot (cast(void*) p);
	133	return p;
	134	}
	135
	136	/***************************************************************
	137
	138	Invoked when a specific T*[] is discarded
129	139
130	140	***************************************************************/
…	…
132	142	void collect (T*[] t)
133	143	{
134		if (t)
135		delete t;
136		}
137
	144	assert (t.ptr);
	145	GC.removeRoot (t.ptr);
	146	free (t.ptr);
	147	}
	148
	149	/***************************************************************
	150
	151	Invoked when a specific T is discarded
	152
	153	***************************************************************/
	154
	155	void collect (T* p)
	156	{
	157	assert (p);
	158	auto d = cast(Cache*) p;
	159	d.next = cache;
	160	cache = d;
	161	}
	162
138	163	/***************************************************************
139	164
…	…
144	169	False return will cause a series of discrete collect
145	170	calls
146
	171
147	172	***************************************************************/
148	173
149	174	bool collect (bool all = true)
150	175	{
	176	if (all)
	177	{
	178	foreach (ref list; lists)
	179	{
	180	GC.removeRoot (list.ptr);
	181	free (list.ptr);
	182	list = null;
	183	}
	184	cache = null;
	185	lists = null;
	186	return true;
	187	}
151	188	return false;
152	189	}
	190
	191	/***************************************************************
	192
	193	set the chunk size and prepopulate with nodes
	194
	195	***************************************************************/
	196
	197	void config (size_t chunks, int allocate=0)
	198	{
	199	this.chunks = chunks;
	200	if (allocate)
	201	for (int i=allocate/chunks+1; i--;)
	202	newlist;
	203	}
	204
	205	/***************************************************************
	206
	207	list manager
	208
	209	***************************************************************/
	210
	211	private void newlist ()
	212	{
	213	lists.length = lists.length + 1;
	214	auto p = (cast(T*) calloc (chunks, T.sizeof)) [0 .. chunks];
	215	lists[$-1] = p;
	216	GC.addRoot (p.ptr);
	217	auto head = cache;
	218	foreach (ref node; p)
	219	{
	220	auto d = cast(Cache*) &node;
	221	d.next = head;
	222	head = d;
	223	}
	224	cache = head;
	225	}
153	226	}
154
155
156		/***********************************************************************
157
158		Malloc allocation manager.
159
	227
	228
	229	/***********************************************************************
	230
	231	Chunk allocator (non GC)
	232
	233	Can save approximately 30% memory for small elements (tested
	234	with integer elements and a chunk size of 1000), and is at
	235	least twice as fast at adding elements when compared to the
	236	default allocator (approximately 50x faster with LinkedList)
	237
160	238	Note that, due to GC behaviour, you should not configure
161	239	a custom allocator for containers holding anything managed
…	…
171	249	you use a MallocAllocator to manage key/value pairs which
172	250	are themselves allocated via malloc, then you should also
173		provide a reaper delegate to collect those as required.
174
175		***********************************************************************/
176
177		struct Malloc(T)
	251	provide a reaper delegate to collect those as required.
	252
	253	The primary benefit of this allocator is to avoid the GC
	254	scanning the date-structures involved. Use ChunkGC where
	255	that option is unwarranted, or if you have GC-managed data
	256	instead
	257
	258	***********************************************************************/
	259
	260	struct Chunk(T)
178	261	{
179		/***************************************************************
180
181		allocate an array of T sized memory chunks
182
183		***************************************************************/
184
	262	static assert (T.sizeof >= (T).sizeof, "The Chunk allocator can only be used for data sizes of at least " ~ ((T).sizeof).stringof[0..$-1] ~ " bytes!");
	263
	264	private struct Cache {Cache* next;}
	265
	266	private Cache* cache;
	267	private T[][] lists;
	268	private size_t chunks = 256;
	269
	270	/***************************************************************
	271
	272	allocate a T-sized memory chunk
	273
	274	***************************************************************/
	275
185	276	T* allocate ()
186	277	{
187		return cast(T*) calloc (1, T.sizeof);
188		}
189
190		/***************************************************************
191
192		allocate an array of T sized memory chunks
	278	if (cache is null)
	279	newlist;
	280	auto p = cache;
	281	cache = p.next;
	282	return cast(T*) p;
	283	}
	284
	285	/***************************************************************
	286
	287	allocate an array of T* sized memory chunks
193	288
194	289	***************************************************************/
…	…
201	296	/***************************************************************
202	297
203		Invoked when a specific T[] is discarded
	298	Invoked when a specific T*[] is discarded
204	299
205	300	***************************************************************/
…	…
207	302	void collect (T*[] t)
208	303	{
209		~~if (t.length)~~
210		free (t.ptr);
211		}
212
213		/***************************************************************
214
215		Invoked when a specific T[] is discarded
	304	assert (t.ptr);
	305	free (t.ptr);
	306	}
	307
	308	/***************************************************************
	309
	310	Invoked when a specific T is discarded
216	311
217	312	***************************************************************/
218	313
219	314	void collect (T* p)
220		{
221		if (p)
222		free (p);
	315	{
	316	assert (p);
	317	auto d = cast(Cache*) p;
	318	d.next = cache;
	319	cache = d;
223	320	}
224	321
…	…
236	333	bool collect (bool all = true)
237	334	{
	335	if (all)
	336	{
	337	foreach (ref list; lists)
	338	{
	339	free (list.ptr);
	340	list = null;
	341	}
	342	cache = null;
	343	lists = null;
	344	return true;
	345	}
238	346	return false;
239	347	}
	348
	349	/***************************************************************
	350
	351	set the chunk size and prepopulate with nodes
	352
	353	***************************************************************/
	354
	355	void config (size_t chunks, int allocate=0)
	356	{
	357	this.chunks = chunks;
	358	if (allocate)
	359	for (int i=allocate/chunks+1; i--;)
	360	newlist;
	361	}
	362
	363	/***************************************************************
	364
	365	list manager
	366
	367	***************************************************************/
	368
	369	private void newlist ()
	370	{
	371	lists.length = lists.length + 1;
	372	auto p = (cast(T*) calloc (chunks, T.sizeof)) [0 .. chunks];
	373	lists[$-1] = p;
	374	auto head = cache;
	375	foreach (ref node; p)
	376	{
	377	auto d = cast(Cache*) &node;
	378	d.next = head;
	379	head = d;
	380	}
	381	cache = head;
	382	}
240	383	}
241
242
243		/***********************************************************************
244
245		Chunk allocator
246
247		Can save approximately 30% memory for small elements (tested
248		with integer elements and a chunk size of 1000), and is at
249		least twice as fast at adding elements when compared to the
250		default allocator (approximately 50x faster with LinkedList)
251
	384
	385
	386	/***********************************************************************
	387
	388	generic GC allocation manager
	389
	390	Slow and expensive in memory costs
	391
	392	***********************************************************************/
	393
	394	struct Collect(T)
	395	{
	396	/***************************************************************
	397
	398	allocate a T sized memory chunk
	399
	400	***************************************************************/
	401
	402	T* allocate ()
	403	{
	404	return cast(T*) GC.calloc (T.sizeof);
	405	}
	406
	407	/***************************************************************
	408
	409	allocate an array of T sized memory chunks
	410
	411	***************************************************************/
	412
	413	T*[] allocate (size_t count)
	414	{
	415	return new T*[count];
	416	}
	417
	418	/***************************************************************
	419
	420	Invoked when a specific T[] is discarded
	421
	422	***************************************************************/
	423
	424	void collect (T* p)
	425	{
	426	if (p)
	427	delete p;
	428	}
	429
	430	/***************************************************************
	431
	432	Invoked when a specific T[] is discarded
	433
	434	***************************************************************/
	435
	436	void collect (T*[] t)
	437	{
	438	if (t)
	439	delete t;
	440	}
	441
	442	/***************************************************************
	443
	444	Invoked when clear/reset is called on the host.
	445	This is a shortcut to clear everything allocated.
	446
	447	Should return true if supported, or false otherwise.
	448	False return will cause a series of discrete collect
	449	calls
	450
	451	***************************************************************/
	452
	453	bool collect (bool all = true)
	454	{
	455	return false;
	456	}
	457
	458	/***************************************************************
	459
	460	set the chunk size and prepopulate with nodes
	461
	462	***************************************************************/
	463
	464	void config (size_t chunks, int allocate=0)
	465	{
	466	}
	467	}
	468
	469
	470	/***********************************************************************
	471
	472	Malloc allocation manager.
	473
252	474	Note that, due to GC behaviour, you should not configure
253	475	a custom allocator for containers holding anything managed
…	…
263	485	you use a MallocAllocator to manage key/value pairs which
264	486	are themselves allocated via malloc, then you should also
265		provide a reaper delegate to collect those as required.
266
267		***********************************************************************/
268
269		struct ~~Chunk~~(T)
	487	provide a reaper delegate to collect those as required.
	488
	489	***********************************************************************/
	490
	491	struct Malloc(T)
270	492	{
271		~~static assert (T.sizeof >= (T).sizeof, "The Chunk allocator can only be used for data sizes of at least " ~ ((T).sizeof).stringof[0..$-1] ~ " bytes!");~~
272
273		~~private T[] list;~~
274		~~private T[][] lists;~~
275		~~private size_t index;~~
276		~~private size_t freelists;~~
277		~~private size_t presize = 0;~~
278		~~private size_t chunks = 1000;~~
279
280		~~private struct Discarded~~
281		{
282		~~Discarded* next;~~
283		}
284		~~private Discarded* discarded;~~
285
286		/***************************************************************
287
288		~~set the chunk size and preallocate lists~~
289
290		***************************************************************/
291
292		~~void config (size_t chunks, size_t presize)~~
293		{
294		~~this.chunks = chunks;~~
295		~~this.presize = presize;~~
296		~~lists.length = presize;~~
297
298		~~foreach (ref list; lists)~~
299		~~list = block;~~
300		}
301
302	493	/***************************************************************
303	494
…	…
305	496
306	497	***************************************************************/
307
	498
308	499	T* allocate ()
309	500	{
310		if (index >= list.length)
311		if (discarded)
312		{
313		auto p = discarded;
314		discarded = p.next;
315		return cast(T*) p;
316		}
317		else
318		newlist;
319
320		return (&list[index++]);
	501	return cast(T*) calloc (1, T.sizeof);
321	502	}
322	503
…	…
346	527	/***************************************************************
347	528
348		Invoked when a specific T is discarded
	529	Invoked when a specific T[] is discarded
349	530
350	531	***************************************************************/
351	532
352	533	void collect (T* p)
353		{
	534	{
354	535	if (p)
355		{
356		assert (T.sizeof >= (T*).sizeof);
357		auto d = cast(Discarded*) p;
358		d.next = discarded;
359		discarded = d;
360		}
	536	free (p);
361	537	}
362	538
…	…
374	550	bool collect (bool all = true)
375	551	{
376		freelists = 0;
377		newlist;
378		if (all)
379		{
380		foreach (list; lists)
381		free (list.ptr);
382		lists.length = 0;
383		}
384		return true;
385		}
386
387		/***************************************************************
388
389		list manager
390
391		***************************************************************/
392
393		private void newlist ()
394		{
395		index = 0;
396		if (freelists >= lists.length)
397		{
398		lists.length = lists.length + 1;
399		lists[$-1] = block;
400		}
401		list = lists[freelists++];
402		}
403
404		/***************************************************************
405
406		list allocator
407
408		***************************************************************/
409
410		private T[] block ()
411		{
412		return (cast(T*) calloc (chunks, T.sizeof)) [0 .. chunks];
	552	return false;
	553	}
	554
	555	/***************************************************************
	556
	557	set the chunk size and prepopulate with nodes
	558
	559	***************************************************************/
	560
	561	void config (size_t chunks, int allocate=0)
	562	{
413	563	}
414	564	}
415
	565
	566
	567	version (prior_allocator)
	568	{
416	569	/***********************************************************************
417	570
…	…
425	578
426	579	***********************************************************************/
	580
427	581	struct GCChunk(T, uint chunkSize)
428	582	{
…	…
687	841	}
688	842
	843	void config (size_t chunks, int allocate=0)
	844	{
	845	}
689	846	}
690	847
…	…
714	871	}
715	872	}
716
717
	873	else
	874	template DefaultCollect(T) {alias ChunkGC!(T) DefaultCollect;}
	875
	876	}
	877
	878

trunk/tango/util/container/HashMap.d

r5064	r5416
62	62	void buckets (size_t cap)
63	63	void threshold (float desired)
64		~~Allocator allocator()~~
65	64	---
66	65
…	…
114	113	{
115	114	reset;
116		}
117
118		/***********************************************************************
119
120		~~Return the configured allocator~~
121
122		***********************************************************************/
123
124		~~final Alloc allocator ()~~
125		{
126		~~return heap;~~
127	115	}
128	116
…	…
716	704	***********************************************************************/
717	705
718		final ~~void~~ buckets (size_t cap)
	706	final HashMap buckets (size_t cap)
719	707	{
720	708	if (cap < Container.defaultInitialBuckets)
…	…
723	711	if (cap !is buckets)
724	712	resize (cap);
	713	return this;
725	714	}
726	715
…	…
734	723	***********************************************************************/
735	724
736		final ~~void~~ buckets (size_t cap, float threshold)
	725	final HashMap buckets (size_t cap, float threshold)
737	726	{
738	727	loadFactor = threshold;
739		buckets (cast(size_t)(cap / threshold) + 1);
	728	return buckets (cast(size_t)(cap / threshold) + 1);
	729	}
	730
	731	/***********************************************************************
	732
	733	Configure the assigned allocator with the size of each
	734	allocation block (number of nodes allocated at one time)
	735	and the number of nodes to pre-populate the cache with.
	736
	737	Time complexity: O(n)
	738
	739	***********************************************************************/
	740
	741	final HashMap cache (size_t chunk, size_t count=0)
	742	{
	743	heap.config (chunk, count);
	744	return this;
740	745	}
741	746
…	…
1123	1128	void main()
1124	1129	{
	1130	/+
1125	1131	// usage examples ...
1126	1132	auto map = new HashMap!(char[], int);
…	…
1160	1166	while (map.take(v))
1161	1167	Stdout.formatln ("taking {}, {} left", v, map.size);
1162
	1168	+/ int v;
	1169
1163	1170	// setup for benchmark, with a set of integers. We
1164	1171	// use a chunk allocator, and presize the bucket[]
1165		auto test = new HashMap!(int, int, Container.hash, Container.reap, Container.Chunk);
1166		test.allocator.config (1000, 1000);
1167		test.buckets = 1_500_000;
	1172	auto test = new HashMap!(int, int);//, Container.hash, Container.reap, Container.ChunkGC);
	1173	test.buckets(1_500_000);//.cache(8000, 1000000);
1168	1174	const count = 1_000_000;
1169	1175	StopWatch w;
	1176
	1177	GC.collect;
	1178	test.check;
1170	1179
1171	1180	// benchmark adding
…	…
1202	1211
1203	1212	auto aa = new HashMap!(long, int, Container.hash, Container.reap, Container.Chunk);
1204		aa.allocator.config (5000, 1000);
1205		aa.buckets = 7_500_000;
	1213	aa.buckets(7_500_000).cache(100000, 5_000_000);
1206	1214	w.start;
1207	1215	for (int i=5_000_000; i--;)

trunk/tango/util/container/HashSet.d

r5064	r5416
100	100	{
101	101	reset;
102		}
103
104		/***********************************************************************
105
106		~~Return the configured allocator~~
107
108		***********************************************************************/
109
110		~~final Alloc allocator ()~~
111		{
112		~~return heap;~~
113	102	}
114	103
…	…
414	403	***********************************************************************/
415	404
416		final ~~void~~ buckets (size_t cap)
	405	final HashSet buckets (size_t cap)
417	406	{
418	407	if (cap < Container.defaultInitialBuckets)
…	…
421	410	if (cap !is buckets)
422	411	resize (cap);
	412	return this;
423	413	}
424	414
…	…
450	440	if (table)
451	441	checkLoad;
	442	}
	443
	444	/***********************************************************************
	445
	446	Configure the assigned allocator with the size of each
	447	allocation block (number of nodes allocated at one time)
	448	and the number of nodes to pre-populate the cache with.
	449
	450	Time complexity: O(n)
	451
	452	***********************************************************************/
	453
	454	final HashSet cache (size_t chunk, size_t count=0)
	455	{
	456	heap.config (chunk, count);
	457	return this;
452	458	}
453	459
…	…
841	847	// use a chunk allocator, and presize the bucket[]
842	848	auto test = new HashSet!(int, Container.hash, Container.reap, Container.Chunk);
843		test.~~allocator.config (1000, 1~~000);
	849	test.cache (1000, 1_000_000);
844	850	test.buckets = 1_500_000;
845	851	const count = 1_000_000;

trunk/tango/util/container/LinkedList.d

r5064	r5416
133	133	/***********************************************************************
134	134
135		~~Return the configured allocator~~
136
137		***********************************************************************/
138
139		~~final Alloc allocator ()~~
140		{
141		~~return heap;~~
142		}
143
144		/***********************************************************************
145
146	135	Return a generic iterator for contained elements
147	136
…	…
156	145	i.owner = this;
157	146	return i;
	147	}
	148
	149	/***********************************************************************
	150
	151	Configure the assigned allocator with the size of each
	152	allocation block (number of nodes allocated at one time)
	153	and the number of nodes to pre-populate the cache with.
	154
	155	Time complexity: O(n)
	156
	157	***********************************************************************/
	158
	159	final LinkedList cache (size_t chunk, size_t count=0)
	160	{
	161	heap.config (chunk, count);
	162	return this;
158	163	}
159	164
…	…
1123	1128	// use a chunk allocator, and presize the bucket[]
1124	1129	auto test = new LinkedList!(int, Container.reap, Container.Chunk);
1125		test.~~allocator.config (2000, 5~~00);
	1130	test.cache (2000, 1_000_000);
1126	1131	const count = 1_000_000;
1127	1132	StopWatch w;

trunk/tango/util/container/SortedMap.d

r5064	r5416
128	128	/***********************************************************************
129	129
130		~~Return the configured allocator~~
131
132		***********************************************************************/
133
134		~~final Alloc allocator ()~~
135		{
136		~~return heap;~~
137		}
138
139		/***********************************************************************
140
141	130	Return a generic iterator for contained elements
142	131
…	…
169	158	i.node = count ? tree.findFirst(key, cmp, forward) : null;
170	159	return i;
	160	}
	161
	162	/***********************************************************************
	163
	164	Configure the assigned allocator with the size of each
	165	allocation block (number of nodes allocated at one time)
	166	and the number of nodes to pre-populate the cache with.
	167
	168	Time complexity: O(n)
	169
	170	***********************************************************************/
	171
	172	final SortedMap cache (size_t chunk, size_t count=0)
	173	{
	174	heap.config (chunk, count);
	175	return this;
171	176	}
172	177
…	…
1076	1081	// use a chunk allocator, and presize the bucket[]
1077	1082	auto test = new SortedMap!(int, int, Container.reap, Container.Chunk);
1078		test.~~allocator.config (1000, 5~~00);
	1083	test.cache (1000, 500_000);
1079	1084	const count = 500_000;
1080	1085	StopWatch w;

Download in other formats:

Trac

dsource.org

Copyright © 2006-2012 Tango. All Rights Reserved. | Page Width: Static or Dynamic