simple euristic for further free packing improvements
[gitweb.git] / pack-objects.c
index 53caed42dd2778e96cb39d8ba8b9cb175bdf1303..526c090c619530a5fa61bc7530dee5002bab0ea1 100644 (file)
@@ -10,6 +10,7 @@
 #include "tree-walk.h"
 #include <sys/time.h>
 #include <signal.h>
+#include <stdint.h>
 
 static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
 
@@ -156,7 +157,7 @@ static void prepare_pack_revindex(struct pack_revindex *rix)
 
        rix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1));
        for (i = 0; i < num_ent; i++) {
-               long hl = *((long *)(index + 24 * i));
+               uint32_t hl = *((uint32_t *)(index + 24 * i));
                rix->revindex[i] = ntohl(hl);
        }
        /* This knows the pack format -- the 20-byte trailer
@@ -994,6 +995,7 @@ static int type_size_sort(const struct object_entry *a, const struct object_entr
 struct unpacked {
        struct object_entry *entry;
        void *data;
+       struct delta_index *index;
 };
 
 /*
@@ -1004,61 +1006,56 @@ struct unpacked {
  * more importantly, the bigger file is likely the more recent
  * one.
  */
-static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
+static int try_delta(struct unpacked *trg, struct unpacked *src,
+                    struct delta_index *src_index, unsigned max_depth)
 {
-       struct object_entry *cur_entry = cur->entry;
-       struct object_entry *old_entry = old->entry;
-       unsigned long size, oldsize, delta_size, sizediff;
-       long max_size;
+       struct object_entry *trg_entry = trg->entry;
+       struct object_entry *src_entry = src->entry;
+       unsigned long size, src_size, delta_size, sizediff, max_size;
        void *delta_buf;
 
        /* Don't bother doing diffs between different types */
-       if (cur_entry->type != old_entry->type)
+       if (trg_entry->type != src_entry->type)
                return -1;
 
        /* We do not compute delta to *create* objects we are not
         * going to pack.
         */
-       if (cur_entry->preferred_base)
+       if (trg_entry->preferred_base)
                return -1;
 
-       /* If the current object is at pack edge, take the depth the
+       /*
+        * If the current object is at pack edge, take the depth the
         * objects that depend on the current object into account --
         * otherwise they would become too deep.
         */
-       if (cur_entry->delta_child) {
-               if (max_depth <= cur_entry->delta_limit)
+       if (trg_entry->delta_child) {
+               if (max_depth <= trg_entry->delta_limit)
                        return 0;
-               max_depth -= cur_entry->delta_limit;
+               max_depth -= trg_entry->delta_limit;
        }
-
-       if (old_entry->depth >= max_depth)
+       if (src_entry->depth >= max_depth)
                return 0;
 
-       /*
-        * NOTE!
-        *
-        * We always delta from the bigger to the smaller, since that's
-        * more space-efficient (deletes don't have to say _what_ they
-        * delete).
-        */
-       size = cur_entry->size;
-       max_size = size / 2 - 20;
-       if (cur_entry->delta)
-               max_size = cur_entry->delta_size-1;
-       oldsize = old_entry->size;
-       sizediff = oldsize < size ? size - oldsize : 0;
+       /* Now some size filtering euristics. */
+       size = trg_entry->size;
+       max_size = (size/2 - 20) / (src_entry->depth + 1);
+       if (trg_entry->delta && trg_entry->delta_size <= max_size)
+               max_size = trg_entry->delta_size-1;
+       src_size = src_entry->size;
+       sizediff = src_size < size ? size - src_size : 0;
        if (sizediff >= max_size)
                return 0;
-       delta_buf = diff_delta(old->data, oldsize,
-                              cur->data, size, &delta_size, max_size);
+
+       delta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);
        if (!delta_buf)
                return 0;
-       cur_entry->delta = old_entry;
-       cur_entry->delta_size = delta_size;
-       cur_entry->depth = old_entry->depth + 1;
+
+       trg_entry->delta = src_entry;
+       trg_entry->delta_size = delta_size;
+       trg_entry->depth = src_entry->depth + 1;
        free(delta_buf);
-       return 0;
+       return 1;
 }
 
 static void progress_interval(int signum)
@@ -1108,12 +1105,17 @@ static void find_deltas(struct object_entry **list, int window, int depth)
 
                if (entry->size < 50)
                        continue;
-
+               if (n->index)
+                       free_delta_index(n->index);
                free(n->data);
                n->entry = entry;
                n->data = read_sha1_file(entry->sha1, type, &size);
                if (size != entry->size)
-                       die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
+                       die("object %s inconsistent object length (%lu vs %lu)",
+                           sha1_to_hex(entry->sha1), size, entry->size);
+               n->index = create_delta_index(n->data, size);
+               if (!n->index)
+                       die("out of memory");
 
                j = window;
                while (--j > 0) {
@@ -1124,18 +1126,15 @@ static void find_deltas(struct object_entry **list, int window, int depth)
                        m = array + other_idx;
                        if (!m->entry)
                                break;
-                       if (try_delta(n, m, depth) < 0)
+                       if (try_delta(n, m, m->index, depth) < 0)
                                break;
                }
-#if 0
                /* if we made n a delta, and if n is already at max
                 * depth, leaving it in the window is pointless.  we
                 * should evict it first.
-                * ... in theory only; somehow this makes things worse.
                 */
                if (entry->delta && depth <= entry->depth)
                        continue;
-#endif
                idx++;
                if (idx >= window)
                        idx = 0;
@@ -1144,8 +1143,11 @@ static void find_deltas(struct object_entry **list, int window, int depth)
        if (progress)
                fputc('\n', stderr);
 
-       for (i = 0; i < window; ++i)
+       for (i = 0; i < window; ++i) {
+               if (array[i].index)
+                       free_delta_index(array[i].index);
                free(array[i].data);
+       }
        free(array);
 }