From: Rusty Russell Date: Mon, 26 Mar 2018 10:27:12 +0000 (+1030) Subject: intmap: add benchmarks. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=82229812012a9cc9a4876b9542f5539ec99ece46;hp=eb10bf9f4e37a73bae203dab71a4daffa2c96229 intmap: add benchmarks. I wrote these a while ago, dig them out. On my laptop, min-max(avg+/-stdev) of 5 runs: make && for i in `seq 5`; do ./speed 10000000; done | stats make: Nothing to be done for 'all'. 10000000,random generation (nsec),3-4(3.2+/-0.4) 10000000,critbit insert (nsec),1530-1751(1633.2+/-80) 10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97) 10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02) 10000000,critbit iteration (nsec),208-266(242.2+/-19) 10000000,critbit memory (bytes),48 10000000,critbit delete (nsec),1747-1861(1803.8+/-42) 10000000,critbit consecutive iteration (nsec),182-228(210+/-18) 10000000,hash insert (nsec),396-424(412+/-9.6) 10000000,hash successful lookup (nsec),150-164(157.4+/-5.5) 10000000,hash failed lookup (nsec),163-178(170+/-5.5) 10000000,hash iteration (nsec),21-26(23.2+/-1.7) 10000000,hash memory (bytes),45 10000000,hash delete (nsec),179-194(183.6+/-5.3) Signed-off-by: Rusty Russell --- diff --git a/ccan/intmap/benchmark/Makefile b/ccan/intmap/benchmark/Makefile new file mode 100644 index 00000000..bebc6161 --- /dev/null +++ b/ccan/intmap/benchmark/Makefile @@ -0,0 +1,24 @@ +CCANDIR=../../.. +CFLAGS=-Wall -Werror -O3 -I$(CCANDIR) -flto +#CFLAGS=-Wall -Werror -g3 -I$(CCANDIR) +LDFLAGS := -flto -O3 + +all: speed + +CCAN_OBJS:=ccan-intmap.o ccan-time.o ccan-isaac64.o ccan-htable.o ccan-siphash24.o + +speed: speed.o $(CCAN_OBJS) + +clean: + rm -f speed *.o + +ccan-time.o: $(CCANDIR)/ccan/time/time.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-intmap.o: $(CCANDIR)/ccan/intmap/intmap.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-isaac64.o: $(CCANDIR)/ccan/isaac/isaac64.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-htable.o: $(CCANDIR)/ccan/htable/htable.c + $(CC) $(CFLAGS) -c -o $@ $< +ccan-siphash24.o: $(CCANDIR)/ccan/crypto/siphash24/siphash24.c + $(CC) $(CFLAGS) -c -o $@ $< diff --git a/ccan/intmap/benchmark/speed.c b/ccan/intmap/benchmark/speed.c new file mode 100644 index 00000000..7f59af29 --- /dev/null +++ b/ccan/intmap/benchmark/speed.c @@ -0,0 +1,227 @@ +/* Test speed of intmap */ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* hack to let us gather span. */ +struct node { + /* These point to strings or nodes. */ + struct intmap child[2]; + /* The bit where these children differ (0 == lsb) */ + uint8_t bit_num; +}; + +static void update_span(const void *p, size_t s, uintptr_t *min, uintptr_t *max) +{ + if ((uintptr_t)p < *min) + *min = (uintptr_t)p; + if ((uintptr_t)p + s > *max) + *max = (uintptr_t)p + s; +} + +static void getspan(const struct intmap *m, uintptr_t *min, uintptr_t *max) +{ + struct node *n; + /* Leaf node? */ + if (m->v) + return; + + n = m->u.n; + update_span(n, sizeof(*n), min, max); + getspan(&n->child[0], min, max); + getspan(&n->child[1], min, max); +} + +struct htable_elem { + uint64_t index; + uint64_t *v; +}; + +static struct siphash_seed sipseed; + +static uint64_t keyof(const struct htable_elem *elem) +{ + return elem->index; +} + +static size_t hashfn(const uint64_t index) +{ + return siphash24(&sipseed, &index, sizeof(index)); +} + +static bool eqfn(const struct htable_elem *elem, const uint64_t index) +{ + return elem->index == index; +} +HTABLE_DEFINE_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash); + +int main(int argc, char *argv[]) +{ + uint64_t i, total = 0, seed, *v; + size_t max = argv[1] ? atol(argv[1]) : 100000000; + isaac64_ctx isaac; + struct timeabs start, end; + UINTMAP(uint64_t *) map; + struct hash hash; + struct htable_elem *e; + struct hash_iter it; + uintptr_t span_min, span_max; + + uintmap_init(&map); + hash_init(&hash); + + /* We don't want our randomness function to dominate the time, + * nor deal with duplicates (just abort, that's v. unlikely) */ + seed = time_now().ts.tv_sec + time_now().ts.tv_nsec; + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + + start = time_now(); + for (i = 0; i < max; i++) + total += isaac64_next_uint64(&isaac); + end = time_now(); + printf("%zu,random generation (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + if (!uintmap_add(&map, isaac64_next_uint64(&isaac), &i)) + abort(); + } + end = time_now(); + printf("%zu,critbit insert (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + if (uintmap_get(&map, isaac64_next_uint64(&isaac)) != &i) + abort(); + } + end = time_now(); + printf("%zu,critbit successful lookup (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + start = time_now(); + for (i = 0; i < max; i++) { + if (uintmap_get(&map, isaac64_next_uint64(&isaac))) + abort(); + } + end = time_now(); + printf("%zu,critbit failed lookup (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) { + if (v != &i) + abort(); + } + end = time_now(); + printf("%zu,critbit iteration (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + span_min = -1ULL; + span_max = 0; + getspan(uintmap_unwrap_(&map), &span_min, &span_max); + printf("%zu,critbit memory (bytes),%zu\n", + max, (size_t)(span_max - span_min + max / 2) / max); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + if (!uintmap_del(&map, isaac64_next_uint64(&isaac))) + abort(); + } + end = time_now(); + printf("%zu,critbit delete (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + /* Fill with consecutive values */ + for (i = 0; i < max; i++) { + if (!uintmap_add(&map, i, &i)) + abort(); + } + start = time_now(); + for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) { + if (v != &i) + abort(); + } + end = time_now(); + printf("%zu,critbit consecutive iteration (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + sipseed.u.u64[0] = isaac64_next_uint64(&isaac); + sipseed.u.u64[1] = isaac64_next_uint64(&isaac); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + e = malloc(sizeof(*e)); + e->v = &i; + e->index = isaac64_next_uint64(&isaac); + hash_add(&hash, e); + } + end = time_now(); + printf("%zu,hash insert (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + if (hash_get(&hash, isaac64_next_uint64(&isaac))->v != &i) + abort(); + } + end = time_now(); + printf("%zu,hash successful lookup (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + start = time_now(); + for (i = 0; i < max; i++) { + if (hash_get(&hash, isaac64_next_uint64(&isaac))) + abort(); + } + end = time_now(); + printf("%zu,hash failed lookup (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it)) { + if (e->v != &i) + abort(); + } + end = time_now(); + printf("%zu,hash iteration (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + span_min = -1ULL; + span_max = 0; + for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it)) + update_span(e, sizeof(*e), &span_min, &span_max); + /* table itself tends to be allocated in separate memory. */ + span_max += (sizeof(uintptr_t) << hash.raw.bits); + printf("%zu,hash memory (bytes),%zu\n", + max, (size_t)(span_max - span_min + max / 2) / max); + + isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed)); + start = time_now(); + for (i = 0; i < max; i++) { + e = hash_get(&hash, isaac64_next_uint64(&isaac)); + if (!hash_del(&hash, e)) + abort(); + free(e); + } + end = time_now(); + printf("%zu,hash delete (nsec),%"PRIu64"\n", max, + time_to_nsec(time_divide(time_between(end, start), max))); + + /* Use total, but "never happens". */ + return (total == 0); +}