{"thread":{"id":"62929","subject":"[GSOC][RFC PATCH 0/2] midx: implement progress reporting for QSORT operation","startedAt":"2025-02-10T07:46:56Z","lastAt":"2025-02-11T16:29:22Z","messageCount":6,"participants":["Ayush Chandekar","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"512169","messageId":"20250210074623.136599-1-ayu.chandekar@gmail.com","threadId":"62929","inReplyTo":null,"subject":"[GSOC][RFC PATCH 0/2] midx: implement progress reporting for QSORT operation","fromName":"Ayush Chandekar","fromEmail":"ayu.chandekar@gmail.com","sentAt":"2025-02-10T07:46:21Z","receivedAt":"2025-02-10T07:46:56Z","isPatch":true,"sender":{"key":"ayu.chandekar@gmail.com","avatar":"https://avatars.githubusercontent.com/u/137001939?v=4"},"body":"Hi,\nThis small patch series adds progress reporting during the QSORT operation in\nmulti-pack-index verification. This was a TODO in the code which I decided to pickup\nbecause I found it interesting.\n\nFeedback is appreciated!\n\nThanks,\nAyush\n\nAyush Chandekar (2):\n midx: show progress during QSORT operation\n t5319: add test for MIDX QSORT progress reporting\n\n midx.c | 43 +++++++++++++++++++++++++------------\n t/t5319-multi-pack-index.sh | 14 ++++++++++++\n 2 files changed, 43 insertions(+), 14 deletions(-)\n\n-- \n2.48.GIT\n\n"},{"id":"512170","messageId":"20250210074623.136599-3-ayu.chandekar@gmail.com","threadId":"62929","inReplyTo":"20250210074623.136599-1-ayu.chandekar@gmail.com","subject":"[PATCH 2/2] t5319: add test for MIDX QSORT progress reporting","fromName":"Ayush Chandekar","fromEmail":"ayu.chandekar@gmail.com","sentAt":"2025-02-10T07:46:23Z","receivedAt":"2025-02-10T07:46:59Z","isPatch":true,"sender":{"key":"ayu.chandekar@gmail.com","avatar":"https://avatars.githubusercontent.com/u/137001939?v=4"},"body":"Add a test to verify that the multi-pack-index verify command shows\nprogress during the QSORT operation. Create 100 test objects, repack\nthem, and verify the progress reaches 100% during sorting \n\nSigned-off-by: Ayush Chandekar \n---\n\nThis test makes sure the progress reaches 100%, but I couldn't find a way \nwhich could verify that the progress went from 0% to 100% with intermediates.\nI would like if someone can suggest a method for this.\n\nThanks,\nAyush\n\n t/t5319-multi-pack-index.sh | 14 ++++++++++++++\n 1 file changed, 14 insertions(+)\n\ndiff --git a/t/t5319-multi-pack-index.sh b/t/t5319-multi-pack-index.sh\nindex 0f215ad2e8..d368e22e3a 100755\n--- a/t/t5319-multi-pack-index.sh\n+++ b/t/t5319-multi-pack-index.sh\n@@ -658,6 +658,20 @@ test_expect_success 'verify incorrect 64-bit offset' '\n \t\t\"incorrect object offset\"\n '\n \n+test_expect_success 'verify shows QSORT progress' '\n+\t# Create test objects\n+\tfor i in $(test_seq 1 100)\n+\tdo\n+\t\techo \"content $i\" | \\\n+\t\t\tgit hash-object -w --stdin \\\n+\t\t\t|| return 1\n+\tdone &&\n+\tgit repack -ad &&\n+\tgit multi-pack-index write &&\n+\tGIT_PROGRESS_DELAY=0 git multi-pack-index verify --progress 2>actual &&\n+\tgrep \"Sorting objects by packfile: *100%\" actual\n+'\n+\n test_expect_success 'setup expire tests' '\n \tmkdir dup &&\n \t(\n-- \n2.48.GIT\n\n"},{"id":"512171","messageId":"20250210074623.136599-2-ayu.chandekar@gmail.com","threadId":"62929","inReplyTo":"20250210074623.136599-1-ayu.chandekar@gmail.com","subject":"[PATCH 1/2] midx: show progress during QSORT operation","fromName":"Ayush Chandekar","fromEmail":"ayu.chandekar@gmail.com","sentAt":"2025-02-10T07:46:22Z","receivedAt":"2025-02-10T07:46:59Z","isPatch":true,"sender":{"key":"ayu.chandekar@gmail.com","avatar":"https://avatars.githubusercontent.com/u/137001939?v=4"},"body":"Add progress reporting during the QSORT operation in multi-pack-index\nverification. This helps users track the progress of large sorting\noperations.\n\nIn previous versions, the progress would jump directly from 0% to 100%\nwithout any intermediate updates.\n\nSigned-off-by: Ayush Chandekar \n---\n midx.c | 43 +++++++++++++++++++++++++++++--------------\n 1 file changed, 29 insertions(+), 14 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex d91088efb8..69937f5ca8 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -14,6 +14,7 @@\n #include \"pack-bitmap.h\"\n #include \"pack-revindex.h\"\n \n+\n int midx_checksum_valid(struct multi_pack_index *m);\n void clear_midx_files_ext(const char *object_dir, const char *ext,\n \t\t\t const char *keep_hash);\n@@ -853,32 +854,43 @@ static void midx_report(const char *fmt, ...)\n \tva_end(ap);\n }\n \n+/*\n+ * Limit calls to display_progress() for performance reasons.\n+ * The interval here was arbitrarily chosen.\n+ */\n+#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n+#define midx_display_sparse_progress(progress, n) \\\n+\tdo { \\\n+\t\tuint64_t _n = (n); \\\n+\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \\\n+\t\t\tdisplay_progress(progress, _n); \\\n+\t} while (0)\n+\n struct pair_pos_vs_id\n {\n \tuint32_t pos;\n \tuint32_t pack_int_id;\n };\n \n+static struct progress *sort_progress;\n+static uint64_t last_max_pos;\n+\n static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n {\n \tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n \tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n+\t\n+\tif (sort_progress) {\n+\t\tuint64_t max_pos = (a->pos > b->pos) ? a->pos : b->pos;\n+\t\tif (max_pos > last_max_pos) {\n+\t\t\tlast_max_pos = max_pos;\n+\t\t\tmidx_display_sparse_progress(sort_progress, last_max_pos);\n+\t\t}\n+\t}\n \n \treturn b->pack_int_id - a->pack_int_id;\n }\n \n-/*\n- * Limit calls to display_progress() for performance reasons.\n- * The interval here was arbitrarily chosen.\n- */\n-#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n-#define midx_display_sparse_progress(progress, n) \\\n-\tdo { \\\n-\t\tuint64_t _n = (n); \\\n-\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \\\n-\t\t\tdisplay_progress(progress, _n); \\\n-\t} while (0)\n-\n int verify_midx_file(struct repository *r, const char *object_dir, unsigned flags)\n {\n \tstruct pair_pos_vs_id *pairs = NULL;\n@@ -960,12 +972,15 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag\n \t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n \t}\n \n-\tif (flags & MIDX_PROGRESS)\n+\tif (flags & MIDX_PROGRESS) {\n \t\tprogress = start_sparse_progress(r,\n \t\t\t\t\t\t _(\"Sorting objects by packfile\"),\n \t\t\t\t\t\t m->num_objects);\n-\tdisplay_progress(progress, 0); /* TODO: Measure QSORT() progress */\n+\t\tlast_max_pos = 0;\n+\t\tsort_progress = progress;\n+\t}\n \tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n+\tsort_progress = NULL;\n \tstop_progress(&progress);\n \n \tif (flags & MIDX_PROGRESS)\n-- \n2.48.GIT\n\n"},{"id":"512183","messageId":"xmqqzfitbuy1.fsf@gitster.g","threadId":"62929","inReplyTo":"20250210074623.136599-2-ayu.chandekar@gmail.com","subject":"Re: [PATCH 1/2] midx: show progress during QSORT operation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-10T16:55:50Z","receivedAt":"2025-02-10T16:55:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ayush Chandekar writes:\n\n> Add progress reporting during the QSORT operation in multi-pack-index\n> verification. This helps users track the progress of large sorting\n> operations.\n\nHmph. If the implementation is correct (which I cannot tell), this\nneeds to explain why it is a bit better than saying nothing.\n\n> +/*\n> + * Limit calls to display_progress() for performance reasons.\n> + * The interval here was arbitrarily chosen.\n> + */\n> +#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n> +#define midx_display_sparse_progress(progress, n) \\\n> +\tdo { \\\n> +\t\tuint64_t _n = (n); \\\n> +\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \\\n> +\t\t\tdisplay_progress(progress, _n); \\\n> +\t} while (0)\n> +\n> struct pair_pos_vs_id\n> {\n> \tuint32_t pos;\n> \tuint32_t pack_int_id;\n> };\n> \n> +static struct progress *sort_progress;\n> +static uint64_t last_max_pos;\n> +\n> static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n> {\n> \tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n> \tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n\nThis is a compar callback function used by the sorting machinery,\nwhich is called QSORT but system-provided qsort() implementations\nare not necessarily quick-sort [*].\n\n> +\t\n> +\tif (sort_progress) {\n> +\t\tuint64_t max_pos = (a->pos > b->pos) ? a->pos : b->pos;\n> +\t\tif (max_pos > last_max_pos) {\n> +\t\t\tlast_max_pos = max_pos;\n> +\t\t\tmidx_display_sparse_progress(sort_progress, last_max_pos);\n> +\t\t}\n> +\t}\n\nSo I do not quite understand the assumption this implementation of\nthe progress meter makes. \n\nThe assumption seems to be that the element in the array with the\nhighest index MUST not be summoned for comparison until the very end\nof the sorting process, but what guarantees that? Even if we assume\nthat the qsort() implementation supplied by the system implements\nthe divide and conquer plain vanilla quicksort, it may divide the\narray into half, and then sort the top half first before it sorts\nthe bottom half, and doing so recursively will give you the\ncomparison between elements near the end of the array with the\nhighest index fairly early in the process, no?\n\nAnd the standard does not even specify what algorithm should\ninternally be used to implement qsort(3), which our QSORT() macro\neventually calls, so making any assumption on the order the elements\nof the array is fed to the compar callback function sounds doubly a\nfrigile deal.\n\nThanks.\n"},{"id":"512233","messageId":"CAE7as+YPKuBd+ztBerim6e1kZXZwUHdb_qjcMfZSBa4LkiyJow@mail.gmail.com","threadId":"62929","inReplyTo":"xmqqzfitbuy1.fsf@gitster.g","subject":"Re: [PATCH 1/2] midx: show progress during QSORT operation","fromName":"Ayush Chandekar","fromEmail":"ayu.chandekar@gmail.com","sentAt":"2025-02-11T12:23:58Z","receivedAt":"2025-02-11T12:24:10Z","isPatch":true,"sender":{"key":"ayu.chandekar@gmail.com","avatar":"https://avatars.githubusercontent.com/u/137001939?v=4"},"body":"> Hmph. If the implementation is correct (which I cannot tell), this\n> needs to explain why it is a bit better than saying nothing.\nWhile going through the code, I noticed the TODO comment: \"Measure\nQSORT() progress\", and I thought it might be interesting to explore.\nFor big codebases, being stuck at zero would make it feel like there's\nno progress happening and that is why putting a progress might be\nbetter.\n\n> > static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n> > {\n> > struct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n> > struct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n>\n> This is a compar callback function used by the sorting machinery,\n> which is called QSORT but system-provided qsort() implementations\n> are not necessarily quick-sort [*].\nOh.\n\nInitially, I was unsure how to approach it, but I believed that\ntracking the highest pos value seen in comparisons could give a rough\nestimate of progress.\nHowever, as you pointed out, this assumes that qsort() processes\nelements in a structured way where the highest-indexed element isn't\ncompared until later in the sort.\nI now see that this isn't a safe assumption Since there's no guarantee\nthat progress would be reflected meaningfully, this approach isn't\ngood.\n\nLet me know if you have any suggestions/comments:)\n\nThanks,\nAyush\n"},{"id":"512236","messageId":"xmqq8qqc30o0.fsf@gitster.g","threadId":"62929","inReplyTo":"CAE7as+YPKuBd+ztBerim6e1kZXZwUHdb_qjcMfZSBa4LkiyJow@mail.gmail.com","subject":"Re: [PATCH 1/2] midx: show progress during QSORT operation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-11T16:29:19Z","receivedAt":"2025-02-11T16:29:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ayush Chandekar writes:\n\n>> Hmph. If the implementation is correct (which I cannot tell), this\n>> needs to explain why it is a bit better than saying nothing.\n> While going through the code, I noticed the TODO comment: \"Measure\n> QSORT() progress\", and I thought it might be interesting to explore.\n> For big codebases, being stuck at zero would make it feel like there's\n> no progress happening and that is why putting a progress might be\n> better.\n\nThat much I already know---otherwise we would not have that comment\nthere ;-)\n\nWhat I meant was that the proposed log message did not give readers\nany hint how the implementation given in the patch is correct, the\nassumption it makes on the behaviour of sort(3), etc.\n"}]}