From 8b83ecf3a2c7f52e2f5a6e23d330fea43e917fce Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sat, 29 Oct 2016 10:20:34 +1030 Subject: [PATCH] jmap: fix tools/speed Minor fixes on top of patch from rocco@tecsiel.it: Hi Rusty, latest git version of the file ccan/jmap/tools/speed.c does not compile. Please find attacched my own version with the following differences: 1. deleted inclusion of which is no longer in ccan/ 2. added inclusion of 3. added definition of struct jmap_obj in terms of JMAP_MEMBERS(); 4. deleted use of macro JMAP_DEFINE_UINTIDX_TYPE() which is no longer needed 5. changed function normalize() to be aligned with ccan/htable/tools/speed.c 6. repleaced gettimeofday() in favour of time_now() 7. added memory cleanup at the end of the program in terms of jmap_free(jmap); free(objs); to be valgrind safe Signed-off-by: Rusty Russell --- ccan/jmap/tools/Makefile | 4 +- ccan/jmap/tools/speed.c | 155 +++++++++++++++++++-------------------- 2 files changed, 79 insertions(+), 80 deletions(-) diff --git a/ccan/jmap/tools/Makefile b/ccan/jmap/tools/Makefile index b9f07b98..efb46698 100644 --- a/ccan/jmap/tools/Makefile +++ b/ccan/jmap/tools/Makefile @@ -1,6 +1,6 @@ CFLAGS=-Wall -Werror -O3 -I../../.. -LDFLAGS=-lJudy +LDLIBS=-lJudy speed: speed.o -speed.o: speed.c ../jmap.h ../jmap_type.h ../jmap.c +speed.o: speed.c ../jmap.h diff --git a/ccan/jmap/tools/speed.c b/ccan/jmap/tools/speed.c index d2ecd6f6..6cd6d479 100644 --- a/ccan/jmap/tools/speed.c +++ b/ccan/jmap/tools/speed.c @@ -1,38 +1,33 @@ /* Simple speed tests for jmap. */ -#include #include +#include #include #include -#include #include -#include struct object { /* Some contents. Doubles as consistency check. */ struct object *self; }; +struct jmap_obj { + JMAP_MEMBERS(unsigned int, struct object *); +}; + /* 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)); } -JMAP_DEFINE_UINTIDX_TYPE(struct object, obj); - int main(int argc, char *argv[]) { struct object *objs; - size_t i, j, num; - struct timeval start, stop; + unsigned int i, j; + size_t num; + struct timeabs start, stop; struct jmap_obj *jmap; num = argv[1] ? atoi(argv[1]) : 1000000; @@ -42,110 +37,110 @@ int main(int argc, char *argv[]) objs[i].self = &objs[i]; } - jmap = jmap_obj_new(); + jmap = jmap_new(struct jmap_obj); printf("Initial insert: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - jmap_obj_add(jmap, i, objs[i].self); - gettimeofday(&stop, NULL); + jmap_add(jmap, i, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Initial lookup (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - if (jmap_obj_get(jmap, i)->self != objs[i].self) + if (jmap_get(jmap, 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++) - if (jmap_obj_get(jmap, i+num)) + if (jmap_get(jmap, i+num)) 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 (jmap_obj_get(jmap, j)->self != &objs[j]) + if (jmap_get(jmap, j)->self != &objs[j]) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Initial delete all: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - jmap_obj_del(jmap, i); - gettimeofday(&stop, NULL); + jmap_del(jmap, i); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Initial re-inserting: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - jmap_obj_add(jmap, i, objs[i].self); - gettimeofday(&stop, NULL); + jmap_add(jmap, i, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Deleting first half: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - jmap_obj_del(jmap, i); - gettimeofday(&stop, NULL); + jmap_del(jmap, i); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Adding (a different) half: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - jmap_obj_add(jmap, num+i, objs[i].self); - gettimeofday(&stop, NULL); + jmap_add(jmap, num+i, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Lookup after half-change (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 1; i < num; i+=2) - if (jmap_obj_get(jmap, i)->self != objs[i].self) + if (jmap_get(jmap, i)->self != objs[i].self) abort(); for (i = 0; i < num; i+=2) - if (jmap_obj_get(jmap, i+num)->self != objs[i].self) + if (jmap_get(jmap, i+num)->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++) - if (jmap_obj_get(jmap, i+num*2)) + if (jmap_get(jmap, i+num*2)) 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. * so do some changes to see how it operates in long-term. */ printf("Details: churning first time\n"); for (i = 1; i < num; i+=2) { - if (!jmap_obj_del(jmap, i)) + if (!jmap_del(jmap, i)) abort(); - jmap_obj_add(jmap, i, objs[i].self); + jmap_add(jmap, i, objs[i].self); } for (i = 0; i < num; i+=2) { - if (!jmap_obj_del(jmap, i+num)) + if (!jmap_del(jmap, i+num)) abort(); - jmap_obj_add(jmap, i, objs[i].self); + jmap_add(jmap, i, objs[i].self); } for (i = 1; i < 5; i++) { printf("Churning %s time: ", @@ -154,84 +149,88 @@ int main(int argc, char *argv[]) : i == 3 ? "fourth" : "fifth"); fflush(stdout); - gettimeofday(&start, NULL); + + start = time_now(); for (j = 0; j < num; j++) { - if (!jmap_obj_del(jmap, num*(i-1)+j)) + if (!jmap_del(jmap, num*(i-1)+j)) abort(); - jmap_obj_add(jmap, num*i+j, &objs[j]); + jmap_add(jmap, num*i+j, &objs[j]); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); } /* Spread out the keys more to try to make it harder. */ printf("Details: reinserting with spread\n"); for (i = 0; i < num; i++) { - if (!jmap_obj_del(jmap, num*4 + i)) + if (!jmap_del(jmap, num*4 + i)) abort(); - jmap_obj_add(jmap, num * 5 + i * 9, objs[i].self); + jmap_add(jmap, num * 5 + i * 9, objs[i].self); } - if (jmap_obj_popcount(jmap, 0, -1) != num) + if (jmap_popcount(jmap, 0, -1) != num) abort(); printf("Lookup after churn & spread (match): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i++) - if (jmap_obj_get(jmap, num * 5 + i * 9)->self != objs[i].self) { + if (jmap_get(jmap, num * 5 + i * 9)->self != objs[i].self) { printf("i =%u\n", i); 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++) - if (jmap_obj_get(jmap, num * 6 + i * 9)) + if (jmap_get(jmap, num * 6 + i * 9)) 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) - if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j]) + if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j]) abort(); - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Lookup after churn & spread (half-random): "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0, j = 0; i < num/2; i++, j = (j + 10007) % num) { - if (jmap_obj_get(jmap, num * 5 + j * 9)->self != &objs[j]) + if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j]) abort(); - if (jmap_obj_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1]) + if (jmap_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1]) abort(); } - gettimeofday(&stop, NULL); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Deleting half after churn & spread: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - jmap_obj_del(jmap, num * 5 + i * 9); - gettimeofday(&stop, NULL); + jmap_del(jmap, num * 5 + i * 9); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Adding (a different) half after churn & spread: "); fflush(stdout); - gettimeofday(&start, NULL); + start = time_now(); for (i = 0; i < num; i+=2) - jmap_obj_add(jmap, num * 6 + i * 9, objs[i].self); - gettimeofday(&stop, NULL); + jmap_add(jmap, num * 6 + i * 9, objs[i].self); + stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); + jmap_free(jmap); + free (objs); + return 0; } -- 2.39.2