PERFORCE change 147630 for review

[Mayur Shardul]

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

Change 147630 by mayur at 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]);
+	}
+}
+
+