1 #include <stdio.h>
2
3 #ifdef DS_TEST
4 #define STBDS_UNIT_TESTS
5 #endif
6
7 #ifdef DS_STATS
8 #define STBDS_STATISTICS
9 #endif
10
11 #ifndef DS_PERF
12 #define STBDS_ASSERT assert
13 #include <assert.h>
14 #endif
15
16 //#define STBDS_SIPHASH_2_4
17 #define STB_DS_IMPLEMENTATION
18 #include "../stb_ds.h"
19
20 size_t churn_inserts, churn_deletes;
21
churn(int a,int b,int count)22 void churn(int a, int b, int count)
23 {
24 struct { int key,value; } *map=NULL;
25 int i,j,n,k;
26 for (i=0; i < a; ++i)
27 hmput(map,i,i+1);
28 for (n=0; n < count; ++n) {
29 for (j=a; j < b; ++j,++i) {
30 hmput(map,i,i+1);
31 }
32 assert(hmlen(map) == b);
33 for (j=a; j < b; ++j) {
34 k=i-j-1;
35 k = hmdel(map,k);
36 assert(k != 0);
37 }
38 assert(hmlen(map) == a);
39 }
40 hmfree(map);
41 churn_inserts = i;
42 churn_deletes = (b-a) * n;
43 }
44
45 #ifdef DS_TEST
46 #include <stdio.h>
main(int argc,char ** argv)47 int main(int argc, char **argv)
48 {
49 stbds_unit_tests();
50 churn(0,100,1);
51 churn(3,7,50000);
52 churn(3,15,50000);
53 churn(16, 48, 25000);
54 churn(10, 15, 25000);
55 churn(200,500, 5000);
56 churn(2000,5000, 500);
57 churn(20000,50000, 50);
58 printf("Ok!");
59 return 0;
60 }
61 #endif
62
63 #ifdef DS_STATS
64 #define MAX(a,b) ((a) > (b) ? (a) : (b))
65 size_t max_hit_probes, max_miss_probes, total_put_probes, total_miss_probes, churn_misses;
churn_stats(int a,int b,int count)66 void churn_stats(int a, int b, int count)
67 {
68 struct { int key,value; } *map=NULL;
69 int i,j,n,k;
70 churn_misses = 0;
71 for (i=0; i < a; ++i) {
72 hmput(map,i,i+1);
73 max_hit_probes = MAX(max_hit_probes, stbds_hash_probes);
74 total_put_probes += stbds_hash_probes;
75 stbds_hash_probes = 0;
76 }
77
78 for (n=0; n < count; ++n) {
79 for (j=a; j < b; ++j,++i) {
80 hmput(map,i,i+1);
81 max_hit_probes = MAX(max_hit_probes, stbds_hash_probes);
82 total_put_probes += stbds_hash_probes;
83 stbds_hash_probes = 0;
84 }
85 for (j=0; j < (b-a)*10; ++j) {
86 k=i+j;
87 (void) hmgeti(map,k); // miss
88 max_miss_probes = MAX(max_miss_probes, stbds_hash_probes);
89 total_miss_probes += stbds_hash_probes;
90 stbds_hash_probes = 0;
91 ++churn_misses;
92 }
93 assert(hmlen(map) == b);
94 for (j=a; j < b; ++j) {
95 k=i-j-1;
96 k = hmdel(map,k);
97 stbds_hash_probes = 0;
98 assert(k);
99 }
100 assert(hmlen(map) == a);
101 }
102 hmfree(map);
103 churn_inserts = i;
104 churn_deletes = (b-a) * n;
105 }
106
reset_stats(void)107 void reset_stats(void)
108 {
109 stbds_array_grow=0,
110 stbds_hash_grow=0;
111 stbds_hash_shrink=0;
112 stbds_hash_rebuild=0;
113 stbds_hash_probes=0;
114 stbds_hash_alloc=0;
115 stbds_rehash_probes=0;
116 stbds_rehash_items=0;
117 max_hit_probes = 0;
118 max_miss_probes = 0;
119 total_put_probes = 0;
120 total_miss_probes = 0;
121 }
122
print_churn_probe_stats(char * str)123 void print_churn_probe_stats(char *str)
124 {
125 printf("Probes: %3d max hit, %3d max miss, %4.2f avg hit, %4.2f avg miss: %s\n",
126 (int) max_hit_probes, (int) max_miss_probes, (float) total_put_probes / churn_inserts, (float) total_miss_probes / churn_misses, str);
127 reset_stats();
128 }
129
main(int arg,char ** argv)130 int main(int arg, char **argv)
131 {
132 churn_stats(0,500000,1); print_churn_probe_stats("Inserting 500000 items");
133 churn_stats(0,500000,1); print_churn_probe_stats("Inserting 500000 items");
134 churn_stats(0,500000,1); print_churn_probe_stats("Inserting 500000 items");
135 churn_stats(0,500000,1); print_churn_probe_stats("Inserting 500000 items");
136 churn_stats(49000,50000,500); print_churn_probe_stats("Deleting/Inserting 500000 items");
137 churn_stats(49000,50000,500); print_churn_probe_stats("Deleting/Inserting 500000 items");
138 churn_stats(49000,50000,500); print_churn_probe_stats("Deleting/Inserting 500000 items");
139 churn_stats(49000,50000,500); print_churn_probe_stats("Deleting/Inserting 500000 items");
140 return 0;
141 }
142 #endif
143
144 #ifdef DS_PERF
145 #define WIN32_LEAN_AND_MEAN
146 #include <windows.h>
147 #define STB_DEFINE
148 #define STB_NO_REGISTRY
149 //#include "../stb.h"
150
151
152 size_t t0, sum, mn,mx,count;
begin(void)153 void begin(void)
154 {
155 size_t t0;
156 LARGE_INTEGER m;
157 QueryPerformanceCounter(&m);
158 t0 = m.QuadPart;
159 sum = 0;
160 count = 0;
161 mx = 0;
162 mn = ~(size_t) 0;
163 }
164
measure(void)165 void measure(void)
166 {
167 size_t t1, t;
168 LARGE_INTEGER m;
169 QueryPerformanceCounter(&m);
170 t1 = m.QuadPart;
171 t = t1-t0;
172 if (t1 < t0)
173 printf("ALERT: QueryPerformanceCounter was unordered!\n");
174 if (t < mn) mn = t;
175 if (t > mx) mx = t;
176 sum += t;
177 ++count;
178 t0 = t1;
179 }
180
dont_measure(void)181 void dont_measure(void)
182 {
183 size_t t1, t;
184 LARGE_INTEGER m;
185 QueryPerformanceCounter(&m);
186 t0 = m.QuadPart;
187 }
188
189 double timer;
end(void)190 void end(void)
191 {
192 LARGE_INTEGER m;
193 QueryPerformanceFrequency(&m);
194
195 if (count > 3) {
196 // discard the highest and lowest
197 sum -= mn;
198 sum -= mx;
199 count -= 2;
200 }
201 timer = (double) (sum) / count / m.QuadPart * 1000;
202 }
203
build(int a,int b,int count,int step)204 void build(int a, int b, int count, int step)
205 {
206 struct { int key,value; } *map=NULL;
207 int i,j,n,k;
208 for (i=0; i < a; ++i)
209 hmput(map,i*step,i+1);
210 measure();
211 churn_inserts = i;
212 hmfree(map);
213 dont_measure();
214 }
215
216 #ifdef STB__INCLUDE_STB_H
build_stb(int a,int b,int count,int step)217 void build_stb(int a, int b, int count, int step)
218 {
219 stb_idict *d = stb_idict_new_size(8);
220 struct { int key,value; } *map=NULL;
221 int i,j,n,k;
222 for (i=0; i < a; ++i)
223 stb_idict_add(d, i*step, i+1);
224 measure();
225 churn_inserts = i;
226 stb_idict_destroy(d);
227 dont_measure();
228 }
229 #endif
230
churn_skip(unsigned int a,unsigned int b,int count)231 void churn_skip(unsigned int a, unsigned int b, int count)
232 {
233 struct { unsigned int key,value; } *map=NULL;
234 unsigned int i,j,n,k;
235 for (i=0; i < a; ++i)
236 hmput(map,i,i+1);
237 dont_measure();
238 for (n=0; n < count; ++n) {
239 for (j=a; j < b; ++j,++i) {
240 hmput(map,i,i+1);
241 }
242 assert(hmlen(map) == b);
243 for (j=a; j < b; ++j) {
244 k=i-j-1;
245 k = hmdel(map,k);
246 assert(k != 0);
247 }
248 assert(hmlen(map) == a);
249 }
250 measure();
251 churn_inserts = i;
252 churn_deletes = (b-a) * n;
253 hmfree(map);
254 dont_measure();
255 }
256
257 typedef struct { int n[8]; } str32;
churn32(int a,int b,int count,int include_startup)258 void churn32(int a, int b, int count, int include_startup)
259 {
260 struct { str32 key; int value; } *map=NULL;
261 int i,j,n;
262 str32 key = { 0 };
263 for (i=0; i < a; ++i) {
264 key.n[0] = i;
265 hmput(map,key,i+1);
266 }
267 if (!include_startup)
268 dont_measure();
269 for (n=0; n < count; ++n) {
270 for (j=a; j < b; ++j,++i) {
271 key.n[0] = i;
272 hmput(map,key,i+1);
273 }
274 assert(hmlen(map) == b);
275 for (j=a; j < b; ++j) {
276 key.n[0] = i-j-1;
277 hmdel(map,key);
278 }
279 assert(hmlen(map) == a);
280 }
281 measure();
282 hmfree(map);
283 churn_inserts = i;
284 churn_deletes = (b-a) * n;
285 dont_measure();
286 }
287
288 typedef struct { int n[32]; } str256;
churn256(int a,int b,int count,int include_startup)289 void churn256(int a, int b, int count, int include_startup)
290 {
291 struct { str256 key; int value; } *map=NULL;
292 int i,j,n;
293 str256 key = { 0 };
294 for (i=0; i < a; ++i) {
295 key.n[0] = i;
296 hmput(map,key,i+1);
297 }
298 if (!include_startup)
299 dont_measure();
300 for (n=0; n < count; ++n) {
301 for (j=a; j < b; ++j,++i) {
302 key.n[0] = i;
303 hmput(map,key,i+1);
304 }
305 assert(hmlen(map) == b);
306 for (j=a; j < b; ++j) {
307 key.n[0] = i-j-1;
308 hmdel(map,key);
309 }
310 assert(hmlen(map) == a);
311 }
312 measure();
313 hmfree(map);
314 churn_inserts = i;
315 churn_deletes = (b-a) * n;
316 dont_measure();
317 }
318
churn8(int a,int b,int count,int include_startup)319 void churn8(int a, int b, int count, int include_startup)
320 {
321 struct { size_t key,value; } *map=NULL;
322 int i,j,n,k;
323 for (i=0; i < a; ++i)
324 hmput(map,i,i+1);
325 if (!include_startup)
326 dont_measure();
327 for (n=0; n < count; ++n) {
328 for (j=a; j < b; ++j,++i) {
329 hmput(map,i,i+1);
330 }
331 assert(hmlen(map) == b);
332 for (j=a; j < b; ++j) {
333 k=i-j-1;
334 k = hmdel(map,k);
335 assert(k != 0);
336 }
337 assert(hmlen(map) == a);
338 }
339 measure();
340 hmfree(map);
341 churn_inserts = i;
342 churn_deletes = (b-a) * n;
343 dont_measure();
344 }
345
346
main(int arg,char ** argv)347 int main(int arg, char **argv)
348 {
349 int n,s,w;
350 double worst = 0;
351
352 #if 0
353 begin(); for (n=0; n < 2000; ++n) { build_stb(2000,0,0,1); } end(); printf(" // %7.2fms : 2,000 inserts creating 2K table\n", timer);
354 begin(); for (n=0; n < 500; ++n) { build_stb(20000,0,0,1); } end(); printf(" // %7.2fms : 20,000 inserts creating 20K table\n", timer);
355 begin(); for (n=0; n < 100; ++n) { build_stb(200000,0,0,1); } end(); printf(" // %7.2fms : 200,000 inserts creating 200K table\n", timer);
356 begin(); for (n=0; n < 10; ++n) { build_stb(2000000,0,0,1); } end(); printf(" // %7.2fms : 2,000,000 inserts creating 2M table\n", timer);
357 begin(); for (n=0; n < 5; ++n) { build_stb(20000000,0,0,1); } end(); printf(" // %7.2fms : 20,000,000 inserts creating 20M table\n", timer);
358 #endif
359
360 begin(); for (n=0; n < 2000; ++n) { churn8(2000,0,0,1); } end(); printf(" // %7.2fms : 2,000 inserts creating 2K table w/ 8-byte key\n", timer);
361 begin(); for (n=0; n < 500; ++n) { churn8(20000,0,0,1); } end(); printf(" // %7.2fms : 20,000 inserts creating 20K table w/ 8-byte key\n", timer);
362 begin(); for (n=0; n < 100; ++n) { churn8(200000,0,0,1); } end(); printf(" // %7.2fms : 200,000 inserts creating 200K table w/ 8-byte key\n", timer);
363 begin(); for (n=0; n < 10; ++n) { churn8(2000000,0,0,1); } end(); printf(" // %7.2fms : 2,000,000 inserts creating 2M table w/ 8-byte key\n", timer);
364 begin(); for (n=0; n < 5; ++n) { churn8(20000000,0,0,1); } end(); printf(" // %7.2fms : 20,000,000 inserts creating 20M table w/ 8-byte key\n", timer);
365
366 #if 0
367 begin(); for (n=0; n < 2000; ++n) { churn32(2000,0,0,1); } end(); printf(" // %7.2fms : 2,000 inserts creating 2K table w/ 32-byte key\n", timer);
368 begin(); for (n=0; n < 500; ++n) { churn32(20000,0,0,1); } end(); printf(" // %7.2fms : 20,000 inserts creating 20K table w/ 32-byte key\n", timer);
369 begin(); for (n=0; n < 100; ++n) { churn32(200000,0,0,1); } end(); printf(" // %7.2fms : 200,000 inserts creating 200K table w/ 32-byte key\n", timer);
370 begin(); for (n=0; n < 10; ++n) { churn32(2000000,0,0,1); } end(); printf(" // %7.2fms : 2,000,000 inserts creating 2M table w/ 32-byte key\n", timer);
371 begin(); for (n=0; n < 5; ++n) { churn32(20000000,0,0,1); } end(); printf(" // %7.2fms : 20,000,000 inserts creating 20M table w/ 32-byte key\n", timer);
372
373 begin(); for (n=0; n < 2000; ++n) { churn256(2000,0,0,1); } end(); printf(" // %7.2fms : 2,000 inserts creating 2K table w/ 256-byte key\n", timer);
374 begin(); for (n=0; n < 500; ++n) { churn256(20000,0,0,1); } end(); printf(" // %7.2fms : 20,000 inserts creating 20K table w/ 256-byte key\n", timer);
375 begin(); for (n=0; n < 100; ++n) { churn256(200000,0,0,1); } end(); printf(" // %7.2fms : 200,000 inserts creating 200K table w/ 256-byte key\n", timer);
376 begin(); for (n=0; n < 10; ++n) { churn256(2000000,0,0,1); } end(); printf(" // %7.2fms : 2,000,000 inserts creating 2M table w/ 256-byte key\n", timer);
377 begin(); for (n=0; n < 5; ++n) { churn256(20000000,0,0,1); } end(); printf(" // %7.2fms : 20,000,000 inserts creating 20M table w/ 256-byte key\n", timer);
378 #endif
379
380 begin(); for (n=0; n < 2000; ++n) { build(2000,0,0,1); } end(); printf(" // %7.2fms : 2,000 inserts creating 2K table w/ 4-byte key\n", timer);
381 begin(); for (n=0; n < 500; ++n) { build(20000,0,0,1); } end(); printf(" // %7.2fms : 20,000 inserts creating 20K table w/ 4-byte key\n", timer);
382 begin(); for (n=0; n < 100; ++n) { build(200000,0,0,1); } end(); printf(" // %7.2fms : 200,000 inserts creating 200K table w/ 4-byte key\n", timer);
383 begin(); for (n=0; n < 10; ++n) { build(2000000,0,0,1); } end(); printf(" // %7.2fms : 2,000,000 inserts creating 2M table w/ 4-byte key\n", timer);
384 begin(); for (n=0; n < 5; ++n) { build(20000000,0,0,1); } end(); printf(" // %7.2fms : 20,000,000 inserts creating 20M table w/ 4-byte key\n", timer);
385
386 begin(); for (n=0; n < 60; ++n) { churn_skip(2000,2100,5000); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 2K table\n", timer);
387 begin(); for (n=0; n < 30; ++n) { churn_skip(20000,21000,500); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 20K table\n", timer);
388 begin(); for (n=0; n < 15; ++n) { churn_skip(200000,201000,500); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 200K table\n", timer);
389 begin(); for (n=0; n < 8; ++n) { churn_skip(2000000,2001000,500); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 2M table\n", timer);
390 begin(); for (n=0; n < 5; ++n) { churn_skip(20000000,20001000,500); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 20M table\n", timer);
391 begin(); for (n=0; n < 1; ++n) { churn_skip(200000000u,200001000u,500); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 200M table\n", timer);
392 // even though the above measures a roughly fixed amount of work, we still have to build the table n times, hence the fewer measurements each time
393
394 begin(); for (n=0; n < 60; ++n) { churn_skip(1000,3000,250); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 2K table\n", timer);
395 begin(); for (n=0; n < 15; ++n) { churn_skip(10000,30000,25); } end(); printf(" // %7.2fms : 500,000 inserts & deletes in 20K table\n", timer);
396 begin(); for (n=0; n < 7; ++n) { churn_skip(100000,300000,10); } end(); printf(" // %7.2fms : 2,000,000 inserts & deletes in 200K table\n", timer);
397 begin(); for (n=0; n < 2; ++n) { churn_skip(1000000,3000000,10); } end(); printf(" // %7.2fms : 20,000,000 inserts & deletes in 2M table\n", timer);
398
399 // search for bad intervals.. in practice this just seems to measure execution variance
400 for (s = 2; s < 64; ++s) {
401 begin(); for (n=0; n < 50; ++n) { build(200000,0,0,s); } end();
402 if (timer > worst) {
403 worst = timer;
404 w = s;
405 }
406 }
407 for (; s <= 1024; s *= 2) {
408 begin(); for (n=0; n < 50; ++n) { build(200000,0,0,s); } end();
409 if (timer > worst) {
410 worst = timer;
411 w = s;
412 }
413 }
414 printf(" // %7.2fms(%d) : Worst time from inserting 200,000 items with spacing %d.\n", worst, w, w);
415
416 return 0;
417 }
418 #endif
419