Commit bed3229b555ecd18bc7824c3ead7d2372b5f4f5a
2009-01-03T03:34:09
Precompute the fanout decoding and the oid offset in a pack-*.idx The fanout table is fairly commonly accessed, we need to read it twice for each object we lookup in any given pack file. Most of the processors running Git are running in little-endian mode, as they are variants of the x86 platform, so reading the fanout is a costly operation as we need to convert from network byte order to local byte order. By decoding the fanout table into a malloc obtained buffer we can save these 2 decode operations per lookup and make search go more quickly. This also cleans up the initialization of the search functions by cutting out a few instructions, saving a small amount of time. Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
diff --git a/src/odb.c b/src/odb.c
index 158e2b7..c6dbfe0 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -46,6 +46,8 @@ struct git_pack {
/** The .idx file, mapped into memory. */
git_file idx_fd;
gitfo_map idx_map;
+ uint32_t *im_fanout;
+ unsigned char *im_oid;
uint32_t *im_crc;
uint32_t *im_offset32;
uint32_t *im_offset64;
@@ -520,11 +522,10 @@ static int pack_openidx_map(git_pack *p)
static int idxv1_search(off_t *out, git_pack *p, const git_oid *id)
{
- unsigned char *data = p->idx_map.data;
- size_t lo = id->id[0] ? decode32(data + ((id->id[0]-1) << 2)) : 0;
- size_t hi = decode32(data + (id->id[0] << 2));
+ unsigned char *data = p->im_oid;
+ size_t lo = id->id[0] ? p->im_fanout[id->id[0] - 1] : 0;
+ size_t hi = p->im_fanout[id->id[0]];
- data += 1024;
do {
size_t mid = (lo + hi) >> 1;
size_t pos = 24 * mid;
@@ -542,30 +543,42 @@ static int idxv1_search(off_t *out, git_pack *p, const git_oid *id)
static int pack_openidx_v1(git_pack *p)
{
- uint32_t *fanout = p->idx_map.data;
+ uint32_t *src_fanout = p->idx_map.data;
+ uint32_t *im_fanout;
size_t expsz;
int j;
+ if (!(im_fanout = git__malloc(sizeof(*im_fanout) * 256)))
+ return GIT_ERROR;
+
+ im_fanout[0] = decode32(&src_fanout[0]);
for (j = 1; j < 256; j++) {
- if (decode32(&fanout[j]) < decode32(&fanout[j - 1]))
+ im_fanout[j] = decode32(&src_fanout[j]);
+ if (im_fanout[j] < im_fanout[j - 1]) {
+ free(im_fanout);
return GIT_ERROR;
+ }
}
- p->obj_cnt = decode32(&fanout[255]);
+ p->obj_cnt = im_fanout[255];
+
expsz = 4 * 256 + 24 * p->obj_cnt + 2 * 20;
- if (expsz != p->idx_map.len)
+ if (expsz != p->idx_map.len) {
+ free(im_fanout);
return GIT_ERROR;
+ }
p->idx_search = idxv1_search;
+ p->im_fanout = im_fanout;
+ p->im_oid = (unsigned char*)(src_fanout + 256);
return GIT_SUCCESS;
}
static int idxv2_search(off_t *out, git_pack *p, const git_oid *id)
{
- unsigned char *data = ((unsigned char*)p->idx_map.data) + 8;
- size_t lo = id->id[0] ? decode32(data + ((id->id[0]-1) << 2)) : 0;
- size_t hi = decode32(data + (id->id[0] << 2));
+ unsigned char *data = p->im_oid;
+ size_t lo = id->id[0] ? p->im_fanout[id->id[0] - 1] : 0;
+ size_t hi = p->im_fanout[id->id[0]];
- data += 1024;
do {
size_t mid = (lo + hi) >> 1;
size_t pos = 20 * mid;
@@ -587,17 +600,28 @@ static int idxv2_search(off_t *out, git_pack *p, const git_oid *id)
static int pack_openidx_v2(git_pack *p)
{
- void *data = ((unsigned char*)p->idx_map.data) + 8;
- uint32_t *fanout = data;
+ unsigned char *data = p->idx_map.data;
+ uint32_t *src_fanout = (uint32_t*)(data + 8);
+ uint32_t *im_fanout;
int j;
+ if (!(im_fanout = git__malloc(sizeof(*im_fanout) * 256)))
+ return GIT_ERROR;
+
+ im_fanout[0] = decode32(&src_fanout[0]);
for (j = 1; j < 256; j++) {
- if (decode32(&fanout[j]) < decode32(&fanout[j - 1]))
+ im_fanout[j] = decode32(&src_fanout[j]);
+ if (im_fanout[j] < im_fanout[j - 1]) {
+ free(im_fanout);
return GIT_ERROR;
+ }
}
- p->obj_cnt = decode32(&fanout[255]);
+ p->obj_cnt = im_fanout[255];
+
p->idx_search = idxv2_search;
- p->im_crc = (uint32_t*)(data + 1024 + (20 * p->obj_cnt));
+ p->im_fanout = im_fanout;
+ p->im_oid = (unsigned char*)(src_fanout + 256);
+ p->im_crc = (uint32_t*)(p->im_oid + 20 * p->obj_cnt);
p->im_offset32 = p->im_crc + p->obj_cnt;
p->im_offset64 = p->im_offset32 + p->obj_cnt;
return GIT_SUCCESS;
@@ -661,6 +685,7 @@ static void pack_dec(git_pack *p)
if (p->idx_search) {
gitfo_free_map(&p->idx_map);
gitfo_close(p->idx_fd);
+ free(p->im_fanout);
}
gitlck_free(&p->lock);