tracker r2052 - in branches/indexer-split: . src/libtracker-db

[carlosg svn gnome org]

Author: carlosg
Date: Tue Aug 12 12:49:02 2008
New Revision: 2052
URL: http://svn.gnome.org/viewvc/tracker?rev=2052&view=rev

Log:
2008-08-12  Carlos Garnacho  <carlos imendio com>

        * src/libtracker-db/tracker-db-index.c (indexer_update_word): Improve
        performance CPU-wise when inserting words into the index. Perform
        binary searches on previous hits, since insertions are guaranteed to
        be ordered. Shift array over deleted values with g_memmove().


Modified:
   branches/indexer-split/ChangeLog
   branches/indexer-split/src/libtracker-db/tracker-db-index.c

Modified: branches/indexer-split/src/libtracker-db/tracker-db-index.c
==============================================================================
--- branches/indexer-split/src/libtracker-db/tracker-db-index.c	(original)
+++ branches/indexer-split/src/libtracker-db/tracker-db-index.c	Tue Aug 12 12:49:02 2008
@@ -559,7 +559,7 @@
 	gint                score;
 	gint                tsiz;
 	guint               j;
-	gint                i, k;
+	gint                i;
 
 	g_return_val_if_fail (index != NULL, FALSE);
 	g_return_val_if_fail (word != NULL, FALSE);
@@ -583,7 +583,7 @@
 				word, -1, 
 				(char *) new_hits->data, 
 				new_hits->len * sizeof (TrackerDBIndexItem), 
-				DP_DCAT);
+				DP_DOVER);
 
 		if (!result) {
 			g_warning ("Could not store word:'%s'", word);
@@ -597,11 +597,27 @@
 	old_hit_count = tsiz / sizeof (TrackerDBIndexItem);
 
 	for (j = 0; j < new_hits->len; j++) {
+		guint left, right, center;
+
 		new_hit = &g_array_index (new_hits, TrackerDBIndexItem, j); 
 		edited = FALSE;
 
-		for (i = 0; i < old_hit_count; i++) {
-			if (previous_hits[i].id == new_hit->id) {
+		left = 0;
+		right = old_hit_count;
+		center = (right - left) / 2;
+
+		/* New items are going to have always a higher service ID,
+		 * so the insertion is sorted, perform a binary search.
+		 */
+
+		while (center > 0) {
+			center += left;
+
+			if (new_hit->id > previous_hits[center].id) {
+				left = center;
+			} else if (new_hit->id < previous_hits[center].id) {
+				right = center;
+			} else if (previous_hits[i].id == new_hit->id) {
 				write_back = TRUE;
 				
 				/* NB the paramter score can be negative */
@@ -611,10 +627,8 @@
 				/* Check for deletion */		
 				if (score < 1) {
 					/* Shift all subsequent records in array down one place */
-					for (k = i + 1; k < old_hit_count; k++) {
-						previous_hits[k - 1] = previous_hits[k];
-					}
-					
+					g_memmove (&previous_hits[i], &previous_hits[i + 1],
+						   (old_hit_count - i) * sizeof (TrackerDBIndexItem));
 					old_hit_count--;
 				} else {
 					guint32 service_type;
@@ -629,8 +643,10 @@
 				edited = TRUE;
 				break;
 			}
+
+			center = (right - left) / 2;
 		}
-		
+
 		/* Add hits that could not be updated directly here so
 		 * they can be appended later
 		 */
@@ -808,7 +824,7 @@
 	if (priv->index) {
 		size = g_hash_table_size (priv->cache);
 		g_debug ("Flushing index with %d items in cache", size);
-		
+
 		g_hash_table_foreach_remove (priv->cache, 
 					     cache_flush_foreach, 
 					     priv->index);