{"thread":{"id":"49105","subject":"[PATCH v4 0/7] Add delta islands support","startedAt":"2018-08-12T05:12:16Z","lastAt":"2018-08-16T06:04:46Z","messageCount":15,"participants":["Christian Couder","Ramsay Jones","Jeff King"],"isPatch":true,"patchVersion":4,"patchTotal":7},"messages":[{"id":"355280","messageId":"20180812051151.6425-1-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":null,"subject":"[PATCH v4 0/7] Add delta islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:44Z","receivedAt":"2018-08-12T05:12:16Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series is upstreaming work made by GitHub and available in:\n\nhttps://github.com/peff/git/commits/jk/delta-islands\n\nThe above work has been already described in the following article:\n\nhttps://githubengineering.com/counting-objects/\n\nThe above branch contains only one patch. In this patch series the\npatch has been split into 4 patches (1/7, 3/7, 4/7 and 5/7) with their\nown commit message, and on top of that 3 new patches (2/7, 6/7 and\n7/7) have been added. The new patches implement things that have been\nrequested on the mailing list.\n\nI kept Peff as the author of the original 4 patches and took the\nliberty to add his Signed-off-by to them.\n\nAs explained in details in the \"Counting Objects\" article referenced\nabove, the goal of the delta island mechanism is for a hosting\nprovider to make it possible to have the \"forks\" of a repository share\nas much storage as possible while preventing object packs to contain\ndeltas between different forks.\n\nIf deltas between different forks are not prevented, when users clone\nor fetch a fork, preparing the pack that should be sent to them can be\nvery costly CPU wise, as objects from a different fork should not be\nsent, which means that a lot of deltas might need to be computed\nagain (instead of reusing existing deltas).\n\n\nThe following changes have been made since the previous iteration:\n\n* suggested by Ramsay: remove the first patch that made\n get_delta_base() in packfile.c non static as it is not necessary\n\n* suggested by Peff: use ALLOC_GROW() in island_config_callback() in\n delta-islands.c in patch 1/7\n\n* suggested by SZEDER Gabor: use ALLOC_ARRAY() in\n deduplicate_islands() in delta-islands.c in patch 1/7\n\n\nThis patch series is also available on GitHub in:\n\nhttps://github.com/chriscool/git/commits/delta-islands\n\nThe previous versions are available there:\n\nV3: https://github.com/chriscool/git/commits/delta-islands29\nV2: https://github.com/chriscool/git/commits/delta-islands19\nV1: https://github.com/chriscool/git/commits/delta-islands6\n\nV3: https://public-inbox.org/git/20180809155532.26151-1-chriscool@tuxfamily.org/\nV2: https://public-inbox.org/git/20180805172525.15278-1-chriscool@tuxfamily.org/\nV1: https://public-inbox.org/git/20180722054836.28935-1-chriscool@tuxfamily.org/\n\n\nChristian Couder (3):\n pack-objects: refactor code into compute_layer_order()\n pack-objects: move tree_depth into 'struct packing_data'\n pack-objects: move 'layer' into 'struct packing_data'\n\nJeff King (4):\n Add delta-islands.{c,h}\n pack-objects: add delta-islands support\n repack: add delta-islands support\n t: add t5319-delta-islands.sh\n\n Documentation/config.txt | 19 ++\n Documentation/git-pack-objects.txt | 97 ++++++\n Documentation/git-repack.txt | 5 +\n Makefile | 1 +\n builtin/pack-objects.c | 137 +++++---\n builtin/repack.c | 9 +\n delta-islands.c | 502 +++++++++++++++++++++++++++++\n delta-islands.h | 11 +\n pack-objects.c | 12 +\n pack-objects.h | 39 +++\n t/t5319-delta-islands.sh | 143 ++++++++\n 11 files changed, 932 insertions(+), 43 deletions(-)\n create mode 100644 delta-islands.c\n create mode 100644 delta-islands.h\n create mode 100755 t/t5319-delta-islands.sh\n\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355281","messageId":"20180812051151.6425-2-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:45Z","receivedAt":"2018-08-12T05:12:16Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nHosting providers that allow users to \"fork\" existing\nrepos want those forks to share as much disk space as\npossible.\n\nAlternates are an existing solution to keep all the\nobjects from all the forks into a unique central repo,\nbut this can have some drawbacks. Especially when\npacking the central repo, deltas will be created\nbetween objects from different forks.\n\nThis can make cloning or fetching a fork much slower\nand much more CPU intensive as Git might have to\ncompute new deltas for many objects to avoid sending\nobjects from a different fork.\n\nBecause the inefficiency primarily arises when an\nobject is delitified against another object that does\nnot exist in the same fork, we partition objects into\nsets that appear in the same fork, and define\n\"delta islands\". When finding delta base, we do not\nallow an object outside the same island to be\nconsidered as its base.\n\nSo \"delta islands\" is a way to store objects from\ndifferent forks in the same repo and packfile without\nhaving deltas between objects from different forks.\n\nThis patch implements the delta islands mechanism in\n\"delta-islands.{c,h}\", but does not yet make use of it.\n\nA few new fields are added in 'struct object_entry'\nin \"pack-objects.h\" though.\n\nThe documentation will follow in a patch that actually\nuses delta islands in \"builtin/pack-objects.c\".\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Makefile | 1 +\n delta-islands.c | 493 ++++++++++++++++++++++++++++++++++++++++++++++++\n delta-islands.h | 11 ++\n pack-objects.h | 4 +\n 4 files changed, 509 insertions(+)\n create mode 100644 delta-islands.c\n create mode 100644 delta-islands.h\n\ndiff --git a/Makefile b/Makefile\nindex bc4fc8eeab..e7994888e8 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -841,6 +841,7 @@ LIB_OBJS += csum-file.o\n LIB_OBJS += ctype.o\n LIB_OBJS += date.o\n LIB_OBJS += decorate.o\n+LIB_OBJS += delta-islands.o\n LIB_OBJS += diffcore-break.o\n LIB_OBJS += diffcore-delta.o\n LIB_OBJS += diffcore-order.o\ndiff --git a/delta-islands.c b/delta-islands.c\nnew file mode 100644\nindex 0000000000..c0b0da6837\n--- /dev/null\n+++ b/delta-islands.c\n@@ -0,0 +1,493 @@\n+#include \"cache.h\"\n+#include \"attr.h\"\n+#include \"object.h\"\n+#include \"blob.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+#include \"tree.h\"\n+#include \"delta.h\"\n+#include \"pack.h\"\n+#include \"tree-walk.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"list-objects.h\"\n+#include \"progress.h\"\n+#include \"refs.h\"\n+#include \"khash.h\"\n+#include \"pack-bitmap.h\"\n+#include \"pack-objects.h\"\n+#include \"delta-islands.h\"\n+#include \"sha1-array.h\"\n+#include \"config.h\"\n+\n+KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\n+\n+static khash_sha1 *island_marks;\n+static unsigned island_counter;\n+static unsigned island_counter_core;\n+\n+static kh_str_t *remote_islands;\n+\n+struct remote_island {\n+\tuint64_t hash;\n+\tstruct oid_array oids;\n+};\n+\n+struct island_bitmap {\n+\tuint32_t refcount;\n+\tuint32_t bits[];\n+};\n+\n+static uint32_t island_bitmap_size;\n+\n+/*\n+ * Allocate a new bitmap; if \"old\" is not NULL, the new bitmap will be a copy\n+ * of \"old\". Otherwise, the new bitmap is empty.\n+ */\n+static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)\n+{\n+\tsize_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);\n+\tstruct island_bitmap *b = xcalloc(1, size);\n+\n+\tif (old)\n+\t\tmemcpy(b, old, size);\n+\n+\tb->refcount = 1;\n+\treturn b;\n+}\n+\n+static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < island_bitmap_size; ++i)\n+\t\ta->bits[i] |= b->bits[i];\n+}\n+\n+static int island_bitmap_is_subset(struct island_bitmap *self,\n+\t\tstruct island_bitmap *super)\n+{\n+\tuint32_t i;\n+\n+\tif (self == super)\n+\t\treturn 1;\n+\n+\tfor (i = 0; i < island_bitmap_size; ++i) {\n+\t\tif ((self->bits[i] & super->bits[i]) != self->bits[i])\n+\t\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+#define ISLAND_BITMAP_BLOCK(x) (x / 32)\n+#define ISLAND_BITMAP_MASK(x) (1 << (x % 32))\n+\n+static void island_bitmap_set(struct island_bitmap *self, uint32_t i)\n+{\n+\tself->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);\n+}\n+\n+static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n+{\n+\treturn (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;\n+}\n+\n+int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n+{\n+\tkhiter_t trg_pos, src_pos;\n+\n+\t/* If we aren't using islands, assume everything goes together. */\n+\tif (!island_marks)\n+\t\treturn 1;\n+\n+\t/*\n+\t * If we don't have a bitmap for the target, we can delta it\n+\t * against anything -- it's not an important object\n+\t */\n+\ttrg_pos = kh_get_sha1(island_marks, trg_oid->hash);\n+\tif (trg_pos >= kh_end(island_marks))\n+\t\treturn 1;\n+\n+\t/*\n+\t * if the source (our delta base) doesn't have a bitmap,\n+\t * we don't want to base any deltas on it!\n+\t */\n+\tsrc_pos = kh_get_sha1(island_marks, src_oid->hash);\n+\tif (src_pos >= kh_end(island_marks))\n+\t\treturn 0;\n+\n+\treturn island_bitmap_is_subset(kh_value(island_marks, trg_pos),\n+\t\t\t\tkh_value(island_marks, src_pos));\n+}\n+\n+int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n+{\n+\tkhiter_t a_pos, b_pos;\n+\tstruct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;\n+\n+\tif (!island_marks)\n+\t\treturn 0;\n+\n+\ta_pos = kh_get_sha1(island_marks, a->hash);\n+\tif (a_pos < kh_end(island_marks))\n+\t\ta_bitmap = kh_value(island_marks, a_pos);\n+\n+\tb_pos = kh_get_sha1(island_marks, b->hash);\n+\tif (b_pos < kh_end(island_marks))\n+\t\tb_bitmap = kh_value(island_marks, b_pos);\n+\n+\tif (a_bitmap) {\n+\t\tif (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))\n+\t\t\treturn -1;\n+\t}\n+\tif (b_bitmap) {\n+\t\tif (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap))\n+\t\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static struct island_bitmap *create_or_get_island_marks(struct object *obj)\n+{\n+\tkhiter_t pos;\n+\tint hash_ret;\n+\n+\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n+\tif (hash_ret)\n+\t\tkh_value(island_marks, pos) = island_bitmap_new(NULL);\n+\n+\treturn kh_value(island_marks, pos);\n+}\n+\n+static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n+{\n+\tstruct island_bitmap *b;\n+\tkhiter_t pos;\n+\tint hash_ret;\n+\n+\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n+\tif (hash_ret) {\n+\t\t/*\n+\t\t * We don't have one yet; make a copy-on-write of the\n+\t\t * parent.\n+\t\t */\n+\t\tmarks->refcount++;\n+\t\tkh_value(island_marks, pos) = marks;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * We do have it. Make sure we split any copy-on-write before\n+\t * updating.\n+\t */\n+\tb = kh_value(island_marks, pos);\n+\tif (b->refcount > 1) {\n+\t\tb->refcount--;\n+\t\tb = kh_value(island_marks, pos) = island_bitmap_new(b);\n+\t}\n+\tisland_bitmap_or(b, marks);\n+}\n+\n+static void mark_remote_island_1(struct remote_island *rl, int is_core_island)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < rl->oids.nr; ++i) {\n+\t\tstruct island_bitmap *marks;\n+\t\tstruct object *obj = parse_object(the_repository, &rl->oids.oid[i]);\n+\n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\n+\t\tmarks = create_or_get_island_marks(obj);\n+\t\tisland_bitmap_set(marks, island_counter);\n+\n+\t\tif (is_core_island && obj->type == OBJ_COMMIT)\n+\t\t\tobj->flags |= NEEDS_BITMAP;\n+\n+\t\t/* If it was a tag, also make sure we hit the underlying object. */\n+\t\twhile (obj && obj->type == OBJ_TAG) {\n+\t\t\tobj = ((struct tag *)obj)->tagged;\n+\t\t\tif (obj) {\n+\t\t\t\tparse_object(the_repository, &obj->oid);\n+\t\t\t\tmarks = create_or_get_island_marks(obj);\n+\t\t\t\tisland_bitmap_set(marks, island_counter);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (is_core_island)\n+\t\tisland_counter_core = island_counter;\n+\n+\tisland_counter++;\n+}\n+\n+static int cmp_tree_depth(const void *va, const void *vb)\n+{\n+\tstruct object_entry *a = *(struct object_entry **)va;\n+\tstruct object_entry *b = *(struct object_entry **)vb;\n+\treturn a->tree_depth - b->tree_depth;\n+}\n+\n+void resolve_tree_islands(int progress, struct packing_data *to_pack)\n+{\n+\tstruct progress *progress_state = NULL;\n+\tstruct object_entry **todo;\n+\tint nr = 0;\n+\tint i;\n+\n+\tif (!island_marks)\n+\t\treturn;\n+\n+\t/*\n+\t * We process only trees, as commits and tags have already been handled\n+\t * (and passed their marks on to root trees, as well. We must make sure\n+\t * to process them in descending tree-depth order so that marks\n+\t * propagate down the tree properly, even if a sub-tree is found in\n+\t * multiple parent trees.\n+\t */\n+\tALLOC_ARRAY(todo, to_pack->nr_objects);\n+\tfor (i = 0; i < to_pack->nr_objects; i++) {\n+\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n+\t\t\ttodo[nr++] = &to_pack->objects[i];\n+\t}\n+\tQSORT(todo, nr, cmp_tree_depth);\n+\n+\tif (progress)\n+\t\tprogress_state = start_progress(_(\"Propagating island marks\"), nr);\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct object_entry *ent = todo[i];\n+\t\tstruct island_bitmap *root_marks;\n+\t\tstruct tree *tree;\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\t\tkhiter_t pos;\n+\n+\t\tpos = kh_get_sha1(island_marks, ent->idx.oid.hash);\n+\t\tif (pos >= kh_end(island_marks))\n+\t\t\tcontinue;\n+\n+\t\troot_marks = kh_value(island_marks, pos);\n+\n+\t\ttree = lookup_tree(the_repository, &ent->idx.oid);\n+\t\tif (!tree || parse_tree(tree) < 0)\n+\t\t\tdie(_(\"bad tree object %s\"), oid_to_hex(&ent->idx.oid));\n+\n+\t\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\tstruct object *obj;\n+\n+\t\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\t\tcontinue;\n+\n+\t\t\tobj = lookup_object(the_repository, entry.oid->hash);\n+\t\t\tif (!obj)\n+\t\t\t\tcontinue;\n+\n+\t\t\tset_island_marks(obj, root_marks);\n+\t\t}\n+\n+\t\tfree_tree_buffer(tree);\n+\n+\t\tdisplay_progress(progress_state, i+1);\n+\t}\n+\n+\tstop_progress(&progress_state);\n+\tfree(todo);\n+}\n+\n+static regex_t *island_regexes;\n+static unsigned int island_regexes_alloc, island_regexes_nr;\n+static const char *core_island_name;\n+\n+static int island_config_callback(const char *k, const char *v, void *cb)\n+{\n+\tif (!strcmp(k, \"pack.island\")) {\n+\t\tstruct strbuf re = STRBUF_INIT;\n+\n+\t\tif (!v)\n+\t\t\treturn config_error_nonbool(k);\n+\n+\t\tALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc);\n+\n+\t\tif (*v != '^')\n+\t\t\tstrbuf_addch(&re, '^');\n+\t\tstrbuf_addstr(&re, v);\n+\n+\t\tif (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))\n+\t\t\tdie(_(\"failed to load island regex for '%s': %s\"), k, re.buf);\n+\n+\t\tstrbuf_release(&re);\n+\t\tisland_regexes_nr++;\n+\t\treturn 0;\n+\t}\n+\n+\tif (!strcmp(k, \"pack.islandcore\"))\n+\t\treturn git_config_string(&core_island_name, k, v);\n+\n+\treturn 0;\n+}\n+\n+static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n+{\n+\tuint64_t sha_core;\n+\tstruct remote_island *rl = NULL;\n+\n+\tint hash_ret;\n+\tkhiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);\n+\n+\tif (hash_ret) {\n+\t\tkh_key(remote_islands, pos) = xstrdup(island_name);\n+\t\tkh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));\n+\t}\n+\n+\trl = kh_value(remote_islands, pos);\n+\toid_array_append(&rl->oids, oid);\n+\n+\tmemcpy(&sha_core, oid->hash, sizeof(uint64_t));\n+\trl->hash += sha_core;\n+}\n+\n+static int find_island_for_ref(const char *refname, const struct object_id *oid,\n+\t\t\t int flags, void *data)\n+{\n+\t/*\n+\t * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,\n+\t * so we can diagnose below a config with more capture groups\n+\t * than we support.\n+\t */\n+\tregmatch_t matches[16];\n+\tint i, m;\n+\tstruct strbuf island_name = STRBUF_INIT;\n+\n+\t/* walk backwards to get last-one-wins ordering */\n+\tfor (i = island_regexes_nr - 1; i >= 0; i--) {\n+\t\tif (!regexec(&island_regexes[i], refname,\n+\t\t\t ARRAY_SIZE(matches), matches, 0))\n+\t\t\tbreak;\n+\t}\n+\n+\tif (i < 0)\n+\t\treturn 0;\n+\n+\tif (matches[ARRAY_SIZE(matches) - 1].rm_so != -1)\n+\t\twarning(_(\"island regex from config has \"\n+\t\t\t \"too many capture groups (max=%d)\"),\n+\t\t\t(int)ARRAY_SIZE(matches) - 2);\n+\n+\tfor (m = 1; m < ARRAY_SIZE(matches); m++) {\n+\t\tregmatch_t *match = &matches[m];\n+\n+\t\tif (match->rm_so == -1)\n+\t\t\tcontinue;\n+\n+\t\tif (island_name.len)\n+\t\t\tstrbuf_addch(&island_name, '-');\n+\n+\t\tstrbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);\n+\t}\n+\n+\tadd_ref_to_island(island_name.buf, oid);\n+\tstrbuf_release(&island_name);\n+\treturn 0;\n+}\n+\n+static struct remote_island *get_core_island(void)\n+{\n+\tif (core_island_name) {\n+\t\tkhiter_t pos = kh_get_str(remote_islands, core_island_name);\n+\t\tif (pos < kh_end(remote_islands))\n+\t\t\treturn kh_value(remote_islands, pos);\n+\t}\n+\n+\treturn NULL;\n+}\n+\n+static void deduplicate_islands(void)\n+{\n+\tstruct remote_island *island, *core = NULL, **list;\n+\tunsigned int island_count, dst, src, ref, i = 0;\n+\n+\tisland_count = kh_size(remote_islands);\n+\tALLOC_ARRAY(list, island_count);\n+\n+\tkh_foreach_value(remote_islands, island, {\n+\t\tlist[i++] = island;\n+\t});\n+\n+\tfor (ref = 0; ref + 1 < island_count; ref++) {\n+\t\tfor (src = ref + 1, dst = src; src < island_count; src++) {\n+\t\t\tif (list[ref]->hash == list[src]->hash)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (src != dst)\n+\t\t\t\tlist[dst] = list[src];\n+\n+\t\t\tdst++;\n+\t\t}\n+\t\tisland_count = dst;\n+\t}\n+\n+\tisland_bitmap_size = (island_count / 32) + 1;\n+\tcore = get_core_island();\n+\n+\tfor (i = 0; i < island_count; ++i) {\n+\t\tmark_remote_island_1(list[i], core && list[i]->hash == core->hash);\n+\t}\n+\n+\tfree(list);\n+}\n+\n+void load_delta_islands(void)\n+{\n+\tisland_marks = kh_init_sha1();\n+\tremote_islands = kh_init_str();\n+\n+\tgit_config(island_config_callback, NULL);\n+\tfor_each_ref(find_island_for_ref, NULL);\n+\tdeduplicate_islands();\n+\n+\tfprintf(stderr, _(\"Marked %d islands, done.\\n\"), island_counter);\n+}\n+\n+void propagate_island_marks(struct commit *commit)\n+{\n+\tkhiter_t pos = kh_get_sha1(island_marks, commit->object.oid.hash);\n+\n+\tif (pos < kh_end(island_marks)) {\n+\t\tstruct commit_list *p;\n+\t\tstruct island_bitmap *root_marks = kh_value(island_marks, pos);\n+\n+\t\tparse_commit(commit);\n+\t\tset_island_marks(&get_commit_tree(commit)->object, root_marks);\n+\t\tfor (p = commit->parents; p; p = p->next)\n+\t\t\tset_island_marks(&p->item->object, root_marks);\n+\t}\n+}\n+\n+int compute_pack_layers(struct packing_data *to_pack)\n+{\n+\tuint32_t i;\n+\n+\tif (!core_island_name || !island_marks)\n+\t\treturn 1;\n+\n+\tfor (i = 0; i < to_pack->nr_objects; ++i) {\n+\t\tstruct object_entry *entry = &to_pack->objects[i];\n+\t\tkhiter_t pos = kh_get_sha1(island_marks, entry->idx.oid.hash);\n+\n+\t\tentry->layer = 1;\n+\n+\t\tif (pos < kh_end(island_marks)) {\n+\t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n+\n+\t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n+\t\t\t\tentry->layer = 0;\n+\t\t}\n+\t}\n+\n+\treturn 2;\n+}\ndiff --git a/delta-islands.h b/delta-islands.h\nnew file mode 100644\nindex 0000000000..f9725730f4\n--- /dev/null\n+++ b/delta-islands.h\n@@ -0,0 +1,11 @@\n+#ifndef DELTA_ISLANDS_H\n+#define DELTA_ISLANDS_H\n+\n+int island_delta_cmp(const struct object_id *a, const struct object_id *b);\n+int in_same_island(const struct object_id *, const struct object_id *);\n+void resolve_tree_islands(int progress, struct packing_data *to_pack);\n+void load_delta_islands(void);\n+void propagate_island_marks(struct commit *commit);\n+int compute_pack_layers(struct packing_data *to_pack);\n+\n+#endif /* DELTA_ISLANDS_H */\ndiff --git a/pack-objects.h b/pack-objects.h\nindex edf74dabdd..8eecd67991 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -100,6 +100,10 @@ struct object_entry {\n \tunsigned type_:TYPE_BITS;\n \tunsigned no_try_delta:1;\n \tunsigned in_pack_type:TYPE_BITS; /* could be delta */\n+\n+\tunsigned int tree_depth; /* should be repositioned for packing? */\n+\tunsigned char layer;\n+\n \tunsigned preferred_base:1; /*\n \t\t\t\t * we do not pack this, but is available\n \t\t\t\t * to be used as the base object to delta\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355282","messageId":"20180812051151.6425-6-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 5/7] t: add t5319-delta-islands.sh","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:49Z","receivedAt":"2018-08-12T05:12:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n t/t5319-delta-islands.sh | 143 +++++++++++++++++++++++++++++++++++++++\n 1 file changed, 143 insertions(+)\n create mode 100755 t/t5319-delta-islands.sh\n\ndiff --git a/t/t5319-delta-islands.sh b/t/t5319-delta-islands.sh\nnew file mode 100755\nindex 0000000000..fea92a5777\n--- /dev/null\n+++ b/t/t5319-delta-islands.sh\n@@ -0,0 +1,143 @@\n+#!/bin/sh\n+\n+test_description='exercise delta islands'\n+. ./test-lib.sh\n+\n+# returns true iff $1 is a delta based on $2\n+is_delta_base () {\n+\tdelta_base=$(echo \"$1\" | git cat-file --batch-check='%(deltabase)') &&\n+\techo >&2 \"$1 has base $delta_base\" &&\n+\ttest \"$delta_base\" = \"$2\"\n+}\n+\n+# generate a commit on branch $1 with a single file, \"file\", whose\n+# content is mostly based on the seed $2, but with a unique bit\n+# of content $3 appended. This should allow us to see whether\n+# blobs of different refs delta against each other.\n+commit() {\n+\tblob=$({ test-tool genrandom \"$2\" 10240 && echo \"$3\"; } |\n+\t git hash-object -w --stdin) &&\n+\ttree=$(printf '100644 blob %s\\tfile\\n' \"$blob\" | git mktree) &&\n+\tcommit=$(echo \"$2-$3\" | git commit-tree \"$tree\" ${4:+-p \"$4\"}) &&\n+\tgit update-ref \"refs/heads/$1\" \"$commit\" &&\n+\teval \"$1\"'=$(git rev-parse $1:file)' &&\n+\teval \"echo >&2 $1=\\$$1\"\n+}\n+\n+test_expect_success 'setup commits' '\n+\tcommit one seed 1 &&\n+\tcommit two seed 12\n+'\n+\n+# Note: This is heavily dependent on the \"prefer larger objects as base\"\n+# heuristic.\n+test_expect_success 'vanilla repack deltas one against two' '\n+\tgit repack -adf &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island repack with no island definition is vanilla' '\n+\tgit repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island repack with no matches is vanilla' '\n+\tgit -c \"pack.island=refs/foo\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'separate islands disallows delta' '\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'same island allows delta' '\n+\tgit -c \"pack.island=refs/heads\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'coalesce same-named islands' '\n+\tgit \\\n+\t\t-c \"pack.island=refs/(.*)/one\" \\\n+\t\t-c \"pack.island=refs/(.*)/two\" \\\n+\t\trepack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island restrictions drop reused deltas' '\n+\tgit repack -adfi &&\n+\tis_delta_base $one $two &&\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adi &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'island regexes are left-anchored' '\n+\tgit -c \"pack.island=heads/(.*)\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island regexes follow last-one-wins scheme' '\n+\tgit \\\n+\t\t-c \"pack.island=refs/heads/(.*)\" \\\n+\t\t-c \"pack.island=refs/heads/\" \\\n+\t\trepack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'setup shared history' '\n+\tcommit root shared root &&\n+\tcommit one shared 1 root &&\n+\tcommit two shared 12-long root\n+'\n+\n+# We know that $two will be preferred as a base from $one,\n+# because we can transform it with a pure deletion.\n+#\n+# We also expect $root as a delta against $two by the \"longest is base\" rule.\n+test_expect_success 'vanilla delta goes between branches' '\n+\tgit repack -adf &&\n+\tis_delta_base $one $two &&\n+\tis_delta_base $root $two\n+'\n+\n+# Here we should allow $one to base itself on $root; even though\n+# they are in different islands, the objects in $root are in a superset\n+# of islands compared to those in $one.\n+#\n+# Similarly, $two can delta against $root by our rules. And unlike $one,\n+# in which we are just allowing it, the island rules actually put $root\n+# as a possible base for $two, which it would not otherwise be (due to the size\n+# sorting).\n+test_expect_success 'deltas allowed against superset islands' '\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi &&\n+\tis_delta_base $one $root &&\n+\tis_delta_base $two $root\n+'\n+\n+# We are going to test the packfile order here, so we again have to make some\n+# assumptions. We assume that \"$root\", as part of our core \"one\", must come\n+# before \"$two\". This should be guaranteed by the island code. However, for\n+# this test to fail without islands, we are also assuming that it would not\n+# otherwise do so. This is true by the current write order, which will put\n+# commits (and their contents) before their parents.\n+test_expect_success 'island core places core objects first' '\n+\tcat >expect <<-EOF &&\n+\t$root\n+\t$two\n+\tEOF\n+\tgit -c \"pack.island=refs/heads/(.*)\" \\\n+\t -c \"pack.islandcore=one\" \\\n+\t repack -adfi &&\n+\tgit verify-pack -v .git/objects/pack/*.pack |\n+\tcut -d\" \" -f1 |\n+\tegrep \"$root|$two\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'unmatched island core is not fatal' '\n+\tgit -c \"pack.islandcore=one\" repack -adfi\n+'\n+\n+test_done\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355283","messageId":"20180812051151.6425-3-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 2/7] pack-objects: refactor code into compute_layer_order()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:46Z","receivedAt":"2018-08-12T05:12:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"In a following commit, as we will use delta islands, we will\nhave to compute the write order for different layers, not just\nfor one.\n\nLet's prepare for that by refactoring the code that will be\nused to compute the write order for a given layer into a new\ncompute_layer_order() function.\n\nThis will make it easier to see and understand what the\nfollowing changes are doing.\n\nHelped-by: Duy Nguyen \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 90 +++++++++++++++++++++++-------------------\n 1 file changed, 50 insertions(+), 40 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4391504a91..99b6329399 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -667,48 +667,15 @@ static void add_family_to_write_order(struct object_entry **wo,\n \tadd_descendants_to_write_order(wo, endp, root);\n }\n \n-static struct object_entry **compute_write_order(void)\n+static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)\n {\n-\tunsigned int i, wo_end, last_untagged;\n-\n-\tstruct object_entry **wo;\n+\tunsigned int i, last_untagged;\n \tstruct object_entry *objects = to_pack.objects;\n \n \tfor (i = 0; i < to_pack.nr_objects; i++) {\n-\t\tobjects[i].tagged = 0;\n-\t\tobjects[i].filled = 0;\n-\t\tSET_DELTA_CHILD(&objects[i], NULL);\n-\t\tSET_DELTA_SIBLING(&objects[i], NULL);\n-\t}\n-\n-\t/*\n-\t * Fully connect delta_child/delta_sibling network.\n-\t * Make sure delta_sibling is sorted in the original\n-\t * recency order.\n-\t */\n-\tfor (i = to_pack.nr_objects; i > 0;) {\n-\t\tstruct object_entry *e = &objects[--i];\n-\t\tif (!DELTA(e))\n-\t\t\tcontinue;\n-\t\t/* Mark me as the first child */\n-\t\te->delta_sibling_idx = DELTA(e)->delta_child_idx;\n-\t\tSET_DELTA_CHILD(DELTA(e), e);\n-\t}\n-\n-\t/*\n-\t * Mark objects that are at the tip of tags.\n-\t */\n-\tfor_each_tag_ref(mark_tagged, NULL);\n-\n-\t/*\n-\t * Give the objects in the original recency order until\n-\t * we see a tagged tip.\n-\t */\n-\tALLOC_ARRAY(wo, to_pack.nr_objects);\n-\tfor (i = wo_end = 0; i < to_pack.nr_objects; i++) {\n \t\tif (objects[i].tagged)\n \t\t\tbreak;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\tadd_to_write_order(wo, wo_end, &objects[i]);\n \t}\n \tlast_untagged = i;\n \n@@ -717,7 +684,7 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor (; i < to_pack.nr_objects; i++) {\n \t\tif (objects[i].tagged)\n-\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t\tadd_to_write_order(wo, wo_end, &objects[i]);\n \t}\n \n \t/*\n@@ -727,7 +694,7 @@ static struct object_entry **compute_write_order(void)\n \t\tif (oe_type(&objects[i]) != OBJ_COMMIT &&\n \t\t oe_type(&objects[i]) != OBJ_TAG)\n \t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\tadd_to_write_order(wo, wo_end, &objects[i]);\n \t}\n \n \t/*\n@@ -736,7 +703,7 @@ static struct object_entry **compute_write_order(void)\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n \t\tif (oe_type(&objects[i]) != OBJ_TREE)\n \t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\tadd_to_write_order(wo, wo_end, &objects[i]);\n \t}\n \n \t/*\n@@ -744,8 +711,51 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n \t\tif (!objects[i].filled)\n-\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t\tadd_family_to_write_order(wo, wo_end, &objects[i]);\n \t}\n+}\n+\n+static struct object_entry **compute_write_order(void)\n+{\n+\tunsigned int i, wo_end;\n+\n+\tstruct object_entry **wo;\n+\tstruct object_entry *objects = to_pack.objects;\n+\n+\tfor (i = 0; i < to_pack.nr_objects; i++) {\n+\t\tobjects[i].tagged = 0;\n+\t\tobjects[i].filled = 0;\n+\t\tSET_DELTA_CHILD(&objects[i], NULL);\n+\t\tSET_DELTA_SIBLING(&objects[i], NULL);\n+\t}\n+\n+\t/*\n+\t * Fully connect delta_child/delta_sibling network.\n+\t * Make sure delta_sibling is sorted in the original\n+\t * recency order.\n+\t */\n+\tfor (i = to_pack.nr_objects; i > 0;) {\n+\t\tstruct object_entry *e = &objects[--i];\n+\t\tif (!DELTA(e))\n+\t\t\tcontinue;\n+\t\t/* Mark me as the first child */\n+\t\te->delta_sibling_idx = DELTA(e)->delta_child_idx;\n+\t\tSET_DELTA_CHILD(DELTA(e), e);\n+\t}\n+\n+\t/*\n+\t * Mark objects that are at the tip of tags.\n+\t */\n+\tfor_each_tag_ref(mark_tagged, NULL);\n+\n+\t/*\n+\t * Give the objects in the original recency order until\n+\t * we see a tagged tip.\n+\t */\n+\tALLOC_ARRAY(wo, to_pack.nr_objects);\n+\two_end = 0;\n+\n+\tcompute_layer_order(wo, &wo_end);\n \n \tif (wo_end != to_pack.nr_objects)\n \t\tdie(\"ordered %u objects, expected %\"PRIu32, wo_end, to_pack.nr_objects);\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355284","messageId":"20180812051151.6425-5-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 4/7] repack: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:48Z","receivedAt":"2018-08-12T05:12:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nImplement simple support for --delta-islands option and\nrepack.useDeltaIslands config variable in git repack.\n\nThis allows users to setup delta islands in their config and\nget the benefit of less disk usage while cloning and fetching\nis still quite fast and not much more CPU intensive.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config.txt | 4 ++++\n Documentation/git-repack.txt | 5 +++++\n builtin/repack.c | 9 +++++++++\n 3 files changed, 18 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 27bb77f9e7..2bd31078b2 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -3145,6 +3145,10 @@ repack.packKeptObjects::\n \tindex is being written (either via `--write-bitmap-index` or\n \t`repack.writeBitmaps`).\n \n+repack.useDeltaIslands::\n+\tIf set to true, makes `git repack` act as if `--delta-islands`\n+\twas passed. Defaults to `false`.\n+\n repack.writeBitmaps::\n \tWhen true, git will write a bitmap index when packing all\n \tobjects to disk (e.g., when `git repack -a` is run). This\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex d90e7907f4..a8b2d4722f 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -155,6 +155,11 @@ depth is 4095.\n \tbeing removed. In addition, any unreachable loose objects will\n \tbe packed (and their loose counterparts removed).\n \n+-i::\n+--delta-islands::\n+\tPass the `--delta-islands` option to `git-pack-objects`, see\n+\tlinkgit:git-pack-objects[1].\n+\n Configuration\n -------------\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 6c636e159e..5ab9ee69e4 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -12,6 +12,7 @@\n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n static int write_bitmaps;\n+static int use_delta_islands;\n static char *packdir, *packtmp;\n \n static const char *const git_repack_usage[] = {\n@@ -40,6 +41,10 @@ static int repack_config(const char *var, const char *value, void *cb)\n \t\twrite_bitmaps = git_config_bool(var, value);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(var, \"repack.usedeltaislands\")) {\n+\t\tuse_delta_islands = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(var, value, cb);\n }\n \n@@ -194,6 +199,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --local to git-pack-objects\")),\n \t\tOPT_BOOL('b', \"write-bitmap-index\", &write_bitmaps,\n \t\t\t\tN_(\"write bitmap index\")),\n+\t\tOPT_BOOL('i', \"delta-islands\", &use_delta_islands,\n+\t\t\t\tN_(\"pass --delta-islands to git-pack-objects\")),\n \t\tOPT_STRING(0, \"unpack-unreachable\", &unpack_unreachable, N_(\"approxidate\"),\n \t\t\t\tN_(\"with -A, do not loosen objects older than this\")),\n \t\tOPT_BOOL('k', \"keep-unreachable\", &keep_unreachable,\n@@ -267,6 +274,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\targv_array_pushf(&cmd.args, \"--no-reuse-object\");\n \tif (write_bitmaps)\n \t\targv_array_push(&cmd.args, \"--write-bitmap-index\");\n+\tif (use_delta_islands)\n+\t\targv_array_push(&cmd.args, \"--delta-islands\");\n \n \tif (pack_everything & ALL_INTO_ONE) {\n \t\tget_non_kept_pack_filenames(&existing_packs, &keep_pack_list);\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355285","messageId":"20180812051151.6425-4-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 3/7] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:47Z","receivedAt":"2018-08-12T05:12:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nImplement support for delta islands in git pack-objects\nand document how delta islands work in\n\"Documentation/git-pack-objects.txt\" and Documentation/config.txt.\n\nThis allows users to setup delta islands in their config and\nget the benefit of less disk usage while cloning and fetching\nis still quite fast and not much more CPU intensive.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config.txt | 15 +++++\n Documentation/git-pack-objects.txt | 97 ++++++++++++++++++++++++++++++\n builtin/pack-objects.c | 57 +++++++++++++++---\n 3 files changed, 161 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 63365dcf3d..27bb77f9e7 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -2585,6 +2585,21 @@ Note that changing the compression level will not automatically recompress\n all existing objects. You can force recompression by passing the -F option\n to linkgit:git-repack[1].\n \n+pack.island::\n+\tAn extended regular expression configuring a set of delta\n+\tislands. See \"DELTA ISLANDS\" in linkgit:git-pack-objects[1]\n+\tfor details.\n+\n+pack.islandCore::\n+\tSpecify an island name which gets to have its objects be\n+\tpacked first. This creates a kind of pseudo-pack at the front\n+\tof one pack, so that the objects from the specified island are\n+\thopefully faster to copy into any pack that should be served\n+\tto a user requesting these objects. In practice this means\n+\tthat the island specified should likely correspond to what is\n+\tthe most commonly cloned in the repo. See also \"DELTA ISLANDS\"\n+\tin linkgit:git-pack-objects[1].\n+\n pack.deltaCacheSize::\n \tThe maximum memory in bytes used for caching deltas in\n \tlinkgit:git-pack-objects[1] before writing them out to a pack.\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex d95b472d16..40c825c381 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -289,6 +289,103 @@ Unexpected missing object will raise an error.\n --unpack-unreachable::\n \tKeep unreachable objects in loose form. This implies `--revs`.\n \n+--delta-islands::\n+\tRestrict delta matches based on \"islands\". See DELTA ISLANDS\n+\tbelow.\n+\n+\n+DELTA ISLANDS\n+-------------\n+\n+When possible, `pack-objects` tries to reuse existing on-disk deltas to\n+avoid having to search for new ones on the fly. This is an important\n+optimization for serving fetches, because it means the server can avoid\n+inflating most objects at all and just send the bytes directly from\n+disk. This optimization can't work when an object is stored as a delta\n+against a base which the receiver does not have (and which we are not\n+already sending). In that case the server \"breaks\" the delta and has to\n+find a new one, which has a high CPU cost. Therefore it's important for\n+performance that the set of objects in on-disk delta relationships match\n+what a client would fetch.\n+\n+In a normal repository, this tends to work automatically. The objects\n+are mostly reachable from the branches and tags, and that's what clients\n+fetch. Any deltas we find on the server are likely to be between objects\n+the client has or will have.\n+\n+But in some repository setups, you may have several related but separate\n+groups of ref tips, with clients tending to fetch those groups\n+independently. For example, imagine that you are hosting several \"forks\"\n+of a repository in a single shared object store, and letting clients\n+view them as separate repositories through `GIT_NAMESPACE` or separate\n+repos using the alternates mechanism. A naive repack may find that the\n+optimal delta for an object is against a base that is only found in\n+another fork. But when a client fetches, they will not have the base\n+object, and we'll have to find a new delta on the fly.\n+\n+A similar situation may exist if you have many refs outside of\n+`refs/heads/` and `refs/tags/` that point to related objects (e.g.,\n+`refs/pull` or `refs/changes` used by some hosting providers). By\n+default, clients fetch only heads and tags, and deltas against objects\n+found only in those other groups cannot be sent as-is.\n+\n+Delta islands solve this problem by allowing you to group your refs into\n+distinct \"islands\". Pack-objects computes which objects are reachable\n+from which islands, and refuses to make a delta from an object `A`\n+against a base which is not present in all of `A`'s islands. This\n+results in slightly larger packs (because we miss some delta\n+opportunities), but guarantees that a fetch of one island will not have\n+to recompute deltas on the fly due to crossing island boundaries.\n+\n+When repacking with delta islands the delta window tends to get\n+clogged with candidates that are forbidden by the config. Repacking\n+with a big --window helps (and doesn't take as long as it otherwise\n+might because we can reject some object pairs based on islands before\n+doing any computation on the content).\n+\n+Islands are configured via the `pack.island` option, which can be\n+specified multiple times. Each value is a left-anchored regular\n+expressions matching refnames. For example:\n+\n+-------------------------------------------\n+[pack]\n+island = refs/heads/\n+island = refs/tags/\n+-------------------------------------------\n+\n+puts heads and tags into an island (whose name is the empty string; see\n+below for more on naming). Any refs which do not match those regular\n+expressions (e.g., `refs/pull/123`) is not in any island. Any object\n+which is reachable only from `refs/pull/` (but not heads or tags) is\n+therefore not a candidate to be used as a base for `refs/heads/`.\n+\n+Refs are grouped into islands based on their \"names\", and two regexes\n+that produce the same name are considered to be in the same\n+island. The names are computed from the regexes by concatenating any\n+capture groups from the regex, with a '-' dash in between. (And if\n+there are no capture groups, then the name is the empty string, as in\n+the above example.) This allows you to create arbitrary numbers of\n+islands. Only up to 14 such capture groups are supported though.\n+\n+For example, imagine you store the refs for each fork in\n+`refs/virtual/ID`, where `ID` is a numeric identifier. You might then\n+configure:\n+\n+-------------------------------------------\n+[pack]\n+island = refs/virtual/([0-9]+)/heads/\n+island = refs/virtual/([0-9]+)/tags/\n+island = refs/virtual/([0-9]+)/(pull)/\n+-------------------------------------------\n+\n+That puts the heads and tags for each fork in their own island (named\n+\"1234\" or similar), and the pull refs for each go into their own\n+\"1234-pull\".\n+\n+Note that we pick a single island for each regex to go into, using \"last\n+one wins\" ordering (which allows repo-specific config to take precedence\n+over user-wide config, and so forth).\n+\n SEE ALSO\n --------\n linkgit:git-rev-list[1]\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 99b6329399..30ef48dc43 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -24,6 +24,7 @@\n #include \"streaming.h\"\n #include \"thread-utils.h\"\n #include \"pack-bitmap.h\"\n+#include \"delta-islands.h\"\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n@@ -59,6 +60,7 @@ static struct packing_data to_pack;\n \n static struct pack_idx_entry **written_list;\n static uint32_t nr_result, nr_written, nr_seen;\n+static uint32_t write_layer;\n \n static int non_empty;\n static int reuse_delta = 1, reuse_object = 1;\n@@ -93,6 +95,8 @@ static uint16_t write_bitmap_options;\n \n static int exclude_promisor_objects;\n \n+static int use_delta_islands;\n+\n static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;\n static unsigned long cache_max_small_delta_size = 1000;\n@@ -607,7 +611,7 @@ static inline void add_to_write_order(struct object_entry **wo,\n \t\t\t unsigned int *endp,\n \t\t\t struct object_entry *e)\n {\n-\tif (e->filled)\n+\tif (e->filled || e->layer != write_layer)\n \t\treturn;\n \two[(*endp)++] = e;\n \te->filled = 1;\n@@ -710,13 +714,14 @@ static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)\n \t * Finally all the rest in really tight order\n \t */\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (!objects[i].filled)\n+\t\tif (!objects[i].filled && objects[i].layer == write_layer)\n \t\t\tadd_family_to_write_order(wo, wo_end, &objects[i]);\n \t}\n }\n \n static struct object_entry **compute_write_order(void)\n {\n+\tuint32_t max_layers = 1;\n \tunsigned int i, wo_end;\n \n \tstruct object_entry **wo;\n@@ -748,14 +753,14 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor_each_tag_ref(mark_tagged, NULL);\n \n-\t/*\n-\t * Give the objects in the original recency order until\n-\t * we see a tagged tip.\n-\t */\n+\tif (use_delta_islands)\n+\t\tmax_layers = compute_pack_layers(&to_pack);\n+\n \tALLOC_ARRAY(wo, to_pack.nr_objects);\n \two_end = 0;\n \n-\tcompute_layer_order(wo, &wo_end);\n+\tfor (; write_layer < max_layers; ++write_layer)\n+\t\tcompute_layer_order(wo, &wo_end);\n \n \tif (wo_end != to_pack.nr_objects)\n \t\tdie(\"ordered %u objects, expected %\"PRIu32, wo_end, to_pack.nr_objects);\n@@ -1514,7 +1519,8 @@ static void check_object(struct object_entry *entry)\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL))) {\n+\t\tif (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL)) &&\n+\t\t in_same_island(&entry->idx.oid, &base_entry->idx.oid)) {\n \t\t\t/*\n \t\t\t * If base_ref was set above that means we wish to\n \t\t\t * reuse delta data, and we even found that base\n@@ -1830,6 +1836,11 @@ static int type_size_sort(const void *_a, const void *_b)\n \t\treturn -1;\n \tif (a->preferred_base < b->preferred_base)\n \t\treturn 1;\n+\tif (use_delta_islands) {\n+\t\tint island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);\n+\t\tif (island_cmp)\n+\t\t\treturn island_cmp;\n+\t}\n \tif (a_size > b_size)\n \t\treturn -1;\n \tif (a_size < b_size)\n@@ -1978,6 +1989,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (trg_size < src_size / 32)\n \t\treturn 0;\n \n+\tif (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))\n+\t\treturn 0;\n+\n \t/* Load data if not already done */\n \tif (!trg->data) {\n \t\tread_lock();\n@@ -2516,6 +2530,9 @@ static void prepare_pack(int window, int depth)\n \tuint32_t i, nr_deltas;\n \tunsigned n;\n \n+\tif (use_delta_islands)\n+\t\tresolve_tree_islands(progress, &to_pack);\n+\n \tget_object_details();\n \n \t/*\n@@ -2679,6 +2696,9 @@ static void show_commit(struct commit *commit, void *data)\n \n \tif (write_bitmap_index)\n \t\tindex_commit_for_bitmap(commit);\n+\n+\tif (use_delta_islands)\n+\t\tpropagate_island_marks(commit);\n }\n \n static void show_object(struct object *obj, const char *name, void *data)\n@@ -2686,6 +2706,19 @@ static void show_object(struct object *obj, const char *name, void *data)\n \tadd_preferred_base_object(name);\n \tadd_object_entry(&obj->oid, obj->type, name, 0);\n \tobj->flags |= OBJECT_ADDED;\n+\n+\tif (use_delta_islands) {\n+\t\tconst char *p;\n+\t\tunsigned depth = 0;\n+\t\tstruct object_entry *ent;\n+\n+\t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n+\t\t\tdepth++;\n+\n+\t\tent = packlist_find(&to_pack, obj->oid.hash, NULL);\n+\t\tif (ent && depth > ent->tree_depth)\n+\t\t\tent->tree_depth = depth;\n+\t}\n }\n \n static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)\n@@ -3013,6 +3046,9 @@ static void get_object_list(int ac, const char **av)\n \tif (use_bitmap_index && !get_object_list_from_bitmap(&revs))\n \t\treturn;\n \n+\tif (use_delta_islands)\n+\t\tload_delta_islands();\n+\n \tif (prepare_revision_walk(&revs))\n \t\tdie(\"revision walk setup failed\");\n \tmark_edges_uninteresting(&revs, show_edge);\n@@ -3192,6 +3228,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t option_parse_missing_action },\n \t\tOPT_BOOL(0, \"exclude-promisor-objects\", &exclude_promisor_objects,\n \t\t\t N_(\"do not pack objects in promisor packfiles\")),\n+\t\tOPT_BOOL(0, \"delta-islands\", &use_delta_islands,\n+\t\t\t N_(\"respect islands during delta compression\")),\n \t\tOPT_END(),\n \t};\n \n@@ -3318,6 +3356,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (pack_to_stdout || !rev_list_all)\n \t\twrite_bitmap_index = 0;\n \n+\tif (use_delta_islands)\n+\t\targv_array_push(&rp, \"--topo-order\");\n+\n \tif (progress && all_progress_implied)\n \t\tprogress = 2;\n \n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355286","messageId":"20180812051151.6425-7-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 6/7] pack-objects: move tree_depth into 'struct packing_data'","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:50Z","receivedAt":"2018-08-12T05:12:23Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This reduces the size of 'struct object_entry' and therefore\nmakes packing objects more efficient.\n\nThis also renames cmp_tree_depth() into tree_depth_compare(),\nas it is more modern to have the name of the compare functions\nend with \"compare\".\n\nHelped-by: Jeff King \nHelped-by: Duy Nguyen \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 4 ++--\n delta-islands.c | 27 ++++++++++++++++++---------\n pack-objects.c | 6 ++++++\n pack-objects.h | 21 ++++++++++++++++++++-\n 4 files changed, 46 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 30ef48dc43..fd3e514b31 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2716,8 +2716,8 @@ static void show_object(struct object *obj, const char *name, void *data)\n \t\t\tdepth++;\n \n \t\tent = packlist_find(&to_pack, obj->oid.hash, NULL);\n-\t\tif (ent && depth > ent->tree_depth)\n-\t\t\tent->tree_depth = depth;\n+\t\tif (ent && depth > oe_tree_depth(&to_pack, ent))\n+\t\t\toe_set_tree_depth(&to_pack, ent, depth);\n \t}\n }\n \ndiff --git a/delta-islands.c b/delta-islands.c\nindex c0b0da6837..14d34e16cb 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -224,17 +224,23 @@ static void mark_remote_island_1(struct remote_island *rl, int is_core_island)\n \tisland_counter++;\n }\n \n-static int cmp_tree_depth(const void *va, const void *vb)\n+struct tree_islands_todo {\n+\tstruct object_entry *entry;\n+\tunsigned int depth;\n+};\n+\n+static int tree_depth_compare(const void *a, const void *b)\n {\n-\tstruct object_entry *a = *(struct object_entry **)va;\n-\tstruct object_entry *b = *(struct object_entry **)vb;\n-\treturn a->tree_depth - b->tree_depth;\n+\tconst struct tree_islands_todo *todo_a = a;\n+\tconst struct tree_islands_todo *todo_b = b;\n+\n+\treturn todo_a->depth - todo_b->depth;\n }\n \n void resolve_tree_islands(int progress, struct packing_data *to_pack)\n {\n \tstruct progress *progress_state = NULL;\n-\tstruct object_entry **todo;\n+\tstruct tree_islands_todo *todo;\n \tint nr = 0;\n \tint i;\n \n@@ -250,16 +256,19 @@ void resolve_tree_islands(int progress, struct packing_data *to_pack)\n \t */\n \tALLOC_ARRAY(todo, to_pack->nr_objects);\n \tfor (i = 0; i < to_pack->nr_objects; i++) {\n-\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n-\t\t\ttodo[nr++] = &to_pack->objects[i];\n+\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE) {\n+\t\t\ttodo[nr].entry = &to_pack->objects[i];\n+\t\t\ttodo[nr].depth = oe_tree_depth(to_pack, &to_pack->objects[i]);\n+\t\t\tnr++;\n+\t\t}\n \t}\n-\tQSORT(todo, nr, cmp_tree_depth);\n+\tQSORT(todo, nr, tree_depth_compare);\n \n \tif (progress)\n \t\tprogress_state = start_progress(_(\"Propagating island marks\"), nr);\n \n \tfor (i = 0; i < nr; i++) {\n-\t\tstruct object_entry *ent = todo[i];\n+\t\tstruct object_entry *ent = todo[i].entry;\n \t\tstruct island_bitmap *root_marks;\n \t\tstruct tree *tree;\n \t\tstruct tree_desc desc;\ndiff --git a/pack-objects.c b/pack-objects.c\nindex 92708522e7..30314572e6 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -160,6 +160,9 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,\n \n \t\tif (!pdata->in_pack_by_idx)\n \t\t\tREALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);\n+\n+\t\tif (pdata->tree_depth)\n+\t\t\tREALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc);\n \t}\n \n \tnew_entry = pdata->objects + pdata->nr_objects++;\n@@ -175,5 +178,8 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,\n \tif (pdata->in_pack)\n \t\tpdata->in_pack[pdata->nr_objects - 1] = NULL;\n \n+\tif (pdata->tree_depth)\n+\t\tpdata->tree_depth[pdata->nr_objects - 1] = 0;\n+\n \treturn new_entry;\n }\ndiff --git a/pack-objects.h b/pack-objects.h\nindex 8eecd67991..3cb5527eeb 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -101,7 +101,6 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned in_pack_type:TYPE_BITS; /* could be delta */\n \n-\tunsigned int tree_depth; /* should be repositioned for packing? */\n \tunsigned char layer;\n \n \tunsigned preferred_base:1; /*\n@@ -145,6 +144,9 @@ struct packing_data {\n \tstruct packed_git **in_pack;\n \n \tuintmax_t oe_size_limit;\n+\n+\t/* delta islands */\n+\tunsigned int *tree_depth;\n };\n \n void prepare_packing_data(struct packing_data *pdata);\n@@ -350,4 +352,21 @@ static inline void oe_set_delta_size(struct packing_data *pack,\n \t\t \"where delta size is the same as entry size\");\n }\n \n+static inline unsigned int oe_tree_depth(struct packing_data *pack,\n+\t\t\t\t\t struct object_entry *e)\n+{\n+\tif (!pack->tree_depth)\n+\t\treturn 0;\n+\treturn pack->tree_depth[e - pack->objects];\n+}\n+\n+static inline void oe_set_tree_depth(struct packing_data *pack,\n+\t\t\t\t struct object_entry *e,\n+\t\t\t\t unsigned int tree_depth)\n+{\n+\tif (!pack->tree_depth)\n+\t\tALLOC_ARRAY(pack->tree_depth, pack->nr_objects);\n+\tpack->tree_depth[e - pack->objects] = tree_depth;\n+}\n+\n #endif\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355287","messageId":"20180812051151.6425-8-chriscool@tuxfamily.org","threadId":"49105","inReplyTo":"20180812051151.6425-1-chriscool@tuxfamily.org","subject":"[PATCH v4 7/7] pack-objects: move 'layer' into 'struct packing_data'","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-12T05:11:51Z","receivedAt":"2018-08-12T05:12:24Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This reduces the size of 'struct object_entry' from 88 bytes\nto 80 and therefore makes packing objects more efficient.\n\nFor example on a Linux repo with 12M objects,\n`git pack-objects --all` needs extra 96MB memory even if the\nlayer feature is not used.\n\nHelped-by: Jeff King \nHelped-by: Duy Nguyen \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 4 ++--\n delta-islands.c | 4 ++--\n pack-objects.c | 6 ++++++\n pack-objects.h | 20 ++++++++++++++++++--\n 4 files changed, 28 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex fd3e514b31..d5d91eeed5 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -611,7 +611,7 @@ static inline void add_to_write_order(struct object_entry **wo,\n \t\t\t unsigned int *endp,\n \t\t\t struct object_entry *e)\n {\n-\tif (e->filled || e->layer != write_layer)\n+\tif (e->filled || oe_layer(&to_pack, e) != write_layer)\n \t\treturn;\n \two[(*endp)++] = e;\n \te->filled = 1;\n@@ -714,7 +714,7 @@ static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)\n \t * Finally all the rest in really tight order\n \t */\n \tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (!objects[i].filled && objects[i].layer == write_layer)\n+\t\tif (!objects[i].filled && oe_layer(&to_pack, &objects[i]) == write_layer)\n \t\t\tadd_family_to_write_order(wo, wo_end, &objects[i]);\n \t}\n }\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 14d34e16cb..2ced34d99c 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -488,13 +488,13 @@ int compute_pack_layers(struct packing_data *to_pack)\n \t\tstruct object_entry *entry = &to_pack->objects[i];\n \t\tkhiter_t pos = kh_get_sha1(island_marks, entry->idx.oid.hash);\n \n-\t\tentry->layer = 1;\n+\t\toe_set_layer(to_pack, entry, 1);\n \n \t\tif (pos < kh_end(island_marks)) {\n \t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n \n \t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n-\t\t\t\tentry->layer = 0;\n+\t\t\t\toe_set_layer(to_pack, entry, 0);\n \t\t}\n \t}\n \ndiff --git a/pack-objects.c b/pack-objects.c\nindex 30314572e6..98389460c2 100644\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -163,6 +163,9 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,\n \n \t\tif (pdata->tree_depth)\n \t\t\tREALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc);\n+\n+\t\tif (pdata->layer)\n+\t\t\tREALLOC_ARRAY(pdata->layer, pdata->nr_alloc);\n \t}\n \n \tnew_entry = pdata->objects + pdata->nr_objects++;\n@@ -181,5 +184,8 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,\n \tif (pdata->tree_depth)\n \t\tpdata->tree_depth[pdata->nr_objects - 1] = 0;\n \n+\tif (pdata->layer)\n+\t\tpdata->layer[pdata->nr_objects - 1] = 0;\n+\n \treturn new_entry;\n }\ndiff --git a/pack-objects.h b/pack-objects.h\nindex 3cb5527eeb..ad3c208764 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -101,8 +101,6 @@ struct object_entry {\n \tunsigned no_try_delta:1;\n \tunsigned in_pack_type:TYPE_BITS; /* could be delta */\n \n-\tunsigned char layer;\n-\n \tunsigned preferred_base:1; /*\n \t\t\t\t * we do not pack this, but is available\n \t\t\t\t * to be used as the base object to delta\n@@ -147,6 +145,7 @@ struct packing_data {\n \n \t/* delta islands */\n \tunsigned int *tree_depth;\n+\tunsigned char *layer;\n };\n \n void prepare_packing_data(struct packing_data *pdata);\n@@ -369,4 +368,21 @@ static inline void oe_set_tree_depth(struct packing_data *pack,\n \tpack->tree_depth[e - pack->objects] = tree_depth;\n }\n \n+static inline unsigned char oe_layer(struct packing_data *pack,\n+\t\t\t\t struct object_entry *e)\n+{\n+\tif (!pack->layer)\n+\t\treturn 0;\n+\treturn pack->layer[e - pack->objects];\n+}\n+\n+static inline void oe_set_layer(struct packing_data *pack,\n+\t\t\t\tstruct object_entry *e,\n+\t\t\t\tunsigned char layer)\n+{\n+\tif (!pack->layer)\n+\t\tALLOC_ARRAY(pack->layer, pack->nr_objects);\n+\tpack->layer[e - pack->objects] = layer;\n+}\n+\n #endif\n-- \n2.18.0.554.gdb07901040.dirty\n\n"},{"id":"355303","messageId":"2113c74c-b230-6ea1-a980-d6d008bac759@ramsayjones.plus.com","threadId":"49105","inReplyTo":"20180812051151.6425-2-chriscool@tuxfamily.org","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-08-13T01:14:45Z","receivedAt":"2018-08-13T01:14:51Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 12/08/18 06:11, Christian Couder wrote:\n> From: Jeff King \n> \n> Hosting providers that allow users to \"fork\" existing\n> repos want those forks to share as much disk space as\n> possible.\n> \n> Alternates are an existing solution to keep all the\n> objects from all the forks into a unique central repo,\n> but this can have some drawbacks. Especially when\n> packing the central repo, deltas will be created\n> between objects from different forks.\n> \n> This can make cloning or fetching a fork much slower\n> and much more CPU intensive as Git might have to\n> compute new deltas for many objects to avoid sending\n> objects from a different fork.\n> \n> Because the inefficiency primarily arises when an\n> object is delitified against another object that does\n\ns/delitified/deltified/ ?\n\n> not exist in the same fork, we partition objects into\n> sets that appear in the same fork, and define\n> \"delta islands\". When finding delta base, we do not\n> allow an object outside the same island to be\n> considered as its base.\n> \n> So \"delta islands\" is a way to store objects from\n> different forks in the same repo and packfile without\n> having deltas between objects from different forks.\n> \n> This patch implements the delta islands mechanism in\n> \"delta-islands.{c,h}\", but does not yet make use of it.\n> \n> A few new fields are added in 'struct object_entry'\n> in \"pack-objects.h\" though.\n> \n> The documentation will follow in a patch that actually\n> uses delta islands in \"builtin/pack-objects.c\".\n> \n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> Makefile | 1 +\n> delta-islands.c | 493 ++++++++++++++++++++++++++++++++++++++++++++++++\n> delta-islands.h | 11 ++\n> pack-objects.h | 4 +\n> 4 files changed, 509 insertions(+)\n> create mode 100644 delta-islands.c\n> create mode 100644 delta-islands.h\n> \n> diff --git a/Makefile b/Makefile\n> index bc4fc8eeab..e7994888e8 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -841,6 +841,7 @@ LIB_OBJS += csum-file.o\n> LIB_OBJS += ctype.o\n> LIB_OBJS += date.o\n> LIB_OBJS += decorate.o\n> +LIB_OBJS += delta-islands.o\n> LIB_OBJS += diffcore-break.o\n> LIB_OBJS += diffcore-delta.o\n> LIB_OBJS += diffcore-order.o\n> diff --git a/delta-islands.c b/delta-islands.c\n> new file mode 100644\n> index 0000000000..c0b0da6837\n> --- /dev/null\n> +++ b/delta-islands.c\n> @@ -0,0 +1,493 @@\n> +#include \"cache.h\"\n> +#include \"attr.h\"\n> +#include \"object.h\"\n> +#include \"blob.h\"\n> +#include \"commit.h\"\n> +#include \"tag.h\"\n> +#include \"tree.h\"\n> +#include \"delta.h\"\n> +#include \"pack.h\"\n> +#include \"tree-walk.h\"\n> +#include \"diff.h\"\n> +#include \"revision.h\"\n> +#include \"list-objects.h\"\n> +#include \"progress.h\"\n> +#include \"refs.h\"\n> +#include \"khash.h\"\n\nI was wondering how many copies of the inline functions\nintroduced by this header we had, so:\n\n $ nm git | grep ' t ' | cut -d' ' -f3 | sort | uniq -c | sort -rn | grep kh_\n 3 kh_resize_sha1\n 3 kh_put_sha1\n 3 kh_init_sha1\n 3 kh_get_sha1\n 1 kh_resize_str\n 1 kh_resize_sha1_pos\n 1 kh_put_str\n 1 kh_put_sha1_pos\n 1 kh_init_str\n 1 kh_init_sha1_pos\n 1 kh_get_str\n 1 kh_get_sha1_pos\n 1 kh_destroy_sha1\n $ \n\nLooking at the individual object files, we see:\n\n $ nm pack-bitmap-write.o | grep ' t ' | grep kh_\n 00000000000001cc t kh_get_sha1\n 00000000000001b7 t kh_init_sha1\n 000000000000085e t kh_put_sha1\n 0000000000000310 t kh_resize_sha1\n $ \n\nSo, the two instances of the sha1 hash-map are never\ndestroyed (kh_destroy_sha1 is not present in the object\nfile).\n\n $ nm pack-bitmap.o | grep ' t ' | grep kh_\n 00000000000002d9 t kh_destroy_sha1\n 000000000000032b t kh_get_sha1\n 0000000000000daa t kh_get_sha1_pos\n 00000000000002c4 t kh_init_sha1\n 0000000000000d95 t kh_init_sha1_pos\n 00000000000009bd t kh_put_sha1\n 0000000000001432 t kh_put_sha1_pos\n 000000000000046f t kh_resize_sha1\n 0000000000000eee t kh_resize_sha1_pos\n $ \n\nThe sha1_pos hash-map is not destroyed here.\n\n $ nm delta-islands.o | grep ' t ' | grep kh_\n 00000000000002be t kh_get_sha1\n 0000000000000e52 t kh_get_str\n 00000000000002a9 t kh_init_sha1\n 0000000000000e3d t kh_init_str\n 0000000000000950 t kh_put_sha1\n 00000000000014e4 t kh_put_str\n 0000000000000402 t kh_resize_sha1\n 0000000000000f96 t kh_resize_str\n $ \n\nAnd neither the sha1 or str hash-maps are destroyed here.\n(That is not necessarily a problem, of course! ;-) )\n \n> +#include \"pack-bitmap.h\"\n> +#include \"pack-objects.h\"\n> +#include \"delta-islands.h\"\n> +#include \"sha1-array.h\"\n> +#include \"config.h\"\n> +\n> +KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\n> +\n> +static khash_sha1 *island_marks;\n> +static unsigned island_counter;\n> +static unsigned island_counter_core;\n> +\n> +static kh_str_t *remote_islands;\n> +\n> +struct remote_island {\n> +\tuint64_t hash;\n> +\tstruct oid_array oids;\n> +};\n> +\n> +struct island_bitmap {\n> +\tuint32_t refcount;\n> +\tuint32_t bits[];\n\nUse FLEX_ARRAY here? We are slowly moving toward requiring\ncertain C99 features, but I can't remember a flex array\nweather-balloon patch.\n\n> +};\n> +\n> +static uint32_t island_bitmap_size;\n> +\n> +/*\n> + * Allocate a new bitmap; if \"old\" is not NULL, the new bitmap will be a copy\n> + * of \"old\". Otherwise, the new bitmap is empty.\n> + */\n> +static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)\n> +{\n> +\tsize_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);\n> +\tstruct island_bitmap *b = xcalloc(1, size);\n> +\n> +\tif (old)\n> +\t\tmemcpy(b, old, size);\n> +\n> +\tb->refcount = 1;\n> +\treturn b;\n> +}\n> +\n> +static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)\n> +{\n> +\tuint32_t i;\n> +\n> +\tfor (i = 0; i < island_bitmap_size; ++i)\n> +\t\ta->bits[i] |= b->bits[i];\n> +}\n> +\n> +static int island_bitmap_is_subset(struct island_bitmap *self,\n> +\t\tstruct island_bitmap *super)\n> +{\n> +\tuint32_t i;\n> +\n> +\tif (self == super)\n> +\t\treturn 1;\n> +\n> +\tfor (i = 0; i < island_bitmap_size; ++i) {\n> +\t\tif ((self->bits[i] & super->bits[i]) != self->bits[i])\n> +\t\t\treturn 0;\n> +\t}\n> +\n> +\treturn 1;\n> +}\n> +\n> +#define ISLAND_BITMAP_BLOCK(x) (x / 32)\n> +#define ISLAND_BITMAP_MASK(x) (1 << (x % 32))\n> +\n> +static void island_bitmap_set(struct island_bitmap *self, uint32_t i)\n> +{\n> +\tself->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);\n> +}\n> +\n> +static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n> +{\n> +\treturn (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;\n> +}\n> +\n> +int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n\nHmm, what does the trg_ prefix stand for?\n\n> +{\n> +\tkhiter_t trg_pos, src_pos;\n> +\n> +\t/* If we aren't using islands, assume everything goes together. */\n> +\tif (!island_marks)\n> +\t\treturn 1;\n> +\n> +\t/*\n> +\t * If we don't have a bitmap for the target, we can delta it\n\n... Ah, OK, trg_ => target.\n\n> +\t * against anything -- it's not an important object\n> +\t */\n> +\ttrg_pos = kh_get_sha1(island_marks, trg_oid->hash);\n> +\tif (trg_pos >= kh_end(island_marks))\n> +\t\treturn 1;\n> +\n> +\t/*\n> +\t * if the source (our delta base) doesn't have a bitmap,\n> +\t * we don't want to base any deltas on it!\n> +\t */\n> +\tsrc_pos = kh_get_sha1(island_marks, src_oid->hash);\n> +\tif (src_pos >= kh_end(island_marks))\n> +\t\treturn 0;\n> +\n> +\treturn island_bitmap_is_subset(kh_value(island_marks, trg_pos),\n> +\t\t\t\tkh_value(island_marks, src_pos));\n> +}\n> +\n> +int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n> +{\n> +\tkhiter_t a_pos, b_pos;\n> +\tstruct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;\n> +\n> +\tif (!island_marks)\n> +\t\treturn 0;\n> +\n> +\ta_pos = kh_get_sha1(island_marks, a->hash);\n> +\tif (a_pos < kh_end(island_marks))\n> +\t\ta_bitmap = kh_value(island_marks, a_pos);\n> +\n> +\tb_pos = kh_get_sha1(island_marks, b->hash);\n> +\tif (b_pos < kh_end(island_marks))\n> +\t\tb_bitmap = kh_value(island_marks, b_pos);\n> +\n> +\tif (a_bitmap) {\n> +\t\tif (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))\n> +\t\t\treturn -1;\n> +\t}\n> +\tif (b_bitmap) {\n> +\t\tif (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap))\n> +\t\t\treturn 1;\n> +\t}\n> +\n> +\treturn 0;\n> +}\n> +\n> +static struct island_bitmap *create_or_get_island_marks(struct object *obj)\n> +{\n> +\tkhiter_t pos;\n> +\tint hash_ret;\n> +\n> +\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n> +\tif (hash_ret)\n> +\t\tkh_value(island_marks, pos) = island_bitmap_new(NULL);\n> +\n> +\treturn kh_value(island_marks, pos);\n> +}\n> +\n> +static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n> +{\n> +\tstruct island_bitmap *b;\n> +\tkhiter_t pos;\n> +\tint hash_ret;\n> +\n> +\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n> +\tif (hash_ret) {\n> +\t\t/*\n> +\t\t * We don't have one yet; make a copy-on-write of the\n> +\t\t * parent.\n> +\t\t */\n> +\t\tmarks->refcount++;\n> +\t\tkh_value(island_marks, pos) = marks;\n> +\t\treturn;\n> +\t}\n> +\n> +\t/*\n> +\t * We do have it. Make sure we split any copy-on-write before\n> +\t * updating.\n> +\t */\n> +\tb = kh_value(island_marks, pos);\n> +\tif (b->refcount > 1) {\n> +\t\tb->refcount--;\n> +\t\tb = kh_value(island_marks, pos) = island_bitmap_new(b);\n> +\t}\n> +\tisland_bitmap_or(b, marks);\n> +}\n> +\n> +static void mark_remote_island_1(struct remote_island *rl, int is_core_island)\n> +{\n> +\tuint32_t i;\n> +\n> +\tfor (i = 0; i < rl->oids.nr; ++i) {\n> +\t\tstruct island_bitmap *marks;\n> +\t\tstruct object *obj = parse_object(the_repository, &rl->oids.oid[i]);\n> +\n> +\t\tif (!obj)\n> +\t\t\tcontinue;\n> +\n> +\t\tmarks = create_or_get_island_marks(obj);\n> +\t\tisland_bitmap_set(marks, island_counter);\n> +\n> +\t\tif (is_core_island && obj->type == OBJ_COMMIT)\n> +\t\t\tobj->flags |= NEEDS_BITMAP;\n> +\n> +\t\t/* If it was a tag, also make sure we hit the underlying object. */\n> +\t\twhile (obj && obj->type == OBJ_TAG) {\n> +\t\t\tobj = ((struct tag *)obj)->tagged;\n> +\t\t\tif (obj) {\n> +\t\t\t\tparse_object(the_repository, &obj->oid);\n> +\t\t\t\tmarks = create_or_get_island_marks(obj);\n> +\t\t\t\tisland_bitmap_set(marks, island_counter);\n> +\t\t\t}\n> +\t\t}\n> +\t}\n> +\n> +\tif (is_core_island)\n> +\t\tisland_counter_core = island_counter;\n> +\n> +\tisland_counter++;\n> +}\n> +\n> +static int cmp_tree_depth(const void *va, const void *vb)\n> +{\n> +\tstruct object_entry *a = *(struct object_entry **)va;\n> +\tstruct object_entry *b = *(struct object_entry **)vb;\n> +\treturn a->tree_depth - b->tree_depth;\n> +}\n> +\n> +void resolve_tree_islands(int progress, struct packing_data *to_pack)\n> +{\n> +\tstruct progress *progress_state = NULL;\n> +\tstruct object_entry **todo;\n> +\tint nr = 0;\n> +\tint i;\n> +\n> +\tif (!island_marks)\n> +\t\treturn;\n> +\n> +\t/*\n> +\t * We process only trees, as commits and tags have already been handled\n> +\t * (and passed their marks on to root trees, as well. We must make sure\n> +\t * to process them in descending tree-depth order so that marks\n> +\t * propagate down the tree properly, even if a sub-tree is found in\n> +\t * multiple parent trees.\n> +\t */\n> +\tALLOC_ARRAY(todo, to_pack->nr_objects);\n> +\tfor (i = 0; i < to_pack->nr_objects; i++) {\n> +\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n> +\t\t\ttodo[nr++] = &to_pack->objects[i];\n> +\t}\n> +\tQSORT(todo, nr, cmp_tree_depth);\n> +\n> +\tif (progress)\n> +\t\tprogress_state = start_progress(_(\"Propagating island marks\"), nr);\n> +\n> +\tfor (i = 0; i < nr; i++) {\n> +\t\tstruct object_entry *ent = todo[i];\n> +\t\tstruct island_bitmap *root_marks;\n> +\t\tstruct tree *tree;\n> +\t\tstruct tree_desc desc;\n> +\t\tstruct name_entry entry;\n> +\t\tkhiter_t pos;\n> +\n> +\t\tpos = kh_get_sha1(island_marks, ent->idx.oid.hash);\n> +\t\tif (pos >= kh_end(island_marks))\n> +\t\t\tcontinue;\n> +\n> +\t\troot_marks = kh_value(island_marks, pos);\n> +\n> +\t\ttree = lookup_tree(the_repository, &ent->idx.oid);\n> +\t\tif (!tree || parse_tree(tree) < 0)\n> +\t\t\tdie(_(\"bad tree object %s\"), oid_to_hex(&ent->idx.oid));\n> +\n> +\t\tinit_tree_desc(&desc, tree->buffer, tree->size);\n> +\t\twhile (tree_entry(&desc, &entry)) {\n> +\t\t\tstruct object *obj;\n> +\n> +\t\t\tif (S_ISGITLINK(entry.mode))\n> +\t\t\t\tcontinue;\n> +\n> +\t\t\tobj = lookup_object(the_repository, entry.oid->hash);\n> +\t\t\tif (!obj)\n> +\t\t\t\tcontinue;\n> +\n> +\t\t\tset_island_marks(obj, root_marks);\n> +\t\t}\n> +\n> +\t\tfree_tree_buffer(tree);\n> +\n> +\t\tdisplay_progress(progress_state, i+1);\n> +\t}\n> +\n> +\tstop_progress(&progress_state);\n> +\tfree(todo);\n> +}\n> +\n> +static regex_t *island_regexes;\n> +static unsigned int island_regexes_alloc, island_regexes_nr;\n> +static const char *core_island_name;\n> +\n> +static int island_config_callback(const char *k, const char *v, void *cb)\n> +{\n> +\tif (!strcmp(k, \"pack.island\")) {\n> +\t\tstruct strbuf re = STRBUF_INIT;\n> +\n> +\t\tif (!v)\n> +\t\t\treturn config_error_nonbool(k);\n> +\n> +\t\tALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc);\n> +\n> +\t\tif (*v != '^')\n> +\t\t\tstrbuf_addch(&re, '^');\n> +\t\tstrbuf_addstr(&re, v);\n> +\n> +\t\tif (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))\n> +\t\t\tdie(_(\"failed to load island regex for '%s': %s\"), k, re.buf);\n> +\n> +\t\tstrbuf_release(&re);\n> +\t\tisland_regexes_nr++;\n> +\t\treturn 0;\n> +\t}\n> +\n> +\tif (!strcmp(k, \"pack.islandcore\"))\n> +\t\treturn git_config_string(&core_island_name, k, v);\n> +\n> +\treturn 0;\n> +}\n> +\n> +static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n> +{\n> +\tuint64_t sha_core;\n> +\tstruct remote_island *rl = NULL;\n> +\n> +\tint hash_ret;\n> +\tkhiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);\n> +\n> +\tif (hash_ret) {\n> +\t\tkh_key(remote_islands, pos) = xstrdup(island_name);\n> +\t\tkh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));\n> +\t}\n> +\n> +\trl = kh_value(remote_islands, pos);\n> +\toid_array_append(&rl->oids, oid);\n> +\n> +\tmemcpy(&sha_core, oid->hash, sizeof(uint64_t));\n> +\trl->hash += sha_core;\n\nHmm, so the first 64-bits of the oid of each ref that is part of\nthis island is added together as a 'hash' for the island. And this\nis used to de-duplicate the islands? Any false positives? (does it\nmatter - it would only affect performance, not correctness, right?)\n\n> +}\n> +\n> +static int find_island_for_ref(const char *refname, const struct object_id *oid,\n> +\t\t\t int flags, void *data)\n> +{\n> +\t/*\n> +\t * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,\n> +\t * so we can diagnose below a config with more capture groups\n> +\t * than we support.\n> +\t */\n> +\tregmatch_t matches[16];\n> +\tint i, m;\n> +\tstruct strbuf island_name = STRBUF_INIT;\n> +\n> +\t/* walk backwards to get last-one-wins ordering */\n> +\tfor (i = island_regexes_nr - 1; i >= 0; i--) {\n> +\t\tif (!regexec(&island_regexes[i], refname,\n> +\t\t\t ARRAY_SIZE(matches), matches, 0))\n> +\t\t\tbreak;\n> +\t}\n> +\n> +\tif (i < 0)\n> +\t\treturn 0;\n> +\n> +\tif (matches[ARRAY_SIZE(matches) - 1].rm_so != -1)\n> +\t\twarning(_(\"island regex from config has \"\n> +\t\t\t \"too many capture groups (max=%d)\"),\n> +\t\t\t(int)ARRAY_SIZE(matches) - 2);\n> +\n> +\tfor (m = 1; m < ARRAY_SIZE(matches); m++) {\n> +\t\tregmatch_t *match = &matches[m];\n> +\n> +\t\tif (match->rm_so == -1)\n> +\t\t\tcontinue;\n> +\n> +\t\tif (island_name.len)\n> +\t\t\tstrbuf_addch(&island_name, '-');\n> +\n> +\t\tstrbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);\n> +\t}\n> +\n> +\tadd_ref_to_island(island_name.buf, oid);\n> +\tstrbuf_release(&island_name);\n> +\treturn 0;\n> +}\n> +\n> +static struct remote_island *get_core_island(void)\n> +{\n> +\tif (core_island_name) {\n> +\t\tkhiter_t pos = kh_get_str(remote_islands, core_island_name);\n> +\t\tif (pos < kh_end(remote_islands))\n> +\t\t\treturn kh_value(remote_islands, pos);\n> +\t}\n> +\n> +\treturn NULL;\n> +}\n> +\n> +static void deduplicate_islands(void)\n> +{\n> +\tstruct remote_island *island, *core = NULL, **list;\n> +\tunsigned int island_count, dst, src, ref, i = 0;\n> +\n> +\tisland_count = kh_size(remote_islands);\n> +\tALLOC_ARRAY(list, island_count);\n> +\n> +\tkh_foreach_value(remote_islands, island, {\n> +\t\tlist[i++] = island;\n> +\t});\n> +\n> +\tfor (ref = 0; ref + 1 < island_count; ref++) {\n> +\t\tfor (src = ref + 1, dst = src; src < island_count; src++) {\n> +\t\t\tif (list[ref]->hash == list[src]->hash)\n> +\t\t\t\tcontinue;\n> +\n> +\t\t\tif (src != dst)\n> +\t\t\t\tlist[dst] = list[src];\n> +\n> +\t\t\tdst++;\n> +\t\t}\n> +\t\tisland_count = dst;\n> +\t}\n> +\n> +\tisland_bitmap_size = (island_count / 32) + 1;\n> +\tcore = get_core_island();\n> +\n> +\tfor (i = 0; i < island_count; ++i) {\n> +\t\tmark_remote_island_1(list[i], core && list[i]->hash == core->hash);\n> +\t}\n> +\n> +\tfree(list);\n> +}\n> +\n> +void load_delta_islands(void)\n> +{\n> +\tisland_marks = kh_init_sha1();\n> +\tremote_islands = kh_init_str();\n> +\n> +\tgit_config(island_config_callback, NULL);\n> +\tfor_each_ref(find_island_for_ref, NULL);\n> +\tdeduplicate_islands();\n> +\n> +\tfprintf(stderr, _(\"Marked %d islands, done.\\n\"), island_counter);\n> +}\n> +\n> +void propagate_island_marks(struct commit *commit)\n> +{\n> +\tkhiter_t pos = kh_get_sha1(island_marks, commit->object.oid.hash);\n> +\n> +\tif (pos < kh_end(island_marks)) {\n> +\t\tstruct commit_list *p;\n> +\t\tstruct island_bitmap *root_marks = kh_value(island_marks, pos);\n> +\n> +\t\tparse_commit(commit);\n> +\t\tset_island_marks(&get_commit_tree(commit)->object, root_marks);\n> +\t\tfor (p = commit->parents; p; p = p->next)\n> +\t\t\tset_island_marks(&p->item->object, root_marks);\n> +\t}\n> +}\n> +\n> +int compute_pack_layers(struct packing_data *to_pack)\n> +{\n> +\tuint32_t i;\n> +\n> +\tif (!core_island_name || !island_marks)\n> +\t\treturn 1;\n> +\n> +\tfor (i = 0; i < to_pack->nr_objects; ++i) {\n> +\t\tstruct object_entry *entry = &to_pack->objects[i];\n> +\t\tkhiter_t pos = kh_get_sha1(island_marks, entry->idx.oid.hash);\n> +\n> +\t\tentry->layer = 1;\n> +\n> +\t\tif (pos < kh_end(island_marks)) {\n> +\t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n> +\n> +\t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n> +\t\t\t\tentry->layer = 0;\n> +\t\t}\n> +\t}\n> +\n> +\treturn 2;\n> +}\n> diff --git a/delta-islands.h b/delta-islands.h\n> new file mode 100644\n> index 0000000000..f9725730f4\n> --- /dev/null\n> +++ b/delta-islands.h\n> @@ -0,0 +1,11 @@\n> +#ifndef DELTA_ISLANDS_H\n> +#define DELTA_ISLANDS_H\n> +\n> +int island_delta_cmp(const struct object_id *a, const struct object_id *b);\n> +int in_same_island(const struct object_id *, const struct object_id *);\n> +void resolve_tree_islands(int progress, struct packing_data *to_pack);\n> +void load_delta_islands(void);\n> +void propagate_island_marks(struct commit *commit);\n> +int compute_pack_layers(struct packing_data *to_pack);\n> +\n> +#endif /* DELTA_ISLANDS_H */\n> diff --git a/pack-objects.h b/pack-objects.h\n> index edf74dabdd..8eecd67991 100644\n> --- a/pack-objects.h\n> +++ b/pack-objects.h\n> @@ -100,6 +100,10 @@ struct object_entry {\n> \tunsigned type_:TYPE_BITS;\n> \tunsigned no_try_delta:1;\n> \tunsigned in_pack_type:TYPE_BITS; /* could be delta */\n> +\n> +\tunsigned int tree_depth; /* should be repositioned for packing? */\n> +\tunsigned char layer;\n> +\n> \tunsigned preferred_base:1; /*\n> \t\t\t\t * we do not pack this, but is available\n> \t\t\t\t * to be used as the base object to delta\n> \n\nSorry, I spent so long reading this patch, I have run out of\ntime tonight (and I am busy tomorrow) to read the rest of the\nseries.\n\nATB,\nRamsay Jones\n\n"},{"id":"355304","messageId":"CAP8UFD1tX+rAxQc47o-50Kzo6hnX9mTWH2BPSq9HiO_OgBzYTw@mail.gmail.com","threadId":"49105","inReplyTo":"2113c74c-b230-6ea1-a980-d6d008bac759@ramsayjones.plus.com","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-13T03:33:59Z","receivedAt":"2018-08-13T03:34:04Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Aug 13, 2018 at 3:14 AM, Ramsay Jones\n wrote:\n> On 12/08/18 06:11, Christian Couder wrote:\n\n>> Because the inefficiency primarily arises when an\n>> object is delitified against another object that does\n>\n> s/delitified/deltified/ ?\n\nOk, this will be in the next reroll if any.\n\n>> not exist in the same fork, we partition objects into\n>> sets that appear in the same fork, and define\n>> \"delta islands\". When finding delta base, we do not\n>> allow an object outside the same island to be\n>> considered as its base.\n\n>> --- /dev/null\n>> +++ b/delta-islands.c\n>> @@ -0,0 +1,493 @@\n>> +#include \"cache.h\"\n>> +#include \"attr.h\"\n>> +#include \"object.h\"\n>> +#include \"blob.h\"\n>> +#include \"commit.h\"\n>> +#include \"tag.h\"\n>> +#include \"tree.h\"\n>> +#include \"delta.h\"\n>> +#include \"pack.h\"\n>> +#include \"tree-walk.h\"\n>> +#include \"diff.h\"\n>> +#include \"revision.h\"\n>> +#include \"list-objects.h\"\n>> +#include \"progress.h\"\n>> +#include \"refs.h\"\n>> +#include \"khash.h\"\n>\n> I was wondering how many copies of the inline functions\n> introduced by this header we had, so:\n>\n> $ nm git | grep ' t ' | cut -d' ' -f3 | sort | uniq -c | sort -rn | grep kh_\n> 3 kh_resize_sha1\n> 3 kh_put_sha1\n> 3 kh_init_sha1\n> 3 kh_get_sha1\n> 1 kh_resize_str\n> 1 kh_resize_sha1_pos\n> 1 kh_put_str\n> 1 kh_put_sha1_pos\n> 1 kh_init_str\n> 1 kh_init_sha1_pos\n> 1 kh_get_str\n> 1 kh_get_sha1_pos\n> 1 kh_destroy_sha1\n> $\n>\n> Looking at the individual object files, we see:\n>\n> $ nm pack-bitmap-write.o | grep ' t ' | grep kh_\n> 00000000000001cc t kh_get_sha1\n> 00000000000001b7 t kh_init_sha1\n> 000000000000085e t kh_put_sha1\n> 0000000000000310 t kh_resize_sha1\n> $\n>\n> So, the two instances of the sha1 hash-map are never\n> destroyed (kh_destroy_sha1 is not present in the object\n> file).\n\nThis is interesting (even though it seems related to more code than\nthe current patch series).\n\nAs those hash maps are in 'struct bitmap_writer' and a static instance is used:\n\n static struct bitmap_writer writer;\n\nit maybe ok.\n\n> $ nm pack-bitmap.o | grep ' t ' | grep kh_\n> 00000000000002d9 t kh_destroy_sha1\n> 000000000000032b t kh_get_sha1\n> 0000000000000daa t kh_get_sha1_pos\n> 00000000000002c4 t kh_init_sha1\n> 0000000000000d95 t kh_init_sha1_pos\n> 00000000000009bd t kh_put_sha1\n> 0000000000001432 t kh_put_sha1_pos\n> 000000000000046f t kh_resize_sha1\n> 0000000000000eee t kh_resize_sha1_pos\n> $\n>\n> The sha1_pos hash-map is not destroyed here.\n\nYeah, maybe a line like:\n\nkh_destroy_pos(b->ext_index.positions);\n\nis missing from free_bitmap_index()?\n\nAdding that should be in a separate patch from this series though.\n\n> $ nm delta-islands.o | grep ' t ' | grep kh_\n> 00000000000002be t kh_get_sha1\n> 0000000000000e52 t kh_get_str\n> 00000000000002a9 t kh_init_sha1\n> 0000000000000e3d t kh_init_str\n> 0000000000000950 t kh_put_sha1\n> 00000000000014e4 t kh_put_str\n> 0000000000000402 t kh_resize_sha1\n> 0000000000000f96 t kh_resize_str\n> $\n>\n> And neither the sha1 or str hash-maps are destroyed here.\n> (That is not necessarily a problem, of course! ;-) )\n\nThe instances are declared as static:\n\n static khash_sha1 *island_marks;\n\n static kh_str_t *remote_islands;\n\nso it maybe ok.\n\n>> +struct island_bitmap {\n>> + uint32_t refcount;\n>> + uint32_t bits[];\n>\n> Use FLEX_ARRAY here? We are slowly moving toward requiring\n> certain C99 features, but I can't remember a flex array\n> weather-balloon patch.\n\nThis was already discussed by Junio and Peff there:\n\nhttps://public-inbox.org/git/20180727130229.GB18599@sigill.intra.peff.net/\n\n>> +};\n\n>> +int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n>\n> Hmm, what does the trg_ prefix stand for?\n>\n>> +{\n>> + khiter_t trg_pos, src_pos;\n>> +\n>> + /* If we aren't using islands, assume everything goes together. */\n>> + if (!island_marks)\n>> + return 1;\n>> +\n>> + /*\n>> + * If we don't have a bitmap for the target, we can delta it\n>\n> ... Ah, OK, trg_ => target.\n\nI am ok to replace \"trg\" with \"target\" (or maybe \"dst\"? or something\nelse) and \"src\" with \"source\" if you think it would make things\nclearer.\n\n>> +static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n>> +{\n>> + uint64_t sha_core;\n>> + struct remote_island *rl = NULL;\n>> +\n>> + int hash_ret;\n>> + khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);\n>> +\n>> + if (hash_ret) {\n>> + kh_key(remote_islands, pos) = xstrdup(island_name);\n>> + kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));\n>> + }\n>> +\n>> + rl = kh_value(remote_islands, pos);\n>> + oid_array_append(&rl->oids, oid);\n>> +\n>> + memcpy(&sha_core, oid->hash, sizeof(uint64_t));\n>> + rl->hash += sha_core;\n>\n> Hmm, so the first 64-bits of the oid of each ref that is part of\n> this island is added together as a 'hash' for the island. And this\n> is used to de-duplicate the islands? Any false positives? (does it\n> matter - it would only affect performance, not correctness, right?)\n\nI would think that a false positive from pure chance is very unlikely.\nWe would need to approach billions of delta islands (as 2 to the power\n64/2 is in the order of billions) for the probability to be\nsignificant. GitHub has less than 50 millions users and it is very\nunlikely that a significant proportion of these users will fork the\nsame repo.\n\nNow if there is a false positive because two forks have exactly the\nsame refs, then it is not a problem if they are considered the same,\nbecause they are actually the same.\n\n>> +}\n\n> Sorry, I spent so long reading this patch, I have run out of\n> time tonight (and I am busy tomorrow) to read the rest of the\n> series.\n\nThank you for your interesting review,\nChristian.\n"},{"id":"355356","messageId":"7a780fe9-e8bf-804a-82e6-8df81cd5c41c@ramsayjones.plus.com","threadId":"49105","inReplyTo":"CAP8UFD1tX+rAxQc47o-50Kzo6hnX9mTWH2BPSq9HiO_OgBzYTw@mail.gmail.com","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2018-08-13T12:17:18Z","receivedAt":"2018-08-13T12:17:23Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 13/08/18 04:33, Christian Couder wrote:\n> On Mon, Aug 13, 2018 at 3:14 AM, Ramsay Jones\n[snip]\n>> And neither the sha1 or str hash-maps are destroyed here.\n>> (That is not necessarily a problem, of course! ;-) )\n> \n> The instances are declared as static:\n> \n> static khash_sha1 *island_marks;\n> \n> static kh_str_t *remote_islands;\n> \n> so it maybe ok.\n\nYes, that's fine.\n\n> \n>>> +struct island_bitmap {\n>>> + uint32_t refcount;\n>>> + uint32_t bits[];\n>>\n>> Use FLEX_ARRAY here? We are slowly moving toward requiring\n>> certain C99 features, but I can't remember a flex array\n>> weather-balloon patch.\n> \n> This was already discussed by Junio and Peff there:\n> \n> https://public-inbox.org/git/20180727130229.GB18599@sigill.intra.peff.net/\n> \n\nThat is a fine discussion, without a firm conclusion, but I don't\nthink you can simply do nothing here:\n\n $ cat -n junk.c\n 1\t#include \n 2\t\n 3\tstruct island_bitmap {\n 4\t\tuint32_t refcount;\n 5\t\tuint32_t bits[];\n 6\t};\n 7\t\n $ gcc --std=c89 --pedantic -c junk.c\n junk.c:5:11: warning: ISO C90 does not support flexible array members [-Wpedantic]\n uint32_t bits[];\n ^~~~\n $ gcc --std=c99 --pedantic -c junk.c\n $ \n \n>>> +};\n> \n>>> +int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n>>\n>> Hmm, what does the trg_ prefix stand for?\n>>\n>>> +{\n>>> + khiter_t trg_pos, src_pos;\n>>> +\n>>> + /* If we aren't using islands, assume everything goes together. */\n>>> + if (!island_marks)\n>>> + return 1;\n>>> +\n>>> + /*\n>>> + * If we don't have a bitmap for the target, we can delta it\n>>\n>> ... Ah, OK, trg_ => target.\n> \n> I am ok to replace \"trg\" with \"target\" (or maybe \"dst\"? or something\n> else) and \"src\" with \"source\" if you think it would make things\n> clearer.\n\nIf it had been dst_ (or target), I would not have had a 'huh?'\nmoment, but it is not all that important.\n\n> \n>>> +static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n>>> +{\n>>> + uint64_t sha_core;\n>>> + struct remote_island *rl = NULL;\n>>> +\n>>> + int hash_ret;\n>>> + khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);\n>>> +\n>>> + if (hash_ret) {\n>>> + kh_key(remote_islands, pos) = xstrdup(island_name);\n>>> + kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));\n>>> + }\n>>> +\n>>> + rl = kh_value(remote_islands, pos);\n>>> + oid_array_append(&rl->oids, oid);\n>>> +\n>>> + memcpy(&sha_core, oid->hash, sizeof(uint64_t));\n>>> + rl->hash += sha_core;\n>>\n>> Hmm, so the first 64-bits of the oid of each ref that is part of\n>> this island is added together as a 'hash' for the island. And this\n>> is used to de-duplicate the islands? Any false positives? (does it\n>> matter - it would only affect performance, not correctness, right?)\n> \n> I would think that a false positive from pure chance is very unlikely.\n> We would need to approach billions of delta islands (as 2 to the power\n> 64/2 is in the order of billions) for the probability to be\n> significant. GitHub has less than 50 millions users and it is very\n> unlikely that a significant proportion of these users will fork the\n> same repo.\n> \n> Now if there is a false positive because two forks have exactly the\n> same refs, then it is not a problem if they are considered the same,\n> because they are actually the same.\n\nYep, good point.\n\nATB,\nRamsay Jones\n"},{"id":"355422","messageId":"20180813181149.GA10013@sigill.intra.peff.net","threadId":"49105","inReplyTo":"7a780fe9-e8bf-804a-82e6-8df81cd5c41c@ramsayjones.plus.com","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-13T18:11:49Z","receivedAt":"2018-08-13T18:11:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 01:17:18PM +0100, Ramsay Jones wrote:\n\n> >>> +struct island_bitmap {\n> >>> + uint32_t refcount;\n> >>> + uint32_t bits[];\n> >>\n> >> Use FLEX_ARRAY here? We are slowly moving toward requiring\n> >> certain C99 features, but I can't remember a flex array\n> >> weather-balloon patch.\n> > \n> > This was already discussed by Junio and Peff there:\n> > \n> > https://public-inbox.org/git/20180727130229.GB18599@sigill.intra.peff.net/\n> > \n> \n> That is a fine discussion, without a firm conclusion, but I don't\n> think you can simply do nothing here:\n> \n> $ cat -n junk.c\n> 1\t#include \n> 2\t\n> 3\tstruct island_bitmap {\n> 4\t\tuint32_t refcount;\n> 5\t\tuint32_t bits[];\n> 6\t};\n> 7\t\n> $ gcc --std=c89 --pedantic -c junk.c\n> junk.c:5:11: warning: ISO C90 does not support flexible array members [-Wpedantic]\n> uint32_t bits[];\n> ^~~~\n> $ gcc --std=c99 --pedantic -c junk.c\n\nRight, whether we use the FLEX_ALLOC macros or not, this needs to be\ndeclared with FLEX_ARRAY, not an empty \"[]\".\n\nI'm fine either way on using the FLEX_ALLOC macros.\n\n> >> ... Ah, OK, trg_ => target.\n> > \n> > I am ok to replace \"trg\" with \"target\" (or maybe \"dst\"? or something\n> > else) and \"src\" with \"source\" if you think it would make things\n> > clearer.\n> \n> If it had been dst_ (or target), I would not have had a 'huh?'\n> moment, but it is not all that important.\n\nFWIW, these are all inherited from try_delta(), etc, in the existing\ncode. I'm fine with using another term, but we should probably do it\nuniversally. And if we do, probably \"base\" is a better name than \"src\",\nsince the direction depends on which part of the relationship you are\nconsidering. I'm not sure what that makes \"dst\".\n\n-Peff\n"},{"id":"355448","messageId":"20180813190005.GB10013@sigill.intra.peff.net","threadId":"49105","inReplyTo":"CAP8UFD1tX+rAxQc47o-50Kzo6hnX9mTWH2BPSq9HiO_OgBzYTw@mail.gmail.com","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-13T19:00:06Z","receivedAt":"2018-08-13T19:00:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 05:33:59AM +0200, Christian Couder wrote:\n\n> >> + memcpy(&sha_core, oid->hash, sizeof(uint64_t));\n> >> + rl->hash += sha_core;\n> >\n> > Hmm, so the first 64-bits of the oid of each ref that is part of\n> > this island is added together as a 'hash' for the island. And this\n> > is used to de-duplicate the islands? Any false positives? (does it\n> > matter - it would only affect performance, not correctness, right?)\n> \n> I would think that a false positive from pure chance is very unlikely.\n> We would need to approach billions of delta islands (as 2 to the power\n> 64/2 is in the order of billions) for the probability to be\n> significant. GitHub has less than 50 millions users and it is very\n> unlikely that a significant proportion of these users will fork the\n> same repo.\n> \n> Now if there is a false positive because two forks have exactly the\n> same refs, then it is not a problem if they are considered the same,\n> because they are actually the same.\n\nRight, the idea is to find such same-ref setups to avoid spending a\npointless bit in the per-object bitmap. In the GitHub setup, it would be\nan indication that two people forked at exactly the same time, so they\nhave the same refs and the same delta requirements. If one of them later\nupdates, that relationship would change at the next repack.\n\nI don't know that we ever collected numbers for how often this happens.\nSo let me see if I can dig some up.\n\nOn our git/git repository network, it looks like we have ~14k forks, and\n~4k are unique by this hashing scheme. So it really is saving us\n10k-bits per bitmap. That's over 1k-byte per object in the worst case.\nThere are ~24M objects (many times what is in git.git, but people push\nlots of random things to their forks), so that's saving us up to 24GB in\nRAM. Of course it almost certainly isn't that helpful in practice, since\nwe copy-on-write the bitmaps to avoid the full cost per object. But I\nthink it's fair to say it is helping (more numbers below).\n\nThe distribution of buckets itself looks pretty power-law-ish from\neyeballing it. The biggest one has 92 forks, and then it trails off\nquickly to smaller numbers, and then eventually a long tail of\nsingletons.\n\nThe numbers for torvalds/linux are similar. There are ~23k forks, only\n~8k of which are unique. rails/rails has 12k/17k unique. So there's some\nfluctuation, but the notion that there will be a bunch of identical\nforks seems solid.\n\nIf you're curious what the actual memory usage is for a repack of\ngit/git, here are some rough numbers from eyeballing RSS via \"top\" while\nwatching the repack progress meter (I didn't want to do a full valgrind\nrun because it's S-L-O-W):\n\n - after loading the islands, we're at ~3GB RSS. Some of that is shared\n (the mmap'd packed-refs file is 1GB by itself), but probably 1-1.5GB\n is real heap, likely from the gigantic fork list.\n\n - we grow to around 6GB RSS before starting \"counting objects\". I\n think this is largely prepare_revision_walk(), since we're making\n \"struct commit\" objects for all the ref tips (and this is mmap-ing\n packfiles, too, which counts against our RSS)\n\n - by the time \"counting objects\" is done, we're at ~10GB. We're not\n yet running with Duy's memory-slimming for pack-objects, so it's\n 100+ bytes per object_entry. Which means we're probably only\n spending a GB or so on island bitmaps, but at this point we've only\n marked commits and root-trees.\n\n - By the time \"propagating island marks\" is done, we'll have marked\n all the trees and blobs, and RSS is up to ~11GB.\n\nSo all in all (and I'd emphasize this is extremely rough) I think it\nprobably costs about 2GB for the feature in this particular case. But\nyou need much more to repack at this size sanely anyway.\n\nIf I were doing this patch series from scratch, I might implement the\nfork de-duping and copy-on-write bits successively so I could take good\nmeasurements of how much they help (and brag about it in the commit\nmessages). But I don't know if it's worth untangling now or not.\n\n-Peff\n"},{"id":"355802","messageId":"CAP8UFD1A8Z_Eh+N8204zSUG5Pnji+5=uwOiDr+LrbFGFJ-qPtg@mail.gmail.com","threadId":"49105","inReplyTo":"20180813181149.GA10013@sigill.intra.peff.net","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-16T06:02:05Z","receivedAt":"2018-08-16T06:02:09Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Aug 13, 2018 at 8:11 PM, Jeff King wrote:\n> On Mon, Aug 13, 2018 at 01:17:18PM +0100, Ramsay Jones wrote:\n>\n>> >>> +struct island_bitmap {\n>> >>> + uint32_t refcount;\n>> >>> + uint32_t bits[];\n>> >>\n>> >> Use FLEX_ARRAY here? We are slowly moving toward requiring\n>> >> certain C99 features, but I can't remember a flex array\n>> >> weather-balloon patch.\n>> >\n>> > This was already discussed by Junio and Peff there:\n>> >\n>> > https://public-inbox.org/git/20180727130229.GB18599@sigill.intra.peff.net/\n>>\n>> That is a fine discussion, without a firm conclusion, but I don't\n>> think you can simply do nothing here:\n>>\n>> $ cat -n junk.c\n>> 1 #include \n>> 2\n>> 3 struct island_bitmap {\n>> 4 uint32_t refcount;\n>> 5 uint32_t bits[];\n>> 6 };\n>> 7\n>> $ gcc --std=c89 --pedantic -c junk.c\n>> junk.c:5:11: warning: ISO C90 does not support flexible array members [-Wpedantic]\n>> uint32_t bits[];\n>> ^~~~\n>> $ gcc --std=c99 --pedantic -c junk.c\n>\n> Right, whether we use the FLEX_ALLOC macros or not, this needs to be\n> declared with FLEX_ARRAY, not an empty \"[]\".\n\nOk, it will use FLEX_ARRAY in the reroll I will send soon.\n\nThanks Ramsay and Peff!\n"},{"id":"355803","messageId":"CAP8UFD0Rm6t+uiE7s=HtA1MpW7YuK_G24wadkk7AgJUpPhkrrQ@mail.gmail.com","threadId":"49105","inReplyTo":"20180813190005.GB10013@sigill.intra.peff.net","subject":"Re: [PATCH v4 1/7] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-16T06:04:42Z","receivedAt":"2018-08-16T06:04:46Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Aug 13, 2018 at 9:00 PM, Jeff King wrote:\n> On Mon, Aug 13, 2018 at 05:33:59AM +0200, Christian Couder wrote:\n>\n>> >> + memcpy(&sha_core, oid->hash, sizeof(uint64_t));\n>> >> + rl->hash += sha_core;\n>> >\n>> > Hmm, so the first 64-bits of the oid of each ref that is part of\n>> > this island is added together as a 'hash' for the island. And this\n>> > is used to de-duplicate the islands? Any false positives? (does it\n>> > matter - it would only affect performance, not correctness, right?)\n>>\n>> I would think that a false positive from pure chance is very unlikely.\n>> We would need to approach billions of delta islands (as 2 to the power\n>> 64/2 is in the order of billions) for the probability to be\n>> significant. GitHub has less than 50 millions users and it is very\n>> unlikely that a significant proportion of these users will fork the\n>> same repo.\n>>\n>> Now if there is a false positive because two forks have exactly the\n>> same refs, then it is not a problem if they are considered the same,\n>> because they are actually the same.\n>\n> Right, the idea is to find such same-ref setups to avoid spending a\n> pointless bit in the per-object bitmap. In the GitHub setup, it would be\n> an indication that two people forked at exactly the same time, so they\n> have the same refs and the same delta requirements. If one of them later\n> updates, that relationship would change at the next repack.\n>\n> I don't know that we ever collected numbers for how often this happens.\n> So let me see if I can dig some up.\n>\n> On our git/git repository network, it looks like we have ~14k forks, and\n> ~4k are unique by this hashing scheme. So it really is saving us\n> 10k-bits per bitmap. That's over 1k-byte per object in the worst case.\n> There are ~24M objects (many times what is in git.git, but people push\n> lots of random things to their forks), so that's saving us up to 24GB in\n> RAM. Of course it almost certainly isn't that helpful in practice, since\n> we copy-on-write the bitmaps to avoid the full cost per object. But I\n> think it's fair to say it is helping (more numbers below).\n\n[...]\n\n> So all in all (and I'd emphasize this is extremely rough) I think it\n> probably costs about 2GB for the feature in this particular case. But\n> you need much more to repack at this size sanely anyway.\n\nThanks for the interesting numbers!\n"}]}