From 8872c3a3910dbf4e6470e8a6f86e4c645712805b Mon Sep 17 00:00:00 2001 From: =?utf8?q?Zbigniew=20J=C4=99drzejewski-Szmek?= Date: Tue, 18 Dec 2018 11:35:48 +0100 Subject: [PATCH] test-hashmap: add test to compare hashmap_free performance The point here is to compare speed of hashmap_destroy with free and a different freeing function, to the implementation details of hashmap_clear can be evaluated. Results: current code: /* test_hashmap_free (slow, 1048576 entries) */ string_hash_ops test took 2.494499s custom_free_hash_ops test took 2.640449s string_hash_ops test took 2.287734s custom_free_hash_ops test took 2.557632s string_hash_ops test took 2.299791s custom_free_hash_ops test took 2.586975s string_hash_ops test took 2.314099s custom_free_hash_ops test took 2.589327s string_hash_ops test took 2.319137s custom_free_hash_ops test took 2.584038s code with a patch which restores the "fast path" using: for (idx = skip_free_buckets(h, 0); idx != IDX_NIL; idx = skip_free_buckets(h, idx + 1)) in the case where both free_key and free_value are either free or NULL: /* test_hashmap_free (slow, 1048576 entries) */ string_hash_ops test took 2.347013s custom_free_hash_ops test took 2.585104s string_hash_ops test took 2.311583s custom_free_hash_ops test took 2.578388s string_hash_ops test took 2.283658s custom_free_hash_ops test took 2.621675s string_hash_ops test took 2.334675s custom_free_hash_ops test took 2.601568s So the test is noisy, but there clearly is no significant difference with the "fast path" restored. I'm surprised by this, but it shows that the current "safe" implementation does not cause a performance loss. When the code is compiled with optimization, those times are significantly lower (e.g. 1.1s and 1.4s), but again, there is no difference with the "fast path" restored. The difference between string_hash_ops and custom_free_hash_ops is the additional cost of global modification and the extra function call. --- src/test/test-hashmap-plain.c | 49 +++++++++++++++++++++++++++++++++++ src/test/test-hashmap.c | 9 +++++++ 2 files changed, 58 insertions(+) diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 039c0e0e590..5376aa84c40 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -3,6 +3,7 @@ #include "alloc-util.h" #include "hashmap.h" #include "log.h" +#include "stdio-util.h" #include "string-util.h" #include "strv.h" #include "tests.h" @@ -782,6 +783,53 @@ static void test_hashmap_many(void) { } } +extern unsigned custom_counter; +extern const struct hash_ops boring_hash_ops, custom_hash_ops; + +static void test_hashmap_free(void) { + Hashmap *h; + bool slow = slow_tests_enabled(); + usec_t ts, n; + char b[FORMAT_TIMESPAN_MAX]; + unsigned n_entries = slow ? 1 << 20 : 240; + + const struct { + const char *title; + const struct hash_ops *ops; + unsigned expect_counter; + } tests[] = { + { "string_hash_ops", &boring_hash_ops, 2 * n_entries}, + { "custom_free_hash_ops", &custom_hash_ops, 0 }, + }; + + log_info("/* %s (%s, %u entries) */", __func__, slow ? "slow" : "fast", n_entries); + + for (unsigned j = 0; j < ELEMENTSOF(tests); j++) { + ts = now(CLOCK_MONOTONIC); + assert_se(h = hashmap_new(tests[j].ops)); + + custom_counter = 0; + for (unsigned i = 0; i < n_entries; i++) { + char s[DECIMAL_STR_MAX(unsigned)]; + char *k, *v; + + xsprintf(s, "%u", i); + assert_se(k = strdup(s)); + assert_se(v = strdup(s)); + custom_counter += 2; + + assert_se(hashmap_put(h, k, v) >= 0); + } + + hashmap_free(h); + + n = now(CLOCK_MONOTONIC); + log_info("%s test took %s", tests[j].title, format_timespan(b, sizeof b, n - ts, 0)); + + assert_se(custom_counter == tests[j].expect_counter); + } +} + static void test_hashmap_first(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; @@ -955,6 +1003,7 @@ void test_hashmap_funcs(void) { test_hashmap_get2(); test_hashmap_size(); test_hashmap_many(); + test_hashmap_free(); test_hashmap_first(); test_hashmap_first_key(); test_hashmap_steal_first_key(); diff --git a/src/test/test-hashmap.c b/src/test/test-hashmap.c index 6f29266d6e9..ee4c0e66dbd 100644 --- a/src/test/test-hashmap.c +++ b/src/test/test-hashmap.c @@ -3,6 +3,15 @@ #include "hashmap.h" #include "util.h" +unsigned custom_counter = 0; +static void custom_destruct(void* p) { + custom_counter--; + free(p); +} + +DEFINE_HASH_OPS_FULL(boring_hash_ops, char, string_hash_func, string_compare_func, free, char, free); +DEFINE_HASH_OPS_FULL(custom_hash_ops, char, string_hash_func, string_compare_func, custom_destruct, char, custom_destruct); + void test_hashmap_funcs(void); void test_ordered_hashmap_funcs(void); -- 2.47.3