{"thread":{"id":"58422","subject":"[PATCH] reftable: pass pq_entry by address","startedAt":"2022-09-13T05:08:56Z","lastAt":"2022-09-15T07:50:01Z","messageCount":9,"participants":["Elijah Conners","Han-Wen Nienhuys","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"462965","messageId":"183353220fe.d7826593472673.3445243727369286065@elijahpepe.com","threadId":"58422","inReplyTo":null,"subject":"[PATCH] reftable: pass pq_entry by address","fromName":"Elijah Conners","fromEmail":"business@elijahpepe.com","sentAt":"2022-09-13T04:53:41Z","receivedAt":"2022-09-13T05:08:56Z","isPatch":true,"sender":{"key":"business@elijahpepe.com","avatar":"https://avatars.githubusercontent.com/u/29153977?v=4"},"body":"In merged_iter_pqueue_add, the pq_entry parameter is passed by value,\nalthough it exceeds 64 bytes.\n\nSigned-off-by: Elijah Conners \n---\n reftable/merged.c | 4 ++--\n reftable/pq.c | 4 ++--\n reftable/pq.h | 2 +-\n reftable/pq_test.c | 2 +-\n 4 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 2a6efa110d..5ded470c08 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -36,7 +36,7 @@ static int merged_iter_init(struct merged_iter *mi)\n \t\t\t\t.rec = rec,\n \t\t\t\t.index = i,\n \t\t\t};\n-\t\t\tmerged_iter_pqueue_add(&mi->pq, e);\n+\t\t\tmerged_iter_pqueue_add(&mi->pq, &e);\n \t\t}\n \t}\n \n@@ -71,7 +71,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,\n \t\treturn 0;\n \t}\n \n-\tmerged_iter_pqueue_add(&mi->pq, e);\n+\tmerged_iter_pqueue_add(&mi->pq, &e);\n \treturn 0;\n }\n \ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex 96ca6dd37b..156f78a064 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -71,7 +71,7 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)\n \treturn e;\n }\n \n-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)\n+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e)\n {\n \tint i = 0;\n \n@@ -81,7 +81,7 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)\n \t\t\t\t\t pq->cap * sizeof(struct pq_entry));\n \t}\n \n-\tpq->heap[pq->len++] = e;\n+\tpq->heap[pq->len++] = *e;\n \ti = pq->len - 1;\n \twhile (i > 0) {\n \t\tint j = (i - 1) / 2;\ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex 56fc1b6d87..e5e9234baf 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -26,7 +26,7 @@ struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);\n int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);\n void merged_iter_pqueue_check(struct merged_iter_pqueue pq);\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);\n-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);\n+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e);\n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);\n int pq_less(struct pq_entry *a, struct pq_entry *b);\n \ndiff --git a/reftable/pq_test.c b/reftable/pq_test.c\nindex 7de5e886f3..011b5c7502 100644\n--- a/reftable/pq_test.c\n+++ b/reftable/pq_test.c\n@@ -46,7 +46,7 @@ static void test_pq(void)\n \t\t\t\t\t .u.ref = {\n \t\t\t\t\t\t .refname = names[i],\n \t\t\t\t\t } } };\n-\t\tmerged_iter_pqueue_add(&pq, e);\n+\t\tmerged_iter_pqueue_add(&pq, &e);\n \t\tmerged_iter_pqueue_check(pq);\n \t\ti = (i * 7) % N;\n \t} while (i != 1);\n-- \n2.29.2.windows.2\n\n\n\n"},{"id":"462968","messageId":"CAFQ2z_PATan--dz79j1MUHFCobegX8id=zMxGxk5ftzwK70bnw@mail.gmail.com","threadId":"58422","inReplyTo":"183353220fe.d7826593472673.3445243727369286065@elijahpepe.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2022-09-13T09:11:00Z","receivedAt":"2022-09-13T09:11:19Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Tue, Sep 13, 2022 at 6:53 AM Elijah Conners wrote:\n>\n> In merged_iter_pqueue_add, the pq_entry parameter is passed by value,\n> although it exceeds 64 bytes.\n\n\nLGTM.\n\n-- \nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\n\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\n\nRegistergericht und -nummer: Hamburg, HRB 86891\n\nSitz der Gesellschaft: Hamburg\n\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"},{"id":"462972","messageId":"xmqqbkrjb75g.fsf@gitster.g","threadId":"58422","inReplyTo":"183353220fe.d7826593472673.3445243727369286065@elijahpepe.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-09-13T15:55:55Z","receivedAt":"2022-09-13T17:07:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Conners writes:\n\n> In merged_iter_pqueue_add, the pq_entry parameter is passed by value,\n> although it exceeds 64 bytes.\n\nDo we have any hard guidance like \"do not pass an data item whose\nsize is larger than 64 bytes\" in our coding guidelines? If not,\nmake sure that the reference to 64 bytes does not look like one.\n\nWhile this patch is not bad as a change, we are going to make a copy\nof the value with structure assignment at the leaf level, I am not\nsure how big a deal this is in practice.\n\nIn any case, wouldn't it make sense to make the \"we pass reference\nnot because we want to let the callee modify the value, but because\nthe callee deep in the callchain wants to copy the contents out of\nit\" parameter a pointer to a constant? I.e.\n\n void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)\n\nOther than that, looking good.\n"},{"id":"462978","messageId":"18337ea407a.10c144c52599576.4708941661785569426@elijahpepe.com","threadId":"58422","inReplyTo":"xmqqbkrjb75g.fsf@gitster.g","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Elijah Conners","fromEmail":"business@elijahpepe.com","sentAt":"2022-09-13T17:34:02Z","receivedAt":"2022-09-13T18:21:13Z","isPatch":true,"sender":{"key":"business@elijahpepe.com","avatar":"https://avatars.githubusercontent.com/u/29153977?v=4"},"body":"Junio C Hamano writes:\n > Do we have any hard guidance like \"do not pass an data item whose\n > size is larger than 64 bytes\" in our coding guidelines? If not,\n > make sure that the reference to 64 bytes does not look like one.\nWhile we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.\n\n > In any case, wouldn't it make sense to make the \"we pass reference\n > not because we want to let the callee modify the value, but because\n > the callee deep in the callchain wants to copy the contents out of\n > it\" parameter a pointer to a constant? \nYes. I overlooked that making this change. Feel free to make that change, otherwise I'll do it myself.\n"},{"id":"462979","messageId":"CAFQ2z_OR8uLe3rs0r09a3fvSQUE2H4WQTquddUwEeahoiRWimA@mail.gmail.com","threadId":"58422","inReplyTo":"18337ea407a.10c144c52599576.4708941661785569426@elijahpepe.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2022-09-13T17:36:59Z","receivedAt":"2022-09-13T18:22:19Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Tue, Sep 13, 2022 at 7:34 PM Elijah Conners wrote:\n>\n> Junio C Hamano writes:\n> > Do we have any hard guidance like \"do not pass an data item whose\n> > size is larger than 64 bytes\" in our coding guidelines? If not,\n> > make sure that the reference to 64 bytes does not look like one.\n> While we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.\n\nit might be a bit slower, but \"dangerous\"? How so?\n\n-- \nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\n\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\n\nRegistergericht und -nummer: Hamburg, HRB 86891\n\nSitz der Gesellschaft: Hamburg\n\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"},{"id":"462982","messageId":"18338058407.117ce7158612837.8515739237320978792@elijahpepe.com","threadId":"58422","inReplyTo":"CAFQ2z_OR8uLe3rs0r09a3fvSQUE2H4WQTquddUwEeahoiRWimA@mail.gmail.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Elijah Conners","fromEmail":"business@elijahpepe.com","sentAt":"2022-09-13T18:03:49Z","receivedAt":"2022-09-13T18:38:49Z","isPatch":true,"sender":{"key":"business@elijahpepe.com","avatar":"https://avatars.githubusercontent.com/u/29153977?v=4"},"body":"Han-Wen Nienhuys writes:\n > it might be a bit slower, but \"dangerous\"? How so?\nIn this context, dangerous is the wrong word, but in some cases large objects on the stack can cause stack overflows. In this case, slower is the right word here.\n"},{"id":"463025","messageId":"1833e6d2e00.103444050857631.1873200534809982162@elijahpepe.com","threadId":"58422","inReplyTo":"183353220fe.d7826593472673.3445243727369286065@elijahpepe.com","subject":"[PATCH] reftable: use const with the pq_entry param","fromName":"Elijah Conners","fromEmail":"business@elijahpepe.com","sentAt":"2022-09-14T23:54:46Z","receivedAt":"2022-09-14T23:54:57Z","isPatch":true,"sender":{"key":"business@elijahpepe.com","avatar":"https://avatars.githubusercontent.com/u/29153977?v=4"},"body":"Signed-off-by: Elijah Conners \n---\n reftable/pq.c | 2 +-\n reftable/pq.h | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/pq.c b/reftable/pq.c\nindex 156f78a064..dcefeb793a 100644\n--- a/reftable/pq.c\n+++ b/reftable/pq.c\n@@ -71,7 +71,7 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)\n \treturn e;\n }\n \n-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e)\n+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)\n {\n \tint i = 0;\n \ndiff --git a/reftable/pq.h b/reftable/pq.h\nindex e5e9234baf..e85bac9b52 100644\n--- a/reftable/pq.h\n+++ b/reftable/pq.h\n@@ -26,7 +26,7 @@ struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);\n int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);\n void merged_iter_pqueue_check(struct merged_iter_pqueue pq);\n struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);\n-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e);\n+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);\n void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);\n int pq_less(struct pq_entry *a, struct pq_entry *b);\n \n-- \n2.29.2.windows.2\n\n\n\n"},{"id":"463028","messageId":"xmqqsfktpe2o.fsf@gitster.g","threadId":"58422","inReplyTo":"18337ea407a.10c144c52599576.4708941661785569426@elijahpepe.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-09-15T02:27:11Z","receivedAt":"2022-09-15T02:27:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Conners writes:\n\n> Junio C Hamano writes:\n> > Do we have any hard guidance like \"do not pass an data item whose\n> > size is larger than 64 bytes\" in our coding guidelines? If not,\n> > make sure that the reference to 64 bytes does not look like one.\n> While we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.\n>\n> > In any case, wouldn't it make sense to make the \"we pass reference\n> > not because we want to let the callee modify the value, but because\n> > the callee deep in the callchain wants to copy the contents out of\n> > it\" parameter a pointer to a constant? \n> Yes. I overlooked that making this change. Feel free to make that change, otherwise I'll do it myself.\n\nOK, will wait for an updated patch that corrects the proposed log\nmessage (i.e. not to say \"size is larger than 64 bytes hence this is\nbad\") with a const pointer.\n\nNote that this project tries to avoid piling \"oops the previous one\nwas wrong, and this is a fix\" patches on top of earlier patch that\nare faulty or suboptimal. Instead \"v2\" and later patches are\nwritten as if an earlier iteration never happened, i.e. allowing the\nauthor to pretend to be perfect human ;-).\n\nThanks.\n"},{"id":"463033","messageId":"CAFQ2z_P0k-VQ0mj4RQquA1SJX8RyY+63s2U2pkEr80+B8O4YXQ@mail.gmail.com","threadId":"58422","inReplyTo":"18338058407.117ce7158612837.8515739237320978792@elijahpepe.com","subject":"Re: [PATCH] reftable: pass pq_entry by address","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@google.com","sentAt":"2022-09-15T07:49:44Z","receivedAt":"2022-09-15T07:50:01Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"On Tue, Sep 13, 2022 at 8:03 PM Elijah Conners wrote:\n>\n> Han-Wen Nienhuys writes:\n> > it might be a bit slower, but \"dangerous\"? How so?\n> In this context, dangerous is the wrong word, but in some cases large objects on the stack can cause stack overflows. In this case, slower is the right word here.\n\nI'll let you paint this bikeshed, but do note that the priority queue\nisn't actually optimal here, in a much bigger way. In the typical\ncase, you'd have\n\n1. large base reftable (created by GC)\n2. small updates (created by individual ref updates)\n\nWhen you're iterating, most of the iteration entries will come from\nthe large base reftable, and only occasionally, you have to get\nentries from the small tables.\nIn this scenario, the current code will insert entries from the large\ntable into the priority queue, have it filter up to the top at cost\nlog(number-of-tables), for each of the entries to be read.\n\nWith the current online compaction, number-of-tables =\nlog(number-of-refs), so at log(log(number-of-refs)) it's not a huge\ncost, but certainly larger than the cost of copying the entry once in\nthe function.\n\nJGit has an optimization here where it tries to get the next entry\nfrom the table that previously provided the minimum entry. I didn't\nimplement it for simplicity's sake, but if you care about performance,\nyou might want to try your hand at that.\n\n\n-- \nHan-Wen Nienhuys - Google Munich\nI work 80%. Don't expect answers from me on Fridays.\n--\n\nGoogle Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich\n\nRegistergericht und -nummer: Hamburg, HRB 86891\n\nSitz der Gesellschaft: Hamburg\n\nGeschäftsführer: Paul Manicle, Liana Sebastian\n"}]}