summaryrefslogtreecommitdiff
path: root/pack-objects.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-06-26 13:43:41 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-06-26 13:43:41 -0700
commit521a4f4cf4bb2d59a51a5355bfb6b148c4aa31ed (patch)
treea653b6d581fa2332c371784226c9c51820280a07 /pack-objects.c
parent102fc37f3b3d213841d4cff47a75d385824a3027 (diff)
downloadgit-521a4f4cf4bb2d59a51a5355bfb6b148c4aa31ed.tar.gz
git-pack-objects: do the delta search in reverse size order
Starting from big objects and going backwards means that we end up picking a delta that goes from a bigger object to a smaller one. That's advantageous for two reasons: the bigger object is likely the newer one (since things tend to grow, rather than shrink), and doing a delete tends to be smaller than doing an add. So the deltas don't tend to be top-of-tree, and the packed end result is just slightly smaller.
Diffstat (limited to 'pack-objects.c')
-rw-r--r--pack-objects.c28
1 files changed, 16 insertions, 12 deletions
diff --git a/pack-objects.c b/pack-objects.c
index aa6cb6d35e..286e4501c6 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -280,18 +280,18 @@ struct unpacked {
};
/*
- * We search for deltas in a list sorted by type and by size, and
- * walk the "old" chain backwards in the list, so if the type
- * has changed or the size difference is too big, there's no point
- * in even continuing the walk, since the other old objects are
- * going to be even smaller or of a different type. So return -1
- * once we determine that there's no point even trying.
+ * We search for deltas _backwards_ in a list sorted by type and
+ * by size, so that we see progressively smaller and smaller files.
+ * That's because we prefer deltas to be from the bigger file
+ * to the smaller - deletes are potentially cheaper, but perhaps
+ * more importantly, the bigger file is likely the more recent
+ * one.
*/
static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
{
struct object_entry *cur_entry = cur->entry;
struct object_entry *old_entry = old->entry;
- unsigned long size, oldsize, delta_size;
+ unsigned long size, oldsize, delta_size, sizediff;
long max_size;
void *delta_buf;
@@ -299,12 +299,12 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de
if (cur_entry->type != old_entry->type)
return -1;
- /* Size is guaranteed to be larger than or equal to oldsize */
size = cur_entry->size;
if (size < 50)
return -1;
oldsize = old_entry->size;
- if (size - oldsize > oldsize / 4)
+ sizediff = oldsize > size ? oldsize - size : size - oldsize;
+ if (sizediff > size / 8)
return -1;
if (old_entry->depth >= max_depth)
return 0;
@@ -332,13 +332,14 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de
static void find_deltas(struct object_entry **list, int window, int depth)
{
- unsigned int i;
+ int i, idx;
unsigned int array_size = window * sizeof(struct unpacked);
struct unpacked *array = xmalloc(array_size);
memset(array, 0, array_size);
- for (i = 0; i < nr_objects; i++) {
- unsigned int idx = i % window;
+ i = nr_objects;
+ idx = 0;
+ while (--i >= 0) {
struct object_entry *entry = list[i];
struct unpacked *n = array + idx;
unsigned long size;
@@ -362,6 +363,9 @@ static void find_deltas(struct object_entry **list, int window, int depth)
if (try_delta(n, m, depth) < 0)
break;
}
+ idx++;
+ if (idx >= window)
+ idx = 0;
}
}