(unknown)

From: Geert Bosch <bosch@gnat.com>
Date: Mon, 2 Apr 2007 11:24:46 +0200
Subject: [PATCH] find_pack_entry_one: Use interpolation search for finding objects in the pack index.

Also be careful about avoiding overflow in signed integer arithmetic.

Signed-off-by: Geert Bosch <bosch@gnat.com>
---
This patch is what I used in my experiments before proposing an
alternative file format for the index.  This gives about a 2.5%
speed-up for git-rev-list --all on the Linux repository,
while not changing anything at all for small repositories.
These tests were done on a Core 2 Duo MacBook Pro with Mac OS X.

  -Geert

 sha1_file.c |   37 ++++++++++++++++++++++++++++++++-----
 1 files changed, 32 insertions(+), 5 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 9c26038..e463710 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1547,14 +1547,39 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 				  struct packed_git *p)
 {
 	const uint32_t *level1_ofs = p->index_data;
-	int hi = ntohl(level1_ofs[*sha1]);
-	int lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
+	const unsigned char level1_key = sha1[0];
+	const unsigned int level2_key =  (sha1[1] << 16) + (sha1[2] << 8)
+	    + sha1[3];
+	uint32_t hi = ntohl(level1_ofs[level1_key]);
+	uint32_t lo = !level1_key ? 0 : ntohl(level1_ofs[level1_key - 1]);
+	uint32_t mi = ((hi - lo) * (level2_key >> 13) >> 11)  + lo;
 	const unsigned char *index = p->index_data;
+	const int ents = hi - lo;
+
+        uint32_t try;
 
 	index += 4 * 256;
 
-	do {
-		int mi = (lo + hi) / 2;
+        if (ents < 0xffffff)
+        do {
+		int ofs = 24 * mi + 4;
+
+		try = ntohl(*((uint32_t *) (index + ofs))) & 0xffffff;
+
+		if (try < level2_key) {
+			lo = mi + 1;
+			mi = lo + (((level2_key - try) >> 16) * ents >> 8);
+			if (mi >= hi || mi < lo) mi = hi - 1;
+		}
+		else if (try > level2_key)
+		{
+			hi = mi;
+			mi = hi - 1 - (((try - level2_key) >> 16) * ents >> 8);
+			if (mi < lo || mi >= hi) mi = lo;
+		}
+	} while (try != level2_key && lo + (ents >> 8) < hi);
+
+        while (lo < hi) {
 		int cmp = hashcmp(index + 24 * mi + 4, sha1);
 		if (!cmp)
 			return ntohl(*((uint32_t *)((char *)index + (24 * mi))));
@@ -1562,7 +1587,9 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 			hi = mi;
 		else
 			lo = mi+1;
-	} while (lo < hi);
+		mi = lo + (hi - lo) / 2;
+	};
+
 	return 0;
 }
 

-- 
1.4.5-rc0.GIT