X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhtable%2Ftools%2Fspeed.c;h=e185b6f69eb74f3435789d82abe144eb32d8d1ca;hp=72a08e6b4cd1e253b14436e644d5ab5d5608739f;hb=HEAD;hpb=78e983a7a6e5250ebf963d5d93fe34c1d27d5a39 diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c index 72a08e6b..e185b6f6 100644 --- a/ccan/htable/tools/speed.c +++ b/ccan/htable/tools/speed.c @@ -2,11 +2,11 @@ #include #include #include +#include #include #include -#include +#include #include -#include static size_t hashcount; struct object { @@ -28,12 +28,12 @@ static size_t hash_obj(const unsigned int *key) return hashl(key, 1, 0); } -static bool cmp(const unsigned int *key1, const unsigned int *key2) +static bool cmp(const struct object *object, const unsigned int *key) { - return *key1 == *key2; + return object->key == *key; } -HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj); +HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj); static unsigned int popcount(unsigned long val) { @@ -74,8 +74,8 @@ static size_t perfect(const struct htable *ht) continue; if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]), ht->priv)) == i) { - assert((ht->table[i] & ht->perfect_bit) - == ht->perfect_bit); + assert((ht->table[i] & ht_perfect_mask(ht)) + == ht_perfect_mask(ht)); placed_perfect++; } } @@ -94,17 +94,11 @@ static size_t count_deleted(const struct htable *ht) } /* Nanoseconds per operation */ -static size_t normalize(const struct timeval *start, - const struct timeval *stop, +static size_t normalize(const struct timeabs *start, + const struct timeabs *stop, unsigned int num) { - struct timeval diff; - - timersub(stop, start, &diff); - - /* Floating point is more accurate here. */ - return (double)(diff.tv_sec * 1000000 + diff.tv_usec) - / num * 1000; + return time_to_nsec(time_divide(time_between(*stop, *start), num)); } static size_t worst_run(struct htable *ht, size_t *deleted) @@ -133,10 +127,10 @@ static size_t worst_run(struct htable *ht, size_t *deleted) int main(int argc, char *argv[]) { struct object *objs; - size_t i, j, num, deleted; - struct timeval start, stop; - struct htable_obj *ht; - struct htable *htr; + unsigned int i, j; + size_t num, deleted; + struct timeabs start, stop; + struct htable_obj ht; bool make_dumb = false; if (argv[1] && strcmp(argv[1], "--dumb") == 0) { @@ -151,88 +145,87 @@ int main(int argc, char *argv[]) objs[i].self = &objs[i]; } - ht = htable_obj_new(); - htr = (void *)ht; + htable_obj_init(&ht); printf("Initial insert: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - htable_obj_add(ht, objs[i].self); - gettimeofday(&stop, NULL); + htable_obj_add(&ht, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n", - 1U << htr->bits, popcount(htr->common_mask), - perfect(htr) * 100.0 / htr->elems); + 1U << ht.raw.bits, popcount(ht.raw.common_mask), + perfect(&ht.raw) * 100.0 / ht.raw.elems); if (make_dumb) { /* Screw with mask, to hobble us. */ - update_common(htr, (void *)~htr->common_bits); + update_common(&ht.raw, (void *)~ht.raw.common_bits); printf("Details: DUMB MODE: mask bits %u\n", - popcount(htr->common_mask)); + popcount(ht.raw.common_mask)); } printf("Initial lookup (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - if (htable_obj_get(ht, &i)->self != objs[i].self) + if (htable_obj_get(&ht, &i)->self != objs[i].self) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Initial lookup (miss): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) { unsigned int n = i + num; - if (htable_obj_get(ht, &n)) + if (htable_obj_get(&ht, &n)) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); /* Lookups in order are very cache-friendly for judy; try random */ printf("Initial lookup (random): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) - if (htable_obj_get(ht, &j)->self != &objs[j]) + if (htable_obj_get(&ht, &j)->self != &objs[j]) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); hashcount = 0; printf("Initial delete all: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: rehashes %zu\n", hashcount); printf("Initial re-inserting: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - htable_obj_add(ht, objs[i].self); - gettimeofday(&stop, NULL); + htable_obj_add(&ht, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); hashcount = 0; printf("Deleting first half: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: rehashes %zu, delete markers %zu\n", - hashcount, count_deleted(htr)); + hashcount, count_deleted(&ht.raw)); printf("Adding (a different) half: "); fflush(stdout); @@ -240,38 +233,38 @@ int main(int argc, char *argv[]) for (i = 0; i < num; i+=2) objs[i].key = num+i; - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - htable_obj_add(ht, objs[i].self); - gettimeofday(&stop, NULL); + htable_obj_add(&ht, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); printf("Lookup after half-change (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 1; i < num; i+=2) - if (htable_obj_get(ht, &i)->self != objs[i].self) + if (htable_obj_get(&ht, &i)->self != objs[i].self) abort(); for (i = 0; i < num; i+=2) { unsigned int n = i + num; - if (htable_obj_get(ht, &n)->self != objs[i].self) + if (htable_obj_get(&ht, &n)->self != objs[i].self) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Lookup after half-change (miss): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) { unsigned int n = i + num * 2; - if (htable_obj_get(ht, &n)) + if (htable_obj_get(&ht, &n)) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); /* Hashtables with delete markers can fill with markers over time. @@ -288,15 +281,15 @@ int main(int argc, char *argv[]) : "fifth"); fflush(stdout); } - gettimeofday(&start, NULL); + start = time_now(); for (j = 0; j < num; j++) { - if (!htable_obj_del(ht, &objs[j])) + if (!htable_obj_del(&ht, &objs[j])) abort(); objs[j].key = num*i+j; - if (!htable_obj_add(ht, &objs[j])) + if (!htable_obj_add(&ht, &objs[j])) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); if (i != 0) printf(" %zu ns\n", normalize(&start, &stop, num)); } @@ -304,58 +297,58 @@ int main(int argc, char *argv[]) /* Spread out the keys more to try to make it harder. */ printf("Details: reinserting with spread\n"); for (i = 0; i < num; i++) { - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); objs[i].key = num * 5 + i * 9; - if (!htable_obj_add(ht, objs[i].self)) + if (!htable_obj_add(&ht, objs[i].self)) abort(); } printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); - i = worst_run(htr, &deleted); - printf("Details: worst run %zu (%zu deleted)\n", i, deleted); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); + i = worst_run(&ht.raw, &deleted); + printf("Details: worst run %u (%zu deleted)\n", i, deleted); printf("Lookup after churn & spread (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) { unsigned int n = num * 5 + i * 9; - if (htable_obj_get(ht, &n)->self != objs[i].self) + if (htable_obj_get(&ht, &n)->self != objs[i].self) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Lookup after churn & spread (miss): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) { - unsigned int n = num * 6 + i * 9; - if (htable_obj_get(ht, &n)) + unsigned int n = num * (5 + 9) + i * 9; + if (htable_obj_get(&ht, &n)) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Lookup after churn & spread (random): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) { unsigned int n = num * 5 + j * 9; - if (htable_obj_get(ht, &n)->self != &objs[j]) + if (htable_obj_get(&ht, &n)->self != &objs[j]) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); hashcount = 0; printf("Deleting half after churn & spread: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Adding (a different) half after churn & spread: "); @@ -364,14 +357,14 @@ int main(int argc, char *argv[]) for (i = 0; i < num; i+=2) objs[i].key = num*6+i*9; - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - htable_obj_add(ht, objs[i].self); - gettimeofday(&stop, NULL); + htable_obj_add(&ht, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); return 0; }