PERFORCE change 147591 for review

[Mayur Shardul]

http://perforce.freebsd.org/chv.cgi?CH=147591

Change 147591 by mayur at 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]);