{"thread":{"id":"52272","subject":"[PATCH v3 0/9] Rewrite packfile reuse code","startedAt":"2019-11-15T14:16:03Z","lastAt":"2020-01-23T22:29:38Z","messageCount":42,"participants":["Christian Couder","Jonathan Tan","Junio C Hamano","Johannes Schindelin","Jeff King"],"isPatch":true,"patchVersion":3,"patchTotal":9},"messages":[{"id":"386315","messageId":"20191115141541.11149-1-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":null,"subject":"[PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:32Z","receivedAt":"2019-11-15T14:16:03Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series is rewriting the code that tries to reuse existing\npackfiles.\n\nThe code in this patch series was written by GitHub, and Peff nicely\nprovided it in the following discussion:\n\nhttps://public-inbox.org/git/3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au/\n\nThe first versions of this patch series were also discussed:\n\nV2: https://public-inbox.org/git/20191019103531.23274-1-chriscool@tuxfamily.org/\nV1: https://public-inbox.org/git/20190913130226.7449-1-chriscool@tuxfamily.org/\n\nThanks to the reviewers!\n\nAccording to Peff this new code is a lot smarter than what it\nreplaces. It allows \"holes\" in the chunks of packfile to be reused,\nand skips over them. It rewrites OFS_DELTA offsets as it goes to\naccount for the holes. So it's basically a linear walk over the\npackfile, but with the important distinction that we don't add those\nobjects to the object_entry array, which makes them very lightweight\n(especially in memory use, but they also aren't considered bases for\nfinding new deltas, etc). It seems like a good compromise between the\ncost to serve a clone and the quality of the resulting packfile.\n\nChanges since the previous patch series are the following:\n\n - Rebased onto current master (d9f6f3b619, The first batch post 2.24\n cycle, 2019-11-10)\n\n - Remove a paragraph in the commit message of patch 3/9 as suggested\n by Jonathan Tan.\n\n - Improve commit message of patch 9/9 as suggested by Jonathan Tan.\n\n - Renamed fields of struct reused_chunk in patch 9/9 as suggested by\n Jonathan Tan.\n\n - Added a few comments in patch 9/9 as suggested by Jonathan Tan.\n\nIt could be a good idea if Peff could answer some of the comments made\nby Jonathan Tan about patch 9/9.\n\nI have put Peff as the author of all the commits.\n\nJeff King (9):\n builtin/pack-objects: report reused packfile objects\n packfile: expose get_delta_base()\n ewah/bitmap: introduce bitmap_word_alloc()\n pack-bitmap: don't rely on bitmap_git->reuse_objects\n pack-bitmap: introduce bitmap_walk_contains()\n csum-file: introduce hashfile_total()\n pack-objects: introduce pack.allowPackReuse\n builtin/pack-objects: introduce obj_is_packed()\n pack-objects: improve partial packfile reuse\n\n Documentation/config/pack.txt | 4 +\n builtin/pack-objects.c | 243 +++++++++++++++++++++++++++-------\n csum-file.h | 9 ++\n ewah/bitmap.c | 13 +-\n ewah/ewok.h | 1 +\n pack-bitmap.c | 178 ++++++++++++++++++-------\n pack-bitmap.h | 6 +-\n packfile.c | 10 +-\n packfile.h | 3 +\n 9 files changed, 357 insertions(+), 110 deletions(-)\n\n-- \n2.24.0-rc1\n\n"},{"id":"386316","messageId":"20191115141541.11149-2-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 1/9] builtin/pack-objects: report reused packfile objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:33Z","receivedAt":"2019-11-15T14:16:03Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nTo see when packfile reuse kicks in or not, it is useful to\nshow reused packfile objects statistics in the output of\nupload-pack.\n\nHelped-by: James Ramsay \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5876583220..f2c2703090 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3509,7 +3509,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (progress)\n \t\tfprintf_ln(stderr,\n \t\t\t _(\"Total %\"PRIu32\" (delta %\"PRIu32\"),\"\n-\t\t\t \" reused %\"PRIu32\" (delta %\"PRIu32\")\"),\n-\t\t\t written, written_delta, reused, reused_delta);\n+\t\t\t \" reused %\"PRIu32\" (delta %\"PRIu32\"),\"\n+\t\t\t \" pack-reused %\"PRIu32),\n+\t\t\t written, written_delta, reused, reused_delta,\n+\t\t\t reuse_packfile_objects);\n \treturn 0;\n }\n-- \n2.24.0-rc1\n\n"},{"id":"386317","messageId":"20191115141541.11149-3-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 2/9] packfile: expose get_delta_base()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:34Z","receivedAt":"2019-11-15T14:16:04Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nIn a following commit get_delta_base() will be used outside\npackfile.c, so let's make it non static and declare it in\npackfile.h.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n packfile.c | 10 +++++-----\n packfile.h | 3 +++\n 2 files changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 355066de17..81e66847bf 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1173,11 +1173,11 @@ const struct packed_git *has_packed_and_bad(struct repository *r,\n \treturn NULL;\n }\n \n-static off_t get_delta_base(struct packed_git *p,\n-\t\t\t\t struct pack_window **w_curs,\n-\t\t\t\t off_t *curpos,\n-\t\t\t\t enum object_type type,\n-\t\t\t\t off_t delta_obj_offset)\n+off_t get_delta_base(struct packed_git *p,\n+\t\t struct pack_window **w_curs,\n+\t\t off_t *curpos,\n+\t\t enum object_type type,\n+\t\t off_t delta_obj_offset)\n {\n \tunsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);\n \toff_t base_offset;\ndiff --git a/packfile.h b/packfile.h\nindex fc7904ec81..ec536a4ae5 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -151,6 +151,9 @@ void *unpack_entry(struct repository *r, struct packed_git *, off_t, enum object\n unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\n int unpack_object_header(struct packed_git *, struct pack_window **, off_t *, unsigned long *);\n+off_t get_delta_base(struct packed_git *p, struct pack_window **w_curs,\n+\t\t off_t *curpos, enum object_type type,\n+\t\t off_t delta_obj_offset);\n \n void release_pack_memory(size_t);\n \n-- \n2.24.0-rc1\n\n"},{"id":"386318","messageId":"20191115141541.11149-4-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:35Z","receivedAt":"2019-11-15T14:16:07Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nIn a following commit we will need to allocate a variable\nnumber of bitmap words, instead of always 32, so let's add\nbitmap_word_alloc() for this purpose.\n\nHelped-by: Jonathan Tan \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n ewah/bitmap.c | 13 +++++++++----\n ewah/ewok.h | 1 +\n 2 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..b5fed9621f 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -22,21 +22,26 @@\n #define EWAH_MASK(x) ((eword_t)1 << (x % BITS_IN_EWORD))\n #define EWAH_BLOCK(x) (x / BITS_IN_EWORD)\n \n-struct bitmap *bitmap_new(void)\n+struct bitmap *bitmap_word_alloc(size_t word_alloc)\n {\n \tstruct bitmap *bitmap = xmalloc(sizeof(struct bitmap));\n-\tbitmap->words = xcalloc(32, sizeof(eword_t));\n-\tbitmap->word_alloc = 32;\n+\tbitmap->words = xcalloc(word_alloc, sizeof(eword_t));\n+\tbitmap->word_alloc = word_alloc;\n \treturn bitmap;\n }\n \n+struct bitmap *bitmap_new(void)\n+{\n+\treturn bitmap_word_alloc(32);\n+}\n+\n void bitmap_set(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\n \n \tif (block >= self->word_alloc) {\n \t\tsize_t old_size = self->word_alloc;\n-\t\tself->word_alloc = block * 2;\n+\t\tself->word_alloc = block ? block * 2 : 1;\n \t\tREALLOC_ARRAY(self->words, self->word_alloc);\n \t\tmemset(self->words + old_size, 0x0,\n \t\t\t(self->word_alloc - old_size) * sizeof(eword_t));\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 84b2a29faa..1b98b57c8b 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -172,6 +172,7 @@ struct bitmap {\n };\n \n struct bitmap *bitmap_new(void);\n+struct bitmap *bitmap_word_alloc(size_t word_alloc);\n void bitmap_set(struct bitmap *self, size_t pos);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_reset(struct bitmap *self);\n-- \n2.24.0-rc1\n\n"},{"id":"386319","messageId":"20191115141541.11149-6-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:37Z","receivedAt":"2019-11-15T14:16:08Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will use this helper function in a following commit to\ntell us if an object is packed.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 12 ++++++++++++\n pack-bitmap.h | 3 +++\n 2 files changed, 15 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 016d0319fc..8a51302a1a 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -826,6 +826,18 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n+int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n+\t\t\t struct bitmap *bitmap, const struct object_id *oid)\n+{\n+\tint idx;\n+\n+\tif (!bitmap)\n+\t\treturn 0;\n+\n+\tidx = bitmap_position(bitmap_git, oid);\n+\treturn idx >= 0 && bitmap_get(bitmap, idx);\n+}\n+\n void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\n \t\t\t\t show_reachable_fn show_reachable)\n {\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 466c5afa09..6ab6033dbe 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -3,6 +3,7 @@\n \n #include \"ewah/ewok.h\"\n #include \"khash.h\"\n+#include \"pack.h\"\n #include \"pack-objects.h\"\n \n struct commit;\n@@ -53,6 +54,8 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\n+int bitmap_walk_contains(struct bitmap_index *,\n+\t\t\t struct bitmap *bitmap, const struct object_id *oid);\n \n /*\n * After a traversal has been performed by prepare_bitmap_walk(), this can be\n-- \n2.24.0-rc1\n\n"},{"id":"386320","messageId":"20191115141541.11149-7-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 6/9] csum-file: introduce hashfile_total()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:38Z","receivedAt":"2019-11-15T14:16:10Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will need this helper function in a following commit\nto give us total number of bytes fed to the hashfile so far.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n csum-file.h | 9 +++++++++\n 1 file changed, 9 insertions(+)\n\ndiff --git a/csum-file.h b/csum-file.h\nindex a98b1eee53..f9cbd317fb 100644\n--- a/csum-file.h\n+++ b/csum-file.h\n@@ -42,6 +42,15 @@ void hashflush(struct hashfile *f);\n void crc32_begin(struct hashfile *);\n uint32_t crc32_end(struct hashfile *);\n \n+/*\n+ * Returns the total number of bytes fed to the hashfile so far (including ones\n+ * that have not been written out to the descriptor yet).\n+ */\n+static inline off_t hashfile_total(struct hashfile *f)\n+{\n+\treturn f->total + f->offset;\n+}\n+\n static inline void hashwrite_u8(struct hashfile *f, uint8_t data)\n {\n \thashwrite(f, &data, sizeof(data));\n-- \n2.24.0-rc1\n\n"},{"id":"386321","messageId":"20191115141541.11149-5-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 4/9] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:36Z","receivedAt":"2019-11-15T14:16:10Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will no longer compute bitmap_git->reuse_objects in a\nfollowing commit, so we cannot rely on it anymore to\nterminate the loop early; we have to iterate to the end.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 18 +++++++-----------\n 1 file changed, 7 insertions(+), 11 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e07c798879..016d0319fc 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -622,7 +622,7 @@ static void show_objects_for_type(\n \tenum object_type object_type,\n \tshow_reachable_fn show_reach)\n {\n-\tsize_t pos = 0, i = 0;\n+\tsize_t i = 0;\n \tuint32_t offset;\n \n \tstruct ewah_iterator it;\n@@ -630,13 +630,15 @@ static void show_objects_for_type(\n \n \tstruct bitmap *objects = bitmap_git->result;\n \n-\tif (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)\n-\t\treturn;\n-\n \tewah_iterator_init(&it, type_filter);\n \n-\twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n+\tfor (i = 0; i < objects->word_alloc &&\n+\t\t\tewah_iterator_next(&filter, &it); i++) {\n \t\teword_t word = objects->words[i] & filter;\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n+\n+\t\tif (!word)\n+\t\t\tcontinue;\n \n \t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n \t\t\tstruct object_id oid;\n@@ -648,9 +650,6 @@ static void show_objects_for_type(\n \n \t\t\toffset += ewah_bit_ctz64(word >> offset);\n \n-\t\t\tif (pos + offset < bitmap_git->reuse_objects)\n-\t\t\t\tcontinue;\n-\n \t\t\tentry = &bitmap_git->pack->revindex[pos + offset];\n \t\t\tnth_packed_object_oid(&oid, bitmap_git->pack, entry->nr);\n \n@@ -659,9 +658,6 @@ static void show_objects_for_type(\n \n \t\t\tshow_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);\n \t\t}\n-\n-\t\tpos += BITS_IN_EWORD;\n-\t\ti++;\n \t}\n }\n \n-- \n2.24.0-rc1\n\n"},{"id":"386322","messageId":"20191115141541.11149-8-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 7/9] pack-objects: introduce pack.allowPackReuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:39Z","receivedAt":"2019-11-15T14:16:11Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's make it possible to configure if we want pack reuse or not.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config/pack.txt | 4 ++++\n builtin/pack-objects.c | 8 +++++++-\n 2 files changed, 11 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex 1d66f0c992..58323a351f 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -27,6 +27,10 @@ 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.allowPackReuse::\n+\tWhen true, which is the default, Git will try to reuse parts\n+\tof existing packfiles when preparing new packfiles.\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]\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f2c2703090..4fcfcf6097 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -96,6 +96,7 @@ static off_t reuse_packfile_offset;\n \n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n+static int allow_pack_reuse = 1;\n static enum {\n \tWRITE_BITMAP_FALSE = 0,\n \tWRITE_BITMAP_QUIET,\n@@ -2699,6 +2700,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\tuse_bitmap_index_default = git_config_bool(k, v);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.allowpackreuse\")) {\n+\t\tallow_pack_reuse = git_config_bool(k, v);\n+\t\treturn 0;\n+\t}\n \tif (!strcmp(k, \"pack.threads\")) {\n \t\tdelta_search_threads = git_config_int(k, v);\n \t\tif (delta_search_threads < 0)\n@@ -3030,7 +3035,8 @@ static void loosen_unused_packed_objects(void)\n */\n static int pack_options_allow_reuse(void)\n {\n-\treturn pack_to_stdout &&\n+\treturn allow_pack_reuse &&\n+\t pack_to_stdout &&\n \t allow_ofs_delta &&\n \t !ignore_packed_keep_on_disk &&\n \t !ignore_packed_keep_in_core &&\n-- \n2.24.0-rc1\n\n"},{"id":"386324","messageId":"20191115141541.11149-9-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 8/9] builtin/pack-objects: introduce obj_is_packed()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:40Z","receivedAt":"2019-11-15T14:16:14Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's refactor the way we check if an object is packed by\nintroducing obj_is_packed(). This function is now a simple\nwrapper around packlist_find(), but it will evolve in a\nfollowing commit.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 4fcfcf6097..08898331ef 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2553,6 +2553,11 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \tfree(p);\n }\n \n+static int obj_is_packed(const struct object_id *oid)\n+{\n+\treturn !!packlist_find(&to_pack, oid);\n+}\n+\n static void add_tag_chain(const struct object_id *oid)\n {\n \tstruct tag *tag;\n@@ -2564,7 +2569,7 @@ static void add_tag_chain(const struct object_id *oid)\n \t * it was included via bitmaps, we would not have parsed it\n \t * previously).\n \t */\n-\tif (packlist_find(&to_pack, oid))\n+\tif (obj_is_packed(oid))\n \t\treturn;\n \n \ttag = lookup_tag(the_repository, oid);\n@@ -2588,7 +2593,7 @@ static int add_ref_tag(const char *path, const struct object_id *oid, int flag,\n \n \tif (starts_with(path, \"refs/tags/\") && /* is a tag? */\n \t !peel_ref(path, &peeled) && /* peelable? */\n-\t packlist_find(&to_pack, &peeled)) /* object packed? */\n+\t obj_is_packed(&peeled)) /* object packed? */\n \t\tadd_tag_chain(oid);\n \treturn 0;\n }\n-- \n2.24.0-rc1\n\n"},{"id":"386323","messageId":"20191115141541.11149-10-chriscool@tuxfamily.org","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"[PATCH v3 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-11-15T14:15:41Z","receivedAt":"2019-11-15T14:16:15Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nThe old code to reuse deltas from an existing packfile\njust tried to dump a whole segment of the pack verbatim.\nThat's faster than the traditional way of actually adding\nobjects to the packing list, but it didn't kick in very\noften. This new code is really going for a middle ground:\ndo _some_ per-object work, but way less than we'd\ntraditionally do.\n\nFor instance, packing torvalds/linux on GitHub servers\njust now reused 6.5M objects, but only needed ~50k\nchunks.\n\nTo implement this, we store the chunks of the packfile\nthat we reuse in a dynamic array of `struct reused_chunk`,\nand we use a reuse_packfile_bitmap to speed up reusing\nparts of packfiles.\n\nThe dynamic array of `struct reused_chunk` is useful\nbecause we need to know the accumulated offset due to\nmissing objects. So without the array we'd end up having\nto walk over the revindex for that set of objects. The\narray is basically caching those accumulated offsets\n(for the parts we _do_ include), so we don't have to\ncompute them repeatedly.\n\nAdditional checks are added in have_duplicate_entry()\nand obj_is_packed() to avoid duplicate objects in the\nreuse bitmap. It was probably buggy to not have such a\ncheck before.\n\nIf a client both asks for a tag by sha1 and specifies\n\"include-tag\", we may end up including the tag in the reuse\nbitmap (due to the first thing), and then later adding it to\nthe packlist (due to the second). This results in duplicate\nobjects in the pack, which git chokes on. We should notice\nthat we are already including it when doing the include-tag\nportion, and avoid adding it to the packlist.\n\nThe simplest place to fix this is right in add_ref_tag,\nwhere we could avoid peeling the tag at all if we know that\nwe are already including it. However, I've pushed the check\ninstead into have_duplicate_entry(). This fixes not only\nthis case, but also means that we cannot have any similar\nproblems lurking in other code.\n\nNo tests, because git does not actually exhibit this \"ask\nfor it and also include-tag\" behavior. We do one or the\nother on clone, depending on whether --single-branch is set.\nHowever, libgit2 does both.\n\nHelped-by: Jonathan Tan \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 222 ++++++++++++++++++++++++++++++++---------\n pack-bitmap.c | 150 ++++++++++++++++++++--------\n pack-bitmap.h | 3 +-\n 3 files changed, 288 insertions(+), 87 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 08898331ef..64ab033923 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -92,7 +92,7 @@ static struct progress *progress_state;\n \n static struct packed_git *reuse_packfile;\n static uint32_t reuse_packfile_objects;\n-static off_t reuse_packfile_offset;\n+static struct bitmap *reuse_packfile_bitmap;\n \n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n@@ -785,57 +785,185 @@ static struct object_entry **compute_write_order(void)\n \treturn wo;\n }\n \n-static off_t write_reused_pack(struct hashfile *f)\n+\n+/*\n+ * A reused set of objects. All objects in a chunk have the same\n+ * relative position in the original packfile and the generated\n+ * packfile.\n+ */\n+\n+static struct reused_chunk {\n+\t/* The offset of the first object of this chunk in the original\n+\t * packfile. */\n+\toff_t original;\n+\t/* The offset of the first object of this chunk in the generated\n+\t * packfile minus \"original\". */\n+\toff_t difference;\n+} *reused_chunks;\n+static int reused_chunks_nr;\n+static int reused_chunks_alloc;\n+\n+static void record_reused_object(off_t where, off_t offset)\n {\n-\tunsigned char buffer[8192];\n-\toff_t to_write, total;\n-\tint fd;\n+\tif (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].difference == offset)\n+\t\treturn;\n \n-\tif (!is_pack_valid(reuse_packfile))\n-\t\tdie(_(\"packfile is invalid: %s\"), reuse_packfile->pack_name);\n+\tALLOC_GROW(reused_chunks, reused_chunks_nr + 1,\n+\t\t reused_chunks_alloc);\n+\treused_chunks[reused_chunks_nr].original = where;\n+\treused_chunks[reused_chunks_nr].difference = offset;\n+\treused_chunks_nr++;\n+}\n \n-\tfd = git_open(reuse_packfile->pack_name);\n-\tif (fd < 0)\n-\t\tdie_errno(_(\"unable to open packfile for reuse: %s\"),\n-\t\t\t reuse_packfile->pack_name);\n+/*\n+ * Binary search to find the chunk that \"where\" is in. Note\n+ * that we're not looking for an exact match, just the first\n+ * chunk that contains it (which implicitly ends at the start\n+ * of the next chunk.\n+ */\n+static off_t find_reused_offset(off_t where)\n+{\n+\tint lo = 0, hi = reused_chunks_nr;\n+\twhile (lo < hi) {\n+\t\tint mi = lo + ((hi - lo) / 2);\n+\t\tif (where == reused_chunks[mi].original)\n+\t\t\treturn reused_chunks[mi].difference;\n+\t\tif (where < reused_chunks[mi].original)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t}\n \n-\tif (lseek(fd, sizeof(struct pack_header), SEEK_SET) == -1)\n-\t\tdie_errno(_(\"unable to seek in reused packfile\"));\n+\t/*\n+\t * The first chunk starts at zero, so we can't have gone below\n+\t * there.\n+\t */\n+\tassert(lo);\n+\treturn reused_chunks[lo-1].difference;\n+}\n+\n+static void write_reused_pack_one(size_t pos, struct hashfile *out,\n+\t\t\t\t struct pack_window **w_curs)\n+{\n+\toff_t offset, next, cur;\n+\tenum object_type type;\n+\tunsigned long size;\n \n-\tif (reuse_packfile_offset < 0)\n-\t\treuse_packfile_offset = reuse_packfile->pack_size - the_hash_algo->rawsz;\n+\toffset = reuse_packfile->revindex[pos].offset;\n+\tnext = reuse_packfile->revindex[pos + 1].offset;\n \n-\ttotal = to_write = reuse_packfile_offset - sizeof(struct pack_header);\n+\trecord_reused_object(offset, offset - hashfile_total(out));\n \n-\twhile (to_write) {\n-\t\tint read_pack = xread(fd, buffer, sizeof(buffer));\n+\tcur = offset;\n+\ttype = unpack_object_header(reuse_packfile, w_curs, &cur, &size);\n+\tassert(type >= 0);\n \n-\t\tif (read_pack <= 0)\n-\t\t\tdie_errno(_(\"unable to read from reused packfile\"));\n+\tif (type == OBJ_OFS_DELTA) {\n+\t\toff_t base_offset;\n+\t\toff_t fixup;\n+\n+\t\tunsigned char header[MAX_PACK_OBJECT_HEADER];\n+\t\tunsigned len;\n+\n+\t\tbase_offset = get_delta_base(reuse_packfile, w_curs, &cur, type, offset);\n+\t\tassert(base_offset != 0);\n+\n+\t\t/* Convert to REF_DELTA if we must... */\n+\t\tif (!allow_ofs_delta) {\n+\t\t\tint base_pos = find_revindex_position(reuse_packfile, base_offset);\n+\t\t\tconst unsigned char *base_sha1 =\n+\t\t\t\tnth_packed_object_sha1(reuse_packfile,\n+\t\t\t\t\t\t reuse_packfile->revindex[base_pos].nr);\n+\n+\t\t\tlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t\t\t OBJ_REF_DELTA, size);\n+\t\t\thashwrite(out, header, len);\n+\t\t\thashwrite(out, base_sha1, 20);\n+\t\t\tcopy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);\n+\t\t\treturn;\n+\t\t}\n \n-\t\tif (read_pack > to_write)\n-\t\t\tread_pack = to_write;\n+\t\t/* Otherwise see if we need to rewrite the offset... */\n+\t\tfixup = find_reused_offset(offset) -\n+\t\t\tfind_reused_offset(base_offset);\n+\t\tif (fixup) {\n+\t\t\tunsigned char ofs_header[10];\n+\t\t\tunsigned i, ofs_len;\n+\t\t\toff_t ofs = offset - base_offset - fixup;\n \n-\t\thashwrite(f, buffer, read_pack);\n-\t\tto_write -= read_pack;\n+\t\t\tlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t\t\t OBJ_OFS_DELTA, size);\n+\n+\t\t\ti = sizeof(ofs_header) - 1;\n+\t\t\tofs_header[i] = ofs & 127;\n+\t\t\twhile (ofs >>= 7)\n+\t\t\t\tofs_header[--i] = 128 | (--ofs & 127);\n+\n+\t\t\tofs_len = sizeof(ofs_header) - i;\n+\n+\t\t\thashwrite(out, header, len);\n+\t\t\thashwrite(out, ofs_header + sizeof(ofs_header) - ofs_len, ofs_len);\n+\t\t\tcopy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* ...otherwise we have no fixup, and can write it verbatim */\n+\t}\n+\n+\tcopy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);\n+}\n+\n+static size_t write_reused_pack_verbatim(struct hashfile *out,\n+\t\t\t\t\t struct pack_window **w_curs)\n+{\n+\tsize_t pos = 0;\n+\n+\twhile (pos < reuse_packfile_bitmap->word_alloc &&\n+\t\t\treuse_packfile_bitmap->words[pos] == (eword_t)~0)\n+\t\tpos++;\n+\n+\tif (pos) {\n+\t\toff_t to_write;\n+\n+\t\twritten = (pos * BITS_IN_EWORD);\n+\t\tto_write = reuse_packfile->revindex[written].offset\n+\t\t\t- sizeof(struct pack_header);\n+\n+\t\t/* We're recording one chunk, not one object. */\n+\t\trecord_reused_object(sizeof(struct pack_header), 0);\n+\t\thashflush(out);\n+\t\tcopy_pack_data(out, reuse_packfile, w_curs,\n+\t\t\tsizeof(struct pack_header), to_write);\n \n-\t\t/*\n-\t\t * We don't know the actual number of objects written,\n-\t\t * only how many bytes written, how many bytes total, and\n-\t\t * how many objects total. So we can fake it by pretending all\n-\t\t * objects we are writing are the same size. This gives us a\n-\t\t * smooth progress meter, and at the end it matches the true\n-\t\t * answer.\n-\t\t */\n-\t\twritten = reuse_packfile_objects *\n-\t\t\t\t(((double)(total - to_write)) / total);\n \t\tdisplay_progress(progress_state, written);\n \t}\n+\treturn pos;\n+}\n \n-\tclose(fd);\n-\twritten = reuse_packfile_objects;\n-\tdisplay_progress(progress_state, written);\n-\treturn reuse_packfile_offset - sizeof(struct pack_header);\n+static void write_reused_pack(struct hashfile *f)\n+{\n+\tsize_t i = 0;\n+\tuint32_t offset;\n+\tstruct pack_window *w_curs = NULL;\n+\n+\tif (allow_ofs_delta)\n+\t\ti = write_reused_pack_verbatim(f, &w_curs);\n+\n+\tfor (; i < reuse_packfile_bitmap->word_alloc; ++i) {\n+\t\teword_t word = reuse_packfile_bitmap->words[i];\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n+\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n+\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\twrite_reused_pack_one(pos + offset, f, &w_curs);\n+\t\t\tdisplay_progress(progress_state, ++written);\n+\t\t}\n+\t}\n+\n+\tunuse_pack(&w_curs);\n }\n \n static const char no_split_warning[] = N_(\n@@ -868,11 +996,9 @@ static void write_pack_file(void)\n \t\toffset = write_pack_header(f, nr_remaining);\n \n \t\tif (reuse_packfile) {\n-\t\t\toff_t packfile_size;\n \t\t\tassert(pack_to_stdout);\n-\n-\t\t\tpackfile_size = write_reused_pack(f);\n-\t\t\toffset += packfile_size;\n+\t\t\twrite_reused_pack(f);\n+\t\t\toffset = hashfile_total(f);\n \t\t}\n \n \t\tnr_written = 0;\n@@ -1001,6 +1127,10 @@ static int have_duplicate_entry(const struct object_id *oid,\n {\n \tstruct object_entry *entry;\n \n+\tif (reuse_packfile_bitmap &&\n+\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))\n+\t\treturn 1;\n+\n \tentry = packlist_find(&to_pack, oid);\n \tif (!entry)\n \t\treturn 0;\n@@ -2555,7 +2685,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \n static int obj_is_packed(const struct object_id *oid)\n {\n-\treturn !!packlist_find(&to_pack, oid);\n+\treturn packlist_find(&to_pack, oid) ||\n+\t\t(reuse_packfile_bitmap &&\n+\t\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n }\n \n static void add_tag_chain(const struct object_id *oid)\n@@ -2661,6 +2793,7 @@ static void prepare_pack(int window, int depth)\n \n \tif (nr_deltas && n > 1) {\n \t\tunsigned nr_done = 0;\n+\n \t\tif (progress)\n \t\t\tprogress_state = start_progress(_(\"Compressing objects\"),\n \t\t\t\t\t\t\tnr_deltas);\n@@ -3042,7 +3175,6 @@ static int pack_options_allow_reuse(void)\n {\n \treturn allow_pack_reuse &&\n \t pack_to_stdout &&\n-\t allow_ofs_delta &&\n \t !ignore_packed_keep_on_disk &&\n \t !ignore_packed_keep_in_core &&\n \t (!local || !have_non_local_packs) &&\n@@ -3059,7 +3191,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t\t\tbitmap_git,\n \t\t\t&reuse_packfile,\n \t\t\t&reuse_packfile_objects,\n-\t\t\t&reuse_packfile_offset)) {\n+\t\t\t&reuse_packfile_bitmap)) {\n \t\tassert(reuse_packfile_objects);\n \t\tnr_result += reuse_packfile_objects;\n \t\tdisplay_progress(progress_state, nr_result);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 8a51302a1a..cbfc544411 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -326,6 +326,13 @@ static int load_pack_bitmap(struct bitmap_index *bitmap_git)\n \tmunmap(bitmap_git->map, bitmap_git->map_size);\n \tbitmap_git->map = NULL;\n \tbitmap_git->map_size = 0;\n+\n+\tkh_destroy_oid_map(bitmap_git->bitmaps);\n+\tbitmap_git->bitmaps = NULL;\n+\n+\tkh_destroy_oid_pos(bitmap_git->ext_index.positions);\n+\tbitmap_git->ext_index.positions = NULL;\n+\n \treturn -1;\n }\n \n@@ -764,65 +771,126 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \treturn NULL;\n }\n \n-int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n-\t\t\t\t struct packed_git **packfile,\n-\t\t\t\t uint32_t *entries,\n-\t\t\t\t off_t *up_to)\n+static void try_partial_reuse(struct bitmap_index *bitmap_git,\n+\t\t\t size_t pos,\n+\t\t\t struct bitmap *reuse,\n+\t\t\t struct pack_window **w_curs)\n {\n+\tstruct revindex_entry *revidx;\n+\toff_t offset;\n+\tenum object_type type;\n+\tunsigned long size;\n+\n+\tif (pos >= bitmap_git->pack->num_objects)\n+\t\treturn; /* not actually in the pack */\n+\n+\trevidx = &bitmap_git->pack->revindex[pos];\n+\toffset = revidx->offset;\n+\ttype = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);\n+\tif (type < 0)\n+\t\treturn; /* broken packfile, punt */\n+\n+\tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n+\t\toff_t base_offset;\n+\t\tint base_pos;\n+\n+\t\t/*\n+\t\t * Find the position of the base object so we can look it up\n+\t\t * in our bitmaps. If we can't come up with an offset, or if\n+\t\t * that offset is not in the revidx, the pack is corrupt.\n+\t\t * There's nothing we can do, so just punt on this object,\n+\t\t * and the normal slow path will complain about it in\n+\t\t * more detail.\n+\t\t */\n+\t\tbase_offset = get_delta_base(bitmap_git->pack, w_curs,\n+\t\t\t\t\t &offset, type, revidx->offset);\n+\t\tif (!base_offset)\n+\t\t\treturn;\n+\t\tbase_pos = find_revindex_position(bitmap_git->pack, base_offset);\n+\t\tif (base_pos < 0)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * We assume delta dependencies always point backwards. This\n+\t\t * lets us do a single pass, and is basically always true\n+\t\t * due to the way OFS_DELTAs work. You would not typically\n+\t\t * find REF_DELTA in a bitmapped pack, since we only bitmap\n+\t\t * packs we write fresh, and OFS_DELTA is the default). But\n+\t\t * let's double check to make sure the pack wasn't written with\n+\t\t * odd parameters.\n+\t\t */\n+\t\tif (base_pos >= pos)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * And finally, if we're not sending the base as part of our\n+\t\t * reuse chunk, then don't send this object either. The base\n+\t\t * would come after us, along with other objects not\n+\t\t * necessarily in the pack, which means we'd need to convert\n+\t\t * to REF_DELTA on the fly. Better to just let the normal\n+\t\t * object_entry code path handle it.\n+\t\t */\n+\t\tif (!bitmap_get(reuse, base_pos))\n+\t\t\treturn;\n+\t}\n+\n \t/*\n-\t * Reuse the packfile content if we need more than\n-\t * 90% of its objects\n+\t * If we got here, then the object is OK to reuse. Mark it.\n \t */\n-\tstatic const double REUSE_PERCENT = 0.9;\n+\tbitmap_set(reuse, pos);\n+}\n \n+int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct packed_git **packfile_out,\n+\t\t\t\t uint32_t *entries,\n+\t\t\t\t struct bitmap **reuse_out)\n+{\n \tstruct bitmap *result = bitmap_git->result;\n-\tuint32_t reuse_threshold;\n-\tuint32_t i, reuse_objects = 0;\n+\tstruct bitmap *reuse;\n+\tstruct pack_window *w_curs = NULL;\n+\tsize_t i = 0;\n+\tuint32_t offset;\n \n \tassert(result);\n \n-\tfor (i = 0; i < result->word_alloc; ++i) {\n-\t\tif (result->words[i] != (eword_t)~0) {\n-\t\t\treuse_objects += ewah_bit_ctz64(~result->words[i]);\n-\t\t\tbreak;\n-\t\t}\n-\n-\t\treuse_objects += BITS_IN_EWORD;\n-\t}\n+\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n+\t\ti++;\n \n-#ifdef GIT_BITMAP_DEBUG\n-\t{\n-\t\tconst unsigned char *sha1;\n-\t\tstruct revindex_entry *entry;\n+\t/* Don't mark objects not in the packfile */\n+\tif (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n+\t\ti = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n \n-\t\tentry = &bitmap_git->reverse_index->revindex[reuse_objects];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git->pack, entry->nr);\n+\treuse = bitmap_word_alloc(i);\n+\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\n \n-\t\tfprintf(stderr, \"Failed to reuse at %d (%016llx)\\n\",\n-\t\t\treuse_objects, result->words[i]);\n-\t\tfprintf(stderr, \" %s\\n\", hash_to_hex(sha1));\n-\t}\n-#endif\n+\tfor (; i < result->word_alloc; ++i) {\n+\t\teword_t word = result->words[i];\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n \n-\tif (!reuse_objects)\n-\t\treturn -1;\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n \n-\tif (reuse_objects >= bitmap_git->pack->num_objects) {\n-\t\tbitmap_git->reuse_objects = *entries = bitmap_git->pack->num_objects;\n-\t\t*up_to = -1; /* reuse the full pack */\n-\t\t*packfile = bitmap_git->pack;\n-\t\treturn 0;\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\ttry_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);\n+\t\t}\n \t}\n \n-\treuse_threshold = bitmap_popcount(bitmap_git->result) * REUSE_PERCENT;\n+\tunuse_pack(&w_curs);\n \n-\tif (reuse_objects < reuse_threshold)\n+\t*entries = bitmap_popcount(reuse);\n+\tif (!*entries) {\n+\t\tbitmap_free(reuse);\n \t\treturn -1;\n+\t}\n \n-\tbitmap_git->reuse_objects = *entries = reuse_objects;\n-\t*up_to = bitmap_git->pack->revindex[reuse_objects].offset;\n-\t*packfile = bitmap_git->pack;\n-\n+\t/*\n+\t * Drop any reused objects from the result, since they will not\n+\t * need to be handled separately.\n+\t */\n+\tbitmap_and_not(result, reuse);\n+\t*packfile_out = bitmap_git->pack;\n+\t*reuse_out = reuse;\n \treturn 0;\n }\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 6ab6033dbe..bcd03b8993 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -50,7 +50,8 @@ void test_bitmap_walk(struct rev_info *revs);\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\n int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n \t\t\t\t struct packed_git **packfile,\n-\t\t\t\t uint32_t *entries, off_t *up_to);\n+\t\t\t\t uint32_t *entries,\n+\t\t\t\t struct bitmap **reuse_out);\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\n-- \n2.24.0-rc1\n\n"},{"id":"386338","messageId":"20191115180319.113991-1-jonathantanmy@google.com","threadId":"52272","inReplyTo":"20191115141541.11149-1-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-11-15T18:03:19Z","receivedAt":"2019-11-15T18:03:29Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> It could be a good idea if Peff could answer some of the comments made\n> by Jonathan Tan about patch 9/9.\n> \n> I have put Peff as the author of all the commits.\n\nThanks. I think the series looks mostly good except for the questions I\nraised in patch 9/9, so I'll wait for Peff to respond too.\n"},{"id":"386975","messageId":"xmqqeexwxyc0.fsf@gitster-ct.c.googlers.com","threadId":"52272","inReplyTo":"20191115180319.113991-1-jonathantanmy@google.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-11-25T06:30:07Z","receivedAt":"2019-11-25T06:30:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n>> It could be a good idea if Peff could answer some of the comments made\n>> by Jonathan Tan about patch 9/9.\n>> \n>> I have put Peff as the author of all the commits.\n>\n> Thanks. I think the series looks mostly good except for the questions I\n> raised in patch 9/9, so I'll wait for Peff to respond too.\n\nHmph, the round before this one has been in 'next' for quite a\nwhile, so should I eject it before waiting for Peff to respond\nbefore queuing this one?\n\nThanks.\n"},{"id":"386977","messageId":"xmqqa78kxy1i.fsf@gitster-ct.c.googlers.com","threadId":"52272","inReplyTo":"xmqqeexwxyc0.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-11-25T06:36:25Z","receivedAt":"2019-11-25T06:36:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Jonathan Tan writes:\n>\n>>> It could be a good idea if Peff could answer some of the comments made\n>>> by Jonathan Tan about patch 9/9.\n>>> \n>>> I have put Peff as the author of all the commits.\n>>\n>> Thanks. I think the series looks mostly good except for the questions I\n>> raised in patch 9/9, so I'll wait for Peff to respond too.\n>\n> Hmph, the round before this one has been in 'next' for quite a\n> while, so should I eject it before waiting for Peff to respond\n> before queuing this one?\n\nAfter rebasing these v3 patches on top of the base of the one in\n'next', the only difference seems to be the log message of 3/9 and\nthe contents of 9/9. I guess I'll mark the topic as \"on hold\" for\nnow before doing anything, as I am officially taking a time-off most\nof this week ;-)\n\nThanks.\n"},{"id":"387649","messageId":"xmqq8snpw2pk.fsf@gitster-ct.c.googlers.com","threadId":"52272","inReplyTo":"xmqqa78kxy1i.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-06T21:42:31Z","receivedAt":"2019-12-06T21:42:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Junio C Hamano writes:\n>\n>> Jonathan Tan writes:\n>>\n>>>> It could be a good idea if Peff could answer some of the comments made\n>>>> by Jonathan Tan about patch 9/9.\n>>>> \n>>>> I have put Peff as the author of all the commits.\n>>>\n>>> Thanks. I think the series looks mostly good except for the questions I\n>>> raised in patch 9/9, so I'll wait for Peff to respond too.\n>>\n>> Hmph, the round before this one has been in 'next' for quite a\n>> while, so should I eject it before waiting for Peff to respond\n>> before queuing this one?\n>\n> After rebasing these v3 patches on top of the base of the one in\n> 'next', the only difference seems to be the log message of 3/9 and\n> the contents of 9/9. I guess I'll mark the topic as \"on hold\" for\n> now before doing anything, as I am officially taking a time-off most\n> of this week ;-)\n\nSo..., that week has passed---anything new?\n\nThanks.\n"},{"id":"387672","messageId":"CAP8UFD20LMxuV7KWAvobybHYZruDiADX-yOFPLyMxsHS7HZN0g@mail.gmail.com","threadId":"52272","inReplyTo":"xmqq8snpw2pk.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-07T10:12:27Z","receivedAt":"2019-12-07T10:12:44Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Dec 6, 2019 at 10:42 PM Junio C Hamano wrote:\n>\n> Junio C Hamano writes:\n>\n> > Junio C Hamano writes:\n> >\n> >> Jonathan Tan writes:\n> >>\n> >>>> It could be a good idea if Peff could answer some of the comments made\n> >>>> by Jonathan Tan about patch 9/9.\n> >>>>\n> >>>> I have put Peff as the author of all the commits.\n> >>>\n> >>> Thanks. I think the series looks mostly good except for the questions I\n> >>> raised in patch 9/9, so I'll wait for Peff to respond too.\n> >>\n> >> Hmph, the round before this one has been in 'next' for quite a\n> >> while, so should I eject it before waiting for Peff to respond\n> >> before queuing this one?\n> >\n> > After rebasing these v3 patches on top of the base of the one in\n> > 'next', the only difference seems to be the log message of 3/9 and\n> > the contents of 9/9. I guess I'll mark the topic as \"on hold\" for\n> > now before doing anything, as I am officially taking a time-off most\n> > of this week ;-)\n>\n> So..., that week has passed---anything new?\n\nUnfortunately, no.\n\nIf you want I can send an incremental change on the content of 9/9 on\ntop of what's in next. Otherwise I can't see what I could do on this.\n\nPeff, could you tell us if you might have time to take a look at this soon?\n"},{"id":"387700","messageId":"nycvar.QRO.7.76.6.1912072145290.31080@tvgsbejvaqbjf.bet","threadId":"52272","inReplyTo":"CAP8UFD20LMxuV7KWAvobybHYZruDiADX-yOFPLyMxsHS7HZN0g@mail.gmail.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-12-07T20:47:07Z","receivedAt":"2019-12-07T20:47:46Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Chris,\n\nOn Sat, 7 Dec 2019, Christian Couder wrote:\n\n> On Fri, Dec 6, 2019 at 10:42 PM Junio C Hamano wrote:\n> >\n> > Junio C Hamano writes:\n> >\n> > > Junio C Hamano writes:\n> > >\n> > >> Jonathan Tan writes:\n> > >>\n> > >>>> It could be a good idea if Peff could answer some of the comments made\n> > >>>> by Jonathan Tan about patch 9/9.\n> > >>>>\n> > >>>> I have put Peff as the author of all the commits.\n> > >>>\n> > >>> Thanks. I think the series looks mostly good except for the questions I\n> > >>> raised in patch 9/9, so I'll wait for Peff to respond too.\n> > >>\n> > >> Hmph, the round before this one has been in 'next' for quite a\n> > >> while, so should I eject it before waiting for Peff to respond\n> > >> before queuing this one?\n> > >\n> > > After rebasing these v3 patches on top of the base of the one in\n> > > 'next', the only difference seems to be the log message of 3/9 and\n> > > the contents of 9/9. I guess I'll mark the topic as \"on hold\" for\n> > > now before doing anything, as I am officially taking a time-off most\n> > > of this week ;-)\n> >\n> > So..., that week has passed---anything new?\n>\n> Unfortunately, no.\n>\n> If you want I can send an incremental change on the content of 9/9 on\n> top of what's in next. Otherwise I can't see what I could do on this.\n>\n> Peff, could you tell us if you might have time to take a look at this soon?\n\nChris, correct me if I am wrong, but was it not your decision to\ncontribute these patches? Are you saying that you do not understand them\nwell enough to drive this patch series forward (e.g. address all reviews\nand questions) and are basically trying to force Peff to contribute them\ninstead?\n\nCiao,\nJohannes\n"},{"id":"387708","messageId":"CAP8UFD1rmv7dvWBe5=dnrh8icfsE_PWEukmuUmqB9dWJ9NQTkg@mail.gmail.com","threadId":"52272","inReplyTo":"nycvar.QRO.7.76.6.1912072145290.31080@tvgsbejvaqbjf.bet","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-08T07:53:31Z","receivedAt":"2019-12-08T07:53:47Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Johannes,\n\nOn Sat, Dec 7, 2019 at 9:47 PM Johannes Schindelin\n wrote:\n>\n> On Sat, 7 Dec 2019, Christian Couder wrote:\n>\n> > On Fri, Dec 6, 2019 at 10:42 PM Junio C Hamano wrote:\n> > >\n> > > Junio C Hamano writes:\n> > >\n> > > > Junio C Hamano writes:\n> > > >\n> > > >> Jonathan Tan writes:\n> > > >>\n> > > >>>> It could be a good idea if Peff could answer some of the comments made\n> > > >>>> by Jonathan Tan about patch 9/9.\n> > > >>>>\n> > > >>>> I have put Peff as the author of all the commits.\n> > > >>>\n> > > >>> Thanks. I think the series looks mostly good except for the questions I\n> > > >>> raised in patch 9/9, so I'll wait for Peff to respond too.\n> > > >>\n> > > >> Hmph, the round before this one has been in 'next' for quite a\n> > > >> while, so should I eject it before waiting for Peff to respond\n> > > >> before queuing this one?\n> > > >\n> > > > After rebasing these v3 patches on top of the base of the one in\n> > > > 'next', the only difference seems to be the log message of 3/9 and\n> > > > the contents of 9/9. I guess I'll mark the topic as \"on hold\" for\n> > > > now before doing anything, as I am officially taking a time-off most\n> > > > of this week ;-)\n> > >\n> > > So..., that week has passed---anything new?\n> >\n> > Unfortunately, no.\n> >\n> > If you want I can send an incremental change on the content of 9/9 on\n> > top of what's in next. Otherwise I can't see what I could do on this.\n> >\n> > Peff, could you tell us if you might have time to take a look at this soon?\n>\n> Chris, correct me if I am wrong, but was it not your decision to\n> contribute these patches?\n\nPlease take a look at:\n\nhttps://public-inbox.org/git/3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au/\n\nand Peff's response to James Ramsay's email.\n\nPeff wrote:\n\n> It's been on my todo list to upstream for a while, but I've dragged my\n> feet on it because there's a lot of cleanup/polishing from the original\n> patches (they were never very clean in the first place, and we've merged\n> a dozen or more times with upstream since then, so the updates are\n> spread across a bunch of merge commits).\n\nand then:\n\n> Yeah, I think we should work on getting our changes (including those\n> stats) into upstream.\n\nSo actually I thought that I was helping Peff on this, though I know\nof course that it's also helping GitLab and everyone else. That's why\nI put Peff as the author of the patches.\n\n> Are you saying that you do not understand them\n> well enough to drive this patch series forward (e.g. address all reviews\n> and questions) and are basically trying to force Peff to contribute them\n> instead?\n\nYeah, I don't understand them well enough to answer Jonathan Tan's questions.\n\nBut no I am not trying to force Peff. I am trying to work with him.\nWhen he said he thought we should work on getting the change into\nupstream, I just thought he meant it and would be willing to help.\n\n\n\n\n\n> Ciao,\n> Johannes\n"},{"id":"387709","messageId":"nycvar.QRO.7.76.6.1912080942360.31080@tvgsbejvaqbjf.bet","threadId":"52272","inReplyTo":"CAP8UFD1rmv7dvWBe5=dnrh8icfsE_PWEukmuUmqB9dWJ9NQTkg@mail.gmail.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-12-08T08:54:01Z","receivedAt":"2019-12-08T08:54:44Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Chris,\n\nOn Sun, 8 Dec 2019, Christian Couder wrote:\n\n> Peff wrote:\n>\n> > It's been on my todo list to upstream for a while, but I've dragged my\n> > feet on it because there's a lot of cleanup/polishing from the original\n> > patches (they were never very clean in the first place, and we've merged\n> > a dozen or more times with upstream since then, so the updates are\n> > spread across a bunch of merge commits).\n>\n> and then:\n>\n> > Yeah, I think we should work on getting our changes (including those\n> > stats) into upstream.\n>\n> So actually I thought that I was helping Peff on this, though I know\n> of course that it's also helping GitLab and everyone else.\n\nIn my experience, sending the initial set of patches is the easiest part\nof contributing patches, by far. The most involved part of the process is\nto react to reviewer comments and to prepare new iterations.\n\nYou can see this challenge in action in all the Git for Windows\npatches/patch series I am \"upstreaming\".\n\nSo actually I think that you are doing a disservice to Peff: if he had\ntime for that tedious part of the patch contribution, I am sure it would\nhave been no burden at all to send the initial set of patches.\n\n> That's why I put Peff as the author of the patches.\n\nNo, that is not the reason. You might think that that is the reason, but\nthe real reason why Peff is marked as the author of those patches is that\nhe really authored those patches.\n\nIn light of what you said, I don't think that it is a good idea to go\nforward by leaning even further on Peff. From his activity on the Git\nmailing list, I deduce that he is not exactly in need of even more work.\n\nInstead, I think that if you truly want to push these patches forward, you\nwill have to dig deeper yourself, and answer Jonathan Tan's questions, and\npossibly adjust the patches accordingly and send a new iteration.\n\nI perceive it as very unfair toward Peff that this has not yet happened.\n\nCiao,\nJohannes\n"},{"id":"387711","messageId":"CAP8UFD1fp_uaR5+=Hp24y4zq+rVuwfgiFntDtr8i3B7Bx4k-_w@mail.gmail.com","threadId":"52272","inReplyTo":"nycvar.QRO.7.76.6.1912080942360.31080@tvgsbejvaqbjf.bet","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-08T10:26:43Z","receivedAt":"2019-12-08T10:26:58Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Dscho,\n\nOn Sun, Dec 8, 2019 at 9:54 AM Johannes Schindelin\n wrote:\n>\n> On Sun, 8 Dec 2019, Christian Couder wrote:\n>\n> > Peff wrote:\n> >\n> > > It's been on my todo list to upstream for a while, but I've dragged my\n> > > feet on it because there's a lot of cleanup/polishing from the original\n> > > patches (they were never very clean in the first place, and we've merged\n> > > a dozen or more times with upstream since then, so the updates are\n> > > spread across a bunch of merge commits).\n> >\n> > and then:\n> >\n> > > Yeah, I think we should work on getting our changes (including those\n> > > stats) into upstream.\n> >\n> > So actually I thought that I was helping Peff on this, though I know\n> > of course that it's also helping GitLab and everyone else.\n>\n> In my experience, sending the initial set of patches is the easiest part\n> of contributing patches, by far. The most involved part of the process is\n> to react to reviewer comments and to prepare new iterations.\n>\n> You can see this challenge in action in all the Git for Windows\n> patches/patch series I am \"upstreaming\".\n>\n> So actually I think that you are doing a disservice to Peff: if he had\n> time for that tedious part of the patch contribution, I am sure it would\n> have been no burden at all to send the initial set of patches.\n\nI think Peff can say by himself what he thinks about my work when I\nrework the raw patches he sends to help get them upstreamed.\n\nIt's not the first time that I have done that and every time I have\ndone it, I think he has found it useful. Even this time he also wrote\nthat my work has been useful.\n\n> > That's why I put Peff as the author of the patches.\n>\n> No, that is not the reason. You might think that that is the reason, but\n> the real reason why Peff is marked as the author of those patches is that\n> he really authored those patches.\n\nThat doesn't contradict at all what I am saying. I am saying that I\nkept Peff as the author because I am just helping him, which means\nthat I actually acknowledge that he really authored those patches, no?\n\n> In light of what you said, I don't think that it is a good idea to go\n> forward by leaning even further on Peff. From his activity on the Git\n> mailing list, I deduce that he is not exactly in need of even more work.\n\nI think it's ok to ping people, even many times, when they have said\nthat they want to work on something but for some reason don't do it.\nThat's what Junio did by the way too. Junio just pinged everyone\ninvolved, and then I pinged Peff specifically as I think the part of\nthe work left is more his than mine.\n\nIf Peff had said that he doesn't want to work on this any more then I\nwouldn't ping him, and I would perhaps try something else, like just\nask for only the first patch (1/9) to be merged.\n\n> Instead, I think that if you truly want to push these patches forward, you\n> will have to dig deeper yourself, and answer Jonathan Tan's questions, and\n> possibly adjust the patches accordingly and send a new iteration.\n\nI think that it's ok to ping Peff until he says that he doesn't or\ncannot for some reason work on this anymore. This shouldn't be a big\nburden for him to say that, no?\n\n> I perceive it as very unfair toward Peff that this has not yet happened.\n\nI perceive it as unfair to me that you think that I have to do a lot\nof work on this when Peff hasn't even said that he doesn't want to, or\ncannot, answer Jonathan's question.\n\nBest,\nChristian.\n"},{"id":"387713","messageId":"nycvar.QRO.7.76.6.1912081144110.31080@tvgsbejvaqbjf.bet","threadId":"52272","inReplyTo":"CAP8UFD1fp_uaR5+=Hp24y4zq+rVuwfgiFntDtr8i3B7Bx4k-_w@mail.gmail.com","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-12-08T10:45:48Z","receivedAt":"2019-12-08T10:46:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Chris,\n\nOn Sun, 8 Dec 2019, Christian Couder wrote:\n\n> I perceive it as unfair to me that you think that I have to do a lot\n> of work on this when Peff hasn't even said that he doesn't want to, or\n> cannot, answer Jonathan's question.\n\nWell, you have time enough to send lengthy replies on a Sunday morning\n(while Peff apparently did not even have time to say that he lacks the\ntime to work on this).\n\nSo there,\nJohannes\n"},{"id":"387726","messageId":"20191209061853.GA38588@coredump.intra.peff.net","threadId":"52272","inReplyTo":"nycvar.QRO.7.76.6.1912080942360.31080@tvgsbejvaqbjf.bet","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T06:18:53Z","receivedAt":"2019-12-09T06:19:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Dec 08, 2019 at 09:54:01AM +0100, Johannes Schindelin wrote:\n\n> > That's why I put Peff as the author of the patches.\n> \n> No, that is not the reason. You might think that that is the reason, but\n> the real reason why Peff is marked as the author of those patches is that\n> he really authored those patches.\n> \n> In light of what you said, I don't think that it is a good idea to go\n> forward by leaning even further on Peff. From his activity on the Git\n> mailing list, I deduce that he is not exactly in need of even more work.\n> \n> Instead, I think that if you truly want to push these patches forward, you\n> will have to dig deeper yourself, and answer Jonathan Tan's questions, and\n> possibly adjust the patches accordingly and send a new iteration.\n> \n> I perceive it as very unfair toward Peff that this has not yet happened.\n\nTo be clear, I am not bothered by this. And in fact I feel bad that I\npromised Christian that I take a careful look at the patches again, but\nhaven't gotten around to it (for an embarrassingly long time now).\n\nNow I would _love_ if somebody else dug into the topic enough to\nunderstand all of the ins and outs, and whether what they're doing is\nsane (or could be done better). But barring that, these patches have\nbeen battle-tested for many years on GitHub's servers, so even if we\njust take them as-is I hope it would be an improvement.\n\nFortunately I have some other work to do that I would like very much to\nprocrastinate on, so let me see if that can summon the willpower for me\nto review these.\n\n> Well, you have time enough to send lengthy replies on a Sunday morning\n> (while Peff apparently did not even have time to say that he lacks the\n> time to work on this).\n\nOne tricky thing here is that I leave messages or subthreads that I\nintend to act on in my incoming Git mbox. And of course as time goes on,\nthose get pushed further back in the pile. But when new messages arrive,\nmutt attaches them to the old threads, and I sometimes don't see them\n(until I go back and sift through the pile).\n\nI wish there was a good way to have mutt remain in threaded mode, but\nsort the threads by recent activity. Setting sort_aux=last-date kind of\nworks, but last time I tried it, I got annoyed that it did funny things\nwith the order of patches within a thread (if somebody replies to patch\n3/5, and then 2/5, it will pull 3/5 down as \"more recent\").\n\nDscho, you may feel free to roll your eyes and mutter under your breath\nabout email if you wish. ;)\n\n-Peff\n"},{"id":"387727","messageId":"20191209062449.GA40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-2-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 1/9] builtin/pack-objects: report reused packfile objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T06:24:49Z","receivedAt":"2019-12-09T06:24:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:33PM +0100, Christian Couder wrote:\n\n> From: Jeff King \n> \n> To see when packfile reuse kicks in or not, it is useful to\n> show reused packfile objects statistics in the output of\n> upload-pack.\n\nYep, I think this one makes sense. I would be a bit curious to see how\noften reuse actually kicks in for you with the current code. Back when I\nworked on this topic in 2015, it was kicking in for us almost-never (at\nleast for big repos like torvalds/linux that we were interested in\nmeasuring), but that's because we were packing all of the forks together\n(and still do). The earlier heuristics made no sense for that case.\n\nI don't know if it's really worth spending a lot of time trying to\ncollect data, though.\n\n-Peff\n"},{"id":"387728","messageId":"20191209062601.GB40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-3-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 2/9] packfile: expose get_delta_base()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T06:26:01Z","receivedAt":"2019-12-09T06:26:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:34PM +0100, Christian Couder wrote:\n\n> In a following commit get_delta_base() will be used outside\n> packfile.c, so let's make it non static and declare it in\n> packfile.h.\n\nYep, obvious and hopefully uncontroversial.\n\n-Peff\n"},{"id":"387729","messageId":"20191209062841.GC40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-4-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T06:28:41Z","receivedAt":"2019-12-09T06:28:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:35PM +0100, Christian Couder wrote:\n\n> In a following commit we will need to allocate a variable\n> number of bitmap words, instead of always 32, so let's add\n> bitmap_word_alloc() for this purpose.\n\nThis name is much better than the horrible \"bitmap_new2()\" it was called\nin the original. ;)\n\nI wonder if \"new_with_world_alloc\" or \"new_with_size\" would make it more\nobvious that this is also a constructor, though.\n\n> void bitmap_set(struct bitmap *self, size_t pos)\n> {\n> \tsize_t block = EWAH_BLOCK(pos);\n> \n> \tif (block >= self->word_alloc) {\n> \t\tsize_t old_size = self->word_alloc;\n> -\t\tself->word_alloc = block * 2;\n> +\t\tself->word_alloc = block ? block * 2 : 1;\n\nSince this hunk caused so much confusion, maybe worth calling it out in\nthe commit message. Something like:\n\n Note that we have to adjust the block growth in bitmap_set(), since\n a caller could now use an initial size of \"0\" (we don't plan to do\n that, but it doesn't hurt to be defensive).\n\n-Peff\n"},{"id":"387730","messageId":"20191209064740.GD40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-5-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 4/9] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T06:47:40Z","receivedAt":"2019-12-09T06:47:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:36PM +0100, Christian Couder wrote:\n\n> From: Jeff King \n> \n> We will no longer compute bitmap_git->reuse_objects in a\n> following commit, so we cannot rely on it anymore to\n> terminate the loop early; we have to iterate to the end.\n\nHmm. In my original work from 2015 (which you never saw as individual\ncommits), this came somewhere in the middle, after moving to per-object\nreuse.\n\nI think by dropping these hunks now, the state of the code at this point\nwould mean that we might write the objects twice. We'd mark them as\n\"reused\" and send them as part of write_reused_pack(). But we'd also\nsend them to pack-objects via the show_reachable_fn callback, and it\nwould add them to the usual packing list.\n\nAnd indeed, t5310.10 fails at this point in the series with:\n\n Cloning into bare repository 'clone.git'...\n remote: Enumerating objects: 331, done. \n remote: Counting objects: 100% (331/331), done. \n remote: Compressing objects: 100% (111/111), done. \n remote: Total 662 (delta 108), reused 331 (delta 108), pack-reused 331 \n Receiving objects: 100% (662/662), 53.14 KiB | 17.71 MiB/s, done.\n Resolving deltas: 100% (216/216), done.\n fatal: The same object 00c1d3730931e66eb08dabe3a3c9fa16621d728a appears twice in the pack\n fatal: index-pack failed\n\nand then starts working again after the final patch.\n\n-Peff\n"},{"id":"387731","messageId":"20191209070642.GE40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-6-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T07:06:42Z","receivedAt":"2019-12-09T07:06:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:37PM +0100, Christian Couder wrote:\n\n> We will use this helper function in a following commit to\n> tell us if an object is packed.\n\nYeah, makes sense. This is eventually used in have_duplicate_entry() in\npack-objects, to check whether an object is already mentioned in\nreuse_packfile_bitmap. And that's the part that would fix the test\nfailures from the previous commit.\n\nBut of course we don't yet have reuse_packfile_bitmap; that comes later.\n\n> +int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n> +\t\t\t struct bitmap *bitmap, const struct object_id *oid)\n> +{\n> +\tint idx;\n> +\n> +\tif (!bitmap)\n> +\t\treturn 0;\n> +\n> +\tidx = bitmap_position(bitmap_git, oid);\n> +\treturn idx >= 0 && bitmap_get(bitmap, idx);\n> +}\n\nThis is really a factoring out of code in\nbitmap_has_oid_in_uninteresting(). So I think you could simplify that\nlike:\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex cbfc544411..f5749d0ab3 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1194,16 +1194,6 @@ void free_bitmap_index(struct bitmap_index *b)\n int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n \t\t\t\t const struct object_id *oid)\n {\n-\tint pos;\n-\n-\tif (!bitmap_git)\n-\t\treturn 0; /* no bitmap loaded */\n-\tif (!bitmap_git->haves)\n-\t\treturn 0; /* walk had no \"haves\" */\n-\n-\tpos = bitmap_position_packfile(bitmap_git, oid);\n-\tif (pos < 0)\n-\t\treturn 0;\n-\n-\treturn bitmap_get(bitmap_git->haves, pos);\n+\treturn bitmap_git &&\n+\t bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);\n }\n\nOne curiosity is that bitmap_has_oid_in_uninteresting() only uses\nbitmap_position_packfile(), not bitmap_position(). So it wouldn't find\nobjects which weren't in the bitmapped packfile (i.e., ones where we\nextended the bitmap to handle loose objects, or objects in other packs).\n\nThat seems like a bug in the current code to me. I suspect nobody\nnoticed because the only effect would be that sometimes we fail to\nnotice that we could reuse a delta against such an object (which isn't\nincorrect, just suboptimal). I don't think p5311 would show this,\nthough, because it simulates a server that is fully packed.\n\nI think it's probably still worth doing this as a preparatory patch,\nthough:\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e07c798879..6df22e7291 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1125,7 +1125,7 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n \tif (!bitmap_git->haves)\n \t\treturn 0; /* walk had no \"haves\" */\n \n-\tpos = bitmap_position_packfile(bitmap_git, oid);\n+\tpos = bitmap_position(bitmap_git, oid);\n \tif (pos < 0)\n \t\treturn 0;\n \n\n-Peff\n"},{"id":"387732","messageId":"20191209070716.GF40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-7-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 6/9] csum-file: introduce hashfile_total()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T07:07:16Z","receivedAt":"2019-12-09T07:07:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:38PM +0100, Christian Couder wrote:\n\n> From: Jeff King \n> \n> We will need this helper function in a following commit\n> to give us total number of bytes fed to the hashfile so far.\n\nYep, makes sense.\n\n-Peff\n"},{"id":"387733","messageId":"20191209071412.GG40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-8-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 7/9] pack-objects: introduce pack.allowPackReuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T07:14:12Z","receivedAt":"2019-12-09T07:14:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:39PM +0100, Christian Couder wrote:\n\n> From: Jeff King \n> \n> Let's make it possible to configure if we want pack reuse or not.\n\n...because? :)\n\nI mostly used it for debugging and performance testing. I don't think\nthere should be any big downside to using it that would cause people to\nwant to turn it off. But it _might_ cause larger packs, because we\nwouldn't consider the reused objects as bases for finding new deltas.\n\nI think the documentation could mention this. And maybe make it a bit\nmore clear what \"reuse\" means.\n\nSo maybe:\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex 58323a351f..0dac580581 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -28,8 +28,11 @@ all existing objects. You can force recompression by passing the -F option\n to linkgit:git-repack[1].\n \n pack.allowPackReuse::\n-\tWhen true, which is the default, Git will try to reuse parts\n-\tof existing packfiles when preparing new packfiles.\n+\tWhen true, and when reachability bitmaps are enabled,\n+\tpack-objects will try to send parts of the bitmapped packfile\n+\tverbatim. This can reduce memory and CPU usage to serve fetches,\n+\tbut might result in sending a slightly larger pack. Defaults to\n+\ttrue.\n \n pack.island::\n \tAn extended regular expression configuring a set of delta\n\n-Peff\n"},{"id":"387734","messageId":"20191209071453.GH40570@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-9-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 8/9] builtin/pack-objects: introduce obj_is_packed()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T07:14:53Z","receivedAt":"2019-12-09T07:14:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:40PM +0100, Christian Couder wrote:\n\n> From: Jeff King \n> \n> Let's refactor the way we check if an object is packed by\n> introducing obj_is_packed(). This function is now a simple\n> wrapper around packlist_find(), but it will evolve in a\n> following commit.\n\nYep, this is a good refactor.\n\n-Peff\n"},{"id":"387735","messageId":"20191209081129.GA1546451@coredump.intra.peff.net","threadId":"52272","inReplyTo":"20191115141541.11149-10-chriscool@tuxfamily.org","subject":"Re: [PATCH v3 9/9] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-09T08:11:29Z","receivedAt":"2019-12-09T08:11:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 15, 2019 at 03:15:41PM +0100, Christian Couder wrote:\n\n> The old code to reuse deltas from an existing packfile\n> just tried to dump a whole segment of the pack verbatim.\n> That's faster than the traditional way of actually adding\n> objects to the packing list, but it didn't kick in very\n> often. This new code is really going for a middle ground:\n> do _some_ per-object work, but way less than we'd\n> traditionally do.\n\nThis is a good intro to the general problem, but...\n\n> For instance, packing torvalds/linux on GitHub servers\n> just now reused 6.5M objects, but only needed ~50k\n> chunks.\n\nWhat the heck is a chunk? :)\n\nI know, because I wrote the patches, but I think we need to sketch out\nthe solution a bit for the reader.\n\nI think the flow here is:\n\n - we want to do some per-object work (i.e., your intro above)\n\n - the general strategy is to make a bitmap of objects from the\n packfile we'll include, and then iterate over it, writing out each\n object exactly as it is in our on-disk pack, but _not_ adding it to\n our packlist (which costs memory, and increases the search space for\n deltas)\n\n - one complication is that if we're omitting some objects, we can't\n set a delta against a base that we're not sending. So we have to\n check each object in try_partial_reuse() to make sure we have its\n delta (actually, that third big comment in that function is\n incomplete, I think; it talks about sending the object later, not as\n part of the reused pack, but we might not send it at all!).\n\n - another complication is that when we omit parts of the packfile,\n that screws up delta base offsets. So to handle that, we have to\n keep track of which chunks we send (which is the bits you included\n below about chunks)\n\n - and then we can talk about performance; worst case we might have\n interleaved objects that we are sending or not sending, and we'd\n have as many chunks as objects. But in practice we send big chunks,\n so that's where the 6.5M objects vs 50k chunks comes in.\n\n> Additional checks are added in have_duplicate_entry()\n> and obj_is_packed() to avoid duplicate objects in the\n> reuse bitmap. It was probably buggy to not have such a\n> check before.\n> \n> If a client both asks for a tag by sha1 and specifies\n> \"include-tag\", we may end up including the tag in the reuse\n> bitmap (due to the first thing), and then later adding it to\n> the packlist (due to the second). This results in duplicate\n> objects in the pack, which git chokes on. We should notice\n> that we are already including it when doing the include-tag\n> portion, and avoid adding it to the packlist.\n> \n> The simplest place to fix this is right in add_ref_tag,\n> where we could avoid peeling the tag at all if we know that\n> we are already including it. However, I've pushed the check\n> instead into have_duplicate_entry(). This fixes not only\n> this case, but also means that we cannot have any similar\n> problems lurking in other code.\n\nI think this part could go in its own commit. If we introduce\nreuse_packfile_bitmap early, even if it's always an all-or-nothing chunk\nat the beginning of the file with the existing code, then we can\nintroduce the extra checks in have_duplicate_entry() on top of that.\n\nAnd then it would be safe to do the cleanup in show_objects_from_type()\nthat triggers the test failure in patch 4.\n\n> builtin/pack-objects.c | 222 ++++++++++++++++++++++++++++++++---------\n> pack-bitmap.c | 150 ++++++++++++++++++++--------\n> pack-bitmap.h | 3 +-\n> 3 files changed, 288 insertions(+), 87 deletions(-)\n\nIt might be worth having a perf test here. The case this is helping the\nmost, I think, is when somebody cloning wants all of the objects from\nthe beginning of the pack, but then there's a bunch of _other_ stuff.\n\nThat could be unreachable objects kept by \"repack -k\", or maybe objects\nreachable outside of heads and tags. Or objects that are part of other\ndelta islands. This last is the most plausible, really, because we'll\nput all of the root-island objects at the beginning of the pack. So\nmaybe a good perf test would be to take an existing repository add a\nbunch of new commits in refs/foo/, and then repack with delta islands\nsuch that refs/heads and refs/tags are in one (root) island, but\nrefs/foo is in another.\n\nThe old code should fail to do the pack-reuse thing, but we should get\npretty good reuse with the new code (and less CPU and peak RAM,\nhopefully, though the perf suite doesn't measure RAM directly).\n\n\nAnswering some questions from Jonathan's response in the last round\n(some of the quotes are his, some are yours):\n\n> I still don't understand this part. Going off what's written in the\n> commit message here, it seems to me that the issue is that (1) an object\n> can be added to the reuse bitmap without going through to_pack, and (2)\n> this is done when the client asks for a tag by SHA-1. But all objects\n> when specified by SHA-1 go through to_pack, don't they?\n\nNo, if it's part of the reused chunk, we'd avoid adding it to to_pack at\nall (and I think the commit message should make that more clear, as I\ndescribed above).\n\n> >> No tests, because git does not actually exhibit this \"ask\n> >> for it and also include-tag\" behavior. We do one or the\n> >> other on clone, depending on whether --single-branch is set.\n> >> However, libgit2 does both.\n>\n> So my wild guess sould be that maybe the reason is that some of this\n> code was shared (or intended to be shared) with libgit2?\n\nNo, the question is how the client behaves, and how we on the server\nreact to it. Git as a client would never ask for both include-tag and\nfor the tag itself by sha1. But libgit2 will, so a libgit2 client\ncloning from a Git server would trigger the bug.\n\n> > + if (pos >= bitmap_git->pack->num_objects)\n> > + return; /* not actually in the pack */\n>\n> Is this case possible? try_partial_reuse() is only called when there is\n> a 1 at the bit location.\n\nYes, it's possible. The result of a bitmap walk is larger than a given\npack, because we have to extend it to match whatever objects the caller\nasked for. E.g., imagine we have commit A, repack into into a bitmapped\npack, and then somebody pushes up commit B. Now I want to clone, getting\nboth A and B.\n\nOur bitmap result represents the whole answer, and so must include both\nobjects. But since \"B\" isn't in the pack, it doesn't have an assigned\nbit. We add it to the in-memory bitmap_git->ext_index, which gives it a\nbit (valid only for that walk result!). But of course for pack reuse, we\nonly care about the objects that were actually in the bitmapped pack.\n\n> > + /* Don't mark objects not in the packfile */\n> > + if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n> > + i = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n>\n> Why is this necessary? Let's say we have 42 fully-1 words, and therefore\n> i is 42. Shouldn't we allocate 42 words in our reuse bitmap?\n\nThis is the same issue as above. Imagine instead of two objects, imagine\nwe have 42 words worth. But if only 20 words worth are in the packfile,\nthen we have to stop there.\n\nNow we _could_ figure this out for each individual object through the\nsimilar logic in try_partial_reuse(). But we try to take an even faster\npath for the initial chunk of objects. We don't even walk over them\nlooking to see if they're deltas or not. We just send that chunk of the\npack verbatim.\n\nI don't have numbers for how often we hit this path versus the\nindividual try_partial_reuse() path. Possibly the stats could\ndifferentiate that.\n\nThinking on it more, though, I wonder if there's a bug hiding here. We\nknow that we can send the whole initial chunk verbatim for OFS_DELTA\nobjects, because the relative offsets will remain unchanged (i.e., there\nare no \"holes\" that trigger our chunk code). But if there were a\nREF_DELTA in that initial chunk, we have no certainty that the base is\nbeing sent.\n\nIn practice, this doesn't happen because the objects in question have to\nbe in a pack with bitmaps, which means it was written ourselves by\ngit-repack. And we'd never write REF_DELTA objects there.\n\nBut I wonder if it's worth being a bit more careful (and what the\nperformance impact is; it would mean checking the type of every object\nin that initial chunk).\n\n-Peff\n"},{"id":"387740","messageId":"nycvar.QRO.7.76.6.1912091023040.31080@tvgsbejvaqbjf.bet","threadId":"52272","inReplyTo":"20191209061853.GA38588@coredump.intra.peff.net","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-12-09T09:28:33Z","receivedAt":"2019-12-09T09:29:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 9 Dec 2019, Jeff King wrote:\n\n> On Sun, Dec 08, 2019 at 09:54:01AM +0100, Johannes Schindelin wrote:\n>\n> > > That's why I put Peff as the author of the patches.\n> >\n> > No, that is not the reason. You might think that that is the reason, but\n> > the real reason why Peff is marked as the author of those patches is that\n> > he really authored those patches.\n> >\n> > In light of what you said, I don't think that it is a good idea to go\n> > forward by leaning even further on Peff. From his activity on the Git\n> > mailing list, I deduce that he is not exactly in need of even more work.\n> >\n> > Instead, I think that if you truly want to push these patches forward, you\n> > will have to dig deeper yourself, and answer Jonathan Tan's questions, and\n> > possibly adjust the patches accordingly and send a new iteration.\n> >\n> > I perceive it as very unfair toward Peff that this has not yet happened.\n>\n> To be clear, I am not bothered by this. And in fact I feel bad that I\n> promised Christian that I take a careful look at the patches again, but\n> haven't gotten around to it (for an embarrassingly long time now).\n>\n> Now I would _love_ if somebody else dug into the topic enough to\n> understand all of the ins and outs, and whether what they're doing is\n> sane (or could be done better).\n\nThat's what I thought.\n\nWhen I bring patches to the Git mailing list, it means implicitly not only\nthat I understand the ins and outs of them, but also that I am fully\nprepared to address reviewer comments and send out new, enhanced\niterations.\n\nThat holds when I send patch series that include patches authored by\nsomeone else than me. I thought that that is kind of expected, otherwise\nthere would be no good reason for _me_ to send those patches, right?\n\n> But barring that, these patches have been battle-tested for many years\n> on GitHub's servers, so even if we just take them as-is I hope it would\n> be an improvement.\n>\n> Fortunately I have some other work to do that I would like very much to\n> procrastinate on, so let me see if that can summon the willpower for me\n> to review these.\n\nHeh, I know that feeling.\n\n> > Well, you have time enough to send lengthy replies on a Sunday morning\n> > (while Peff apparently did not even have time to say that he lacks the\n> > time to work on this).\n>\n> One tricky thing here is that I leave messages or subthreads that I\n> intend to act on in my incoming Git mbox. And of course as time goes on,\n> those get pushed further back in the pile. But when new messages arrive,\n> mutt attaches them to the old threads, and I sometimes don't see them\n> (until I go back and sift through the pile).\n>\n> I wish there was a good way to have mutt remain in threaded mode, but\n> sort the threads by recent activity. Setting sort_aux=last-date kind of\n> works, but last time I tried it, I got annoyed that it did funny things\n> with the order of patches within a thread (if somebody replies to patch\n> 3/5, and then 2/5, it will pull 3/5 down as \"more recent\").\n\nWhen I hit such a situation, I usually go on this kind of insane\nside-track to figure out whether it would be easy to fix this (it's open\nsource, after all). Last time I tried such a thing, though, I had to admit\nthat it was not easy (but I use Alpine, not mutt, out of sheer inability\nto adjust my muscle memory).\n\n> Dscho, you may feel free to roll your eyes and mutter under your breath\n> about email if you wish. ;)\n\nDone.\n\n;-)\n\nCiao,\nDscho\n"},{"id":"387817","messageId":"xmqqy2vluxwv.fsf@gitster-ct.c.googlers.com","threadId":"52272","inReplyTo":"20191209061853.GA38588@coredump.intra.peff.net","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-09T19:00:32Z","receivedAt":"2019-12-09T19:00:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Now I would _love_ if somebody else dug into the topic enough to\n> understand all of the ins and outs, and whether what they're doing is\n> sane (or could be done better). But barring that, these patches have\n> been battle-tested for many years on GitHub's servers, so even if we\n> just take them as-is I hope it would be an improvement.\n\nSorry; it wasn't my intention to ask accelerating the topic\nforward---it was just to see the current status to adjust my\nexpectations. And you could have stopped at the end of this\nparagraph but ...\n\n> Fortunately I have some other work to do that I would like very much to\n> procrastinate on, so let me see if that can summon the willpower for me\n> to review these.\n\n... I'd love to see us benefit from this ;-)\n"},{"id":"387818","messageId":"xmqqtv69uxou.fsf@gitster-ct.c.googlers.com","threadId":"52272","inReplyTo":"20191209061853.GA38588@coredump.intra.peff.net","subject":"Re: [PATCH v3 0/9] Rewrite packfile reuse code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-12-09T19:05:21Z","receivedAt":"2019-12-09T19:05:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> One tricky thing here is that I leave messages or subthreads that I\n> intend to act on in my incoming Git mbox. And of course as time goes on,\n> those get pushed further back in the pile. But when new messages arrive,\n> mutt attaches them to the old threads, and I sometimes don't see them\n> (until I go back and sift through the pile).\n\nThis is why I still let a tab in my browser to be squat by GMail\nthat shows only the traffic sent to this mailing list, as it is very\ngood at surfacing a thread with new activity even though it is bad\nat everything else, including threading.\n\nFor real work, picking messages up and responding to them, I read\nand handle the list traffic via NNTP interface to public-inbox (and\nlore.k.o these days), but keeping GMail purely as a notification\nchannel has its uses ;-).\n"},{"id":"387941","messageId":"CAP8UFD0YCSW_zDZ-OBif_MUBV3tkGR5554LSdFLkQGTegTxnqQ@mail.gmail.com","threadId":"52272","inReplyTo":"20191209062449.GA40570@coredump.intra.peff.net","subject":"Re: [PATCH v3 1/9] builtin/pack-objects: report reused packfile objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-11T13:48:43Z","receivedAt":"2019-12-11T13:48:57Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 7:24 AM Jeff King wrote:\n>\n> On Fri, Nov 15, 2019 at 03:15:33PM +0100, Christian Couder wrote:\n>\n> > From: Jeff King \n> >\n> > To see when packfile reuse kicks in or not, it is useful to\n> > show reused packfile objects statistics in the output of\n> > upload-pack.\n>\n> Yep, I think this one makes sense. I would be a bit curious to see how\n> often reuse actually kicks in for you with the current code. Back when I\n> worked on this topic in 2015, it was kicking in for us almost-never (at\n> least for big repos like torvalds/linux that we were interested in\n> measuring), but that's because we were packing all of the forks together\n> (and still do). The earlier heuristics made no sense for that case.\n>\n> I don't know if it's really worth spending a lot of time trying to\n> collect data, though.\n\nUnfortunately it's not yet easy for me, or people in my team, to\ncollect data from production servers. I will try to ping people about\nthat though.\n"},{"id":"387942","messageId":"CAP8UFD3PwuSyJ0kjiYKo_UbgqzC1hjJS0rkBjhdfuNmC6hvGvw@mail.gmail.com","threadId":"52272","inReplyTo":"20191209062841.GC40570@coredump.intra.peff.net","subject":"Re: [PATCH v3 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-11T13:50:40Z","receivedAt":"2019-12-11T13:50:57Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 7:28 AM Jeff King wrote:\n>\n> On Fri, Nov 15, 2019 at 03:15:35PM +0100, Christian Couder wrote:\n>\n> > In a following commit we will need to allocate a variable\n> > number of bitmap words, instead of always 32, so let's add\n> > bitmap_word_alloc() for this purpose.\n>\n> This name is much better than the horrible \"bitmap_new2()\" it was called\n> in the original. ;)\n>\n> I wonder if \"new_with_world_alloc\" or \"new_with_size\" would make it more\n> obvious that this is also a constructor, though.\n\nbitmap_new_with_word_alloc() feels a bit verbose to me for such a\nshort function, so for now I kept bitmap_word_alloc().\n\nI think that if we really want to use \"new\" for constructors then a\nbetter solution would be something like renaming bitmap_new(void) to\nbitmap_new_default(void) and bitmap_word_alloc(size_t word_alloc) to\nbitmap_new(size_t word_alloc).\n\n> > void bitmap_set(struct bitmap *self, size_t pos)\n> > {\n> > size_t block = EWAH_BLOCK(pos);\n> >\n> > if (block >= self->word_alloc) {\n> > size_t old_size = self->word_alloc;\n> > - self->word_alloc = block * 2;\n> > + self->word_alloc = block ? block * 2 : 1;\n>\n> Since this hunk caused so much confusion, maybe worth calling it out in\n> the commit message. Something like:\n>\n> Note that we have to adjust the block growth in bitmap_set(), since\n> a caller could now use an initial size of \"0\" (we don't plan to do\n> that, but it doesn't hurt to be defensive).\n\nOk, I added the above as a commit message note in my current version.\n"},{"id":"388006","messageId":"20191212054518.GA1213659@coredump.intra.peff.net","threadId":"52272","inReplyTo":"CAP8UFD3PwuSyJ0kjiYKo_UbgqzC1hjJS0rkBjhdfuNmC6hvGvw@mail.gmail.com","subject":"Re: [PATCH v3 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-12T05:45:18Z","receivedAt":"2019-12-12T05:45:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 11, 2019 at 02:50:40PM +0100, Christian Couder wrote:\n\n> > I wonder if \"new_with_world_alloc\" or \"new_with_size\" would make it more\n> > obvious that this is also a constructor, though.\n> \n> bitmap_new_with_word_alloc() feels a bit verbose to me for such a\n> short function, so for now I kept bitmap_word_alloc().\n\nOK, that's fine with me...\n\n> I think that if we really want to use \"new\" for constructors then a\n> better solution would be something like renaming bitmap_new(void) to\n> bitmap_new_default(void) and bitmap_word_alloc(size_t word_alloc) to\n> bitmap_new(size_t word_alloc).\n\n...but that also would be fine with me.\n\n-Peff\n"},{"id":"388105","messageId":"CAP8UFD12rj9xhc64DVWTrXb+Vdh5FS_pNt1E2-_dmFDOqdzKiw@mail.gmail.com","threadId":"52272","inReplyTo":"20191209064740.GD40570@coredump.intra.peff.net","subject":"Re: [PATCH v3 4/9] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-13T13:26:39Z","receivedAt":"2019-12-13T20:37:18Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 7:47 AM Jeff King wrote:\n\n\n> I think by dropping these hunks now, the state of the code at this point\n> would mean that we might write the objects twice. We'd mark them as\n> \"reused\" and send them as part of write_reused_pack(). But we'd also\n> send them to pack-objects via the show_reachable_fn callback, and it\n> would add them to the usual packing list.\n>\n> And indeed, t5310.10 fails at this point in the series with:\n>\n> Cloning into bare repository 'clone.git'...\n> remote: Enumerating objects: 331, done.\n> remote: Counting objects: 100% (331/331), done.\n> remote: Compressing objects: 100% (111/111), done.\n> remote: Total 662 (delta 108), reused 331 (delta 108), pack-reused 331\n> Receiving objects: 100% (662/662), 53.14 KiB | 17.71 MiB/s, done.\n> Resolving deltas: 100% (216/216), done.\n> fatal: The same object 00c1d3730931e66eb08dabe3a3c9fa16621d728a appears twice in the pack\n> fatal: index-pack failed\n>\n> and then starts working again after the final patch.\n\nYeah, I thought I had tested this, but anyway I squashed this patch\ninto the final patch to avoid failures.\n"},{"id":"388106","messageId":"CAP8UFD2dE6gtmuWNbQj7o7X=kQTgJzk=eWMa0kYJW85WTRcXQA@mail.gmail.com","threadId":"52272","inReplyTo":"20191209070642.GE40570@coredump.intra.peff.net","subject":"Re: [PATCH v3 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-13T13:27:06Z","receivedAt":"2019-12-13T20:37:18Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 8:06 AM Jeff King wrote:\n>\n> On Fri, Nov 15, 2019 at 03:15:37PM +0100, Christian Couder wrote:\n\n> > +int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n> > + struct bitmap *bitmap, const struct object_id *oid)\n> > +{\n> > + int idx;\n> > +\n> > + if (!bitmap)\n> > + return 0;\n> > +\n> > + idx = bitmap_position(bitmap_git, oid);\n> > + return idx >= 0 && bitmap_get(bitmap, idx);\n> > +}\n>\n> This is really a factoring out of code in\n> bitmap_has_oid_in_uninteresting(). So I think you could simplify that\n> like:\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index cbfc544411..f5749d0ab3 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -1194,16 +1194,6 @@ void free_bitmap_index(struct bitmap_index *b)\n> int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n> const struct object_id *oid)\n> {\n> - int pos;\n> -\n> - if (!bitmap_git)\n> - return 0; /* no bitmap loaded */\n> - if (!bitmap_git->haves)\n> - return 0; /* walk had no \"haves\" */\n> -\n> - pos = bitmap_position_packfile(bitmap_git, oid);\n> - if (pos < 0)\n> - return 0;\n> -\n> - return bitmap_get(bitmap_git->haves, pos);\n> + return bitmap_git &&\n> + bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);\n> }\n\nYeah, nice simplification. I added a patch doing that.\n\n> One curiosity is that bitmap_has_oid_in_uninteresting() only uses\n> bitmap_position_packfile(), not bitmap_position(). So it wouldn't find\n> objects which weren't in the bitmapped packfile (i.e., ones where we\n> extended the bitmap to handle loose objects, or objects in other packs).\n>\n> That seems like a bug in the current code to me. I suspect nobody\n> noticed because the only effect would be that sometimes we fail to\n> notice that we could reuse a delta against such an object (which isn't\n> incorrect, just suboptimal). I don't think p5311 would show this,\n> though, because it simulates a server that is fully packed.\n>\n> I think it's probably still worth doing this as a preparatory patch,\n> though:\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index e07c798879..6df22e7291 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -1125,7 +1125,7 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n> if (!bitmap_git->haves)\n> return 0; /* walk had no \"haves\" */\n>\n> - pos = bitmap_position_packfile(bitmap_git, oid);\n> + pos = bitmap_position(bitmap_git, oid);\n> if (pos < 0)\n> return 0;\n\nYeah, I agree that it's a good idea to do it in a preparatory patch,\nso I added a patch doing that before the one doing the simplification\nyou suggest above.\n"},{"id":"388108","messageId":"CAP8UFD3H_6E9FWprV_bHUwwQK96JD1jFtvMBecM5ajnbSjjxPQ@mail.gmail.com","threadId":"52272","inReplyTo":"20191209071412.GG40570@coredump.intra.peff.net","subject":"Re: [PATCH v3 7/9] pack-objects: introduce pack.allowPackReuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-13T13:27:26Z","receivedAt":"2019-12-13T20:37:18Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 8:14 AM Jeff King wrote:\n>\n> On Fri, Nov 15, 2019 at 03:15:39PM +0100, Christian Couder wrote:\n>\n> > From: Jeff King \n> >\n> > Let's make it possible to configure if we want pack reuse or not.\n>\n> ...because? :)\n>\n> I mostly used it for debugging and performance testing. I don't think\n> there should be any big downside to using it that would cause people to\n> want to turn it off. But it _might_ cause larger packs, because we\n> wouldn't consider the reused objects as bases for finding new deltas.\n\nOk, I changed the commit message to:\n\n Let's make it possible to configure if we want pack reuse or not.\n\n The main reason it might not be wanted is probably debugging and\n performance testing, though pack reuse _might_ cause larger packs,\n because we wouldn't consider the reused objects as bases for\n finding new deltas.\n\n> I think the documentation could mention this. And maybe make it a bit\n> more clear what \"reuse\" means.\n>\n> So maybe:\n>\n> diff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\n> index 58323a351f..0dac580581 100644\n> --- a/Documentation/config/pack.txt\n> +++ b/Documentation/config/pack.txt\n> @@ -28,8 +28,11 @@ all existing objects. You can force recompression by passing the -F option\n> to linkgit:git-repack[1].\n>\n> pack.allowPackReuse::\n> - When true, which is the default, Git will try to reuse parts\n> - of existing packfiles when preparing new packfiles.\n> + When true, and when reachability bitmaps are enabled,\n> + pack-objects will try to send parts of the bitmapped packfile\n> + verbatim. This can reduce memory and CPU usage to serve fetches,\n> + but might result in sending a slightly larger pack. Defaults to\n> + true.\n\nYeah, great! I use the above in my current version. Thanks!\n"},{"id":"388436","messageId":"CAP8UFD3k0QFFCpjjOhgvqd11TqFbfKWsEnt6b_egB0bDrVZnwA@mail.gmail.com","threadId":"52272","inReplyTo":"20191209081129.GA1546451@coredump.intra.peff.net","subject":"Re: [PATCH v3 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:26:28Z","receivedAt":"2019-12-18T11:26:44Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Dec 9, 2019 at 9:11 AM Jeff King wrote:\n>\n> On Fri, Nov 15, 2019 at 03:15:41PM +0100, Christian Couder wrote:\n>\n> > The old code to reuse deltas from an existing packfile\n> > just tried to dump a whole segment of the pack verbatim.\n> > That's faster than the traditional way of actually adding\n> > objects to the packing list, but it didn't kick in very\n> > often. This new code is really going for a middle ground:\n> > do _some_ per-object work, but way less than we'd\n> > traditionally do.\n>\n> This is a good intro to the general problem, but...\n>\n> > For instance, packing torvalds/linux on GitHub servers\n> > just now reused 6.5M objects, but only needed ~50k\n> > chunks.\n>\n> What the heck is a chunk? :)\n>\n> I know, because I wrote the patches, but I think we need to sketch out\n> the solution a bit for the reader.\n\nOk with sketching it out.\n\n> I think the flow here is:\n>\n> - we want to do some per-object work (i.e., your intro above)\n>\n> - the general strategy is to make a bitmap of objects from the\n> packfile we'll include, and then iterate over it, writing out each\n> object exactly as it is in our on-disk pack, but _not_ adding it to\n> our packlist (which costs memory, and increases the search space for\n> deltas)\n>\n> - one complication is that if we're omitting some objects, we can't\n> set a delta against a base that we're not sending. So we have to\n> check each object in try_partial_reuse() to make sure we have its\n> delta (actually, that third big comment in that function is\n> incomplete, I think; it talks about sending the object later, not as\n> part of the reused pack, but we might not send it at all!).\n\nAre you talking about this comment:\n\n /*\n * And finally, if we're not sending the base as part of our\n * reuse chunk, then don't send this object either. The base\n * would come after us, along with other objects not\n * necessarily in the pack, which means we'd need to convert\n * to REF_DELTA on the fly. Better to just let the normal\n * object_entry code path handle it.\n */\n\n?\n\nI don't see how it's talking about sending the object later, so I have\nleft it as is. Maybe you can check it again in the v4 series I am\ngoing to send.\n\n> - another complication is that when we omit parts of the packfile,\n> that screws up delta base offsets. So to handle that, we have to\n> keep track of which chunks we send (which is the bits you included\n> below about chunks)\n>\n> - and then we can talk about performance; worst case we might have\n> interleaved objects that we are sending or not sending, and we'd\n> have as many chunks as objects. But in practice we send big chunks,\n> so that's where the 6.5M objects vs 50k chunks comes in.\n\nOk, I have added your points above to the commit message.\n\n> > Additional checks are added in have_duplicate_entry()\n> > and obj_is_packed() to avoid duplicate objects in the\n> > reuse bitmap. It was probably buggy to not have such a\n> > check before.\n> >\n> > If a client both asks for a tag by sha1 and specifies\n> > \"include-tag\", we may end up including the tag in the reuse\n> > bitmap (due to the first thing), and then later adding it to\n> > the packlist (due to the second). This results in duplicate\n> > objects in the pack, which git chokes on. We should notice\n> > that we are already including it when doing the include-tag\n> > portion, and avoid adding it to the packlist.\n> >\n> > The simplest place to fix this is right in add_ref_tag,\n> > where we could avoid peeling the tag at all if we know that\n> > we are already including it. However, I've pushed the check\n> > instead into have_duplicate_entry(). This fixes not only\n> > this case, but also means that we cannot have any similar\n> > problems lurking in other code.\n>\n> I think this part could go in its own commit. If we introduce\n> reuse_packfile_bitmap early, even if it's always an all-or-nothing chunk\n> at the beginning of the file with the existing code, then we can\n> introduce the extra checks in have_duplicate_entry() on top of that.\n\nOk, I have extracted this part into its own commit.\n\n> And then it would be safe to do the cleanup in show_objects_from_type()\n> that triggers the test failure in patch 4.\n\nOk, I have eventually moved patch 4 at the end of the series.\n\n> > builtin/pack-objects.c | 222 ++++++++++++++++++++++++++++++++---------\n> > pack-bitmap.c | 150 ++++++++++++++++++++--------\n> > pack-bitmap.h | 3 +-\n> > 3 files changed, 288 insertions(+), 87 deletions(-)\n>\n> It might be worth having a perf test here. The case this is helping the\n> most, I think, is when somebody cloning wants all of the objects from\n> the beginning of the pack, but then there's a bunch of _other_ stuff.\n>\n> That could be unreachable objects kept by \"repack -k\", or maybe objects\n> reachable outside of heads and tags. Or objects that are part of other\n> delta islands. This last is the most plausible, really, because we'll\n> put all of the root-island objects at the beginning of the pack. So\n> maybe a good perf test would be to take an existing repository add a\n> bunch of new commits in refs/foo/,\n\nNot sure how I could do so. How would you do that?\n\nI think it would be best to add completely new realistic commits that\nare changing the main code base.\n\n> and then repack with delta islands\n> such that refs/heads and refs/tags are in one (root) island, but\n> refs/foo is in another.\n>\n> The old code should fail to do the pack-reuse thing, but we should get\n> pretty good reuse with the new code (and less CPU and peak RAM,\n> hopefully, though the perf suite doesn't measure RAM directly).\n\nI haven't added a perf test. I may do it if I get an idea about how to\nadd new commits in refs/foo/.\n\n> Answering some questions from Jonathan's response in the last round\n> (some of the quotes are his, some are yours):\n>\n> > I still don't understand this part. Going off what's written in the\n> > commit message here, it seems to me that the issue is that (1) an object\n> > can be added to the reuse bitmap without going through to_pack, and (2)\n> > this is done when the client asks for a tag by SHA-1. But all objects\n> > when specified by SHA-1 go through to_pack, don't they?\n>\n> No, if it's part of the reused chunk, we'd avoid adding it to to_pack at\n> all (and I think the commit message should make that more clear, as I\n> described above).\n\nI used your description above to improve the commit message, so I\nguess it now answers his question.\n\n> > >> No tests, because git does not actually exhibit this \"ask\n> > >> for it and also include-tag\" behavior. We do one or the\n> > >> other on clone, depending on whether --single-branch is set.\n> > >> However, libgit2 does both.\n> >\n> > So my wild guess sould be that maybe the reason is that some of this\n> > code was shared (or intended to be shared) with libgit2?\n>\n> No, the question is how the client behaves, and how we on the server\n> react to it. Git as a client would never ask for both include-tag and\n> for the tag itself by sha1. But libgit2 will, so a libgit2 client\n> cloning from a Git server would trigger the bug.\n\nOk, I have made it explicit in the commit message that the bug would\nbe triggered by a libgit2 client but not a Git client.\n\n> > > + if (pos >= bitmap_git->pack->num_objects)\n> > > + return; /* not actually in the pack */\n> >\n> > Is this case possible? try_partial_reuse() is only called when there is\n> > a 1 at the bit location.\n>\n> Yes, it's possible. The result of a bitmap walk is larger than a given\n> pack, because we have to extend it to match whatever objects the caller\n> asked for. E.g., imagine we have commit A, repack into into a bitmapped\n> pack, and then somebody pushes up commit B. Now I want to clone, getting\n> both A and B.\n>\n> Our bitmap result represents the whole answer, and so must include both\n> objects. But since \"B\" isn't in the pack, it doesn't have an assigned\n> bit. We add it to the in-memory bitmap_git->ext_index, which gives it a\n> bit (valid only for that walk result!). But of course for pack reuse, we\n> only care about the objects that were actually in the bitmapped pack.\n\nNot sure if these explanations should go into the commit message or a\ncomment in the code. So I haven't added them for now.\n\n> > > + /* Don't mark objects not in the packfile */\n> > > + if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n> > > + i = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n> >\n> > Why is this necessary? Let's say we have 42 fully-1 words, and therefore\n> > i is 42. Shouldn't we allocate 42 words in our reuse bitmap?\n>\n> This is the same issue as above. Imagine instead of two objects, imagine\n> we have 42 words worth. But if only 20 words worth are in the packfile,\n> then we have to stop there.\n>\n> Now we _could_ figure this out for each individual object through the\n> similar logic in try_partial_reuse(). But we try to take an even faster\n> path for the initial chunk of objects. We don't even walk over them\n> looking to see if they're deltas or not. We just send that chunk of the\n> pack verbatim.\n>\n> I don't have numbers for how often we hit this path versus the\n> individual try_partial_reuse() path. Possibly the stats could\n> differentiate that.\n\nAlso not sure if these explanations should go into the commit message\nor a comment in the code. So I haven't added them for now.\n\n> Thinking on it more, though, I wonder if there's a bug hiding here. We\n> know that we can send the whole initial chunk verbatim for OFS_DELTA\n> objects, because the relative offsets will remain unchanged (i.e., there\n> are no \"holes\" that trigger our chunk code). But if there were a\n> REF_DELTA in that initial chunk, we have no certainty that the base is\n> being sent.\n>\n> In practice, this doesn't happen because the objects in question have to\n> be in a pack with bitmaps, which means it was written ourselves by\n> git-repack. And we'd never write REF_DELTA objects there.\n>\n> But I wonder if it's worth being a bit more careful (and what the\n> performance impact is; it would mean checking the type of every object\n> in that initial chunk).\n\nI haven't done anything related to that. Maybe something can be done\nin a follow up patch.\n\nThanks a lot for the review!\n\nChristian.\n"},{"id":"388490","messageId":"20191219004232.GA24434@coredump.intra.peff.net","threadId":"52272","inReplyTo":"CAP8UFD3k0QFFCpjjOhgvqd11TqFbfKWsEnt6b_egB0bDrVZnwA@mail.gmail.com","subject":"Re: [PATCH v3 9/9] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-12-19T00:42:32Z","receivedAt":"2019-12-19T00:42:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 18, 2019 at 12:26:28PM +0100, Christian Couder wrote:\n\n> > - one complication is that if we're omitting some objects, we can't\n> > set a delta against a base that we're not sending. So we have to\n> > check each object in try_partial_reuse() to make sure we have its\n> > delta (actually, that third big comment in that function is\n> > incomplete, I think; it talks about sending the object later, not as\n> > part of the reused pack, but we might not send it at all!).\n> \n> Are you talking about this comment:\n> \n> /*\n> * And finally, if we're not sending the base as part of our\n> * reuse chunk, then don't send this object either. The base\n> * would come after us, along with other objects not\n> * necessarily in the pack, which means we'd need to convert\n> * to REF_DELTA on the fly. Better to just let the normal\n> * object_entry code path handle it.\n> */\n> \n> ?\n> \n> I don't see how it's talking about sending the object later, so I have\n> left it as is. Maybe you can check it again in the v4 series I am\n> going to send.\n\nYes, that's the comment. It says \"the base would come after us\". That\ncould be true, but it also could be that we are not sending the object\nat all (in fact, that seems more likely in practice). The outcome is the\nsame, though: we don't verbatim reuse the delta'd object if its base is\nnot also being reused.\n\n> > It might be worth having a perf test here. The case this is helping the\n> > most, I think, is when somebody cloning wants all of the objects from\n> > the beginning of the pack, but then there's a bunch of _other_ stuff.\n> >\n> > That could be unreachable objects kept by \"repack -k\", or maybe objects\n> > reachable outside of heads and tags. Or objects that are part of other\n> > delta islands. This last is the most plausible, really, because we'll\n> > put all of the root-island objects at the beginning of the pack. So\n> > maybe a good perf test would be to take an existing repository add a\n> > bunch of new commits in refs/foo/,\n> \n> Not sure how I could do so. How would you do that?\n> \n> I think it would be best to add completely new realistic commits that\n> are changing the main code base.\n\nI agree that would be the most realistic for the \"forked repository\nnetwork\" case that we originally wrote this for. But I think a more\nmundane (and possibly easier to generate) example might be having a\nbunch of refs/notes.\n\nSo perhaps something like this:\n\n-- >8 --\n#!/bin/sh\n\ntest_description='verbatim pack reuse with bitmaps'\n. ./perf-lib.sh\n\ntest_perf_large_repo\n\ntest_expect_success 'generate a bunch of notes' '\n\t# bleh, is there really no way to bulk-add with git-notes?\n\t{\n\t\ttest_tick &&\n\t\techo \"commit refs/notes/commits\" &&\n\t\tprintf \"author %s <%s> %s\\\\n\" \\\n\t\t\t\"$GIT_AUTHOR_NAME\" \\\n\t\t\t\"$GIT_AUTHOR_EMAIL\" \\\n\t\t\t\"$GIT_AUTHOR_DATE\" &&\n\t\tprintf \"committer %s <%s> %s\\\\n\" \\\n\t\t\t\"$GIT_COMMITTER_NAME\" \\\n\t\t\t\"$GIT_COMMITTER_EMAIL\" \\\n\t\t\t\"$GIT_COMMITTER_DATE\" &&\n\t\techo \"data <clone.pack\n'\n\ntest_size 'clone size' '\n\twc -c > > Is this case possible? try_partial_reuse() is only called when there is\n> > > a 1 at the bit location.\n> >\n> > Yes, it's possible. The result of a bitmap walk is larger than a given\n> > pack, because we have to extend it to match whatever objects the caller\n> > asked for. E.g., imagine we have commit A, repack into into a bitmapped\n> > pack, and then somebody pushes up commit B. Now I want to clone, getting\n> > both A and B.\n> >\n> > Our bitmap result represents the whole answer, and so must include both\n> > objects. But since \"B\" isn't in the pack, it doesn't have an assigned\n> > bit. We add it to the in-memory bitmap_git->ext_index, which gives it a\n> > bit (valid only for that walk result!). But of course for pack reuse, we\n> > only care about the objects that were actually in the bitmapped pack.\n> \n> Not sure if these explanations should go into the commit message or a\n> comment in the code. So I haven't added them for now.\n\nI think this is really outside the scope of this series, even, and gets\ninto how the bitmap traversal works in general. I'm sure the\ndocumentation for that could be a bit better.\n\n> > Thinking on it more, though, I wonder if there's a bug hiding here. We\n> > know that we can send the whole initial chunk verbatim for OFS_DELTA\n> > objects, because the relative offsets will remain unchanged (i.e., there\n> > are no \"holes\" that trigger our chunk code). But if there were a\n> > REF_DELTA in that initial chunk, we have no certainty that the base is\n> > being sent.\n> >\n> > In practice, this doesn't happen because the objects in question have to\n> > be in a pack with bitmaps, which means it was written ourselves by\n> > git-repack. And we'd never write REF_DELTA objects there.\n> >\n> > But I wonder if it's worth being a bit more careful (and what the\n> > performance impact is; it would mean checking the type of every object\n> > in that initial chunk).\n> \n> I haven't done anything related to that. Maybe something can be done\n> in a follow up patch.\n\nHmm. I was thinking the problem was introduced in this series, but the\nold code should suffer from this as well. I wondered if it might simply\nbe that the old code did not trigger often enough for anybody to notice,\nbut we have been running the code in this series for several years at\nGitHub. So probably my reasoning above is sound (but it might still be\nworth addressing).\n\n-Peff\n"},{"id":"390309","messageId":"CAP8UFD0h1TFVNqH7g823psaQzmEmzoz200CkZuDOV8GqNV7mrQ@mail.gmail.com","threadId":"52272","inReplyTo":"20191219004232.GA24434@coredump.intra.peff.net","subject":"Re: [PATCH v3 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2020-01-23T22:29:24Z","receivedAt":"2020-01-23T22:29:38Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, Dec 19, 2019 at 1:42 AM Jeff King wrote:\n>\n> On Wed, Dec 18, 2019 at 12:26:28PM +0100, Christian Couder wrote:\n>\n> > > - one complication is that if we're omitting some objects, we can't\n> > > set a delta against a base that we're not sending. So we have to\n> > > check each object in try_partial_reuse() to make sure we have its\n> > > delta (actually, that third big comment in that function is\n> > > incomplete, I think; it talks about sending the object later, not as\n> > > part of the reused pack, but we might not send it at all!).\n> >\n> > Are you talking about this comment:\n> >\n> > /*\n> > * And finally, if we're not sending the base as part of our\n> > * reuse chunk, then don't send this object either. The base\n> > * would come after us, along with other objects not\n> > * necessarily in the pack, which means we'd need to convert\n> > * to REF_DELTA on the fly. Better to just let the normal\n> > * object_entry code path handle it.\n> > */\n> >\n> > ?\n> >\n> > I don't see how it's talking about sending the object later, so I have\n> > left it as is. Maybe you can check it again in the v4 series I am\n> > going to send.\n>\n> Yes, that's the comment. It says \"the base would come after us\". That\n> could be true, but it also could be that we are not sending the object\n> at all (in fact, that seems more likely in practice). The outcome is the\n> same, though: we don't verbatim reuse the delta'd object if its base is\n> not also being reused.\n\nIn the V4 (https://public-inbox.org/git/20191218112547.4974-11-chriscool@tuxfamily.org/)\nthere is now the following in the commit message:\n\nOne complication is that if we're omitting some objects,\nwe can't set a delta against a base that we're not\nsending. So we have to check each object in\ntry_partial_reuse() to make sure we have its delta.\n\nWould you also want the comment to be improved to something like:\n\n /*\n * And finally, if we're not sending the base as part of our\n * reuse chunk, then don't send this object either. Because we\n * should not send the object at all. Or because the base\n * would come after us, along with other objects not\n * necessarily in the pack, which means we'd need to convert\n * to REF_DELTA on the fly. Better to just let the normal\n * object_entry code path handle it.\n */\n\n> > > It might be worth having a perf test here. The case this is helping the\n> > > most, I think, is when somebody cloning wants all of the objects from\n> > > the beginning of the pack, but then there's a bunch of _other_ stuff.\n> > >\n> > > That could be unreachable objects kept by \"repack -k\", or maybe objects\n> > > reachable outside of heads and tags. Or objects that are part of other\n> > > delta islands. This last is the most plausible, really, because we'll\n> > > put all of the root-island objects at the beginning of the pack. So\n> > > maybe a good perf test would be to take an existing repository add a\n> > > bunch of new commits in refs/foo/,\n> >\n> > Not sure how I could do so. How would you do that?\n> >\n> > I think it would be best to add completely new realistic commits that\n> > are changing the main code base.\n>\n> I agree that would be the most realistic for the \"forked repository\n> network\" case that we originally wrote this for. But I think a more\n> mundane (and possibly easier to generate) example might be having a\n> bunch of refs/notes.\n>\n> So perhaps something like this:\n\n[...]\n\nOk, I will add this test to my patch series if I need to resend a V5.\nOtherwise I will send it separately.\n\n> From my limited prodding, it doesn't trigger pack-reuse with the current\n> code, but would after your series. On linux.git, it produces:\n>\n> Test origin origin/jk/packfile-reuse-cleanup\n> ----------------------------------------------------------------------------------\n> 5312.3: clone without notes 14.16(14.26+4.84) 10.80(10.40+0.44) -23.7%\n> 5312.4: clone size 1.4G 1.4G +0.0%\n\nYeah, nice improvement.\n\n> though I suspect the more interesting savings is in RAM (since we don't\n> have to allocate a \"struct object_entry\" for most of the objects). I\n> don't know how hard it would be to collect that data in the perf suite.\n\nI don't know either.\n\n> Running the final pack-objects manually with massif, I get peak heap\n> usage dropping from ~1500MB to ~380MB.\n\nVery nice!\n\n> For git.git it seems less impressive (very little CPU saved, and the\n> resulting pack is slightly larger, perhaps due to not re-considering\n> some deltas whose on-disk versions had to be thrown away):\n>\n> Test origin origin/jk/packfile-reuse-cleanup\n> --------------------------------------------------------------------------------\n> 5312.3: clone without notes 1.22(3.60+0.16) 1.20(3.56+0.16) -1.6%\n> 5312.4: clone size 65.3M 67.0M +2.5%\n\nYeah, I think this is acceptable.\n\n> > > > Is this case possible? try_partial_reuse() is only called when there is\n> > > > a 1 at the bit location.\n> > >\n> > > Yes, it's possible. The result of a bitmap walk is larger than a given\n> > > pack, because we have to extend it to match whatever objects the caller\n> > > asked for. E.g., imagine we have commit A, repack into into a bitmapped\n> > > pack, and then somebody pushes up commit B. Now I want to clone, getting\n> > > both A and B.\n> > >\n> > > Our bitmap result represents the whole answer, and so must include both\n> > > objects. But since \"B\" isn't in the pack, it doesn't have an assigned\n> > > bit. We add it to the in-memory bitmap_git->ext_index, which gives it a\n> > > bit (valid only for that walk result!). But of course for pack reuse, we\n> > > only care about the objects that were actually in the bitmapped pack.\n> >\n> > Not sure if these explanations should go into the commit message or a\n> > comment in the code. So I haven't added them for now.\n>\n> I think this is really outside the scope of this series, even, and gets\n> into how the bitmap traversal works in general. I'm sure the\n> documentation for that could be a bit better.\n\nOk, I will take a look at improving the documentation, either in this\npatch series if I resend it, or in a follow up small series.\n\n> > > Thinking on it more, though, I wonder if there's a bug hiding here. We\n> > > know that we can send the whole initial chunk verbatim for OFS_DELTA\n> > > objects, because the relative offsets will remain unchanged (i.e., there\n> > > are no \"holes\" that trigger our chunk code). But if there were a\n> > > REF_DELTA in that initial chunk, we have no certainty that the base is\n> > > being sent.\n> > >\n> > > In practice, this doesn't happen because the objects in question have to\n> > > be in a pack with bitmaps, which means it was written ourselves by\n> > > git-repack. And we'd never write REF_DELTA objects there.\n> > >\n> > > But I wonder if it's worth being a bit more careful (and what the\n> > > performance impact is; it would mean checking the type of every object\n> > > in that initial chunk).\n> >\n> > I haven't done anything related to that. Maybe something can be done\n> > in a follow up patch.\n>\n> Hmm. I was thinking the problem was introduced in this series, but the\n> old code should suffer from this as well. I wondered if it might simply\n> be that the old code did not trigger often enough for anybody to notice,\n> but we have been running the code in this series for several years at\n> GitHub. So probably my reasoning above is sound (but it might still be\n> worth addressing).\n\nOk, I will take a look.\n\nThanks,\nChristian.\n"}]}