From owner-p4-projects@FreeBSD.ORG Sun Aug 17 07:04:42 2008 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 421561065673; Sun, 17 Aug 2008 07:04:42 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 0684C106566B for ; Sun, 17 Aug 2008 07:04:42 +0000 (UTC) (envelope-from mayur@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [IPv6:2001:4f8:fff6::29]) by mx1.freebsd.org (Postfix) with ESMTP id EDAE08FC13 for ; Sun, 17 Aug 2008 07:04:41 +0000 (UTC) (envelope-from mayur@FreeBSD.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.2/8.14.2) with ESMTP id m7H74fNK064051 for ; Sun, 17 Aug 2008 07:04:41 GMT (envelope-from mayur@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.2/8.14.1/Submit) id m7H74fhQ064049 for perforce@freebsd.org; Sun, 17 Aug 2008 07:04:41 GMT (envelope-from mayur@FreeBSD.org) Date: Sun, 17 Aug 2008 07:04:41 GMT Message-Id: <200808170704.m7H74fhQ064049@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to mayur@FreeBSD.org using -f From: Mayur Shardul To: Perforce Change Reviews Cc: Subject: PERFORCE change 147630 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 17 Aug 2008 07:04:42 -0000 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]); + } +} + +