From: Geert Bosch <bosch@xxxxxxxx>
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@xxxxxxxx>
---
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.
While this passes the test suite, I'm not sure it should be applied,
because it doesn't really address the issues for very large repositories
with large numbers of pack files.
-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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html