{"thread":{"id":"53887","subject":"[PATCH 0/2] Prefetch objects in pack-objects","startedAt":"2020-07-21T00:21:57Z","lastAt":"2020-07-22T21:45:51Z","messageCount":13,"participants":["Jonathan Tan","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"401794","messageId":"cover.1595290841.git.jonathantanmy@google.com","threadId":"53887","inReplyTo":null,"subject":"[PATCH 0/2] Prefetch objects in pack-objects","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T00:21:42Z","receivedAt":"2020-07-21T00:21:57Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Patch 1 is refactoring, and patch 2 is the main patch which introduces\nthe feature.\n\nJonathan Tan (2):\n pack-objects: refactor to oid_object_info_extended\n pack-objects: prefetch objects to be packed\n\n builtin/pack-objects.c | 40 ++++++++++++++++++++++++++++++++++++----\n t/t5300-pack-object.sh | 36 ++++++++++++++++++++++++++++++++++++\n 2 files changed, 72 insertions(+), 4 deletions(-)\n\n-- \n2.28.0.rc0.105.gf9edc3c819-goog\n\n"},{"id":"401796","messageId":"b87764b711621ea3c614dbc8f9e49a8598a25cb1.1595290841.git.jonathantanmy@google.com","threadId":"53887","inReplyTo":"cover.1595290841.git.jonathantanmy@google.com","subject":"[PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T00:21:44Z","receivedAt":"2020-07-21T00:21:59Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"When an object to be packed is noticed to be missing, prefetch all\nto-be-packed objects in one batch.\n\nSigned-off-by: Jonathan Tan \n---\nThere have been recent discussions about using QUICK whenever we use\nSKIP_FETCH_OBJECT. I don't think it fully applies here, since here we\nfully expect the object to be present in the non-partial-clone case.\nHaving said that, I wouldn't be opposed to adding QUICK and then, if the\nobject read fails and if the repo is not a partial clone, to retry the\nobject load (before setting the type to -1).\n---\n builtin/pack-objects.c | 36 ++++++++++++++++++++++++++++++++----\n t/t5300-pack-object.sh | 36 ++++++++++++++++++++++++++++++++++++\n 2 files changed, 68 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e09d140eed..ecef5cda44 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -35,6 +35,7 @@\n #include \"midx.h\"\n #include \"trace2.h\"\n #include \"shallow.h\"\n+#include \"promisor-remote.h\"\n \n #define IN_PACK(obj) oe_in_pack(&to_pack, obj)\n #define SIZE(obj) oe_size(&to_pack, obj)\n@@ -1704,7 +1705,26 @@ static int can_reuse_delta(const struct object_id *base_oid,\n \treturn 0;\n }\n \n-static void check_object(struct object_entry *entry)\n+static void prefetch_to_pack(uint32_t object_index_start) {\n+\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n+\tuint32_t i;\n+\n+\tfor (i = object_index_start; i < to_pack.nr_objects; i++) {\n+\t\tstruct object_entry *entry = to_pack.objects + i;\n+\n+\t\tif (!oid_object_info_extended(the_repository,\n+\t\t\t\t\t &entry->idx.oid,\n+\t\t\t\t\t NULL,\n+\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH))\n+\t\t\tcontinue;\n+\t\toid_array_append(&to_fetch, &entry->idx.oid);\n+\t}\n+\tpromisor_remote_get_direct(the_repository,\n+\t\t\t\t to_fetch.oid, to_fetch.nr);\n+\toid_array_clear(&to_fetch);\n+}\n+\n+static void check_object(struct object_entry *entry, uint32_t object_index)\n {\n \tunsigned long canonical_size;\n \tenum object_type type;\n@@ -1843,8 +1863,16 @@ static void check_object(struct object_entry *entry)\n \t}\n \n \tif (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,\n-\t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0)\n-\t\ttype = -1;\n+\t\t\t\t OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0) {\n+\t\tif (has_promisor_remote()) {\n+\t\t\tprefetch_to_pack(object_index);\n+\t\t\tif (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,\n+\t\t\t\t\t\t OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0)\n+\t\t\t\ttype = -1;\n+\t\t} else {\n+\t\t\ttype = -1;\n+\t\t}\n+\t}\n \toe_set_type(entry, type);\n \tif (entry->type_valid) {\n \t\tSET_SIZE(entry, canonical_size);\n@@ -2065,7 +2093,7 @@ static void get_object_details(void)\n \n \tfor (i = 0; i < to_pack.nr_objects; i++) {\n \t\tstruct object_entry *entry = sorted_by_offset[i];\n-\t\tcheck_object(entry);\n+\t\tcheck_object(entry, i);\n \t\tif (entry->type_valid &&\n \t\t oe_size_greater_than(&to_pack, entry, big_file_threshold))\n \t\t\tentry->no_try_delta = 1;\ndiff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\nindex 746cdb626e..d553d0ca46 100755\n--- a/t/t5300-pack-object.sh\n+++ b/t/t5300-pack-object.sh\n@@ -497,4 +497,40 @@ test_expect_success 'make sure index-pack detects the SHA1 collision (large blob\n \t)\n '\n \n+test_expect_success 'prefetch objects' '\n+\trm -rf server client &&\n+\n+\tgit init server &&\n+\ttest_config -C server uploadpack.allowanysha1inwant 1 &&\n+\ttest_config -C server uploadpack.allowfilter 1 &&\n+\ttest_config -C server protocol.version 2 &&\n+\n+\techo one >server/one &&\n+\tgit -C server add one &&\n+\tgit -C server commit -m one &&\n+\tgit -C server branch one_branch &&\n+\n+\techo two_a >server/two_a &&\n+\techo two_b >server/two_b &&\n+\tgit -C server add two_a two_b &&\n+\tgit -C server commit -m two &&\n+\n+\techo three >server/three &&\n+\tgit -C server add three &&\n+\tgit -C server commit -m three &&\n+\tgit -C server branch three_branch &&\n+\n+\t# Clone, fetch \"two\" with blobs excluded, and re-push it. This requires\n+\t# the client to have the blobs of \"two\" - verify that these are\n+\t# prefetched in one batch.\n+\tgit clone --filter=blob:none --single-branch -b one_branch \\\n+\t\t\"file://$(pwd)/server\" client &&\n+\ttest_config -C client protocol.version 2 &&\n+\tTWO=$(git -C server rev-parse three_branch^) &&\n+\tgit -C client fetch --filter=blob:none origin \"$TWO\" &&\n+\tGIT_TRACE_PACKET=$(pwd)/trace git -C client push origin \"$TWO\":refs/heads/two_branch &&\n+\tgrep \"git> done\" trace >donelines &&\n+\ttest_line_count = 1 donelines\n+'\n+\n test_done\n-- \n2.28.0.rc0.105.gf9edc3c819-goog\n\n"},{"id":"401795","messageId":"1c32a00601b0cb3c48807d56fb34b10df5373e81.1595290841.git.jonathantanmy@google.com","threadId":"53887","inReplyTo":"cover.1595290841.git.jonathantanmy@google.com","subject":"[PATCH 1/2] pack-objects: refactor to oid_object_info_extended","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T00:21:43Z","receivedAt":"2020-07-21T00:22:00Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Use oid_object_info_extended() instead of oid_object_info() because a\nsubsequent commit needs to specify an additional flag here.\n\nSigned-off-by: Jonathan Tan \n---\n builtin/pack-objects.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 7016b28485..e09d140eed 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1707,6 +1707,8 @@ static int can_reuse_delta(const struct object_id *base_oid,\n static void check_object(struct object_entry *entry)\n {\n \tunsigned long canonical_size;\n+\tenum object_type type;\n+\tstruct object_info oi = {.typep = &type, .sizep = &canonical_size};\n \n \tif (IN_PACK(entry)) {\n \t\tstruct packed_git *p = IN_PACK(entry);\n@@ -1840,8 +1842,10 @@ static void check_object(struct object_entry *entry)\n \t\tunuse_pack(&w_curs);\n \t}\n \n-\toe_set_type(entry,\n-\t\t oid_object_info(the_repository, &entry->idx.oid, &canonical_size));\n+\tif (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,\n+\t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0)\n+\t\ttype = -1;\n+\toe_set_type(entry, type);\n \tif (entry->type_valid) {\n \t\tSET_SIZE(entry, canonical_size);\n \t} else {\n-- \n2.28.0.rc0.105.gf9edc3c819-goog\n\n"},{"id":"401800","messageId":"xmqqd04p8ywt.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"b87764b711621ea3c614dbc8f9e49a8598a25cb1.1595290841.git.jonathantanmy@google.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-21T01:00:50Z","receivedAt":"2020-07-21T01:00:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> When an object to be packed is noticed to be missing, prefetch all\n> to-be-packed objects in one batch.\n>\n> Signed-off-by: Jonathan Tan \n> ---\n\nHmph, the resulting codeflow structure feels somewhat iffy. Perhaps\nI am not reading the code correctly, but\n\n * There is a loop that scans from 0..to_pack.nr_objects and calls\n check_object() for each and every one of them;\n\n * The called check_object(), when it notices that a missing and\n promised (i.e. to be lazily fetched) object is in the to_pack\n array, asks prefetch_to_pack() to scan from that point to the end\n of that array and grabs all of them that are missing.\n\nIt almost feels a lot cleaner to see what is going on in the\nresulting code, instead of the way the new \"loop\" was added, if a\nnew loop is added _before_ the loop to call check_object() on all\nobjects in to_pack array as a pre-processing phase when there is a\npromisor remote. That is, after reverting all the change this patch\nmakes to check_object(), add a new loop in get_object_details() that\nlooks more or less like so:\n\n\tQSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);\n\n+\tif (has_promisor_remote())\n+\t\tprefetch_to_pack(0);\n+\n\tfor (i = 0; i < to_pack.nr_objects; i++) {\n\n\nWas the patch done this way because scanning the entire array twice\nis expensive? The optimization makes sense to me if certain\nconditions are met, like...\n\n - Most of the time there is no missing object due to promisor, even\n if has_promissor_to_remote() is true;\n\n - When there are missing objects due to promisor, pack_offset_sort\n will keep them near the end of the array; and\n\n - Given the oid, oid_object_info_extended() on it with\n OBJECT_INFO_FOR_PREFETCH is expensive.\n\nOnly when all these conditions are met, it would avoid unnecessary\noverhead by scanning only a very later part of the array by delaying\nthe point in the array where prefetch_to_pack() starts scanning.\n\nThanks.\n\n> There have been recent discussions about using QUICK whenever we use\n> SKIP_FETCH_OBJECT. I don't think it fully applies here, since here we\n> fully expect the object to be present in the non-partial-clone case.\n> Having said that, I wouldn't be opposed to adding QUICK and then, if the\n> object read fails and if the repo is not a partial clone, to retry the\n> object load (before setting the type to -1).\n> ---\n> builtin/pack-objects.c | 36 ++++++++++++++++++++++++++++++++----\n> t/t5300-pack-object.sh | 36 ++++++++++++++++++++++++++++++++++++\n> 2 files changed, 68 insertions(+), 4 deletions(-)\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index e09d140eed..ecef5cda44 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n> @@ -35,6 +35,7 @@\n> #include \"midx.h\"\n> #include \"trace2.h\"\n> #include \"shallow.h\"\n> +#include \"promisor-remote.h\"\n> \n> #define IN_PACK(obj) oe_in_pack(&to_pack, obj)\n> #define SIZE(obj) oe_size(&to_pack, obj)\n> @@ -1704,7 +1705,26 @@ static int can_reuse_delta(const struct object_id *base_oid,\n> \treturn 0;\n> }\n> \n> -static void check_object(struct object_entry *entry)\n> +static void prefetch_to_pack(uint32_t object_index_start) {\n> +\tstruct oid_array to_fetch = OID_ARRAY_INIT;\n> +\tuint32_t i;\n> +\n> +\tfor (i = object_index_start; i < to_pack.nr_objects; i++) {\n> +\t\tstruct object_entry *entry = to_pack.objects + i;\n> +\n> +\t\tif (!oid_object_info_extended(the_repository,\n> +\t\t\t\t\t &entry->idx.oid,\n> +\t\t\t\t\t NULL,\n> +\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH))\n> +\t\t\tcontinue;\n> +\t\toid_array_append(&to_fetch, &entry->idx.oid);\n> +\t}\n> +\tpromisor_remote_get_direct(the_repository,\n> +\t\t\t\t to_fetch.oid, to_fetch.nr);\n> +\toid_array_clear(&to_fetch);\n> +}\n> +\n> +static void check_object(struct object_entry *entry, uint32_t object_index)\n> {\n> \tunsigned long canonical_size;\n> \tenum object_type type;\n> @@ -1843,8 +1863,16 @@ static void check_object(struct object_entry *entry)\n> \t}\n> \n> \tif (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,\n> -\t\t\t\t OBJECT_INFO_LOOKUP_REPLACE) < 0)\n> -\t\ttype = -1;\n> +\t\t\t\t OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0) {\n> +\t\tif (has_promisor_remote()) {\n> +\t\t\tprefetch_to_pack(object_index);\n> +\t\t\tif (oid_object_info_extended(the_repository, &entry->idx.oid, &oi,\n> +\t\t\t\t\t\t OBJECT_INFO_SKIP_FETCH_OBJECT | OBJECT_INFO_LOOKUP_REPLACE) < 0)\n> +\t\t\t\ttype = -1;\n> +\t\t} else {\n> +\t\t\ttype = -1;\n> +\t\t}\n> +\t}\n> \toe_set_type(entry, type);\n> \tif (entry->type_valid) {\n> \t\tSET_SIZE(entry, canonical_size);\n> @@ -2065,7 +2093,7 @@ static void get_object_details(void)\n> \n> \tfor (i = 0; i < to_pack.nr_objects; i++) {\n> \t\tstruct object_entry *entry = sorted_by_offset[i];\n> -\t\tcheck_object(entry);\n> +\t\tcheck_object(entry, i);\n> \t\tif (entry->type_valid &&\n> \t\t oe_size_greater_than(&to_pack, entry, big_file_threshold))\n> \t\t\tentry->no_try_delta = 1;\n> diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\n> index 746cdb626e..d553d0ca46 100755\n> --- a/t/t5300-pack-object.sh\n> +++ b/t/t5300-pack-object.sh\n> @@ -497,4 +497,40 @@ test_expect_success 'make sure index-pack detects the SHA1 collision (large blob\n> \t)\n> '\n> \n> +test_expect_success 'prefetch objects' '\n> +\trm -rf server client &&\n> +\n> +\tgit init server &&\n> +\ttest_config -C server uploadpack.allowanysha1inwant 1 &&\n> +\ttest_config -C server uploadpack.allowfilter 1 &&\n> +\ttest_config -C server protocol.version 2 &&\n> +\n> +\techo one >server/one &&\n> +\tgit -C server add one &&\n> +\tgit -C server commit -m one &&\n> +\tgit -C server branch one_branch &&\n> +\n> +\techo two_a >server/two_a &&\n> +\techo two_b >server/two_b &&\n> +\tgit -C server add two_a two_b &&\n> +\tgit -C server commit -m two &&\n> +\n> +\techo three >server/three &&\n> +\tgit -C server add three &&\n> +\tgit -C server commit -m three &&\n> +\tgit -C server branch three_branch &&\n> +\n> +\t# Clone, fetch \"two\" with blobs excluded, and re-push it. This requires\n> +\t# the client to have the blobs of \"two\" - verify that these are\n> +\t# prefetched in one batch.\n> +\tgit clone --filter=blob:none --single-branch -b one_branch \\\n> +\t\t\"file://$(pwd)/server\" client &&\n> +\ttest_config -C client protocol.version 2 &&\n> +\tTWO=$(git -C server rev-parse three_branch^) &&\n> +\tgit -C client fetch --filter=blob:none origin \"$TWO\" &&\n> +\tGIT_TRACE_PACKET=$(pwd)/trace git -C client push origin \"$TWO\":refs/heads/two_branch &&\n> +\tgrep \"git> done\" trace >donelines &&\n> +\ttest_line_count = 1 donelines\n> +'\n> +\n> test_done\n"},{"id":"401811","messageId":"20200721163736.69610-1-jonathantanmy@google.com","threadId":"53887","inReplyTo":"xmqqd04p8ywt.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T16:37:36Z","receivedAt":"2020-07-21T16:37:41Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Hmph, the resulting codeflow structure feels somewhat iffy. Perhaps\n> I am not reading the code correctly, but\n> \n> * There is a loop that scans from 0..to_pack.nr_objects and calls\n> check_object() for each and every one of them;\n> \n> * The called check_object(), when it notices that a missing and\n> promised (i.e. to be lazily fetched) object is in the to_pack\n> array, asks prefetch_to_pack() to scan from that point to the end\n> of that array and grabs all of them that are missing.\n> \n> It almost feels a lot cleaner to see what is going on in the\n> resulting code, instead of the way the new \"loop\" was added, if a\n> new loop is added _before_ the loop to call check_object() on all\n> objects in to_pack array as a pre-processing phase when there is a\n> promisor remote. That is, after reverting all the change this patch\n> makes to check_object(), add a new loop in get_object_details() that\n> looks more or less like so:\n> \n> \tQSORT(sorted_by_offset, to_pack.nr_objects, pack_offset_sort);\n> \n> +\tif (has_promisor_remote())\n> +\t\tprefetch_to_pack(0);\n> +\n> \tfor (i = 0; i < to_pack.nr_objects; i++) {\n> \n> \n> Was the patch done this way because scanning the entire array twice\n> is expensive?\n\nYes. If we called prefetch_to_pack(0) first (as you suggest), this first\nscan involves checking the existence of all objects in the array, so I\nthought it would be expensive. (Checking the existence of an object\nprobably brings the corresponding pack index into disk cache on\nplatforms like Linux, so 2 object reads might not take much more time\nthan 1 object read, but I didn't want to rely on this when I could just\navoid the extra read.)\n\n> The optimization makes sense to me if certain\n> conditions are met, like...\n> \n> - Most of the time there is no missing object due to promisor, even\n> if has_promissor_to_remote() is true;\n\nI think that optimizing for this condition makes sense - most pushes (I\nwould think) are pushes of objects we create locally, and thus no\nobjects are missing.\n\n> - When there are missing objects due to promisor, pack_offset_sort\n> will keep them near the end of the array; and\n> \n> - Given the oid, oid_object_info_extended() on it with\n> OBJECT_INFO_FOR_PREFETCH is expensive.\n\nI see this as expensive since it involves checking of object existence.\n\n> Only when all these conditions are met, it would avoid unnecessary\n> overhead by scanning only a very later part of the array by delaying\n> the point in the array where prefetch_to_pack() starts scanning.\n\nYes (and when there are no missing objects at all, there is no\ndouble-scanning).\n"},{"id":"401816","messageId":"xmqq5zag8yg5.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"20200721163736.69610-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-21T19:23:06Z","receivedAt":"2020-07-21T19:23:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n>> +\tif (has_promisor_remote())\n>> +\t\tprefetch_to_pack(0);\n>> +\n>> \tfor (i = 0; i < to_pack.nr_objects; i++) {\n>> \n>> \n>> Was the patch done this way because scanning the entire array twice\n>> is expensive?\n>\n> Yes. If we called prefetch_to_pack(0) first (as you suggest), this first\n> scan involves checking the existence of all objects in the array, so I\n> thought it would be expensive. (Checking the existence of an object\n> probably brings the corresponding pack index into disk cache on\n> platforms like Linux, so 2 object reads might not take much more time\n> than 1 object read, but I didn't want to rely on this when I could just\n> avoid the extra read.)\n>\n>> The optimization makes sense to me if certain\n>> conditions are met, like...\n>> \n>> - Most of the time there is no missing object due to promisor, even\n>> if has_promissor_to_remote() is true;\n>\n> I think that optimizing for this condition makes sense - most pushes (I\n> would think) are pushes of objects we create locally, and thus no\n> objects are missing.\n>\n>> - When there are missing objects due to promisor, pack_offset_sort\n>> will keep them near the end of the array; and\n\nI do not see this one got answered, but it is crucial if you want to\nargue that the \"lazy decision to prefetch at the last moment\" is a\ngood optimization. If an object in the early part of to_pack array\nis missing, you'd end up doing the same amount of work as the\nsimpler \"if promissor is there, prefetch what is missing\".\n\n>> - Given the oid, oid_object_info_extended() on it with\n>> OBJECT_INFO_FOR_PREFETCH is expensive.\n>\n> I see this as expensive since it involves checking of object existence.\n\nBut doesn't the \"prefetch before starting the main loop\" change the\nequation? If we prefetch, we can mark the objects to be prefetched\nin prefetch_to_pack() so that the main loop do not even have to\ncheck, so the non-lazy loop taken outside the check_object() and\nplaced before the main loop would have to run .nr_objects times, in\naddition to the main loop that runs .nr_objects times, but you won't\nhave to call oid_object_info_extended() twice on the same object?\n\n>> Only when all these conditions are met, it would avoid unnecessary\n>> overhead by scanning only a very later part of the array by delaying\n>> the point in the array where prefetch_to_pack() starts scanning.\n>\n> Yes (and when there are no missing objects at all, there is no\n> double-scanning).\n\nIn any case, the design choice needs to be justified in the log\nmessage. I am not sure if the lazy decision to prefetch at the last\nmoment is really worth the code smell. Perhaps it is, if there is a\nreason to believe that it would save extra work compared to the more\nnaive \"if we have promissor remote, prefetch what is missing\", but I\ndo not think I've heard that reason yet.\n\nThanks.\n"},{"id":"401827","messageId":"xmqqh7u07e41.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"xmqq5zag8yg5.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-21T21:27:42Z","receivedAt":"2020-07-21T21:27:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>>> The optimization makes sense to me if certain\n>>> conditions are met, like...\n>>> \n>>> - Most of the time there is no missing object due to promisor, even\n>>> if has_promissor_to_remote() is true;\n>>\n>> I think that optimizing for this condition makes sense - most pushes (I\n>> would think) are pushes of objects we create locally, and thus no\n>> objects are missing.\n\nAnother simple thing I missed. Why do we specifically refer to\n\"push\" here? Is this codepath in pack-objects not used or less\noften used by upload-pack (which is what serves \"fetch\")? \n\nI just wanted to make sure that we are not optimizing for \"push\",\ntrading efficiency for \"fetch\" off.\n\nThanks.\n"},{"id":"401831","messageId":"20200721232036.1358644-1-jonathantanmy@google.com","threadId":"53887","inReplyTo":"xmqq5zag8yg5.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T23:20:36Z","receivedAt":"2020-07-21T23:20:41Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Jonathan Tan writes:\n> \n> >> +\tif (has_promisor_remote())\n> >> +\t\tprefetch_to_pack(0);\n> >> +\n> >> \tfor (i = 0; i < to_pack.nr_objects; i++) {\n> >> \n> >> \n> >> Was the patch done this way because scanning the entire array twice\n> >> is expensive?\n> >\n> > Yes. If we called prefetch_to_pack(0) first (as you suggest), this first\n> > scan involves checking the existence of all objects in the array, so I\n> > thought it would be expensive. (Checking the existence of an object\n> > probably brings the corresponding pack index into disk cache on\n> > platforms like Linux, so 2 object reads might not take much more time\n> > than 1 object read, but I didn't want to rely on this when I could just\n> > avoid the extra read.)\n> >\n> >> The optimization makes sense to me if certain\n> >> conditions are met, like...\n> >> \n> >> - Most of the time there is no missing object due to promisor, even\n> >> if has_promissor_to_remote() is true;\n> >\n> > I think that optimizing for this condition makes sense - most pushes (I\n> > would think) are pushes of objects we create locally, and thus no\n> > objects are missing.\n> >\n> >> - When there are missing objects due to promisor, pack_offset_sort\n> >> will keep them near the end of the array; and\n> \n> I do not see this one got answered, but it is crucial if you want to\n> argue that the \"lazy decision to prefetch at the last moment\" is a\n> good optimization. If an object in the early part of to_pack array\n> is missing, you'd end up doing the same amount of work as the\n> simpler \"if promissor is there, prefetch what is missing\".\n\nMy argument is that typically *no* objects are missing, so we should\ndelay the prefetch as much as possible in the hope that we don't need it\nat all. I admit that if some objects are missing, I don't know where\nthey will be in the to_pack list.\n\n> >> - Given the oid, oid_object_info_extended() on it with\n> >> OBJECT_INFO_FOR_PREFETCH is expensive.\n> >\n> > I see this as expensive since it involves checking of object existence.\n> \n> But doesn't the \"prefetch before starting the main loop\" change the\n> equation? If we prefetch, we can mark the objects to be prefetched\n> in prefetch_to_pack() so that the main loop do not even have to\n> check, so the non-lazy loop taken outside the check_object() and\n> placed before the main loop would have to run .nr_objects times, in\n> addition to the main loop that runs .nr_objects times, but you won't\n> have to call oid_object_info_extended() twice on the same object?\n\nThe main loop (in get_object_details()) calls check_object() for each\niteration, and check_object() calls oid_object_info_extended()\n(oid_object_info() before patch 1 of this series) in order to get the\nobject's type. I don't see how the prefetch oid_object_info_extended()\n(in order to check existence) would eliminate the need for the main-loop\noid_object_info_extended() (which obtains the object type), unless we\nrecord the type somewhere during the prefetch - but that would make\nthings more complicated than they are now, I think.\n\n> >> Only when all these conditions are met, it would avoid unnecessary\n> >> overhead by scanning only a very later part of the array by delaying\n> >> the point in the array where prefetch_to_pack() starts scanning.\n> >\n> > Yes (and when there are no missing objects at all, there is no\n> > double-scanning).\n> \n> In any case, the design choice needs to be justified in the log\n> message. I am not sure if the lazy decision to prefetch at the last\n> moment is really worth the code smell. Perhaps it is, if there is a\n> reason to believe that it would save extra work compared to the more\n> naive \"if we have promissor remote, prefetch what is missing\", but I\n> do not think I've heard that reason yet.\n\nI still think that there is a reason (the extra existence check), but if\nwe think that the extra existence check is fast enough (compared to the\nother operations in pack-objects) or that there is a way to avoid\ncalling oid_object_info_extended() twice for the same object (even with\nmoving the prefetch loop to the beginning), then I agree that we don't\nneed the lazy decision. (Or if we want to write the simpler code now and\nonly improve the performance if we need it later, that's fine with me\ntoo.)\n"},{"id":"401835","messageId":"20200721233707.1363438-1-jonathantanmy@google.com","threadId":"53887","inReplyTo":"xmqqh7u07e41.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-21T23:37:07Z","receivedAt":"2020-07-21T23:42:48Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Junio C Hamano writes:\n> \n> >>> The optimization makes sense to me if certain\n> >>> conditions are met, like...\n> >>> \n> >>> - Most of the time there is no missing object due to promisor, even\n> >>> if has_promissor_to_remote() is true;\n> >>\n> >> I think that optimizing for this condition makes sense - most pushes (I\n> >> would think) are pushes of objects we create locally, and thus no\n> >> objects are missing.\n> \n> Another simple thing I missed. Why do we specifically refer to\n> \"push\" here? Is this codepath in pack-objects not used or less\n> often used by upload-pack (which is what serves \"fetch\")? \n> \n> I just wanted to make sure that we are not optimizing for \"push\",\n> trading efficiency for \"fetch\" off.\n\nAh...that's true. For \"fetch\" I think it's less important because the\nmultiple roundtrips of the pack negotiation means that the packfiles are\nusually more specific, but this optimization will help \"fetch\" too. I\ndon't think we're optimizing at the expense of \"fetch\" - any\nimprovements should benefit both similarly.\n"},{"id":"401837","messageId":"xmqqzh7s5sv4.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"20200721232036.1358644-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-21T23:51:59Z","receivedAt":"2020-07-21T23:52:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> My argument is that typically *no* objects are missing, so we should\n> delay the prefetch as much as possible in the hope that we don't need it\n> at all. I admit that if some objects are missing, I don't know where\n> they will be in the to_pack list.\n\nOK, if the common case we optimize for is where there is no object\nmissing, then of course \"prefetch missing ones upfront\" will spend\ncycles to ensure all objects we will pack exist before going into\nthe main loop, so the \"delay as much as possible\" optimization makes\nsense.\n\n>> In any case, the design choice needs to be justified in the log\n>> message. I am not sure if the lazy decision to prefetch at the last\n>> moment is really worth the code smell. Perhaps it is, if there is a\n>> reason to believe that it would save extra work compared to the more\n>> naive \"if we have promissor remote, prefetch what is missing\", but I\n>> do not think I've heard that reason yet.\n>\n> I still think that there is a reason (the extra existence check), but if\n> we think that the extra existence check is fast enough (compared to the\n> other operations in pack-objects) or that there is a way to avoid\n> calling oid_object_info_extended() twice for the same object (even with\n> moving the prefetch loop to the beginning), then I agree that we don't\n> need the lazy decision. (Or if we want to write the simpler code now and\n> only improve the performance if we need it later, that's fine with me\n> too.)\n\nNow I finally have, I think, heard some of the reasoning behind the\ndesign decision made before this patch was written. That should be\nwritten in the proposed log message.\n\nThanks.\n\n"},{"id":"401838","messageId":"xmqqv9ig5smu.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"20200721233707.1363438-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-21T23:56:57Z","receivedAt":"2020-07-21T23:57:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n>> Junio C Hamano writes:\n>> \n>> >>> The optimization makes sense to me if certain\n>> >>> conditions are met, like...\n>> >>> \n>> >>> - Most of the time there is no missing object due to promisor, even\n>> >>> if has_promissor_to_remote() is true;\n>> >>\n>> >> I think that optimizing for this condition makes sense - most pushes (I\n>> >> would think) are pushes of objects we create locally, and thus no\n>> >> objects are missing.\n>> \n>> Another simple thing I missed. Why do we specifically refer to\n>> \"push\" here? Is this codepath in pack-objects not used or less\n>> often used by upload-pack (which is what serves \"fetch\")? \n>> \n>> I just wanted to make sure that we are not optimizing for \"push\",\n>> trading efficiency for \"fetch\" off.\n>\n> Ah...that's true. For \"fetch\" I think it's less important because the\n> multiple roundtrips of the pack negotiation means that the packfiles are\n> usually more specific, but this optimization will help \"fetch\" too. I\n> don't think we're optimizing at the expense of \"fetch\" - any\n> improvements should benefit both similarly.\n\nThe one who serves \"fetch\" (i.e. \"upload-pack\") may be advertising\nthe objects that it itself would have to lazily fetch from its\npromisor remote, but that is sort of crazy. As long as we have\nsomething to discourage such an arrangement (i.e. \"don't fetch from\na lazy clone\"), we would be OK to assume that most of the time there\nis no missing objects.\n\nThanks.\n"},{"id":"401866","messageId":"20200722213048.1581991-1-jonathantanmy@google.com","threadId":"53887","inReplyTo":"xmqqzh7s5sv4.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2020-07-22T21:30:48Z","receivedAt":"2020-07-22T21:30:56Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> Jonathan Tan writes:\n> \n> > My argument is that typically *no* objects are missing, so we should\n> > delay the prefetch as much as possible in the hope that we don't need it\n> > at all. I admit that if some objects are missing, I don't know where\n> > they will be in the to_pack list.\n> \n> OK, if the common case we optimize for is where there is no object\n> missing, then of course \"prefetch missing ones upfront\" will spend\n> cycles to ensure all objects we will pack exist before going into\n> the main loop, so the \"delay as much as possible\" optimization makes\n> sense.\n\nOK.\n\n> >> In any case, the design choice needs to be justified in the log\n> >> message. I am not sure if the lazy decision to prefetch at the last\n> >> moment is really worth the code smell. Perhaps it is, if there is a\n> >> reason to believe that it would save extra work compared to the more\n> >> naive \"if we have promissor remote, prefetch what is missing\", but I\n> >> do not think I've heard that reason yet.\n> >\n> > I still think that there is a reason (the extra existence check), but if\n> > we think that the extra existence check is fast enough (compared to the\n> > other operations in pack-objects) or that there is a way to avoid\n> > calling oid_object_info_extended() twice for the same object (even with\n> > moving the prefetch loop to the beginning), then I agree that we don't\n> > need the lazy decision. (Or if we want to write the simpler code now and\n> > only improve the performance if we need it later, that's fine with me\n> > too.)\n> \n> Now I finally have, I think, heard some of the reasoning behind the\n> design decision made before this patch was written. That should be\n> written in the proposed log message.\n> \n> Thanks.\n\nOK - how about:\n\n[start]\nWhen an object to be packed is noticed to be missing, prefetch all\nto-be-packed objects in one batch.\n\nMost of the time (typically, when serving a fetch or when pushing),\npacks consist only of objects that the repo has. To maintain the\nperformance in this case, the existing object type read is made to also\nserve as the object existence check: if the read fails, then we do the\nprefetch.\n\nAn alternative design is to loop over all the entries in to_pack,\nchecking the existence of each object, and prefetching if we notice any\nmissing. This would result in clearer code, but would incur some\nperformance degradation in the aforementioned most common case due to\nthe additional object existence checks.\n\nSigned-off-by: Jonathan Tan \n[end]\n\nThe first paragraph is already in the original, and the rest are\nadditions.\n"},{"id":"401868","messageId":"xmqqo8o7441j.fsf@gitster.c.googlers.com","threadId":"53887","inReplyTo":"20200722213048.1581991-1-jonathantanmy@google.com","subject":"Re: [PATCH 2/2] pack-objects: prefetch objects to be packed","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-22T21:45:44Z","receivedAt":"2020-07-22T21:45:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> OK - how about:\n>\n> [start]\n> When an object to be packed is noticed to be missing, prefetch all\n> to-be-packed objects in one batch.\n>\n> Most of the time (typically, when serving a fetch or when pushing),\n> packs consist only of objects that the repo has. To maintain the\n> performance in this case, the existing object type read is made to also\n> serve as the object existence check: if the read fails, then we do the\n> prefetch.\n>\n> An alternative design is to loop over all the entries in to_pack,\n> checking the existence of each object, and prefetching if we notice any\n> missing. This would result in clearer code, but would incur some\n> performance degradation in the aforementioned most common case due to\n> the additional object existence checks.\n>\n> Signed-off-by: Jonathan Tan \n> [end]\n>\n> The first paragraph is already in the original, and the rest are\n> additions.\n\nSure. \n\nThe first two paragraphs would be sufficient, although the last\nparagraph wouldn't hurt.\n\n"}]}