Date: Sat, 16 Aug 2008 08:14:36 GMT From: Mayur Shardul <mayur@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 147510 for review Message-ID: <200808160814.m7G8EaJh061676@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=147510 Change 147510 by mayur@mayur_freebsd_vm on 2008/08/16 08:14:23 Performance benchmarking. Affected files ... .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#3 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#2 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/splay_tree.c#2 edit Differences ... ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#3 (text+ko) ==== @@ -205,7 +205,7 @@ slot = get_slot(index,rtree,level); if (tmp->rn_children[slot] != NULL) - printf("radix_tree_insert: value already present in the tree\n"); + if(0) printf("radix_tree_insert: value already present in the tree\n"); else tmp->rn_children_count++; /*we will overwrite the old value with the new value*/ @@ -233,7 +233,7 @@ slot = get_slot(index,rtree,level); if (level == 0){ if (tmp->rn_children[slot] == NULL) - printf("radix_tree_lookup: index %d not present\n" + if(0)printf("radix_tree_lookup: index %d not present\n" ,index); return tmp->rn_children[slot]; ==== //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#2 (text+ko) ==== @@ -6,6 +6,7 @@ #include "radix_tree.h" #define N 0xffff +#define X 0xfff extern int main(void) @@ -13,10 +14,70 @@ unsigned long long splay, radix; struct radix_tree *rtree; int i,j; - int vals[N]; + int vals[N], lookups[N],inserts[N],removes[N]; + unsigned long long t_start, t_end; rtree = create_radix_tree(4); - splay_insert(10); - splay_lookup(10); + for(i = 0; i < N; i++){ + vals[i] = random(); + /* about 50% are hits*/ + lookups[i] = ( i % 2 ? vals[i] : random()); + inserts[i] = random(); + } + + for(i = 0; i < X; i++){ + j = random(); + splay_insert(j); + radix_tree_insert(j, rtree, &i); + } + printf("Measuring time for %d lookup operations on radix tree with" + " %d elements\n", N, X); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + radix_tree_lookup(lookups[i],rtree); + } + t_end = rdtsc(); + printf("TSC difference after lookups: %lld\n", (t_end - t_start)); + printf("\n\n\nMeasuring time for %d lookup operations on splay tree with" + " %d elements\n", N, X); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + splay_lookup(lookups[i]); + } + t_end = rdtsc(); + printf("TSC difference after lookups: %lld\n", (t_end - t_start)); + + printf("\n\n\nMeasuring time for %d inserts on radix tree with" + " %d elements\n", N, X); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + radix_tree_insert(inserts[i],rtree,&inserts[i]); + } + t_end = rdtsc(); + printf("TSC difference after inserts: %lld\n", (t_end - t_start)); + printf("Measuring time for %d inserts on splay tree with" + "%d elements\n", N, X); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + splay_insert(inserts[i]); + } + t_end = rdtsc(); + printf("TSC difference after inserts: %lld\n", (t_end - t_start)); + + + printf("\n\n\nMeasuring time for %d removes on radix tree\n", N); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + radix_tree_remove(inserts[i],rtree); + } + t_end = rdtsc(); + printf("TSC difference after removes: %lld\n", (t_end - t_start)); + printf("Measuring time for %d removes on splay tree\n", N); + t_start = rdtsc(); + for(i = 0; i < N; i++){ + splay_remove(inserts[i]); + } + t_end = rdtsc(); + printf("TSC difference after removes: %lld\n", (t_end - t_start)); } ==== //depot/projects/soc2008/mayur_vmalgo/uspace/splay_tree.c#2 (text+ko) ==== @@ -38,14 +38,8 @@ unsigned long long splay_lookup(int pindex) { struct stidx *t = (struct stidx *)malloc(sizeof(struct stidx)); - struct stidx *p = NULL; unsigned long long start, end; t->pindex = pindex; - start = rdtsc(); - p = SPLAY_FIND(splay_tree, &stree, t); - end = rdtsc(); - if(p == NULL){ - printf("Bug!\n"); - } + SPLAY_FIND(splay_tree, &stree, t); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200808160814.m7G8EaJh061676>