From owner-p4-projects@FreeBSD.ORG Sat Aug 16 20:35:45 2008 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 56D29106567F; Sat, 16 Aug 2008 20:35:45 +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 1A48E106567C for ; Sat, 16 Aug 2008 20:35:45 +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 070518FC0C for ; Sat, 16 Aug 2008 20:35:45 +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 m7GKZijU068575 for ; Sat, 16 Aug 2008 20:35:44 GMT (envelope-from mayur@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.2/8.14.1/Submit) id m7GKZi1x068573 for perforce@freebsd.org; Sat, 16 Aug 2008 20:35:44 GMT (envelope-from mayur@FreeBSD.org) Date: Sat, 16 Aug 2008 20:35:44 GMT Message-Id: <200808162035.m7GKZi1x068573@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 147591 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: Sat, 16 Aug 2008 20:35:45 -0000 http://perforce.freebsd.org/chv.cgi?CH=147591 Change 147591 by mayur@mayur_freebsd_vm on 2008/08/16 20:35:00 Benchmarking with preallocation Affected files ... .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#4 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#4 edit Differences ... ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#4 (text+ko) ==== @@ -24,7 +24,10 @@ /* Default values of the tree parameters */ #define DEFAULT_BITS_PER_LEVEL 8 #define DEFAULT_MAX_HEIGHT 4 +#define RESERVED_NODE_COUNT 0xfffff +SLIST_HEAD(, radix_node) res_rnodes_head = + SLIST_HEAD_INITIALIZER(res_rnodes_head); /* * init_radix_tree: @@ -69,6 +72,7 @@ struct radix_node * get_radix_node(struct radix_tree *rtree) { + /* struct radix_node *rnode; int children_cnt; @@ -82,6 +86,16 @@ bzero(rnode, sizeof(struct radix_node)+ sizeof(void *)*children_cnt); return rnode; + */ + struct radix_node *rnode; + + 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)); + return rnode; + } + return NULL; } /* @@ -92,7 +106,8 @@ void put_radix_node( struct radix_node *rnode, struct radix_tree *rtree) { - free(rnode); + //free(rnode); + SLIST_INSERT_HEAD(&res_rnodes_head,rnode,next); } /* @@ -463,3 +478,16 @@ rtree->rt_root = NULL; } } + + +void radix_tree_init(){ + int i; + char *mem = (char *)malloc(RESERVED_NODE_COUNT * + sizeof(struct radix_node)); + for(i = 0; i < RESERVED_NODE_COUNT; i++) + { + SLIST_INSERT_HEAD(&res_rnodes_head, (struct radix_node *)mem, + next); + mem += sizeof(struct radix_node); + } +} ==== //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#4 (text+ko) ==== @@ -38,7 +38,7 @@ } 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" + printf("Measuring time for %d lookup operations on splay tree with" " %d elements\n", N, X); t_start = rdtsc(); for(i = 0; i < N; i++){ @@ -56,7 +56,7 @@ 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); + " %d elements\n", N, X); t = 0; for(i = 0; i < N; i++){ t += splay_insert(inserts[i]);