PERFORCE change 147510 for review

[Mayur Shardul]

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

Change 147510 by mayur at mayur_freebsd_vm on 2008/08/16 08:14:23

	Performance benchmarking.

Affected files ...

.. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#3 edit
.. //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#2 edit
.. //depot/projects/soc2008/mayur_vmalgo/uspace/splay_tree.c#2 edit

Differences ...

==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#3 (text+ko) ====

@@ -205,7 +205,7 @@
 
 	slot = get_slot(index,rtree,level);
 	if (tmp->rn_children[slot] != NULL)
-		printf("radix_tree_insert: value already present in the tree\n");
+		if(0) printf("radix_tree_insert: value already present in the tree\n");
 	else
 		tmp->rn_children_count++;
 	/*we will overwrite the old value with the new value*/
@@ -233,7 +233,7 @@
 		slot = get_slot(index,rtree,level);
 		if (level == 0){
 			if (tmp->rn_children[slot] == NULL)
-				printf("radix_tree_lookup: index %d not	present\n"
+				if(0)printf("radix_tree_lookup: index %d not	present\n"
 				    ,index);
 		
 			return tmp->rn_children[slot];

==== //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_stree.c#2 (text+ko) ====

@@ -6,6 +6,7 @@
 #include "radix_tree.h"
 
 #define N 0xffff
+#define X 0xfff
 
 extern 
 int main(void)
@@ -13,10 +14,70 @@
 	unsigned long long splay, radix;
 	struct radix_tree *rtree;
 	int i,j;
-	int vals[N];
+	int vals[N], lookups[N],inserts[N],removes[N];
+	unsigned long long t_start, t_end;
 
 	rtree = create_radix_tree(4);
-	splay_insert(10);
-	splay_lookup(10);
+	for(i = 0; i < N; i++){
+		vals[i] = random();
+		/* about 50% are hits*/
+		lookups[i] = ( i % 2 ? vals[i] : random());
+		inserts[i] = random();
+	}
+
+	for(i = 0; i < X; i++){
+		j = random();
+		splay_insert(j);
+		radix_tree_insert(j, rtree, &i);
+	}
+	printf("Measuring time for %d lookup operations on radix tree with"
+		" %d elements\n", N, X);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		radix_tree_lookup(lookups[i],rtree);
+	}
+	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"
+		" %d elements\n", N, X);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		splay_lookup(lookups[i]);
+	}
+	t_end = rdtsc();
+	printf("TSC difference after lookups: %lld\n", (t_end - t_start));
+
+	printf("\n\n\nMeasuring time for %d inserts on radix tree with"
+	       " %d elements\n", N, X);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		radix_tree_insert(inserts[i],rtree,&inserts[i]);
+	}
+	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);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		splay_insert(inserts[i]);
+	}
+	t_end = rdtsc();
+	printf("TSC difference after inserts: %lld\n", (t_end - t_start));
+
+
+	printf("\n\n\nMeasuring time for %d removes on radix tree\n", N);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		radix_tree_remove(inserts[i],rtree);
+	}
+	t_end = rdtsc();
+	printf("TSC difference after removes: %lld\n", (t_end - t_start));
+	printf("Measuring time for %d removes on splay tree\n", N);
+	t_start = rdtsc();
+	for(i = 0; i < N; i++){
+		splay_remove(inserts[i]);
+	}
+	t_end = rdtsc();
+	printf("TSC difference after removes: %lld\n", (t_end - t_start));
 
 }

==== //depot/projects/soc2008/mayur_vmalgo/uspace/splay_tree.c#2 (text+ko) ====

@@ -38,14 +38,8 @@
 unsigned long long splay_lookup(int pindex)
 {
 	struct stidx *t = (struct stidx *)malloc(sizeof(struct stidx));
-	struct stidx *p = NULL;
 	unsigned long long start, end;
 	
 	t->pindex = pindex;
-	start = rdtsc();
-	p = SPLAY_FIND(splay_tree, &stree, t);
-	end = rdtsc();
-	if(p == NULL){
-		printf("Bug!\n");
-	}
+	SPLAY_FIND(splay_tree, &stree, t);
 }