Re: [RFC] Packing large repositories

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Mar 31, 2007, 21:20 UTC
Message-ID: <Pine.LNX.4.64.0703311408560.6730@woody.linux-foundation.org>
In-Reply-To: <Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org>

On Sat, 31 Mar 2007, Linus Torvalds wrote:

Show 6 quoted lines

> 
> Here's a stupid patch that does that. It's biggest weakness is that it 
> only does a single iteration of newton-raphson. It should probably do at 
> least one more iteration. I bet that you'd get so close that you find it 
> really quickly if you did that. As it is, it doesn't seem to be any slower 
> than the binary search..

Ok, here's a slightly updated patch that does a few more iterations..

It actually seems to outperform the old binary search for me, although quite frankly, my only test was the eclipse git thing, and doing a

	time git log > /dev/null

which isn't exactly scientific or necessarily even very interesting. For a run of five, I got:

Before:
	real    0m2.940s
	real    0m2.277s
	real    0m2.220s
	real    0m2.377s
	real    0m2.223s

After:
	real    0m2.903s
	real    0m2.217s
	real    0m2.269s
	real    0m2.148s
	real    0m2.215s

ie it's really pretty much in the noise, but the best-of-five actually comes with this Newton-Raphson + linear search thing rather than with the binary search.

Anyway, it's *so* much in the noise that I doubt that object lookup really is a very noticeable cost for this load (and perhaps it never is). But it was interesting to see that at least the theory seems sound.

The patch has some commented-out statistics code (ie "hit it in one" vs reporting how many steps forwards/backwards it needed to look.

Not really meant to be applied, but it was interesting to play with this. NOTE! I don't think the math is really strictly correct (ie the scaling inside the loop), but it's "close enough" to not matter, and this really was meant to be an request-for-discussion.

		Linus

---

diff --git a/sha1_file.c b/sha1_file.c
index 9c26038..b1643ea 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1543,27 +1543,134 @@ int nth_packed_object_sha1(const struct packed_git *p, uint32_t n,
 	return 0;
 }
 
+struct index_entry {
+	uint32_t nb_offset;	/* pack-file offset in network byte order */
+	unsigned char sha1[20];	/* SHA1 of the object */
+};
+
+static off_t pack_search_backward(const struct index_entry *index, uint32_t guess, const unsigned char *sha1)
+{
+	int count = 1;
+	while (guess) {
+		int cmp;
+
+		guess--;
+		index--;
+		cmp = hashcmp(index->sha1, sha1);
+		if (!cmp) {
+//			error("  backward: %d", count);
+			return ntohl(index->nb_offset);
+		}
+		if (cmp < 0)
+			break;
+		count++;
+	}
+	return 0;
+}
+
+static off_t pack_search_forward(const struct index_entry *index, uint32_t guess, uint32_t max, const unsigned char *sha1)
+{
+	int count = 1;
+	while (++guess < max) {
+		int cmp;
+
+		index++;
+		cmp = hashcmp(index->sha1, sha1);
+		if (!cmp) {
+//			error("  forward: %d", count);
+			return ntohl(index->nb_offset);
+		}
+		if (cmp > 0)
+			break;
+		count++;
+	}
+	return 0;
+}
+
+/*
+ * The "fraction" thing is a 32-bit number that is seen as a
+ * fraction of 1<<32. Ie 0x80000000 means "half-way". We use
+ * this as a way to do simple comparisons of 32-bit partial
+ * SHA1 fragments, and to estimate how far off we are from
+ * the value we wish to see.
+ */
+static inline uint32_t get_fraction(const unsigned char *p)
+{
+	return (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
+}
+
+static inline int update_guess(unsigned int nr, uint32_t fraction)
+{
+	return (0x80000000 + nr * (uint64_t) fraction) >> 32;
+}
+
 off_t find_pack_entry_one(const unsigned char *sha1,
 				  struct packed_git *p)
 {
+	int i;
+	const struct index_entry *index;
 	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 *index = p->index_data;
+	uint32_t min, max, first;
+	uint32_t hash_val, guess;
+	int cmp;
 
-	index += 4 * 256;
+	/*
+	 * Get the initial range using the first 8 bits of
+	 * the SHA1 and the 8-bit fan-out in the index
+	 */
+	first = *sha1;
+	min = first ? ntohl(level1_ofs[first - 1]) : 0;
+	max = ntohl(level1_ofs[first]);
+	if (min == max)
+		return 0;
 
-	do {
-		int mi = (lo + hi) / 2;
-		int cmp = hashcmp(index + 24 * mi + 4, sha1);
-		if (!cmp)
-			return ntohl(*((uint32_t *)((char *)index + (24 * mi))));
-		if (cmp > 0)
-			hi = mi;
+	/*
+	 * Initial guess using the next 32 bits of the SHA1
+	 * (using "sha1+1" because the first byte of the SHA1
+	 * is now known to be irrelevant and will always match,
+	 * thanks to the index fan-out)
+	 */
+	hash_val = get_fraction(sha1+1);
+	guess = min + update_guess(max - min, hash_val);
+
+	/*
+	 * Look up that entry in the index file...
+	 */
+	index = (const struct index_entry *)((char *) p->index_data + 4 * 256);
+	index += guess;
+
+	/*
+	 * ..and update the guess with a correction based on how
+	 * close the guessed entry's hash value was.
+	 */
+	for (i = 0; i < 3; i++) {
+		uint32_t guess_hash_val = get_fraction(index->sha1+1);
+		int correction;
+
+		if (guess_hash_val == hash_val)
+			break;
+		if (guess_hash_val < hash_val)
+			correction = update_guess(max - guess, hash_val - guess_hash_val);
 		else
-			lo = mi+1;
-	} while (lo < hi);
-	return 0;
+			correction = -update_guess(guess - min, guess_hash_val - hash_val);
+		if (!correction)
+			break;
+		guess += correction;
+		index += correction;
+	}
+
+	/*
+	 * ..and we should now be close enough that now we'll just use a
+	 * linear search from the updated guess.
+	 */
+	cmp = hashcmp(index->sha1, sha1);
+	if (!cmp) {
+//		error("hit it in one!");
+		return ntohl(index->nb_offset);
+	}
+	if (cmp > 0)
+		return pack_search_backward(index, guess, sha1);
+	return pack_search_forward(index, guess, max, sha1);
 }
 
 static int matches_pack_name(struct packed_git *p, const char *ig)