[PATCH] reftable: pass pq_entry by address

[PATCH] reftable: pass pq_entry by address

[Elijah Conners]

In merged_iter_pqueue_add, the pq_entry parameter is passed by value,
although it exceeds 64 bytes.

Signed-off-by: Elijah Conners <business@elijahpepe.com>
---
 reftable/merged.c  | 4 ++--
 reftable/pq.c      | 4 ++--
 reftable/pq.h      | 2 +-
 reftable/pq_test.c | 2 +-
 4 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/merged.c b/reftable/merged.c
index 2a6efa110d..5ded470c08 100644
--- a/reftable/merged.c
+++ b/reftable/merged.c
@@ -36,7 +36,7 @@ static int merged_iter_init(struct merged_iter *mi)
 				.rec = rec,
 				.index = i,
 			};
-			merged_iter_pqueue_add(&mi->pq, e);
+			merged_iter_pqueue_add(&mi->pq, &e);
 		}
 	}
 
@@ -71,7 +71,7 @@ static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,
 		return 0;
 	}
 
-	merged_iter_pqueue_add(&mi->pq, e);
+	merged_iter_pqueue_add(&mi->pq, &e);
 	return 0;
 }
 
diff --git a/reftable/pq.c b/reftable/pq.c
index 96ca6dd37b..156f78a064 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -71,7 +71,7 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	return e;
 }
 
-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e)
 {
 	int i = 0;
 
@@ -81,7 +81,7 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)
 					    pq->cap * sizeof(struct pq_entry));
 	}
 
-	pq->heap[pq->len++] = e;
+	pq->heap[pq->len++] = *e;
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
diff --git a/reftable/pq.h b/reftable/pq.h
index 56fc1b6d87..e5e9234baf 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -26,7 +26,7 @@ struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
 int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
 int pq_less(struct pq_entry *a, struct pq_entry *b);
 
diff --git a/reftable/pq_test.c b/reftable/pq_test.c
index 7de5e886f3..011b5c7502 100644
--- a/reftable/pq_test.c
+++ b/reftable/pq_test.c
@@ -46,7 +46,7 @@ static void test_pq(void)
 					       .u.ref = {
 						       .refname = names[i],
 					       } } };
-		merged_iter_pqueue_add(&pq, e);
+		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
 		i = (i * 7) % N;
 	} while (i != 1);
-- 
2.29.2.windows.2

Re: [PATCH] reftable: pass pq_entry by address

[Han-Wen Nienhuys]

On Tue, Sep 13, 2022 at 6:53 AM Elijah Conners <business@elijahpepe.com> wrote:
>
> In merged_iter_pqueue_add, the pq_entry parameter is passed by value,
> although it exceeds 64 bytes.


LGTM.

-- 
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Liana Sebastian

Re: [PATCH] reftable: pass pq_entry by address

[Junio C Hamano]

Elijah Conners <business@elijahpepe.com> writes:

> In merged_iter_pqueue_add, the pq_entry parameter is passed by value,
> although it exceeds 64 bytes.

Do we have any hard guidance like "do not pass an data item whose
size is larger than 64 bytes" in our coding guidelines?  If not,
make sure that the reference to 64 bytes does not look like one.

While this patch is not bad as a change, we are going to make a copy
of the value with structure assignment at the leaf level, I am not
sure how big a deal this is in practice.

In any case, wouldn't it make sense to make the "we pass reference
not because we want to let the callee modify the value, but because
the callee deep in the callchain wants to copy the contents out of
it" parameter a pointer to a constant?  I.e.

    void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)

Other than that, looking good.

Re: [PATCH] reftable: pass pq_entry by address

[Elijah Conners]

Junio C Hamano <gitster@pobox.com> writes:
 > Do we have any hard guidance like "do not pass an data item whose
 > size is larger than 64 bytes" in our coding guidelines?  If not,
 > make sure that the reference to 64 bytes does not look like one.
While we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.

 > In any case, wouldn't it make sense to make the "we pass reference
 > not because we want to let the callee modify the value, but because
 > the callee deep in the callchain wants to copy the contents out of
 > it" parameter a pointer to a constant? 
Yes. I overlooked that making this change. Feel free to make that change, otherwise I'll do it myself.

Re: [PATCH] reftable: pass pq_entry by address

[Han-Wen Nienhuys]

On Tue, Sep 13, 2022 at 7:34 PM Elijah Conners <business@elijahpepe.com> wrote:
>
> Junio C Hamano <gitster@pobox.com> writes:
>  > Do we have any hard guidance like "do not pass an data item whose
>  > size is larger than 64 bytes" in our coding guidelines?  If not,
>  > make sure that the reference to 64 bytes does not look like one.
> While we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.

it might be a bit slower, but "dangerous"? How so?

-- 
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Liana Sebastian

Re: [PATCH] reftable: pass pq_entry by address

[Elijah Conners]

Han-Wen Nienhuys <hanwen@google.com> writes:
 > it might be a bit slower, but "dangerous"? How so?
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.

[PATCH] reftable: use const with the pq_entry param

[Elijah Conners]

Signed-off-by: Elijah Conners <business@elijahpepe.com>
---
 reftable/pq.c | 2 +-
 reftable/pq.h | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 156f78a064..dcefeb793a 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -71,7 +71,7 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	return e;
 }
 
-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e)
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
 	int i = 0;
 
diff --git a/reftable/pq.h b/reftable/pq.h
index e5e9234baf..e85bac9b52 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -26,7 +26,7 @@ struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
 int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
-void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry *e);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
 int pq_less(struct pq_entry *a, struct pq_entry *b);
 
-- 
2.29.2.windows.2

Re: [PATCH] reftable: pass pq_entry by address

[Junio C Hamano]

Elijah Conners <business@elijahpepe.com> writes:

> Junio C Hamano <gitster@pobox.com> writes:
>  > Do we have any hard guidance like "do not pass an data item whose
>  > size is larger than 64 bytes" in our coding guidelines?  If not,
>  > make sure that the reference to 64 bytes does not look like one.
> While we don't have hard guidance like that, putting an object that exceeds 64 bytes on the stack is dangerous.
>
>  > In any case, wouldn't it make sense to make the "we pass reference
>  > not because we want to let the callee modify the value, but because
>  > the callee deep in the callchain wants to copy the contents out of
>  > it" parameter a pointer to a constant? 
> Yes. I overlooked that making this change. Feel free to make that change, otherwise I'll do it myself.

OK, will wait for an updated patch that corrects the proposed log
message (i.e. not to say "size is larger than 64 bytes hence this is
bad") with a const pointer.

Note that this project tries to avoid piling "oops the previous one
was wrong, and this is a fix" patches on top of earlier patch that
are faulty or suboptimal.  Instead "v2" and later patches are
written as if an earlier iteration never happened, i.e. allowing the
author to pretend to be perfect human ;-).

Thanks.

Re: [PATCH] reftable: pass pq_entry by address

[Han-Wen Nienhuys]

On Tue, Sep 13, 2022 at 8:03 PM Elijah Conners <business@elijahpepe.com> wrote:
>
> Han-Wen Nienhuys <hanwen@google.com> writes:
>  > it might be a bit slower, but "dangerous"? How so?
> 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.

I'll let you paint this bikeshed, but do note that the priority queue
isn't actually optimal here, in a much bigger way. In the typical
case, you'd have

1. large base reftable (created by GC)
2. small updates (created by individual ref updates)

When you're iterating, most of the iteration entries will come from
the large base reftable, and only occasionally, you have to get
entries from the small tables.
In this scenario, the current code will insert entries from the large
table into the priority queue, have it filter up to the top at cost
log(number-of-tables), for each of the entries to be read.

With the current online compaction, number-of-tables =
log(number-of-refs), so at log(log(number-of-refs)) it's not a huge
cost, but certainly larger than the cost of copying the entry once in
the function.

JGit has an optimization here where it tries to get the next entry
from the table that previously provided the minimum entry. I didn't
implement it for simplicity's sake, but if you care about performance,
you might want to try your hand at that.


-- 
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Liana Sebastian