]>
Commit | Line | Data |
---|---|---|
0e666160 | 1 | /* |
6513cb3d | 2 | * Copyright (c) 2008, 2009, 2010, 2013, 2014, 2016, 2017 Nicira, Inc. |
0e666160 BP |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | /* A non-exhaustive test for some of the functions and macros declared in | |
18 | * cmap.h. */ | |
19 | ||
20 | #include <config.h> | |
3f636c7e | 21 | #undef NDEBUG |
0e666160 | 22 | #include "cmap.h" |
3f636c7e | 23 | #include <assert.h> |
0e666160 BP |
24 | #include <getopt.h> |
25 | #include <string.h> | |
3f636c7e | 26 | #include "bitmap.h" |
0e666160 BP |
27 | #include "command-line.h" |
28 | #include "fat-rwlock.h" | |
29 | #include "hash.h" | |
ee89ea7b | 30 | #include "openvswitch/hmap.h" |
0e666160 BP |
31 | #include "ovstest.h" |
32 | #include "ovs-thread.h" | |
33 | #include "random.h" | |
34 | #include "timeval.h" | |
35 | #include "util.h" | |
36 | ||
0e666160 BP |
37 | /* Sample cmap element. */ |
38 | struct element { | |
39 | int value; | |
40 | struct cmap_node node; | |
41 | }; | |
42 | ||
43 | typedef size_t hash_func(int value); | |
44 | ||
45 | static int | |
46 | compare_ints(const void *a_, const void *b_) | |
47 | { | |
48 | const int *a = a_; | |
49 | const int *b = b_; | |
50 | return *a < *b ? -1 : *a > *b; | |
51 | } | |
52 | ||
53 | /* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */ | |
54 | static void | |
55 | check_cmap(struct cmap *cmap, const int values[], size_t n, | |
56 | hash_func *hash) | |
57 | { | |
cd50723c | 58 | int *sort_values, *cmap_values, *cmap_values2; |
a532e683 | 59 | const struct element *e; |
52a524eb | 60 | size_t i, batch_size; |
0e666160 | 61 | |
cd50723c DDP |
62 | struct cmap_position pos = { 0, 0, 0 }; |
63 | struct cmap_node *node; | |
64 | ||
0e666160 BP |
65 | /* Check that all the values are there in iteration. */ |
66 | sort_values = xmalloc(sizeof *sort_values * n); | |
67 | cmap_values = xmalloc(sizeof *sort_values * n); | |
cd50723c | 68 | cmap_values2 = xmalloc(sizeof *sort_values * n); |
0e666160 | 69 | |
cd50723c | 70 | /* Here we test cursor iteration */ |
0e666160 | 71 | i = 0; |
a532e683 | 72 | CMAP_FOR_EACH (e, node, cmap) { |
0e666160 BP |
73 | assert(i < n); |
74 | cmap_values[i++] = e->value; | |
75 | } | |
76 | assert(i == n); | |
77 | ||
cd50723c DDP |
78 | /* Here we test iteration with cmap_next_position() */ |
79 | i = 0; | |
80 | while ((node = cmap_next_position(cmap, &pos))) { | |
d72eff6c | 81 | e = OBJECT_CONTAINING(node, e, node); |
cd50723c DDP |
82 | |
83 | assert(i < n); | |
84 | cmap_values2[i++] = e->value; | |
85 | } | |
86 | assert(i == n); | |
87 | ||
0e666160 BP |
88 | memcpy(sort_values, values, sizeof *sort_values * n); |
89 | qsort(sort_values, n, sizeof *sort_values, compare_ints); | |
90 | qsort(cmap_values, n, sizeof *cmap_values, compare_ints); | |
cd50723c | 91 | qsort(cmap_values2, n, sizeof *cmap_values2, compare_ints); |
0e666160 BP |
92 | |
93 | for (i = 0; i < n; i++) { | |
94 | assert(sort_values[i] == cmap_values[i]); | |
cd50723c | 95 | assert(sort_values[i] == cmap_values2[i]); |
0e666160 BP |
96 | } |
97 | ||
cd50723c | 98 | free(cmap_values2); |
0e666160 BP |
99 | free(cmap_values); |
100 | free(sort_values); | |
101 | ||
102 | /* Check that all the values are there in lookup. */ | |
103 | for (i = 0; i < n; i++) { | |
104 | size_t count = 0; | |
105 | ||
106 | CMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), cmap) { | |
107 | count += e->value == values[i]; | |
108 | } | |
109 | assert(count == 1); | |
110 | } | |
111 | ||
52a524eb JR |
112 | /* Check that all the values are there in batched lookup. */ |
113 | batch_size = n % BITMAP_ULONG_BITS + 1; | |
114 | for (i = 0; i < n; i += batch_size) { | |
115 | unsigned long map; | |
116 | uint32_t hashes[sizeof map * CHAR_BIT]; | |
117 | const struct cmap_node *nodes[sizeof map * CHAR_BIT]; | |
118 | size_t count = 0; | |
119 | int k, j; | |
120 | ||
121 | j = MIN(n - i, batch_size); /* Actual batch size. */ | |
122 | map = ~0UL >> (BITMAP_ULONG_BITS - j); | |
123 | ||
124 | for (k = 0; k < j; k++) { | |
125 | hashes[k] = hash(values[i + k]); | |
126 | } | |
127 | map = cmap_find_batch(cmap, map, hashes, nodes); | |
128 | ||
3ee6026a | 129 | ULLONG_FOR_EACH_1(k, map) { |
52a524eb JR |
130 | CMAP_NODE_FOR_EACH (e, node, nodes[k]) { |
131 | count += e->value == values[i + k]; | |
132 | } | |
133 | } | |
134 | assert(count == j); /* j elements in a batch. */ | |
135 | } | |
136 | ||
9d933fc7 JR |
137 | /* Check that cmap_first() returns NULL only when cmap_is_empty(). */ |
138 | assert(!cmap_first(cmap) == cmap_is_empty(cmap)); | |
139 | ||
0e666160 BP |
140 | /* Check counters. */ |
141 | assert(cmap_is_empty(cmap) == !n); | |
142 | assert(cmap_count(cmap) == n); | |
143 | } | |
144 | ||
145 | static void | |
146 | shuffle(int *p, size_t n) | |
147 | { | |
148 | for (; n > 1; n--, p++) { | |
149 | int *q = &p[random_range(n)]; | |
150 | int tmp = *p; | |
151 | *p = *q; | |
152 | *q = tmp; | |
153 | } | |
154 | } | |
155 | ||
156 | /* Prints the values in 'cmap', plus 'name' as a title. */ | |
157 | static void OVS_UNUSED | |
158 | print_cmap(const char *name, struct cmap *cmap) | |
159 | { | |
160 | struct cmap_cursor cursor; | |
161 | struct element *e; | |
162 | ||
163 | printf("%s:", name); | |
a532e683 | 164 | CMAP_CURSOR_FOR_EACH (e, node, &cursor, cmap) { |
0e666160 BP |
165 | printf(" %d", e->value); |
166 | } | |
167 | printf("\n"); | |
168 | } | |
169 | ||
170 | /* Prints the 'n' values in 'values', plus 'name' as a title. */ | |
171 | static void OVS_UNUSED | |
172 | print_ints(const char *name, const int *values, size_t n) | |
173 | { | |
174 | size_t i; | |
175 | ||
176 | printf("%s:", name); | |
177 | for (i = 0; i < n; i++) { | |
178 | printf(" %d", values[i]); | |
179 | } | |
180 | printf("\n"); | |
181 | } | |
182 | ||
183 | static size_t | |
184 | identity_hash(int value) | |
185 | { | |
186 | return value; | |
187 | } | |
188 | ||
189 | static size_t | |
190 | good_hash(int value) | |
191 | { | |
192 | return hash_int(value, 0x1234abcd); | |
193 | } | |
194 | ||
195 | static size_t | |
196 | constant_hash(int value OVS_UNUSED) | |
197 | { | |
198 | return 123; | |
199 | } | |
200 | ||
201 | /* Tests basic cmap insertion and deletion. */ | |
202 | static void | |
9d933fc7 | 203 | test_cmap_insert_replace_delete(hash_func *hash) |
0e666160 BP |
204 | { |
205 | enum { N_ELEMS = 1000 }; | |
206 | ||
207 | struct element elements[N_ELEMS]; | |
9d933fc7 | 208 | struct element copies[N_ELEMS]; |
0e666160 | 209 | int values[N_ELEMS]; |
b70e6976 | 210 | struct cmap cmap = CMAP_INITIALIZER; |
0e666160 BP |
211 | size_t i; |
212 | ||
0e666160 BP |
213 | for (i = 0; i < N_ELEMS; i++) { |
214 | elements[i].value = i; | |
215 | cmap_insert(&cmap, &elements[i].node, hash(i)); | |
216 | values[i] = i; | |
217 | check_cmap(&cmap, values, i + 1, hash); | |
218 | } | |
219 | shuffle(values, N_ELEMS); | |
220 | for (i = 0; i < N_ELEMS; i++) { | |
9d933fc7 JR |
221 | copies[values[i]].value = values[i]; |
222 | cmap_replace(&cmap, &elements[values[i]].node, | |
223 | &copies[values[i]].node, hash(values[i])); | |
224 | check_cmap(&cmap, values, N_ELEMS, hash); | |
225 | } | |
226 | shuffle(values, N_ELEMS); | |
227 | for (i = 0; i < N_ELEMS; i++) { | |
228 | cmap_remove(&cmap, &copies[values[i]].node, hash(values[i])); | |
0e666160 BP |
229 | check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash); |
230 | } | |
231 | cmap_destroy(&cmap); | |
232 | } | |
233 | ||
234 | static void | |
235 | run_test(void (*function)(hash_func *)) | |
236 | { | |
237 | hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash }; | |
238 | size_t i; | |
239 | ||
240 | for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) { | |
241 | function(hash_funcs[i]); | |
242 | printf("."); | |
243 | fflush(stdout); | |
244 | } | |
245 | } | |
246 | ||
247 | static void | |
1636c761 | 248 | run_tests(struct ovs_cmdl_context *ctx) |
0e666160 BP |
249 | { |
250 | int n; | |
251 | int i; | |
252 | ||
1636c761 | 253 | n = ctx->argc >= 2 ? atoi(ctx->argv[1]) : 100; |
0e666160 | 254 | for (i = 0; i < n; i++) { |
9d933fc7 | 255 | run_test(test_cmap_insert_replace_delete); |
0e666160 BP |
256 | } |
257 | printf("\n"); | |
258 | } | |
259 | \f | |
260 | static int n_elems; /* Number of elements to insert. */ | |
261 | static int n_threads; /* Number of threads to search and mutate. */ | |
262 | static uint32_t mutation_frac; /* % mutations, as fraction of UINT32_MAX. */ | |
52a524eb JR |
263 | static int n_batch; /* Number of elements in each batch. */ |
264 | ||
265 | #define N_BATCH_MAX BITMAP_ULONG_BITS | |
0e666160 BP |
266 | |
267 | static void benchmark_cmap(void); | |
52a524eb | 268 | static void benchmark_cmap_batched(void); |
0e666160 BP |
269 | static void benchmark_hmap(void); |
270 | ||
271 | static int | |
272 | elapsed(const struct timeval *start) | |
273 | { | |
274 | struct timeval end; | |
275 | ||
276 | xgettimeofday(&end); | |
277 | return timeval_to_msec(&end) - timeval_to_msec(start); | |
278 | } | |
279 | ||
280 | static void | |
1636c761 | 281 | run_benchmarks(struct ovs_cmdl_context *ctx) |
0e666160 | 282 | { |
1636c761 RB |
283 | n_elems = strtol(ctx->argv[1], NULL, 10); |
284 | n_threads = strtol(ctx->argv[2], NULL, 10); | |
285 | mutation_frac = strtod(ctx->argv[3], NULL) / 100.0 * UINT32_MAX; | |
286 | n_batch = ctx->argc > 4 ? strtol(ctx->argv[4], NULL, 10) : 1; | |
0e666160 | 287 | |
52a524eb JR |
288 | if (n_batch > N_BATCH_MAX) { |
289 | n_batch = N_BATCH_MAX; | |
290 | } | |
291 | printf("Benchmarking with n=%d, %d threads, %.2f%% mutations, batch size %d:\n", | |
292 | n_elems, n_threads, (double) mutation_frac / UINT32_MAX * 100., | |
293 | n_batch); | |
0e666160 | 294 | |
52a524eb JR |
295 | if (n_batch > 0) { |
296 | benchmark_cmap_batched(); | |
297 | } | |
298 | putchar('\n'); | |
0e666160 BP |
299 | benchmark_cmap(); |
300 | putchar('\n'); | |
301 | benchmark_hmap(); | |
302 | } | |
303 | \f | |
304 | /* cmap benchmark. */ | |
305 | ||
306 | static struct element * | |
307 | find(const struct cmap *cmap, int value) | |
308 | { | |
309 | struct element *e; | |
310 | ||
311 | CMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), cmap) { | |
312 | if (e->value == value) { | |
313 | return e; | |
314 | } | |
315 | } | |
316 | return NULL; | |
317 | } | |
318 | ||
319 | struct cmap_aux { | |
320 | struct ovs_mutex mutex; | |
321 | struct cmap *cmap; | |
322 | }; | |
323 | ||
324 | static void * | |
325 | search_cmap(void *aux_) | |
326 | { | |
327 | struct cmap_aux *aux = aux_; | |
328 | size_t i; | |
329 | ||
44a48152 JR |
330 | if (mutation_frac) { |
331 | for (i = 0; i < n_elems; i++) { | |
332 | struct element *e; | |
0e666160 | 333 | |
44a48152 JR |
334 | if (random_uint32() < mutation_frac) { |
335 | ovs_mutex_lock(&aux->mutex); | |
336 | e = find(aux->cmap, i); | |
337 | if (e) { | |
338 | cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0)); | |
339 | } | |
340 | ovs_mutex_unlock(&aux->mutex); | |
341 | } else { | |
342 | ignore(find(aux->cmap, i)); | |
0e666160 | 343 | } |
44a48152 JR |
344 | } |
345 | } else { | |
346 | for (i = 0; i < n_elems; i++) { | |
0e666160 BP |
347 | ignore(find(aux->cmap, i)); |
348 | } | |
349 | } | |
350 | return NULL; | |
351 | } | |
352 | ||
353 | static void | |
354 | benchmark_cmap(void) | |
355 | { | |
356 | struct element *elements; | |
357 | struct cmap cmap; | |
358 | struct element *e; | |
0e666160 BP |
359 | struct timeval start; |
360 | pthread_t *threads; | |
361 | struct cmap_aux aux; | |
362 | size_t i; | |
363 | ||
364 | elements = xmalloc(n_elems * sizeof *elements); | |
365 | ||
366 | /* Insertions. */ | |
367 | xgettimeofday(&start); | |
368 | cmap_init(&cmap); | |
369 | for (i = 0; i < n_elems; i++) { | |
370 | elements[i].value = i; | |
371 | cmap_insert(&cmap, &elements[i].node, hash_int(i, 0)); | |
372 | } | |
373 | printf("cmap insert: %5d ms\n", elapsed(&start)); | |
374 | ||
375 | /* Iteration. */ | |
376 | xgettimeofday(&start); | |
a532e683 | 377 | CMAP_FOR_EACH (e, node, &cmap) { |
0e666160 BP |
378 | ignore(e); |
379 | } | |
380 | printf("cmap iterate: %5d ms\n", elapsed(&start)); | |
381 | ||
382 | /* Search and mutation. */ | |
383 | xgettimeofday(&start); | |
384 | aux.cmap = &cmap; | |
385 | ovs_mutex_init(&aux.mutex); | |
386 | threads = xmalloc(n_threads * sizeof *threads); | |
387 | for (i = 0; i < n_threads; i++) { | |
388 | threads[i] = ovs_thread_create("search", search_cmap, &aux); | |
389 | } | |
390 | for (i = 0; i < n_threads; i++) { | |
391 | xpthread_join(threads[i], NULL); | |
392 | } | |
393 | free(threads); | |
394 | printf("cmap search: %5d ms\n", elapsed(&start)); | |
395 | ||
396 | /* Destruction. */ | |
397 | xgettimeofday(&start); | |
a532e683 | 398 | CMAP_FOR_EACH (e, node, &cmap) { |
0e666160 BP |
399 | cmap_remove(&cmap, &e->node, hash_int(e->value, 0)); |
400 | } | |
401 | cmap_destroy(&cmap); | |
402 | printf("cmap destroy: %5d ms\n", elapsed(&start)); | |
403 | ||
404 | free(elements); | |
405 | } | |
52a524eb JR |
406 | |
407 | static size_t | |
408 | find_batch(const struct cmap *cmap, const int value) | |
409 | { | |
410 | size_t i, ret; | |
411 | const size_t end = MIN(n_batch, n_elems - value); | |
52a524eb JR |
412 | uint32_t hashes[N_BATCH_MAX]; |
413 | const struct cmap_node *nodes[N_BATCH_MAX]; | |
414 | ||
415 | if (mutation_frac) { | |
416 | for (i = 0; i < end; i++) { | |
417 | if (random_uint32() < mutation_frac) { | |
418 | break; | |
419 | } | |
420 | hashes[i] = hash_int(value + i, 0); | |
421 | } | |
422 | } else { | |
423 | for (i = 0; i < end; i++) { | |
424 | hashes[i] = hash_int(value + i, 0); | |
425 | } | |
426 | } | |
427 | ||
428 | ret = i; | |
429 | ||
6513cb3d | 430 | unsigned long map = i ? ~0UL >> (BITMAP_ULONG_BITS - i) : 0; |
52a524eb JR |
431 | map = cmap_find_batch(cmap, map, hashes, nodes); |
432 | ||
3ee6026a | 433 | ULLONG_FOR_EACH_1(i, map) { |
52a524eb JR |
434 | struct element *e; |
435 | ||
436 | CMAP_NODE_FOR_EACH (e, node, nodes[i]) { | |
437 | if (OVS_LIKELY(e->value == value + i)) { | |
438 | ignore(e); /* Found result. */ | |
439 | break; | |
440 | } | |
441 | } | |
442 | } | |
443 | return ret; | |
444 | } | |
445 | ||
446 | static void * | |
447 | search_cmap_batched(void *aux_) | |
448 | { | |
449 | struct cmap_aux *aux = aux_; | |
450 | size_t i = 0, j; | |
451 | ||
452 | for (;;) { | |
453 | struct element *e; | |
454 | ||
455 | j = find_batch(aux->cmap, i); | |
456 | i += j; | |
457 | if (i >= n_elems) { | |
458 | break; | |
459 | } | |
460 | if (j < n_batch) { | |
461 | ovs_mutex_lock(&aux->mutex); | |
462 | e = find(aux->cmap, i); | |
463 | if (e) { | |
464 | cmap_remove(aux->cmap, &e->node, hash_int(e->value, 0)); | |
465 | } | |
466 | ovs_mutex_unlock(&aux->mutex); | |
467 | } | |
468 | } | |
469 | ||
470 | return NULL; | |
471 | } | |
472 | ||
473 | static void | |
474 | benchmark_cmap_batched(void) | |
475 | { | |
476 | struct element *elements; | |
477 | struct cmap cmap; | |
478 | struct element *e; | |
479 | struct timeval start; | |
480 | pthread_t *threads; | |
481 | struct cmap_aux aux; | |
482 | size_t i; | |
483 | ||
484 | elements = xmalloc(n_elems * sizeof *elements); | |
485 | ||
486 | /* Insertions. */ | |
487 | xgettimeofday(&start); | |
488 | cmap_init(&cmap); | |
489 | for (i = 0; i < n_elems; i++) { | |
490 | elements[i].value = i; | |
491 | cmap_insert(&cmap, &elements[i].node, hash_int(i, 0)); | |
492 | } | |
493 | printf("cmap insert: %5d ms\n", elapsed(&start)); | |
494 | ||
495 | /* Iteration. */ | |
496 | xgettimeofday(&start); | |
497 | CMAP_FOR_EACH (e, node, &cmap) { | |
498 | ignore(e); | |
499 | } | |
500 | printf("cmap iterate: %5d ms\n", elapsed(&start)); | |
501 | ||
502 | /* Search and mutation. */ | |
503 | xgettimeofday(&start); | |
504 | aux.cmap = &cmap; | |
505 | ovs_mutex_init(&aux.mutex); | |
506 | threads = xmalloc(n_threads * sizeof *threads); | |
507 | for (i = 0; i < n_threads; i++) { | |
508 | threads[i] = ovs_thread_create("search", search_cmap_batched, &aux); | |
509 | } | |
510 | for (i = 0; i < n_threads; i++) { | |
511 | xpthread_join(threads[i], NULL); | |
512 | } | |
513 | free(threads); | |
514 | printf("batch search: %5d ms\n", elapsed(&start)); | |
515 | ||
516 | /* Destruction. */ | |
517 | xgettimeofday(&start); | |
518 | CMAP_FOR_EACH (e, node, &cmap) { | |
519 | cmap_remove(&cmap, &e->node, hash_int(e->value, 0)); | |
520 | } | |
521 | cmap_destroy(&cmap); | |
522 | printf("cmap destroy: %5d ms\n", elapsed(&start)); | |
523 | ||
524 | free(elements); | |
525 | } | |
0e666160 BP |
526 | \f |
527 | /* hmap benchmark. */ | |
528 | struct helement { | |
529 | int value; | |
530 | struct hmap_node node; | |
531 | }; | |
532 | ||
533 | static struct helement * | |
534 | hfind(const struct hmap *hmap, int value) | |
535 | { | |
536 | struct helement *e; | |
537 | ||
538 | HMAP_FOR_EACH_WITH_HASH (e, node, hash_int(value, 0), hmap) { | |
539 | if (e->value == value) { | |
540 | return e; | |
541 | } | |
542 | } | |
543 | return NULL; | |
544 | } | |
545 | ||
546 | struct hmap_aux { | |
547 | struct hmap *hmap; | |
548 | struct fat_rwlock fatlock; | |
549 | }; | |
550 | ||
551 | static void * | |
552 | search_hmap(void *aux_) | |
553 | { | |
554 | struct hmap_aux *aux = aux_; | |
555 | size_t i; | |
556 | ||
44a48152 JR |
557 | if (mutation_frac) { |
558 | for (i = 0; i < n_elems; i++) { | |
0e666160 BP |
559 | if (random_uint32() < mutation_frac) { |
560 | struct helement *e; | |
561 | ||
562 | fat_rwlock_wrlock(&aux->fatlock); | |
563 | e = hfind(aux->hmap, i); | |
564 | if (e) { | |
565 | hmap_remove(aux->hmap, &e->node); | |
566 | } | |
567 | fat_rwlock_unlock(&aux->fatlock); | |
568 | } else { | |
569 | fat_rwlock_rdlock(&aux->fatlock); | |
570 | ignore(hfind(aux->hmap, i)); | |
571 | fat_rwlock_unlock(&aux->fatlock); | |
572 | } | |
44a48152 JR |
573 | } |
574 | } else { | |
575 | for (i = 0; i < n_elems; i++) { | |
576 | ignore(hfind(aux->hmap, i)); | |
0e666160 BP |
577 | } |
578 | } | |
579 | return NULL; | |
580 | } | |
581 | ||
582 | static void | |
583 | benchmark_hmap(void) | |
584 | { | |
585 | struct helement *elements; | |
586 | struct hmap hmap; | |
587 | struct helement *e, *next; | |
588 | struct timeval start; | |
589 | pthread_t *threads; | |
590 | struct hmap_aux aux; | |
591 | size_t i; | |
592 | ||
593 | elements = xmalloc(n_elems * sizeof *elements); | |
594 | ||
595 | xgettimeofday(&start); | |
596 | hmap_init(&hmap); | |
597 | for (i = 0; i < n_elems; i++) { | |
598 | elements[i].value = i; | |
599 | hmap_insert(&hmap, &elements[i].node, hash_int(i, 0)); | |
600 | } | |
601 | ||
602 | printf("hmap insert: %5d ms\n", elapsed(&start)); | |
603 | ||
604 | xgettimeofday(&start); | |
605 | HMAP_FOR_EACH (e, node, &hmap) { | |
606 | ignore(e); | |
607 | } | |
608 | printf("hmap iterate: %5d ms\n", elapsed(&start)); | |
609 | ||
610 | xgettimeofday(&start); | |
611 | aux.hmap = &hmap; | |
612 | fat_rwlock_init(&aux.fatlock); | |
613 | threads = xmalloc(n_threads * sizeof *threads); | |
614 | for (i = 0; i < n_threads; i++) { | |
615 | threads[i] = ovs_thread_create("search", search_hmap, &aux); | |
616 | } | |
617 | for (i = 0; i < n_threads; i++) { | |
618 | xpthread_join(threads[i], NULL); | |
619 | } | |
620 | free(threads); | |
621 | printf("hmap search: %5d ms\n", elapsed(&start)); | |
622 | ||
623 | /* Destruction. */ | |
624 | xgettimeofday(&start); | |
625 | HMAP_FOR_EACH_SAFE (e, next, node, &hmap) { | |
626 | hmap_remove(&hmap, &e->node); | |
627 | } | |
628 | hmap_destroy(&hmap); | |
629 | printf("hmap destroy: %5d ms\n", elapsed(&start)); | |
630 | ||
631 | free(elements); | |
632 | } | |
633 | \f | |
5f383751 | 634 | static const struct ovs_cmdl_command commands[] = { |
1f4a7252 RM |
635 | {"check", NULL, 0, 1, run_tests, OVS_RO}, |
636 | {"benchmark", NULL, 3, 4, run_benchmarks, OVS_RO}, | |
637 | {NULL, NULL, 0, 0, NULL, OVS_RO}, | |
0e666160 BP |
638 | }; |
639 | ||
640 | static void | |
1636c761 | 641 | test_cmap_main(int argc, char *argv[]) |
0e666160 | 642 | { |
1636c761 RB |
643 | struct ovs_cmdl_context ctx = { |
644 | .argc = argc - optind, | |
645 | .argv = argv + optind, | |
646 | }; | |
647 | ||
0e666160 | 648 | set_program_name(argv[0]); |
1636c761 | 649 | ovs_cmdl_run_command(&ctx, commands); |
0e666160 BP |
650 | } |
651 | ||
652 | OVSTEST_REGISTER("test-cmap", test_cmap_main); |