Date: Sun, 17 Aug 2008 07:04:41 GMT From: Mayur Shardul <mayur@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 147630 for review Message-ID: <200808170704.m7H74fhQ064049@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=147630 Change 147630 by mayur@mayur_freebsd_vm on 2008/08/17 07:04:37 benchmarking object of different sizes Affected files ... .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#5 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.h#3 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#5 edit Differences ... ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#5 (text+ko) ==== @@ -92,7 +92,8 @@ if(!SLIST_EMPTY(&res_rnodes_head)){ rnode = SLIST_FIRST(&res_rnodes_head); SLIST_REMOVE_HEAD(&res_rnodes_head, next); - bzero((void *)rnode, sizeof(struct radix_node)); + bzero((void *)rnode, sizeof(struct radix_node) + + sizeof(void *) * (MASK(rtree->rt_bits_per_level) + 1)); return rnode; } return NULL; @@ -174,6 +175,10 @@ /*just add a node at required height*/ while (index > max_index(rtree,rtree->rt_height)) rtree->rt_height++; + + /* this happens when index == 0*/ + if(rtree->rt_height == 0) + rtree->rt_height = 1; rnode = get_radix_node(rtree); if (rnode == NULL){ return (ENOMEM); @@ -311,8 +316,9 @@ if (level == 0){ val = tmp->rn_children[slot]; if (tmp->rn_children[slot] == NULL){ - printf("radix_tree_remove: index %d not present in the tree.\n", - index); + //printf("radix_tree_remove: index " + // " %d not present in the tree.\n", + // index); return NULL; } tmp->rn_children[slot] = NULL; @@ -483,11 +489,13 @@ void radix_tree_init(){ int i; char *mem = (char *)malloc(RESERVED_NODE_COUNT * - sizeof(struct radix_node)); + (sizeof(struct radix_node) + + sizeof(void *) * (MASK(4) + 1))); for(i = 0; i < RESERVED_NODE_COUNT; i++) { SLIST_INSERT_HEAD(&res_rnodes_head, (struct radix_node *)mem, next); - mem += sizeof(struct radix_node); + mem += (sizeof(struct radix_node) + + (sizeof(void *) * (MASK(4) + 1))); } } ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.h#3 (text+ko) ==== @@ -30,4 +30,5 @@ void *radix_tree_remove(rtidx_t index, struct radix_tree *rtree); void *radix_tree_lookup(rtidx_t index, struct radix_tree *rtree); void radix_tree_shrink(struct radix_tree *rtree); +void radix_tree_init(void); #endif ==== //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#5 (text+ko) ==== @@ -8,25 +8,24 @@ #define N 0xffff #define X 0xfff -extern -int main(void) -{ +void benchmark(int max_idx){ unsigned long long splay, radix; struct radix_tree *rtree; int i,j; int vals[N], lookups[N],inserts[N],removes[N]; unsigned long long t_start, t_end,t; - + + radix_tree_init(); rtree = create_radix_tree(4); for(i = 0; i < N; i++){ - vals[i] = random(); + vals[i] = random() % max_idx; /* about 50% are hits*/ - lookups[i] = ( i % 2 ? vals[i] : random()); - inserts[i] = random(); + lookups[i] = ( i % 2 ? vals[i] : (random() % max_idx)); + inserts[i] = random() % max_idx; } for(i = 0; i < X; i++){ - j = random(); + j = random() % max_idx; splay_insert(j); radix_tree_insert(j, rtree, &i); } @@ -80,3 +79,17 @@ printf("TSC difference after removes: %lld\n", (t_end - t_start)); } +extern +int main(void) +{ + int max_idx[] = {2, 16, 64, 256, 1024, 4096, 262144}; + int i; + + for(i = 0; i < 7; i++){ + printf("\n==== Benchmarking with max index = %d \n", + max_idx[i]); + benchmark(max_idx[i]); + } +} + +
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200808170704.m7H74fhQ064049>