{"thread":{"id":"49097","subject":"[PATCH 0/7] speeding up cat-file by reordering object access","startedAt":"2018-08-10T23:07:33Z","lastAt":"2018-08-16T19:45:41Z","messageCount":27,"participants":["Jeff King","Stefan Beller","Jonathan Tan","René Scharfe","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"355215","messageId":"20180810230729.GA19090@sigill.intra.peff.net","threadId":"49097","inReplyTo":null,"subject":"[PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:07:29Z","receivedAt":"2018-08-10T23:07:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This series is meant to replace the RFC discussion in:\n\n https://public-inbox.org/git/20180808231210.242120-1-jonathantanmy@google.com/\n\nand\n\n https://public-inbox.org/git/20180808155045.GB1607@sigill.intra.peff.net/\n\nThe general idea is that accessing objects in packfile order is way\nkinder to the delta base cache, and thus way more efficient. See patches\n4 and 7 in particular for discussion and numbers.\n\nI'm primarily interested in cat-file, so this series is focused there.\nBut there may be other callers of for_each_packed_object() who could\nbenefit. Most of the existing ones just care about getting the oid, so\nthey're better off as-is. It's possible the call in is_promisor_object()\ncould benefit, since it calls parse_object() on each entry it visits. I\ndidn't experiment with it.\n\n [1/7]: for_each_*_object: store flag definitions in a single location\n [2/7]: for_each_*_object: take flag arguments as enum\n [3/7]: for_each_*_object: give more comprehensive docstrings\n [4/7]: for_each_packed_object: support iterating in pack-order\n [5/7]: t1006: test cat-file --batch-all-objects with duplicates\n [6/7]: cat-file: rename batch_{loose,packed}_object callbacks\n [7/7]: cat-file: support \"unordered\" output for --batch-all-objects\n\n Documentation/git-cat-file.txt | 8 ++++\n builtin/cat-file.c | 70 ++++++++++++++++++++++++++++------\n cache.h | 29 +++++++++++---\n commit-graph.c | 2 +-\n packfile.c | 24 +++++++++---\n packfile.h | 23 ++++++-----\n sha1-file.c | 3 +-\n t/t1006-cat-file.sh | 17 ++++++++-\n 8 files changed, 139 insertions(+), 37 deletions(-)\n\n-Peff\n"},{"id":"355216","messageId":"20180810230906.GA19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:09:06Z","receivedAt":"2018-08-10T23:09:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"These flags were split between cache.h and packfile.h,\nbecause some of the flags apply only to packs. However, they\nshare a single numeric namespace, since both are respected\nfor the packed variant. Let's make sure they're defined\ntogether so that nobody accidentally adds a new flag in one\nlocation that duplicates the other.\n\nWhile we're here, let's also put them in an enum (which\nhelps debugger visibility) and use \"(1<\n---\nArguably, all of these for_each_*_object() functions should stay\ntogether. Even though some are related to packfiles and some to loose,\nthey are meant to be a unified API. So I'd be fine to do that on top,\nbut this at least reduces the chance of a mistake in the meantime.\n\n cache.h | 13 ++++++++++++-\n packfile.h | 8 ++------\n 2 files changed, 14 insertions(+), 7 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 8dc7134f00..4187238ecf 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1623,12 +1623,23 @@ int for_each_loose_file_in_objdir_buf(struct strbuf *path,\n \t\t\t\t each_loose_subdir_fn subdir_cb,\n \t\t\t\t void *data);\n \n+/*\n+ * Flags for for_each_*_object(), including for_each_loose below and\n+ * for_each_packed in packfile.h.\n+ */\n+enum for_each_object_flags {\n+\t/* Iterate only over local objects, not alternates. */\n+\tFOR_EACH_OBJECT_LOCAL_ONLY = (1<<0),\n+\n+\t/* Only iterate over packs obtained from the promisor remote. */\n+\tFOR_EACH_OBJECT_PROMISOR_ONLY = (1<<1),\n+};\n+\n /*\n * Iterate over loose objects in both the local\n * repository and any alternates repositories (unless the\n * LOCAL_ONLY flag is set).\n */\n-#define FOR_EACH_OBJECT_LOCAL_ONLY 0x1\n extern int for_each_loose_object(each_loose_object_fn, void *, unsigned flags);\n \n /*\ndiff --git a/packfile.h b/packfile.h\nindex cc7eaffe1b..6ddc6a2e91 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -148,15 +148,11 @@ extern int has_object_pack(const struct object_id *oid);\n \n extern int has_pack_index(const unsigned char *sha1);\n \n-/*\n- * Only iterate over packs obtained from the promisor remote.\n- */\n-#define FOR_EACH_OBJECT_PROMISOR_ONLY 2\n-\n /*\n * Iterate over packed objects in both the local\n * repository and any alternates repositories (unless the\n- * FOR_EACH_OBJECT_LOCAL_ONLY flag, defined in cache.h, is set).\n+ * FOR_EACH_OBJECT_LOCAL_ONLY flag is set). See cache.h for the complete list\n+ * of flags.\n */\n typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355217","messageId":"20180810230944.GB19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 2/7] for_each_*_object: take flag arguments as enum","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:09:44Z","receivedAt":"2018-08-10T23:09:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"It's not wrong to pass our flags in an \"unsigned\", as we\nknow it will be at least as large as the enum. However,\nusing the enum in the declaration makes it more obvious\nwhere to find the list of flags.\n\nWhile we're here, let's also drop the \"extern\" noise-words\nfrom the declarations, per our modern coding style.\n\nSigned-off-by: Jeff King \n---\n cache.h | 3 ++-\n packfile.c | 3 ++-\n packfile.h | 5 +++--\n sha1-file.c | 3 ++-\n 4 files changed, 9 insertions(+), 5 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 4187238ecf..9e02fc494e 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1640,7 +1640,8 @@ enum for_each_object_flags {\n * repository and any alternates repositories (unless the\n * LOCAL_ONLY flag is set).\n */\n-extern int for_each_loose_object(each_loose_object_fn, void *, unsigned flags);\n+int for_each_loose_object(each_loose_object_fn, void *,\n+\t\t\t enum for_each_object_flags flags);\n \n /*\n * Set this to 0 to prevent sha1_object_info_extended() from fetching missing\ndiff --git a/packfile.c b/packfile.c\nindex 6974903e58..9da8f6d728 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1904,7 +1904,8 @@ int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void\n \treturn r;\n }\n \n-int for_each_packed_object(each_packed_object_fn cb, void *data, unsigned flags)\n+int for_each_packed_object(each_packed_object_fn cb, void *data,\n+\t\t\t enum for_each_object_flags flags)\n {\n \tstruct packed_git *p;\n \tint r = 0;\ndiff --git a/packfile.h b/packfile.h\nindex 6ddc6a2e91..9861728514 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -158,8 +158,9 @@ typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n \t\t\t\t uint32_t pos,\n \t\t\t\t void *data);\n-extern int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn, void *data);\n-extern int for_each_packed_object(each_packed_object_fn, void *, unsigned flags);\n+int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn, void *data);\n+int for_each_packed_object(each_packed_object_fn, void *,\n+\t\t\t enum for_each_object_flags flags);\n \n /*\n * Return 1 if an object in a promisor packfile is or refers to the given\ndiff --git a/sha1-file.c b/sha1-file.c\nindex dfa8a35d68..cc0b57a751 100644\n--- a/sha1-file.c\n+++ b/sha1-file.c\n@@ -2146,7 +2146,8 @@ static int loose_from_alt_odb(struct alternate_object_database *alt,\n \treturn r;\n }\n \n-int for_each_loose_object(each_loose_object_fn cb, void *data, unsigned flags)\n+int for_each_loose_object(each_loose_object_fn cb, void *data,\n+\t\t\t enum for_each_object_flags flags)\n {\n \tstruct loose_alt_odb_data alt;\n \tint r;\n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355218","messageId":"20180810231114.GC19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 3/7] for_each_*_object: give more comprehensive docstrings","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:11:14Z","receivedAt":"2018-08-10T23:11:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We already mention the local/alternate behavior of these\nfunctions, but we can help clarify a few other behaviors:\n\n - there's no need to mention LOCAL_ONLY specifically, since\n we already reference the flags by type (and as we add\n more flags, we don't want to have to mention each)\n\n - clarify that reachability doesn't matter here; this is\n all accessible objects\n\n - what ordering/uniqueness guarantees we give\n\n - how pack-specific flags are handled for the loose case\n\nSigned-off-by: Jeff King \n---\n cache.h | 8 +++++---\n packfile.h | 12 ++++++++----\n 2 files changed, 13 insertions(+), 7 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 9e02fc494e..f438540f9b 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1636,9 +1636,11 @@ enum for_each_object_flags {\n };\n \n /*\n- * Iterate over loose objects in both the local\n- * repository and any alternates repositories (unless the\n- * LOCAL_ONLY flag is set).\n+ * Iterate over all accessible loose objects without respect to\n+ * reachability. By default, this includes both local and alternate objects.\n+ * The order in which objects are visited is unspecified.\n+ *\n+ * Any flags specific to packs are ignored.\n */\n int for_each_loose_object(each_loose_object_fn, void *,\n \t\t\t enum for_each_object_flags flags);\ndiff --git a/packfile.h b/packfile.h\nindex 9861728514..c86a8c2716 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -149,10 +149,14 @@ extern int has_object_pack(const struct object_id *oid);\n extern int has_pack_index(const unsigned char *sha1);\n \n /*\n- * Iterate over packed objects in both the local\n- * repository and any alternates repositories (unless the\n- * FOR_EACH_OBJECT_LOCAL_ONLY flag is set). See cache.h for the complete list\n- * of flags.\n+ * Iterate over all accessible packed objects without respect to reachability.\n+ * By default, this includes both local and alternate packs.\n+ *\n+ * Note that some objects may appear twice if they are found in multiple packs.\n+ * Each pack is visited in an unspecified order. Objects within a pack are\n+ * visited in pack-idx order (i.e., sorted by oid).\n+ *\n+ * The list of flags can be found in cache.h.\n */\n typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355219","messageId":"20180810231549.GD19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 4/7] for_each_packed_object: support iterating in pack-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:15:49Z","receivedAt":"2018-08-10T23:15:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We currently iterate over objects within a pack in .idx\norder, which uses the object hashes. That means that it\nis effectively random with respect to the location of the\nobject within the pack. If you're going to access the actual\nobject data, there are two reasons to move linearly through\nthe pack itself:\n\n 1. It improves the locality of access in the packfile. In\n the cold-cache case, this may mean fewer disk seeks, or\n better usage of disk cache.\n\n 2. We store related deltas together in the packfile. Which\n means that the delta base cache can operate much more\n efficiently if we visit all of those related deltas in\n sequence, as the earlier items are likely to still be\n in the cache. Whereas if we visit the objects in\n random order, our cache entries are much more likely to\n have been evicted by unrelated deltas in the meantime.\n\nSo in general, if you're going to access the object contents\npack order is generally going to end up more efficient.\n\nBut if you're simply generating a list of object names, or\nif you're going to end up sorting the result anyway, you're\nbetter off just using the .idx order, as finding the pack\norder means generating the in-memory pack-revindex.\nAccording to the numbers in 8b8dfd5132 (pack-revindex:\nradix-sort the revindex, 2013-07-11), that takes about 200ms\nfor linux.git, and 20ms for git.git (those numbers are a few\nyears old but are still a good ballpark).\n\nThat makes it a good optimization for some cases (we can\nsave tens of seconds in git.git by having good locality of\ndelta access, for a 20ms cost), but a bad one for others\n(e.g., right now \"cat-file --batch-all-objects\n--batch-check=\"%(objectname)\" is 170ms in git.git, so adding\n20ms to that is noticeable).\n\nHence this patch makes it an optional flag. You can't\nactually do any interesting timings yet, as it's not plumbed\nthrough to any user-facing tools like cat-file. That will\ncome in a later patch.\n\nSigned-off-by: Jeff King \n---\n cache.h | 5 +++++\n commit-graph.c | 2 +-\n packfile.c | 21 ++++++++++++++++-----\n packfile.h | 8 +++++---\n 4 files changed, 27 insertions(+), 9 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex f438540f9b..6d14702df2 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1633,6 +1633,11 @@ enum for_each_object_flags {\n \n \t/* Only iterate over packs obtained from the promisor remote. */\n \tFOR_EACH_OBJECT_PROMISOR_ONLY = (1<<1),\n+\n+\t/*\n+\t * Visit objects within a pack in packfile order rather than .idx order\n+\t */\n+\tFOR_EACH_OBJECT_PACK_ORDER = (1<<2),\n };\n \n /*\ndiff --git a/commit-graph.c b/commit-graph.c\nindex b0a55ad128..69a0d1c203 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -730,7 +730,7 @@ void write_commit_graph(const char *obj_dir,\n \t\t\t\tdie(\"error adding pack %s\", packname.buf);\n \t\t\tif (open_pack_index(p))\n \t\t\t\tdie(\"error opening index for %s\", packname.buf);\n-\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids);\n+\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids, 0);\n \t\t\tclose_pack(p);\n \t\t}\n \t\tstrbuf_release(&packname);\ndiff --git a/packfile.c b/packfile.c\nindex 9da8f6d728..ebcb5742ec 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1885,19 +1885,30 @@ int has_pack_index(const unsigned char *sha1)\n \treturn 1;\n }\n \n-int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn cb, void *data)\n+int for_each_object_in_pack(struct packed_git *p,\n+\t\t\t each_packed_object_fn cb, void *data,\n+\t\t\t enum for_each_object_flags flags)\n {\n \tuint32_t i;\n \tint r = 0;\n \n+\tif (flags & FOR_EACH_OBJECT_PACK_ORDER)\n+\t\tload_pack_revindex(p);\n+\n \tfor (i = 0; i < p->num_objects; i++) {\n+\t\tuint32_t pos;\n \t\tstruct object_id oid;\n \n-\t\tif (!nth_packed_object_oid(&oid, p, i))\n+\t\tif (flags & FOR_EACH_OBJECT_PACK_ORDER)\n+\t\t\tpos = p->revindex[i].nr;\n+\t\telse\n+\t\t\tpos = i;\n+\n+\t\tif (!nth_packed_object_oid(&oid, p, pos))\n \t\t\treturn error(\"unable to get sha1 of object %u in %s\",\n-\t\t\t\t i, p->pack_name);\n+\t\t\t\t pos, p->pack_name);\n \n-\t\tr = cb(&oid, p, i, data);\n+\t\tr = cb(&oid, p, pos, data);\n \t\tif (r)\n \t\t\tbreak;\n \t}\n@@ -1922,7 +1933,7 @@ int for_each_packed_object(each_packed_object_fn cb, void *data,\n \t\t\tpack_errors = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tr = for_each_object_in_pack(p, cb, data);\n+\t\tr = for_each_object_in_pack(p, cb, data, flags);\n \t\tif (r)\n \t\t\tbreak;\n \t}\ndiff --git a/packfile.h b/packfile.h\nindex c86a8c2716..99411bdd85 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -153,8 +153,8 @@ extern int has_pack_index(const unsigned char *sha1);\n * By default, this includes both local and alternate packs.\n *\n * Note that some objects may appear twice if they are found in multiple packs.\n- * Each pack is visited in an unspecified order. Objects within a pack are\n- * visited in pack-idx order (i.e., sorted by oid).\n+ * Each pack is visited in an unspecified order. By default, objects within a\n+ * pack are visited in pack-idx order (i.e., sorted by oid).\n *\n * The list of flags can be found in cache.h.\n */\n@@ -162,7 +162,9 @@ typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n \t\t\t\t uint32_t pos,\n \t\t\t\t void *data);\n-int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn, void *data);\n+int for_each_object_in_pack(struct packed_git *p,\n+\t\t\t each_packed_object_fn, void *data,\n+\t\t\t enum for_each_object_flags flags);\n int for_each_packed_object(each_packed_object_fn, void *,\n \t\t\t enum for_each_object_flags flags);\n \n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355220","messageId":"20180810231640.GE19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 5/7] t1006: test cat-file --batch-all-objects with duplicates","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:16:40Z","receivedAt":"2018-08-10T23:16:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The test for --batch-all-objects in t1006 covers a variety\nof object storage situations, but one thing it doesn't cover\nis that we avoid mentioning duplicate objects. We won't have\nany because running \"git repack -ad\" will have packed them\nall and deleted the loose ones.\n\nThis does work (because we sort and de-dup the output list),\nbut it's good to include it in our test. And doubly so for\nwhen we add an unordered mode which has to de-dup in a\ndifferent way.\n\nNote that we cannot just re-create one of the objects, as\nGit will omit the write of an object that is already\npresent. However, we can create a new pack with one of the\nobjects, which forces the duplication.\n\nOne alternative would be to just use \"git repack -a\" instead\nof \"-ad\". But then _every_ object would be duplicated as\nloose and packed, and we might miss a bug that omits packed\nobjects (because we'd show their loose counterparts).\n\nSigned-off-by: Jeff King \n---\n t/t1006-cat-file.sh | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex 13dd510b2e..4fb5e098f2 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -550,8 +550,8 @@ test_expect_success 'git cat-file --batch --follow-symlink returns correct sha a\n test_expect_success 'cat-file --batch-all-objects shows all objects' '\n \t# make new repos so we know the full set of objects; we will\n \t# also make sure that there are some packed and some loose\n-\t# objects, some referenced and some not, and that there are\n-\t# some available only via alternates.\n+\t# objects, some referenced and some not, some duplicates, and that\n+\t# there are some available only via alternates.\n \tgit init all-one &&\n \t(\n \t\tcd all-one &&\n@@ -567,6 +567,8 @@ test_expect_success 'cat-file --batch-all-objects shows all objects' '\n \t\tcd all-two &&\n \t\techo local-unref | git hash-object -w --stdin\n \t) >>expect.unsorted &&\n+\tgit -C all-two rev-parse HEAD:file |\n+\t\tgit -C all-two pack-objects .git/objects/pack/pack &&\n \tsort expect &&\n \tgit -C all-two cat-file --batch-all-objects \\\n \t\t\t\t--batch-check=\"%(objectname)\" >actual &&\n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355221","messageId":"20180810231714.GF19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 6/7] cat-file: rename batch_{loose,packed}_object callbacks","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:17:14Z","receivedAt":"2018-08-10T23:17:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We're not really doing the batch-show operation in these\ncallbacks, but just collecting the set of objects. That\ndistinction will become more important in a future patch, so\nlet's rename them now to avoid cluttering that diff.\n\nSigned-off-by: Jeff King \n---\n builtin/cat-file.c | 18 +++++++++---------\n 1 file changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 4a44b2404f..2d34f3b867 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -420,18 +420,18 @@ static int batch_object_cb(const struct object_id *oid, void *vdata)\n \treturn 0;\n }\n \n-static int batch_loose_object(const struct object_id *oid,\n-\t\t\t const char *path,\n-\t\t\t void *data)\n+static int collect_loose_object(const struct object_id *oid,\n+\t\t\t\tconst char *path,\n+\t\t\t\tvoid *data)\n {\n \toid_array_append(data, oid);\n \treturn 0;\n }\n \n-static int batch_packed_object(const struct object_id *oid,\n-\t\t\t struct packed_git *pack,\n-\t\t\t uint32_t pos,\n-\t\t\t void *data)\n+static int collect_packed_object(const struct object_id *oid,\n+\t\t\t\t struct packed_git *pack,\n+\t\t\t\t uint32_t pos,\n+\t\t\t\t void *data)\n {\n \toid_array_append(data, oid);\n \treturn 0;\n@@ -476,8 +476,8 @@ static int batch_objects(struct batch_options *opt)\n \t\tstruct oid_array sa = OID_ARRAY_INIT;\n \t\tstruct object_cb_data cb;\n \n-\t\tfor_each_loose_object(batch_loose_object, &sa, 0);\n-\t\tfor_each_packed_object(batch_packed_object, &sa, 0);\n+\t\tfor_each_loose_object(collect_loose_object, &sa, 0);\n+\t\tfor_each_packed_object(collect_packed_object, &sa, 0);\n \t\tif (repository_format_partial_clone)\n \t\t\twarning(\"This repository has extensions.partialClone set. Some objects may not be loaded.\");\n \n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355222","messageId":"20180810232457.GG19875@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"[PATCH 7/7] cat-file: support \"unordered\" output for --batch-all-objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:24:57Z","receivedAt":"2018-08-10T23:25:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If you're going to access the contents of every object in a\npackfile, it's generally much more efficient to do so in\npack order, rather than in hash order. That increases the\nlocality of access within the packfile, which in turn is\nfriendlier to the delta base cache, since the packfile puts\nrelated deltas next to each other. By contrast, hash order\nis effectively random, since the sha1 has no discernible\nrelationship to the content.\n\nThis patch introduces an \"--unordered\" option to cat-file\nwhich iterates over packs in pack-order under the hood. You\ncan see the results when dumping all of the file content:\n\n $ time ./git cat-file --batch-all-objects --buffer --batch | wc -c\n 6883195596\n\n real\t0m44.491s\n user\t0m42.902s\n sys\t0m5.230s\n\n $ time ./git cat-file --unordered \\\n --batch-all-objects --buffer --batch | wc -c\n 6883195596\n\n real\t0m6.075s\n user\t0m4.774s\n sys\t0m3.548s\n\nSame output, different order, way faster. The same speed-up\napplies even if you end up accessing the object content in a\ndifferent process, like:\n\n git cat-file --batch-all-objects --buffer --batch-check |\n grep blob |\n git cat-file --batch='%(objectname) %(rest)' |\n wc -c\n\nAdding \"--unordered\" to the first command drops the runtime\nin git.git from 24s to 3.5s.\n\n Side note: there are actually further speedups available\n for doing it all in-process now. Since we are outputting\n the object content during the actual pack iteration, we\n know where to find the object and could skip the extra\n lookup done by oid_object_info(). This patch stops short\n of that optimization since the underlying API isn't ready\n for us to make those sorts of direct requests.\n\nSo if --unordered is so much better, why not make it the\ndefault? Two reasons:\n\n 1. We've promised in the documentation that --batch-all-objects\n outputs in hash order. Since cat-file is plumbing,\n people may be relying on that default, and we can't\n change it.\n\n 2. It's actually _slower_ for some cases. We have to\n compute the pack revindex to walk in pack order. And\n our de-duplication step uses an oidset, rather than a\n sort-and-dedup, which can end up being more expensive.\n If we're just accessing the type and size of each\n object, for example, like:\n\n git cat-file --batch-all-objects --buffer --batch-check\n\n my best-of-five warm cache timings go from 900ms to\n 1100ms using --unordered. Though it's possible in a\n cold-cache or under memory pressure that we could do\n better, since we'd have better locality within the\n packfile.\n\nAnd one final question: why is it \"--unordered\" and not\n\"--pack-order\"? The answer is again two-fold:\n\n 1. \"pack order\" isn't a well-defined thing across the\n whole set of objects. We're hitting loose objects, as\n well as objects in multiple packs, and the only\n ordering we're promising is _within_ a single pack. The\n rest is apparently random.\n\n 2. The point here is optimization. So we don't want to\n promise any particular ordering, but only to say that\n we will choose an ordering which is likely to be\n efficient for accessing the object content. That leaves\n the door open for further changes in the future without\n having to add another compatibility option.\n\nSigned-off-by: Jeff King \n---\n Documentation/git-cat-file.txt | 10 ++++++\n builtin/cat-file.c | 56 +++++++++++++++++++++++++++++++---\n t/t1006-cat-file.sh | 11 +++++++\n 3 files changed, 72 insertions(+), 5 deletions(-)\n\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\nindex f90f09b03f..74013335a1 100644\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -104,6 +104,16 @@ OPTIONS\n \tbuffering; this is much more efficient when invoking\n \t`--batch-check` on a large number of objects.\n \n+--unordered::\n+\tWhen `--batch-all-objects` is in use, visit objects in an\n+\torder which may be more efficient for accessing the object\n+\tcontents than hash order. The exact details of the order are\n+\tunspecified, but if you do not require a specific order, this\n+\tshould generally result in faster output, especially with\n+\t`--batch`. Note that `cat-file` will still show each object\n+\tonly once, even if it is stored multiple times in the\n+\trepository.\n+\n --allow-unknown-type::\n \tAllow -s or -t to query broken/corrupt objects of unknown type.\n \ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 2d34f3b867..45992c9be9 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -21,6 +21,7 @@ struct batch_options {\n \tint print_contents;\n \tint buffer_output;\n \tint all_objects;\n+\tint unordered;\n \tint cmdmode; /* may be 'w' or 'c' for --filters or --textconv */\n \tconst char *format;\n };\n@@ -410,6 +411,7 @@ static void batch_one_object(const char *obj_name, struct batch_options *opt,\n struct object_cb_data {\n \tstruct batch_options *opt;\n \tstruct expand_data *expand;\n+\tstruct oidset *seen;\n };\n \n static int batch_object_cb(const struct object_id *oid, void *vdata)\n@@ -437,6 +439,32 @@ static int collect_packed_object(const struct object_id *oid,\n \treturn 0;\n }\n \n+static int batch_unordered_object(const struct object_id *oid, void *vdata)\n+{\n+\tstruct object_cb_data *data = vdata;\n+\n+\tif (oidset_contains(data->seen, oid))\n+\t\treturn 0;\n+\toidset_insert(data->seen, oid);\n+\n+\treturn batch_object_cb(oid, data);\n+}\n+\n+static int batch_unordered_loose(const struct object_id *oid,\n+\t\t\t\t const char *path,\n+\t\t\t\t void *data)\n+{\n+\treturn batch_unordered_object(oid, data);\n+}\n+\n+static int batch_unordered_packed(const struct object_id *oid,\n+\t\t\t\t struct packed_git *pack,\n+\t\t\t\t uint32_t pos,\n+\t\t\t\t void *data)\n+{\n+\treturn batch_unordered_object(oid, data);\n+}\n+\n static int batch_objects(struct batch_options *opt)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -473,19 +501,35 @@ static int batch_objects(struct batch_options *opt)\n \t\tdata.info.typep = &data.type;\n \n \tif (opt->all_objects) {\n-\t\tstruct oid_array sa = OID_ARRAY_INIT;\n \t\tstruct object_cb_data cb;\n \n-\t\tfor_each_loose_object(collect_loose_object, &sa, 0);\n-\t\tfor_each_packed_object(collect_packed_object, &sa, 0);\n \t\tif (repository_format_partial_clone)\n \t\t\twarning(\"This repository has extensions.partialClone set. Some objects may not be loaded.\");\n \n \t\tcb.opt = opt;\n \t\tcb.expand = &data;\n-\t\toid_array_for_each_unique(&sa, batch_object_cb, &cb);\n \n-\t\toid_array_clear(&sa);\n+\t\tif (opt->unordered) {\n+\t\t\tstruct oidset seen = OIDSET_INIT;\n+\n+\t\t\tcb.seen = &seen;\n+\n+\t\t\tfor_each_loose_object(batch_unordered_loose, &cb, 0);\n+\t\t\tfor_each_packed_object(batch_unordered_packed, &cb,\n+\t\t\t\t\t FOR_EACH_OBJECT_PACK_ORDER);\n+\n+\t\t\toidset_clear(&seen);\n+\t\t} else {\n+\t\t\tstruct oid_array sa = OID_ARRAY_INIT;\n+\n+\t\t\tfor_each_loose_object(collect_loose_object, &sa, 0);\n+\t\t\tfor_each_packed_object(collect_packed_object, &sa, 0);\n+\n+\t\t\toid_array_for_each_unique(&sa, batch_object_cb, &cb);\n+\n+\t\t\toid_array_clear(&sa);\n+\t\t}\n+\n \t\treturn 0;\n \t}\n \n@@ -586,6 +630,8 @@ int cmd_cat_file(int argc, const char **argv, const char *prefix)\n \t\t\t N_(\"follow in-tree symlinks (used with --batch or --batch-check)\")),\n \t\tOPT_BOOL(0, \"batch-all-objects\", &batch.all_objects,\n \t\t\t N_(\"show all objects with --batch or --batch-check\")),\n+\t\tOPT_BOOL(0, \"unordered\", &batch.unordered,\n+\t\t\t N_(\"do not order --batch-all-objects output\")),\n \t\tOPT_END()\n \t};\n \ndiff --git a/t/t1006-cat-file.sh b/t/t1006-cat-file.sh\nindex 4fb5e098f2..7f19d591f2 100755\n--- a/t/t1006-cat-file.sh\n+++ b/t/t1006-cat-file.sh\n@@ -575,4 +575,15 @@ test_expect_success 'cat-file --batch-all-objects shows all objects' '\n \ttest_cmp expect actual\n '\n \n+# The only user-visible difference is that the objects are no longer sorted,\n+# and the resulting sort order is undefined. So we can only check that it\n+# produces the same objects as the ordered case, but that at least exercises\n+# the code.\n+test_expect_success 'cat-file --unordered works' '\n+\tgit -C all-two cat-file --batch-all-objects --unordered \\\n+\t\t\t\t--batch-check=\"%(objectname)\" >actual.unsorted &&\n+\tsort actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.18.0.1058.g7433f71063\n\n"},{"id":"355223","messageId":"CAGZ79kYStPNCodJBqZ-ELh2oEhEyQFFjr0SVn0Bn+gtAspbZiA@mail.gmail.com","threadId":"49097","inReplyTo":"20180810230906.GA19875@sigill.intra.peff.net","subject":"Re: [PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T23:27:25Z","receivedAt":"2018-08-10T23:27:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Aug 10, 2018 at 4:09 PM Jeff King wrote:\n>\n> These flags were split between cache.h and packfile.h,\n> because some of the flags apply only to packs. However, they\n> share a single numeric namespace, since both are respected\n> for the packed variant. Let's make sure they're defined\n> together so that nobody accidentally adds a new flag in one\n> location that duplicates the other.\n>\n> While we're here, let's also put them in an enum (which\n> helps debugger visibility) and use \"(1< counting powers of 2 manually.\n\nAll good, but ...\n\n> cache.h | 13 ++++++++++++-\n> packfile.h | 8 ++------\n> 2 files changed, 14 insertions(+), 7 deletions(-)\n\nrubs me the wrong way. ;-)\n\ncache.h is such a misnomer of a name, and a kitchen sink\nof a file in the Git project that in an ideal world it would\nbe way smaller and contain only things related to some\ncaching related code.\n\nI would suggest object.h or object-store.h instead.\nProbably the object-store as that will be the only external\nexposure and hopefully we'd get the objects in a similar\nshape as the refs subsystem eventually?\n\nI might be biased by commits such as 4f39cd821d1\n(pack: move pack name-related functions, 2017-08-18)\n"},{"id":"355224","messageId":"20180810233133.GA30076@sigill.intra.peff.net","threadId":"49097","inReplyTo":"CAGZ79kYStPNCodJBqZ-ELh2oEhEyQFFjr0SVn0Bn+gtAspbZiA@mail.gmail.com","subject":"Re: [PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:31:34Z","receivedAt":"2018-08-10T23:31:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 10, 2018 at 04:27:25PM -0700, Stefan Beller wrote:\n\n> > cache.h | 13 ++++++++++++-\n> > packfile.h | 8 ++------\n> > 2 files changed, 14 insertions(+), 7 deletions(-)\n> \n> rubs me the wrong way. ;-)\n> \n> cache.h is such a misnomer of a name, and a kitchen sink\n> of a file in the Git project that in an ideal world it would\n> be way smaller and contain only things related to some\n> caching related code.\n> \n> I would suggest object.h or object-store.h instead.\n> Probably the object-store as that will be the only external\n> exposure and hopefully we'd get the objects in a similar\n> shape as the refs subsystem eventually?\n\nYes, for_each_loose_object() ought to be in loose.h to match packfile.h,\nor the whole thing should go into object-store.h.\n\nThis series was already getting long, though, so I'd much rather do this\nnow and other reorganization later (in particular, wherever they end up,\nwe want the flags to move as a unit).\n\n-Peff\n"},{"id":"355225","messageId":"20180810233347.GA30479@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180810233133.GA30076@sigill.intra.peff.net","subject":"Re: [PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-10T23:33:47Z","receivedAt":"2018-08-10T23:33:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 10, 2018 at 07:31:33PM -0400, Jeff King wrote:\n\n> On Fri, Aug 10, 2018 at 04:27:25PM -0700, Stefan Beller wrote:\n> \n> > > cache.h | 13 ++++++++++++-\n> > > packfile.h | 8 ++------\n> > > 2 files changed, 14 insertions(+), 7 deletions(-)\n> > \n> > rubs me the wrong way. ;-)\n> > \n> > cache.h is such a misnomer of a name, and a kitchen sink\n> > of a file in the Git project that in an ideal world it would\n> > be way smaller and contain only things related to some\n> > caching related code.\n> > \n> > I would suggest object.h or object-store.h instead.\n> > Probably the object-store as that will be the only external\n> > exposure and hopefully we'd get the objects in a similar\n> > shape as the refs subsystem eventually?\n> \n> Yes, for_each_loose_object() ought to be in loose.h to match packfile.h,\n> or the whole thing should go into object-store.h.\n\nHeh, I thought you were making up a hypothetical object-store.h, but I\nsee it has already come to pass.\n\nIMHO the whole for_each_*_object() interface should go in there (it even\nhas packed_git defined there already!). I think I'd still just as soon\ndo it on top of this series, but it might not be too bad to do as part\nof a re-roll.\n\n-Peff\n"},{"id":"355226","messageId":"CAGZ79kZ0eN5eaBM8HjLVFpW8-ph3g0ym=-4ONTA7pgV=k3oz-Q@mail.gmail.com","threadId":"49097","inReplyTo":"20180810233347.GA30479@sigill.intra.peff.net","subject":"Re: [PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-10T23:39:14Z","receivedAt":"2018-08-10T23:39:29Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Aug 10, 2018 at 4:33 PM Jeff King wrote:\n>\n> On Fri, Aug 10, 2018 at 07:31:33PM -0400, Jeff King wrote:\n>\n> > On Fri, Aug 10, 2018 at 04:27:25PM -0700, Stefan Beller wrote:\n> >\n> > > > cache.h | 13 ++++++++++++-\n> > > > packfile.h | 8 ++------\n> > > > 2 files changed, 14 insertions(+), 7 deletions(-)\n> > >\n> > > rubs me the wrong way. ;-)\n> > >\n> > > cache.h is such a misnomer of a name, and a kitchen sink\n> > > of a file in the Git project that in an ideal world it would\n> > > be way smaller and contain only things related to some\n> > > caching related code.\n> > >\n> > > I would suggest object.h or object-store.h instead.\n> > > Probably the object-store as that will be the only external\n> > > exposure and hopefully we'd get the objects in a similar\n> > > shape as the refs subsystem eventually?\n> >\n> > Yes, for_each_loose_object() ought to be in loose.h to match packfile.h,\n> > or the whole thing should go into object-store.h.\n>\n> Heh, I thought you were making up a hypothetical object-store.h, but I\n> see it has already come to pass.\n>\n> IMHO the whole for_each_*_object() interface should go in there (it even\n> has packed_git defined there already!). I think I'd still just as soon\n> do it on top of this series, but it might not be too bad to do as part\n> of a re-roll.\n\nYeah, I realize that I distracted myself and ranted about a different thing\nother than the quality of this patch. (We had a couple of internal discussions\nabout project velocity and contributor happiness and I personally think this\nderailing is some sort of anti pattern as fixing things like these is easy\nas compared to user visible things such as file formats or configs.\nSorry for that.)\n\nStefan\n"},{"id":"355227","messageId":"20180811003319.GA29490@sigill.intra.peff.net","threadId":"49097","inReplyTo":"CAGZ79kZ0eN5eaBM8HjLVFpW8-ph3g0ym=-4ONTA7pgV=k3oz-Q@mail.gmail.com","subject":"Re: [PATCH 1/7] for_each_*_object: store flag definitions in a single location","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-11T00:33:19Z","receivedAt":"2018-08-11T00:33:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 10, 2018 at 04:39:14PM -0700, Stefan Beller wrote:\n\n> > IMHO the whole for_each_*_object() interface should go in there (it even\n> > has packed_git defined there already!). I think I'd still just as soon\n> > do it on top of this series, but it might not be too bad to do as part\n> > of a re-roll.\n> \n> Yeah, I realize that I distracted myself and ranted about a different thing\n> other than the quality of this patch. (We had a couple of internal discussions\n> about project velocity and contributor happiness and I personally think this\n> derailing is some sort of anti pattern as fixing things like these is easy\n> as compared to user visible things such as file formats or configs.\n> Sorry for that.)\n\nIt's a tough line to draw sometimes. This kind of ancillary discussion\nis often what spurs further work, so I think the discussions are good to\nhave. And sometimes the right answer is \"yeah, while we're here, let's\nclean this up, too\". This may even be one of those cases.\n\nBut sometimes the right answer is to push back a little and say \"you're\nright, but let's deal with it later\". And maybe later never even\nhappens, but in that case maybe it wasn't that important in the first\nplace. :) Or maybe it takes the same point coming up a few times to\ndecide it's worth pursuing.\n\nI wish I had a good guideline for when to start such a discussion and\nwhen to push back. I mostly just follow my instincts, and my answer (on\neither side of that conversation) might change from day to day. I think\nthe most important guideline is for everybody to be accepting of both\nsides of the conversation (i.e., it's OK to prod a little about\nancillary issues as long as \"yes, but not right now\" is an acceptable\nanswer).\n\nAnd then sometimes you catch me in a philosophical mood...\n\n-Peff\n"},{"id":"355443","messageId":"20180813184506.18232-1-jonathantanmy@google.com","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"Re: [PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2018-08-13T18:45:06Z","receivedAt":"2018-08-13T18:45:12Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> [1/7]: for_each_*_object: store flag definitions in a single location\n> [2/7]: for_each_*_object: take flag arguments as enum\n> [3/7]: for_each_*_object: give more comprehensive docstrings\n> [4/7]: for_each_packed_object: support iterating in pack-order\n> [5/7]: t1006: test cat-file --batch-all-objects with duplicates\n> [6/7]: cat-file: rename batch_{loose,packed}_object callbacks\n> [7/7]: cat-file: support \"unordered\" output for --batch-all-objects\n\nThanks for laying all the patches out so cleanly! All of them are:\nReviewed-by: Jonathan Tan \n\nNormally I would re-explain the patches to demonstrate that I understand\nthem, but in this case, I think they are simple enough - patches 1, 2,\n3, and 6 are refactorings that I agree with, patch 5 just makes a test\nmore comprehensive, and patches 4 and 7 do what their commit messages\nsay.\n\nStefan brought up the concern that cache.h is increasing in size, but I\nagree with the patch as written that it's probably best that we\ncentralize all the flags somewhere, and we can deal with the location in\na future patch.\n"},{"id":"355575","messageId":"20180814181358.GA26391@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180813184506.18232-1-jonathantanmy@google.com","subject":"[PATCH 0/4] finishing touches on jk/for-each-object-iteration","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T18:13:59Z","receivedAt":"2018-08-14T18:14:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 13, 2018 at 11:45:06AM -0700, Jonathan Tan wrote:\n\n> > [1/7]: for_each_*_object: store flag definitions in a single location\n> > [2/7]: for_each_*_object: take flag arguments as enum\n> > [3/7]: for_each_*_object: give more comprehensive docstrings\n> > [4/7]: for_each_packed_object: support iterating in pack-order\n> > [5/7]: t1006: test cat-file --batch-all-objects with duplicates\n> > [6/7]: cat-file: rename batch_{loose,packed}_object callbacks\n> > [7/7]: cat-file: support \"unordered\" output for --batch-all-objects\n> \n> Thanks for laying all the patches out so cleanly! All of them are:\n> Reviewed-by: Jonathan Tan \n> \n> Normally I would re-explain the patches to demonstrate that I understand\n> them, but in this case, I think they are simple enough - patches 1, 2,\n> 3, and 6 are refactorings that I agree with, patch 5 just makes a test\n> more comprehensive, and patches 4 and 7 do what their commit messages\n> say.\n> \n> Stefan brought up the concern that cache.h is increasing in size, but I\n> agree with the patch as written that it's probably best that we\n> centralize all the flags somewhere, and we can deal with the location in\n> a future patch.\n\nThanks for the review. Here are a few patches on top to deal with the\ncache.h thing, as well as some optimizations that came out of discussing\noidset in another thread (I left out for now the \"big\" optimization of\nmoving oidset to a different data structure; that's complicated enough\nto be dealt with on its own, I think).\n\nThe first patch here could arguably be squashed into the final patch of\nthe original series, but I'm OK with it either way.\n\n [1/4]: cat-file: use oidset check-and-insert\n [2/4]: cat-file: split batch \"buf\" into two variables\n [3/4]: cat-file: use a single strbuf for all output\n [4/4]: for_each_*_object: move declarations to object-store.h\n\n builtin/cat-file.c | 43 +++++++++++---------\n builtin/prune-packed.c | 1 +\n cache.h | 75 -----------------------------------\n object-store.h | 90 ++++++++++++++++++++++++++++++++++++++++++\n packfile.h | 20 ----------\n 5 files changed, 116 insertions(+), 113 deletions(-)\n\n-Peff\n"},{"id":"355576","messageId":"20180814181427.GA26919@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180814181358.GA26391@sigill.intra.peff.net","subject":"[PATCH 1/4] cat-file: use oidset check-and-insert","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T18:14:27Z","receivedAt":"2018-08-14T18:14:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We don't need to check if the oidset has our object before\nwe insert it; that's done as part of the insertion. We can\njust rely on the return value from oidset_insert(), which\nsaves one hash lookup per object.\n\nThis measurable speedup is tiny and within the run-to-run\nnoise, but the result is simpler to read, too.\n\nSigned-off-by: Jeff King \n---\n builtin/cat-file.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 45992c9be9..04b5cda191 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -443,9 +443,8 @@ static int batch_unordered_object(const struct object_id *oid, void *vdata)\n {\n \tstruct object_cb_data *data = vdata;\n \n-\tif (oidset_contains(data->seen, oid))\n+\tif (oidset_insert(data->seen, oid))\n \t\treturn 0;\n-\toidset_insert(data->seen, oid);\n \n \treturn batch_object_cb(oid, data);\n }\n-- \n2.18.0.1066.g0d97f3a098\n\n"},{"id":"355578","messageId":"20180814181806.GB26919@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180814181358.GA26391@sigill.intra.peff.net","subject":"[PATCH 2/4] cat-file: split batch \"buf\" into two variables","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T18:18:06Z","receivedAt":"2018-08-14T18:18:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We use the \"buf\" strbuf for two things: to read incoming\nlines, and as a scratch space for test-expanding the\nuser-provided format. Let's split this into two variables\nwith descriptive names, which makes their purpose and\nlifetime more clear.\n\nIt will also help in a future patch when we start using the\n\"output\" buffer for more expansions.\n\nSigned-off-by: Jeff King \n---\nRené, in the patch you sent earlier, I noticed that for the\nnon-batch-all-objects case we use the same strbuf for input and output.\nThat'd probably be OK most of the time (the first thing we do is resolve\nthe input to an oid), but I suspect it could be pretty bad with %(rest).\nWe'd write over or even realloc the string it points into as part of the\noutput.\n\nThis patch just clarifies the names; your reuse idea is in the next one.\n\n builtin/cat-file.c | 14 ++++++++------\n 1 file changed, 8 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 04b5cda191..3ed1d0be80 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -466,7 +466,8 @@ static int batch_unordered_packed(const struct object_id *oid,\n \n static int batch_objects(struct batch_options *opt)\n {\n-\tstruct strbuf buf = STRBUF_INIT;\n+\tstruct strbuf input = STRBUF_INIT;\n+\tstruct strbuf output = STRBUF_INIT;\n \tstruct expand_data data;\n \tint save_warning;\n \tint retval = 0;\n@@ -481,8 +482,9 @@ static int batch_objects(struct batch_options *opt)\n \t */\n \tmemset(&data, 0, sizeof(data));\n \tdata.mark_query = 1;\n-\tstrbuf_expand(&buf, opt->format, expand_format, &data);\n+\tstrbuf_expand(&output, opt->format, expand_format, &data);\n \tdata.mark_query = 0;\n+\tstrbuf_release(&output);\n \tif (opt->cmdmode)\n \t\tdata.split_on_whitespace = 1;\n \n@@ -542,14 +544,14 @@ static int batch_objects(struct batch_options *opt)\n \tsave_warning = warn_on_object_refname_ambiguity;\n \twarn_on_object_refname_ambiguity = 0;\n \n-\twhile (strbuf_getline(&buf, stdin) != EOF) {\n+\twhile (strbuf_getline(&input, stdin) != EOF) {\n \t\tif (data.split_on_whitespace) {\n \t\t\t/*\n \t\t\t * Split at first whitespace, tying off the beginning\n \t\t\t * of the string and saving the remainder (or NULL) in\n \t\t\t * data.rest.\n \t\t\t */\n-\t\t\tchar *p = strpbrk(buf.buf, \" \\t\");\n+\t\t\tchar *p = strpbrk(input.buf, \" \\t\");\n \t\t\tif (p) {\n \t\t\t\twhile (*p && strchr(\" \\t\", *p))\n \t\t\t\t\t*p++ = '\\0';\n@@ -557,10 +559,10 @@ static int batch_objects(struct batch_options *opt)\n \t\t\tdata.rest = p;\n \t\t}\n \n-\t\tbatch_one_object(buf.buf, opt, &data);\n+\t\tbatch_one_object(input.buf, opt, &data);\n \t}\n \n-\tstrbuf_release(&buf);\n+\tstrbuf_release(&input);\n \twarn_on_object_refname_ambiguity = save_warning;\n \treturn retval;\n }\n-- \n2.18.0.1066.g0d97f3a098\n\n"},{"id":"355581","messageId":"20180814182022.GC26919@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180814181358.GA26391@sigill.intra.peff.net","subject":"[PATCH 3/4] cat-file: use a single strbuf for all output","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T18:20:22Z","receivedAt":"2018-08-14T18:20:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we're in batch mode, we end up in batch_object_write()\nfor each object, which allocates its own strbuf for each\ncall. Instead, we can provide a single \"scratch\" buffer that\ngets reused for each output. When running:\n\n git cat-file --batch-all-objects --batch-check='%(objectname)'\n\non git.git, my best-of-five time drops from:\n\n real\t0m0.171s\n user\t0m0.159s\n sys\t0m0.012s\n\nto:\n\n real\t0m0.133s\n user\t0m0.121s\n sys\t0m0.012s\n\nNote that we could do this just by putting the \"scratch\"\npointer into \"struct expand_data\", but I chose instead to\nadd an extra parameter to the callstack. That's more\nverbose, but it makes it a bit more obvious what is going\non, which in turn makes it easy to see where we need to be\nreleasing the string in the caller (right after the loop\nwhich uses it in each case).\n\nBased-on-a-patch-by: René Scharfe \nSigned-off-by: Jeff King \n---\nIt also made it easy to see that without the prior patch,\nwe'd have been using \"buf\" for two parameters. :)\n\n builtin/cat-file.c | 28 +++++++++++++++++-----------\n 1 file changed, 17 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 3ed1d0be80..08dced2614 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -338,11 +338,11 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d\n \t}\n }\n \n-static void batch_object_write(const char *obj_name, struct batch_options *opt,\n+static void batch_object_write(const char *obj_name,\n+\t\t\t struct strbuf *scratch,\n+\t\t\t struct batch_options *opt,\n \t\t\t struct expand_data *data)\n {\n-\tstruct strbuf buf = STRBUF_INIT;\n-\n \tif (!data->skip_object_info &&\n \t oid_object_info_extended(the_repository, &data->oid, &data->info,\n \t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0) {\n@@ -352,10 +352,10 @@ static void batch_object_write(const char *obj_name, struct batch_options *opt,\n \t\treturn;\n \t}\n \n-\tstrbuf_expand(&buf, opt->format, expand_format, data);\n-\tstrbuf_addch(&buf, '\\n');\n-\tbatch_write(opt, buf.buf, buf.len);\n-\tstrbuf_release(&buf);\n+\tstrbuf_reset(scratch);\n+\tstrbuf_expand(scratch, opt->format, expand_format, data);\n+\tstrbuf_addch(scratch, '\\n');\n+\tbatch_write(opt, scratch->buf, scratch->len);\n \n \tif (opt->print_contents) {\n \t\tprint_object_or_die(opt, data);\n@@ -363,7 +363,9 @@ static void batch_object_write(const char *obj_name, struct batch_options *opt,\n \t}\n }\n \n-static void batch_one_object(const char *obj_name, struct batch_options *opt,\n+static void batch_one_object(const char *obj_name,\n+\t\t\t struct strbuf *scratch,\n+\t\t\t struct batch_options *opt,\n \t\t\t struct expand_data *data)\n {\n \tstruct object_context ctx;\n@@ -405,20 +407,21 @@ static void batch_one_object(const char *obj_name, struct batch_options *opt,\n \t\treturn;\n \t}\n \n-\tbatch_object_write(obj_name, opt, data);\n+\tbatch_object_write(obj_name, scratch, opt, data);\n }\n \n struct object_cb_data {\n \tstruct batch_options *opt;\n \tstruct expand_data *expand;\n \tstruct oidset *seen;\n+\tstruct strbuf *scratch;\n };\n \n static int batch_object_cb(const struct object_id *oid, void *vdata)\n {\n \tstruct object_cb_data *data = vdata;\n \toidcpy(&data->expand->oid, oid);\n-\tbatch_object_write(NULL, data->opt, data->expand);\n+\tbatch_object_write(NULL, data->scratch, data->opt, data->expand);\n \treturn 0;\n }\n \n@@ -509,6 +512,7 @@ static int batch_objects(struct batch_options *opt)\n \n \t\tcb.opt = opt;\n \t\tcb.expand = &data;\n+\t\tcb.scratch = &output;\n \n \t\tif (opt->unordered) {\n \t\t\tstruct oidset seen = OIDSET_INIT;\n@@ -531,6 +535,7 @@ static int batch_objects(struct batch_options *opt)\n \t\t\toid_array_clear(&sa);\n \t\t}\n \n+\t\tstrbuf_release(&output);\n \t\treturn 0;\n \t}\n \n@@ -559,10 +564,11 @@ static int batch_objects(struct batch_options *opt)\n \t\t\tdata.rest = p;\n \t\t}\n \n-\t\tbatch_one_object(input.buf, opt, &data);\n+\t\tbatch_one_object(input.buf, &output, opt, &data);\n \t}\n \n \tstrbuf_release(&input);\n+\tstrbuf_release(&output);\n \twarn_on_object_refname_ambiguity = save_warning;\n \treturn retval;\n }\n-- \n2.18.0.1066.g0d97f3a098\n\n"},{"id":"355582","messageId":"20180814182118.GD26919@sigill.intra.peff.net","threadId":"49097","inReplyTo":"20180814181358.GA26391@sigill.intra.peff.net","subject":"[PATCH 4/4] for_each_*_object: move declarations to object-store.h","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T18:21:18Z","receivedAt":"2018-08-14T18:21:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The for_each_loose_object() and for_each_packed_object()\nfunctions are meant to be part of a unified interface: they\nuse the same set of for_each_object_flags, and it's not\ninconceivable that we might one day add a single\nfor_each_object() wrapper around them.\n\nLet's put them together in a single file, so we can avoid\nawkwardness like saying \"the flags for this function are\nover in cache.h\". Moving the loose functions to packfile.h\nis silly. Moving the packed functions to cache.h works, but\nmakes the \"cache.h is a kitchen sink\" problem worse. The\nbest place is the recently-created object-store.h, since\nthese are quite obviously related to object storage.\n\nThe for_each_*_in_objdir() functions do not use the same\nflags, but they are logically part of the same interface as\nfor_each_loose_object(), and share callback signatures. So\nwe'll move those, as well, as they also make sense in\nobject-store.h.\n\nSigned-off-by: Jeff King \n---\nThis patch also happens to be a nice showcase for --color-moved.\n\n builtin/prune-packed.c | 1 +\n cache.h | 75 -----------------------------------\n object-store.h | 90 ++++++++++++++++++++++++++++++++++++++++++\n packfile.h | 20 ----------\n 4 files changed, 91 insertions(+), 95 deletions(-)\n\ndiff --git a/builtin/prune-packed.c b/builtin/prune-packed.c\nindex 4ff525e50f..a9e7b552b9 100644\n--- a/builtin/prune-packed.c\n+++ b/builtin/prune-packed.c\n@@ -3,6 +3,7 @@\n #include \"progress.h\"\n #include \"parse-options.h\"\n #include \"packfile.h\"\n+#include \"object-store.h\"\n \n static const char * const prune_packed_usage[] = {\n \tN_(\"git prune-packed [-n | --dry-run] [-q | --quiet]\"),\ndiff --git a/cache.h b/cache.h\nindex 6d14702df2..aee36afa54 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1575,81 +1575,6 @@ extern int odb_mkstemp(struct strbuf *temp_filename, const char *pattern);\n */\n extern int odb_pack_keep(const char *name);\n \n-/*\n- * Iterate over the files in the loose-object parts of the object\n- * directory \"path\", triggering the following callbacks:\n- *\n- * - loose_object is called for each loose object we find.\n- *\n- * - loose_cruft is called for any files that do not appear to be\n- * loose objects. Note that we only look in the loose object\n- * directories \"objects/[0-9a-f]{2}/\", so we will not report\n- * \"objects/foobar\" as cruft.\n- *\n- * - loose_subdir is called for each top-level hashed subdirectory\n- * of the object directory (e.g., \"$OBJDIR/f0\"). It is called\n- * after the objects in the directory are processed.\n- *\n- * Any callback that is NULL will be ignored. Callbacks returning non-zero\n- * will end the iteration.\n- *\n- * In the \"buf\" variant, \"path\" is a strbuf which will also be used as a\n- * scratch buffer, but restored to its original contents before\n- * the function returns.\n- */\n-typedef int each_loose_object_fn(const struct object_id *oid,\n-\t\t\t\t const char *path,\n-\t\t\t\t void *data);\n-typedef int each_loose_cruft_fn(const char *basename,\n-\t\t\t\tconst char *path,\n-\t\t\t\tvoid *data);\n-typedef int each_loose_subdir_fn(unsigned int nr,\n-\t\t\t\t const char *path,\n-\t\t\t\t void *data);\n-int for_each_file_in_obj_subdir(unsigned int subdir_nr,\n-\t\t\t\tstruct strbuf *path,\n-\t\t\t\teach_loose_object_fn obj_cb,\n-\t\t\t\teach_loose_cruft_fn cruft_cb,\n-\t\t\t\teach_loose_subdir_fn subdir_cb,\n-\t\t\t\tvoid *data);\n-int for_each_loose_file_in_objdir(const char *path,\n-\t\t\t\t each_loose_object_fn obj_cb,\n-\t\t\t\t each_loose_cruft_fn cruft_cb,\n-\t\t\t\t each_loose_subdir_fn subdir_cb,\n-\t\t\t\t void *data);\n-int for_each_loose_file_in_objdir_buf(struct strbuf *path,\n-\t\t\t\t each_loose_object_fn obj_cb,\n-\t\t\t\t each_loose_cruft_fn cruft_cb,\n-\t\t\t\t each_loose_subdir_fn subdir_cb,\n-\t\t\t\t void *data);\n-\n-/*\n- * Flags for for_each_*_object(), including for_each_loose below and\n- * for_each_packed in packfile.h.\n- */\n-enum for_each_object_flags {\n-\t/* Iterate only over local objects, not alternates. */\n-\tFOR_EACH_OBJECT_LOCAL_ONLY = (1<<0),\n-\n-\t/* Only iterate over packs obtained from the promisor remote. */\n-\tFOR_EACH_OBJECT_PROMISOR_ONLY = (1<<1),\n-\n-\t/*\n-\t * Visit objects within a pack in packfile order rather than .idx order\n-\t */\n-\tFOR_EACH_OBJECT_PACK_ORDER = (1<<2),\n-};\n-\n-/*\n- * Iterate over all accessible loose objects without respect to\n- * reachability. By default, this includes both local and alternate objects.\n- * The order in which objects are visited is unspecified.\n- *\n- * Any flags specific to packs are ignored.\n- */\n-int for_each_loose_object(each_loose_object_fn, void *,\n-\t\t\t enum for_each_object_flags flags);\n-\n /*\n * Set this to 0 to prevent sha1_object_info_extended() from fetching missing\n * blobs. This has a difference only if extensions.partialClone is set.\ndiff --git a/object-store.h b/object-store.h\nindex e481f7ad41..162156f5dc 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -262,4 +262,94 @@ int oid_object_info_extended(struct repository *r,\n \t\t\t const struct object_id *,\n \t\t\t struct object_info *, unsigned flags);\n \n+/*\n+ * Iterate over the files in the loose-object parts of the object\n+ * directory \"path\", triggering the following callbacks:\n+ *\n+ * - loose_object is called for each loose object we find.\n+ *\n+ * - loose_cruft is called for any files that do not appear to be\n+ * loose objects. Note that we only look in the loose object\n+ * directories \"objects/[0-9a-f]{2}/\", so we will not report\n+ * \"objects/foobar\" as cruft.\n+ *\n+ * - loose_subdir is called for each top-level hashed subdirectory\n+ * of the object directory (e.g., \"$OBJDIR/f0\"). It is called\n+ * after the objects in the directory are processed.\n+ *\n+ * Any callback that is NULL will be ignored. Callbacks returning non-zero\n+ * will end the iteration.\n+ *\n+ * In the \"buf\" variant, \"path\" is a strbuf which will also be used as a\n+ * scratch buffer, but restored to its original contents before\n+ * the function returns.\n+ */\n+typedef int each_loose_object_fn(const struct object_id *oid,\n+\t\t\t\t const char *path,\n+\t\t\t\t void *data);\n+typedef int each_loose_cruft_fn(const char *basename,\n+\t\t\t\tconst char *path,\n+\t\t\t\tvoid *data);\n+typedef int each_loose_subdir_fn(unsigned int nr,\n+\t\t\t\t const char *path,\n+\t\t\t\t void *data);\n+int for_each_file_in_obj_subdir(unsigned int subdir_nr,\n+\t\t\t\tstruct strbuf *path,\n+\t\t\t\teach_loose_object_fn obj_cb,\n+\t\t\t\teach_loose_cruft_fn cruft_cb,\n+\t\t\t\teach_loose_subdir_fn subdir_cb,\n+\t\t\t\tvoid *data);\n+int for_each_loose_file_in_objdir(const char *path,\n+\t\t\t\t each_loose_object_fn obj_cb,\n+\t\t\t\t each_loose_cruft_fn cruft_cb,\n+\t\t\t\t each_loose_subdir_fn subdir_cb,\n+\t\t\t\t void *data);\n+int for_each_loose_file_in_objdir_buf(struct strbuf *path,\n+\t\t\t\t each_loose_object_fn obj_cb,\n+\t\t\t\t each_loose_cruft_fn cruft_cb,\n+\t\t\t\t each_loose_subdir_fn subdir_cb,\n+\t\t\t\t void *data);\n+\n+/* Flags for for_each_*_object() below. */\n+enum for_each_object_flags {\n+\t/* Iterate only over local objects, not alternates. */\n+\tFOR_EACH_OBJECT_LOCAL_ONLY = (1<<0),\n+\n+\t/* Only iterate over packs obtained from the promisor remote. */\n+\tFOR_EACH_OBJECT_PROMISOR_ONLY = (1<<1),\n+\n+\t/*\n+\t * Visit objects within a pack in packfile order rather than .idx order\n+\t */\n+\tFOR_EACH_OBJECT_PACK_ORDER = (1<<2),\n+};\n+\n+/*\n+ * Iterate over all accessible loose objects without respect to\n+ * reachability. By default, this includes both local and alternate objects.\n+ * The order in which objects are visited is unspecified.\n+ *\n+ * Any flags specific to packs are ignored.\n+ */\n+int for_each_loose_object(each_loose_object_fn, void *,\n+\t\t\t enum for_each_object_flags flags);\n+\n+/*\n+ * Iterate over all accessible packed objects without respect to reachability.\n+ * By default, this includes both local and alternate packs.\n+ *\n+ * Note that some objects may appear twice if they are found in multiple packs.\n+ * Each pack is visited in an unspecified order. By default, objects within a\n+ * pack are visited in pack-idx order (i.e., sorted by oid).\n+ */\n+typedef int each_packed_object_fn(const struct object_id *oid,\n+\t\t\t\t struct packed_git *pack,\n+\t\t\t\t uint32_t pos,\n+\t\t\t\t void *data);\n+int for_each_object_in_pack(struct packed_git *p,\n+\t\t\t each_packed_object_fn, void *data,\n+\t\t\t enum for_each_object_flags flags);\n+int for_each_packed_object(each_packed_object_fn, void *,\n+\t\t\t enum for_each_object_flags flags);\n+\n #endif /* OBJECT_STORE_H */\ndiff --git a/packfile.h b/packfile.h\nindex 99411bdd85..d91e43fe73 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -148,26 +148,6 @@ extern int has_object_pack(const struct object_id *oid);\n \n extern int has_pack_index(const unsigned char *sha1);\n \n-/*\n- * Iterate over all accessible packed objects without respect to reachability.\n- * By default, this includes both local and alternate packs.\n- *\n- * Note that some objects may appear twice if they are found in multiple packs.\n- * Each pack is visited in an unspecified order. By default, objects within a\n- * pack are visited in pack-idx order (i.e., sorted by oid).\n- *\n- * The list of flags can be found in cache.h.\n- */\n-typedef int each_packed_object_fn(const struct object_id *oid,\n-\t\t\t\t struct packed_git *pack,\n-\t\t\t\t uint32_t pos,\n-\t\t\t\t void *data);\n-int for_each_object_in_pack(struct packed_git *p,\n-\t\t\t each_packed_object_fn, void *data,\n-\t\t\t enum for_each_object_flags flags);\n-int for_each_packed_object(each_packed_object_fn, void *,\n-\t\t\t enum for_each_object_flags flags);\n-\n /*\n * Return 1 if an object in a promisor packfile is or refers to the given\n * object, 0 otherwise.\n-- \n2.18.0.1066.g0d97f3a098\n"},{"id":"355599","messageId":"567deabf-cdd3-c4e3-bb6a-b593c1f87c6e@web.de","threadId":"49097","inReplyTo":"20180814182022.GC26919@sigill.intra.peff.net","subject":"Re: [PATCH 3/4] cat-file: use a single strbuf for all output","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-08-14T19:30:57Z","receivedAt":"2018-08-14T19:31:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 14.08.2018 um 20:20 schrieb Jeff King:\n> When we're in batch mode, we end up in batch_object_write()\n> for each object, which allocates its own strbuf for each\n> call. Instead, we can provide a single \"scratch\" buffer that\n> gets reused for each output. When running:\n> \n> git cat-file --batch-all-objects --batch-check='%(objectname)'\n> \n> on git.git, my best-of-five time drops from:\n> \n> real\t0m0.171s\n> user\t0m0.159s\n> sys\t0m0.012s\n> \n> to:\n> \n> real\t0m0.133s\n> user\t0m0.121s\n> sys\t0m0.012s\n> \n> Note that we could do this just by putting the \"scratch\"\n> pointer into \"struct expand_data\", but I chose instead to\n> add an extra parameter to the callstack. That's more\n> verbose, but it makes it a bit more obvious what is going\n> on, which in turn makes it easy to see where we need to be\n> releasing the string in the caller (right after the loop\n> which uses it in each case).\n> \n> Based-on-a-patch-by: René Scharfe \n> Signed-off-by: Jeff King \n> ---\n> It also made it easy to see that without the prior patch,\n> we'd have been using \"buf\" for two parameters. :)\n\nGood catch.\n\n> \n> builtin/cat-file.c | 28 +++++++++++++++++-----------\n> 1 file changed, 17 insertions(+), 11 deletions(-)\n> \n> diff --git a/builtin/cat-file.c b/builtin/cat-file.c\n> index 3ed1d0be80..08dced2614 100644\n> --- a/builtin/cat-file.c\n> +++ b/builtin/cat-file.c\n> @@ -338,11 +338,11 @@ static void print_object_or_die(struct batch_options *opt, struct expand_data *d\n> \t}\n> }\n> \n> -static void batch_object_write(const char *obj_name, struct batch_options *opt,\n> +static void batch_object_write(const char *obj_name,\n> +\t\t\t struct strbuf *scratch,\n> +\t\t\t struct batch_options *opt,\n> \t\t\t struct expand_data *data)\n> {\n> -\tstruct strbuf buf = STRBUF_INIT;\n\nWe could also avoid passing that buffer around by making it static. I\nshy away from adding static variables because the resulting code won't\nbe thread-safe, but that fear might be irrational, especially with\ncat-file.\n\n> -\n> \tif (!data->skip_object_info &&\n> \t oid_object_info_extended(the_repository, &data->oid, &data->info,\n> \t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0) {\n> @@ -352,10 +352,10 @@ static void batch_object_write(const char *obj_name, struct batch_options *opt,\n> \t\treturn;\n> \t}\n> \n> -\tstrbuf_expand(&buf, opt->format, expand_format, data);\n> -\tstrbuf_addch(&buf, '\\n');\n> -\tbatch_write(opt, buf.buf, buf.len);\n> -\tstrbuf_release(&buf);\n> +\tstrbuf_reset(scratch);\n> +\tstrbuf_expand(scratch, opt->format, expand_format, data);\n> +\tstrbuf_addch(scratch, '\\n');\n> +\tbatch_write(opt, scratch->buf, scratch->len);\n> \n> \tif (opt->print_contents) {\n> \t\tprint_object_or_die(opt, data);\n> @@ -363,7 +363,9 @@ static void batch_object_write(const char *obj_name, struct batch_options *opt,\n> \t}\n> }\n> \n> -static void batch_one_object(const char *obj_name, struct batch_options *opt,\n> +static void batch_one_object(const char *obj_name,\n> +\t\t\t struct strbuf *scratch,\n> +\t\t\t struct batch_options *opt,\n> \t\t\t struct expand_data *data)\n> {\n> \tstruct object_context ctx;\n> @@ -405,20 +407,21 @@ static void batch_one_object(const char *obj_name, struct batch_options *opt,\n> \t\treturn;\n> \t}\n> \n> -\tbatch_object_write(obj_name, opt, data);\n> +\tbatch_object_write(obj_name, scratch, opt, data);\n> }\n> \n> struct object_cb_data {\n> \tstruct batch_options *opt;\n> \tstruct expand_data *expand;\n> \tstruct oidset *seen;\n> +\tstruct strbuf *scratch;\n> };\n> \n> static int batch_object_cb(const struct object_id *oid, void *vdata)\n> {\n> \tstruct object_cb_data *data = vdata;\n> \toidcpy(&data->expand->oid, oid);\n> -\tbatch_object_write(NULL, data->opt, data->expand);\n> +\tbatch_object_write(NULL, data->scratch, data->opt, data->expand);\n> \treturn 0;\n> }\n> \n> @@ -509,6 +512,7 @@ static int batch_objects(struct batch_options *opt)\n> \n> \t\tcb.opt = opt;\n> \t\tcb.expand = &data;\n> +\t\tcb.scratch = &output;\n> \n> \t\tif (opt->unordered) {\n> \t\t\tstruct oidset seen = OIDSET_INIT;\n> @@ -531,6 +535,7 @@ static int batch_objects(struct batch_options *opt)\n> \t\t\toid_array_clear(&sa);\n> \t\t}\n> \n> +\t\tstrbuf_release(&output);\n> \t\treturn 0;\n> \t}\n> \n> @@ -559,10 +564,11 @@ static int batch_objects(struct batch_options *opt)\n> \t\t\tdata.rest = p;\n> \t\t}\n> \n> -\t\tbatch_one_object(input.buf, opt, &data);\n> +\t\tbatch_one_object(input.buf, &output, opt, &data);\n> \t}\n> \n> \tstrbuf_release(&input);\n> +\tstrbuf_release(&output);\n> \twarn_on_object_refname_ambiguity = save_warning;\n> \treturn retval;\n> }\n> \n"},{"id":"355601","messageId":"20180814193932.GD28452@sigill.intra.peff.net","threadId":"49097","inReplyTo":"567deabf-cdd3-c4e3-bb6a-b593c1f87c6e@web.de","subject":"Re: [PATCH 3/4] cat-file: use a single strbuf for all output","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-14T19:39:32Z","receivedAt":"2018-08-14T19:39:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Aug 14, 2018 at 09:30:57PM +0200, René Scharfe wrote:\n\n> > -static void batch_object_write(const char *obj_name, struct batch_options *opt,\n> > +static void batch_object_write(const char *obj_name,\n> > +\t\t\t struct strbuf *scratch,\n> > +\t\t\t struct batch_options *opt,\n> > \t\t\t struct expand_data *data)\n> > {\n> > -\tstruct strbuf buf = STRBUF_INIT;\n> \n> We could also avoid passing that buffer around by making it static. I\n> shy away from adding static variables because the resulting code won't\n> be thread-safe, but that fear might be irrational, especially with\n> cat-file.\n\nTrue, I didn't even think of that after your original got me in the\nmindset of passing the buffer down. It's not too bad to do it this way,\nand I agree with you that we are better avoiding static variables if we\ncan. Five years ago I might have said the opposite, but we've cleaned up\na lot of confusing hidden-static bits in that time. Let's not go in the\nopposite direction. :)\n\n-Peff\n"},{"id":"355685","messageId":"2ac79ea0-dd58-965d-1158-d08a7731e25d@gmail.com","threadId":"49097","inReplyTo":"20180810231549.GD19875@sigill.intra.peff.net","subject":"Re: [PATCH 4/7] for_each_packed_object: support iterating in pack-order","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-08-15T13:28:44Z","receivedAt":"2018-08-15T13:28:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/10/2018 7:15 PM, Jeff King wrote:\n> diff --git a/commit-graph.c b/commit-graph.c\n> index b0a55ad128..69a0d1c203 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -730,7 +730,7 @@ void write_commit_graph(const char *obj_dir,\n> \t\t\t\tdie(\"error adding pack %s\", packname.buf);\n> \t\t\tif (open_pack_index(p))\n> \t\t\t\tdie(\"error opening index for %s\", packname.buf);\n> -\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids);\n> +\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids, 0);\n> \t\t\tclose_pack(p);\n> \t\t}\n\nThis use in write_commit_graph() is actually a good candidate for \npack-order, since we are checking each object to see if it is a commit. \nThis is only used when running `git commit-graph write --stdin-packs`, \nwhich is how VFS for Git maintains the commit-graph.\n\nI have a note to run performance tests on this case and follow up with a \nchange on top of this series that adds the FOR_EACH_OBJECT_PACK_ORDER flag.\n\nThanks,\n\n-Stolee\n\n"},{"id":"355686","messageId":"fc30f98e-0aa0-89d3-ee32-3d86cc5b342a@gmail.com","threadId":"49097","inReplyTo":"20180810230729.GA19090@sigill.intra.peff.net","subject":"Re: [PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-08-15T14:05:04Z","receivedAt":"2018-08-15T14:05:09Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/10/2018 7:07 PM, Jeff King wrote:\n> The general idea is that accessing objects in packfile order is way\n> kinder to the delta base cache, and thus way more efficient. See patches\n> 4 and 7 in particular for discussion and numbers.\n>\n> I'm primarily interested in cat-file, so this series is focused there.\n> But there may be other callers of for_each_packed_object() who could\n> benefit. Most of the existing ones just care about getting the oid, so\n> they're better off as-is. It's possible the call in is_promisor_object()\n> could benefit, since it calls parse_object() on each entry it visits. I\n> didn't experiment with it.\n\nI like this series, and the follow-up. I could not find any problems \nwith it.\n\nOne thing that I realized while reading it is that the multi-pack-index \nis not integrated into the for_each_packed_object method. I was already \ngoing to work on some cleanups in that area [1][2].\n\nWhen using the new flag with the multi-pack-index, I expect that we will \nwant to load the pack-files that are covered by the multi-pack-index \n(simply, the 'packs' array) and use the same mechanism to traverse them \nin order. The only \"strange\" thing about this is that we would see \nduplicate objects when traversing the pack-files directly but not when \ntraversing the multi-pack-index (since it de-duplicates when indexing).\n\nI hope to have a series working on top of this series by end-of-week.\n\nThanks,\n\n-Stolee\n\n[1] \nhttps://public-inbox.org/git/CAPig+cTU--KrGcv4C_CwBZEuec4dgm_tJqL=CFWKT6vxxR016w@mail.gmail.com/\n\n     Re: [PATCH v4 04/23] multi-pack-index: add 'write' verb\n\n     (Recommends more user-friendly usage reporting in 'git \nmulti-pack-index')\n\n[2] \nhttps://public-inbox.org/git/20180814222846.GG142615@aiede.svl.corp.google.com/\n\n     [PATCH] partial-clone: render design doc using asciidoc\n\n     (The commit-graph and multi-pack-index docs are not in the \nMakefile, either.)\n\n"},{"id":"355857","messageId":"20180816173639.GB882@sigill.intra.peff.net","threadId":"49097","inReplyTo":"2ac79ea0-dd58-965d-1158-d08a7731e25d@gmail.com","subject":"Re: [PATCH 4/7] for_each_packed_object: support iterating in pack-order","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-16T17:36:39Z","receivedAt":"2018-08-16T17:36:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 15, 2018 at 09:28:44AM -0400, Derrick Stolee wrote:\n\n> On 8/10/2018 7:15 PM, Jeff King wrote:\n> > diff --git a/commit-graph.c b/commit-graph.c\n> > index b0a55ad128..69a0d1c203 100644\n> > --- a/commit-graph.c\n> > +++ b/commit-graph.c\n> > @@ -730,7 +730,7 @@ void write_commit_graph(const char *obj_dir,\n> > \t\t\t\tdie(\"error adding pack %s\", packname.buf);\n> > \t\t\tif (open_pack_index(p))\n> > \t\t\t\tdie(\"error opening index for %s\", packname.buf);\n> > -\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids);\n> > +\t\t\tfor_each_object_in_pack(p, add_packed_commits, &oids, 0);\n> > \t\t\tclose_pack(p);\n> > \t\t}\n> \n> This use in write_commit_graph() is actually a good candidate for\n> pack-order, since we are checking each object to see if it is a commit. This\n> is only used when running `git commit-graph write --stdin-packs`, which is\n> how VFS for Git maintains the commit-graph.\n> \n> I have a note to run performance tests on this case and follow up with a\n> change on top of this series that adds the FOR_EACH_OBJECT_PACK_ORDER flag.\n\nI doubt that it will show the dramatic improvement in CPU that I\nmentioned in my commit message, because most of that comes from more\nefficient use of the delta cache. But it's very rare for commits to be\ndeltas (usually it's just almost-twins due to cherry-picks and rebases).\n\nSo you may benefit from block cache efficiency on a cold-cache or on a\nsystem under memory pressure, but I wouldn't expect much change at all\nfor the warm-cache case.\n\nI doubt it will hurt, though; you'll pay for the revindex generation,\nbut that's probably not a big deal compared to walking all the objects.\n\nOne thing you _could_ do is stop walking through the pack when you see a\nnon-commit, since we stick all of the commits at the front. But that's\njust what the code happens to do, and not a strict promise. So I think\nit's a bad idea to rely on it (and in fact the delta-islands work under\ndiscussion elsewhere will break that assumption).\n\n-Peff\n"},{"id":"355859","messageId":"20180816173934.GC882@sigill.intra.peff.net","threadId":"49097","inReplyTo":"fc30f98e-0aa0-89d3-ee32-3d86cc5b342a@gmail.com","subject":"Re: [PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-16T17:39:34Z","receivedAt":"2018-08-16T17:39:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 15, 2018 at 10:05:04AM -0400, Derrick Stolee wrote:\n\n> One thing that I realized while reading it is that the multi-pack-index is\n> not integrated into the for_each_packed_object method. I was already going\n> to work on some cleanups in that area [1][2].\n> \n> When using the new flag with the multi-pack-index, I expect that we will\n> want to load the pack-files that are covered by the multi-pack-index\n> (simply, the 'packs' array) and use the same mechanism to traverse them in\n> order. The only \"strange\" thing about this is that we would see duplicate\n> objects when traversing the pack-files directly but not when traversing the\n> multi-pack-index (since it de-duplicates when indexing).\n\nI think that makes sense. We already see duplicates from\nfor_each_packed_object() when they're in multiple packs, and callers\njust need to be ready to deal with it (and depending on what you're\ndoing, you may actually _want_ the duplicates).\n\nThanks for thinking through the implications for other topics. I hadn't\neven considered how this would interact with midx.\n\n-Peff\n"},{"id":"355872","messageId":"xmqqmutmdu02.fsf@gitster-ct.c.googlers.com","threadId":"49097","inReplyTo":"20180816173934.GC882@sigill.intra.peff.net","subject":"Re: [PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-08-16T18:52:13Z","receivedAt":"2018-08-16T18:52:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I think that makes sense. We already see duplicates from\n> for_each_packed_object() when they're in multiple packs, and callers\n> just need to be ready to deal with it (and depending on what you're\n> doing, you may actually _want_ the duplicates).\n\nYou of course would also see dups between loose and packed until\nprune-packed is run. \n\nI also was thinking about the same thing after Derrick's response,\nbut unless you are very specialized caller, it does not allow you do\nvery much to learn that object X exists as a loose object locally,\nalso as a loose object in our alternate, and also in pack A, but not\nin other packs. You need a way to say \"Read the contents of object\nX from that place, not from any other place\", \"Remove that copy of\nobject X at that place, but not at any other place\" etc. to make\neffective use of that kind of information.\n\nThe codepath that implements runtime access has \"I found a copy\nhere, but it is unusable, so let's go on to look for another usable\ncopy\" fallback. This is a tangent but it is something we should not\nlose in the midx-enabled world.\n"},{"id":"355874","messageId":"20180816194537.GA5813@sigill.intra.peff.net","threadId":"49097","inReplyTo":"xmqqmutmdu02.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 0/7] speeding up cat-file by reordering object access","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-16T19:45:38Z","receivedAt":"2018-08-16T19:45:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 16, 2018 at 11:52:13AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I think that makes sense. We already see duplicates from\n> > for_each_packed_object() when they're in multiple packs, and callers\n> > just need to be ready to deal with it (and depending on what you're\n> > doing, you may actually _want_ the duplicates).\n> \n> You of course would also see dups between loose and packed until\n> prune-packed is run.\n\nYes, although there are two separate calls to look at those two sources,\nso it's a bit more obvious that the caller has to de-dup. I'm not\nopposed to a flag to ask the function to de-dup for us, but it really\nonly makes sense if we do a combined for_each_object() call.\nDe-duping is potentially expensive, and there's little point in\nde-duping the packs if we have to then de-dup the result with the loose\nobjects.\n\nOne benefit of having the iterator function de-dup is that it _could_ be\ndone more efficiently. Right now, even before my recent patches the\ncat-file de-dup happens by creating a secondary list, sorting it, and\nthen skipping the duplicates.\n\nBut if a function knew _all_ of the sources we were going to look at\n(any loose directories, including alternates, and all available packs),\nand it could walk each individual source in sorted order (easy for packs\nby .idx, not too bad for loose by sorting the readdir() results), then\nwe could do it as an online list-merge, with a single walk through the\nresults.\n\nIn practice I don't know if it's worth the effort. If you're accessing\nthe object contents, sorted order really is bad. And if you're just\ncollecting the hashes, then you're likely generating some data structure\nfor future lookups, and you can just de-dup as part of that process.\n\n> I also was thinking about the same thing after Derrick's response,\n> but unless you are very specialized caller, it does not allow you do\n> very much to learn that object X exists as a loose object locally,\n> also as a loose object in our alternate, and also in pack A, but not\n> in other packs. You need a way to say \"Read the contents of object\n> X from that place, not from any other place\", \"Remove that copy of\n> object X at that place, but not at any other place\" etc. to make\n> effective use of that kind of information.\n\nWe do have those functions, and use them. E.g., fsck uses\nread_loose_object() to actually check that particular copy of the\nobject. That's obviously a specialized caller as you note, but then\nanybody iterating over all of the objects is pretty specialized already.\n\n> The codepath that implements runtime access has \"I found a copy\n> here, but it is unusable, so let's go on to look for another usable\n> copy\" fallback. This is a tangent but it is something we should not\n> lose in the midx-enabled world.\n\nYeah, good catch. That's orthogonal to most of this discussion, I think,\nbut it's a possible downside of the midx because it has literally\ndiscarded those duplicate index entries (or at least that's my\nunderstanding). If we kept the .idx for each pack as a fallback for\nolder Gits, then it's easy to solve: in the unlikely case the\n.midx-referenced copy fails, you look in each individual pack for\nanother copy.\n\nBut I think eventually you'd want to stop generating those .idx files,\ntoo, if you know that you'll only use a modern version of Git. I wonder\nif the .midx format should have an extension for \"here are all the\nduplicates I found\". They could even be part of the main index (it's\neasy enough for a binary-search lookup to always point to the start of a\nrun of duplicates), but if you had a ton of duplicates they would slow\nyour binary searches a little.\n\nI'll leave all that to Stolee to ponder. :)\n\n-Peff\n"}]}