git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
@ 2021-09-04 12:40 Jeff King
  2021-09-04 12:41 ` [PATCH 1/2] ref-filter: hacky "streaming" mode Jeff King
                   ` (3 more replies)
  0 siblings, 4 replies; 26+ messages in thread
From: Jeff King @ 2021-09-04 12:40 UTC (permalink / raw)
  To: git; +Cc: ZheNing Hu

Somebody complained to me off-list recently that for-each-ref was slow
when doing a trivial listing (like refname + objectname) of a large
number of refs, even though you could get mostly the same output by
just dumping the packed-refs file.

So I was nerd-sniped into making this horrible series, which does speed
up some cases. It was a combination of "how fast can we easily get it",
plus I was curious _which_ parts of for-each-ref were actually slow.

In this version there are 2 patches, tested against 'git for-each-ref
--format="%(objectname) %(refname)"' on a fully packed repo with 500k
refs:

  - directly outputting items rather than building up a ref_array yields
    about a 1.5x speedup

  - avoiding the whole atom-formatting system yields a 2.5x speedup on
    top of that

I had originally written it against a slightly older version of Git,
before show_ref_array_item() was inlined. In that version, there was a
middle ground where we still created a ref_array_item for each ref, and
then fed it to the "quick" formatter (so we could see the cost of
having to malloc/free a bunch of ref_array_item structs). The numbers
there wre:

  - streaming out items gave a 1.5x speedup

  - using the "quick" formatter gave a 1.8x speedup

  - avoiding the extra malloc/free for each item gave a 1.4x

which makes sense; 1.8 * 1.4 is ~2.5, so it's the same speedup just
broken down further.

I'm not sure I'm really advocating that we should do something like
this, though it is tempting because it does make some common queries
much faster. But I wanted to share it here to give some insight on where
the time may be going in ref-filter / for-each-ref.

  [1/2]: ref-filter: hacky "streaming" mode
  [2/2]: ref-filter: implement "quick" formats

 builtin/for-each-ref.c |   7 +++
 ref-filter.c           | 113 +++++++++++++++++++++++++++++++++++++----
 ref-filter.h           |  21 ++++++++
 3 files changed, 132 insertions(+), 9 deletions(-)

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-04 12:40 [hacky PATCH 0/2] speeding up trivial for-each-ref invocations Jeff King
@ 2021-09-04 12:41 ` Jeff King
  2021-09-05  8:20   ` ZheNing Hu
  2021-09-04 12:42 ` [PATCH 2/2] ref-filter: implement "quick" formats Jeff King
                   ` (2 subsequent siblings)
  3 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-04 12:41 UTC (permalink / raw)
  To: git; +Cc: ZheNing Hu

The ref-filter code is very keen to collect all of the refs in an array
before writing any output. This makes things slower than necessary when
using the default sort order (which is already sorted by refname when we
call for_each_ref()), and when no filtering options require it.

This commit adds a mildly-ugly interface to detect this case and stream
directly from filter_refs(). The caller just needs to call the
"maybe_stream" function. Either way, they can call the usual sort/print
functions; they'll just be noops if we did stream instead of collecting.

Here are some timings on a fully-packed 500k-ref repo:

  Benchmark #1: ./git.orig for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):     340.2 ms ±   5.3 ms    [User: 300.5 ms, System: 39.6 ms]
    Range (min … max):   332.9 ms … 347.0 ms    10 runs

  Benchmark #2: ./git.stream for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):     224.0 ms ±   3.4 ms    [User: 222.7 ms, System: 1.3 ms]
    Range (min … max):   218.1 ms … 228.5 ms    13 runs

  Summary
    './git.stream for-each-ref --format='%(objectname) %(refname)'' ran
      1.52 ± 0.03 times faster than './git.orig for-each-ref --format='%(objectname) %(refname)''

So we definitely shave off some time, though we're still _much_ slower
than a simple `wc -l <packed-refs` (which is around 10ms, though of
course it isn't actually doing as much work).

The point here is to reduce overall effort, though of course the time to
first output is much improved in the streaming version, too (about 250ms
versus 4ms).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/for-each-ref.c |  7 ++++++
 ref-filter.c           | 50 ++++++++++++++++++++++++++++++++++--------
 ref-filter.h           |  8 +++++++
 3 files changed, 56 insertions(+), 9 deletions(-)

diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 89cb6307d4..fe0b92443f 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c
@@ -70,6 +70,13 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	if (verify_ref_format(&format))
 		usage_with_options(for_each_ref_usage, opts);
 
+	/*
+	 * try streaming, but only without maxcount; in theory the ref-filter
+	 * code could learn about maxcount, but for now it is our own thing
+	 */
+	if (!maxcount)
+		ref_filter_maybe_stream(&filter, sorting, icase, &format);
+
 	if (!sorting)
 		sorting = ref_default_sorting();
 	ref_sorting_set_sort_flags_all(sorting, REF_SORTING_ICASE, icase);
diff --git a/ref-filter.c b/ref-filter.c
index 93ce2a6ef2..17b78b1d30 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -2283,15 +2283,19 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 			return 0;
 	}
 
-	/*
-	 * We do not open the object yet; sort may only need refname
-	 * to do its job and the resulting list may yet to be pruned
-	 * by maxcount logic.
-	 */
-	ref = ref_array_push(ref_cbdata->array, refname, oid);
-	ref->commit = commit;
-	ref->flag = flag;
-	ref->kind = kind;
+	if (ref_cbdata->filter->streaming_format) {
+		pretty_print_ref(refname, oid, ref_cbdata->filter->streaming_format);
+	} else {
+		/*
+		 * We do not open the object yet; sort may only need refname
+		 * to do its job and the resulting list may yet to be pruned
+		 * by maxcount logic.
+		 */
+		ref = ref_array_push(ref_cbdata->array, refname, oid);
+		ref->commit = commit;
+		ref->flag = flag;
+		ref->kind = kind;
+	}
 
 	return 0;
 }
@@ -2563,6 +2567,34 @@ void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)
 	QSORT_S(array->items, array->nr, compare_refs, sorting);
 }
 
+void ref_filter_maybe_stream(struct ref_filter *filter,
+			     const struct ref_sorting *sort, int icase,
+			     struct ref_format *format)
+{
+	/* streaming only works with default for_each_ref sort order */
+	if (sort || icase)
+		return;
+
+	/* these filters want to see all candidates up front */
+	if (filter->reachable_from || filter->unreachable_from)
+		return;
+
+	/*
+	 * the %(symref) placeholder is broken with pretty_print_ref(),
+	 * which our streaming code uses. I suspect this is a sign of breakage
+	 * in other callers like verify_tag(), which should be fixed. But for
+	 * now just disable streaming.
+	 *
+	 * Note that this implies we've parsed the format already with
+	 * verify_ref_format().
+	 */
+	if (need_symref)
+		return;
+
+	/* OK to stream */
+	filter->streaming_format = format;
+}
+
 static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)
 {
 	struct strbuf *s = &state->stack->output;
diff --git a/ref-filter.h b/ref-filter.h
index c15dee8d6b..ecea1837a2 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -69,6 +69,9 @@ struct ref_filter {
 		lines;
 	int abbrev,
 		verbose;
+
+	/* if non-NULL, streaming output during filter_refs() is enabled */
+	struct ref_format *streaming_format;
 };
 
 struct ref_format {
@@ -135,6 +138,11 @@ char *get_head_description(void);
 /*  Set up translated strings in the output. */
 void setup_ref_filter_porcelain_msg(void);
 
+/* enable streaming during filter_refs() if options allow it */
+void ref_filter_maybe_stream(struct ref_filter *filter,
+			     const struct ref_sorting *sort, int icase,
+			     struct ref_format *format);
+
 /*
  * Print a single ref, outside of any ref-filter. Note that the
  * name must be a fully qualified refname.
-- 
2.33.0.618.g5b11852304


^ permalink raw reply	[flat|nested] 26+ messages in thread

* [PATCH 2/2] ref-filter: implement "quick" formats
  2021-09-04 12:40 [hacky PATCH 0/2] speeding up trivial for-each-ref invocations Jeff King
  2021-09-04 12:41 ` [PATCH 1/2] ref-filter: hacky "streaming" mode Jeff King
@ 2021-09-04 12:42 ` Jeff King
  2021-09-05  8:20   ` ZheNing Hu
  2021-09-05  8:19 ` [hacky PATCH 0/2] speeding up trivial for-each-ref invocations ZheNing Hu
  2021-09-06  6:54 ` Patrick Steinhardt
  3 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-04 12:42 UTC (permalink / raw)
  To: git; +Cc: ZheNing Hu

Some commonly-used formats can be output _much_ faster than going
through the usual atom-formatting code. E.g., "%(objectname) %(refname)"
can just be a simple printf. This commit detects a few easy cases and
uses a hard-coded output function instead.

Note two things about the implementation:

 - we could probably go further here. E.g., %(refname:lstrip) should be
   easy-ish to optimize, too. Likewise, mixed-text like "delete
   %(refname)" would be nice to have.

 - the code is repetitive and enumerates all the cases, and it feels
   like we ought to be able to generalize it more. But that's exactly
   what the current formatting tries to do!

So this whole thing is pretty horrible, and is a hack around the
slowness of the whole used_atom system. It _should_ be possible to
refactor that system to have roughly the same cost, but this will serve
in the meantime.

Here are some numbers ("stream" is Git with the streaming optimization
from the previous commit, and "quick" is this commit):

  Benchmark #1: ./git.stream for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):     229.2 ms ±   6.6 ms    [User: 228.3 ms, System: 0.9 ms]
    Range (min … max):   220.4 ms … 242.6 ms    13 runs

  Benchmark #2: ./git.quick for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):      94.8 ms ±   2.2 ms    [User: 93.5 ms, System: 1.4 ms]
    Range (min … max):    90.8 ms …  98.2 ms    32 runs

  Summary
    './git.quick for-each-ref --format='%(objectname) %(refname)'' ran
      2.42 ± 0.09 times faster than './git.stream for-each-ref --format='%(objectname) %(refname)''

Signed-off-by: Jeff King <peff@peff.net>
---
 ref-filter.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 ref-filter.h | 13 +++++++++++
 2 files changed, 76 insertions(+)

diff --git a/ref-filter.c b/ref-filter.c
index 17b78b1d30..1efa3aadc8 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1009,6 +1009,37 @@ static int reject_atom(enum atom_type atom_type)
 	return atom_type == ATOM_REST;
 }
 
+static void set_up_quick_format(struct ref_format *format)
+{
+	/* quick formats don't handle any special quoting */
+	if (format->quote_style)
+		return;
+
+	/*
+	 * no atoms at all; this should be uncommon in real life, but it may be
+	 * interesting for benchmarking
+	 */
+	if (!used_atom_cnt) {
+		format->quick = REF_FORMAT_QUICK_VERBATIM;
+		return;
+	}
+
+	/*
+	 * It's tempting to look at used_atom here, but it's wrong to do so: we
+	 * need not only to be sure of the needed atoms, but also their order
+	 * and any verbatim parts of the format. So instead, let's just
+	 * hard-code some specific formats.
+	 */
+	if (!strcmp(format->format, "%(refname)"))
+		format->quick = REF_FORMAT_QUICK_REFNAME;
+	else if (!strcmp(format->format, "%(objectname)"))
+		format->quick = REF_FORMAT_QUICK_OBJECTNAME;
+	else if (!strcmp(format->format, "%(refname) %(objectname)"))
+		format->quick = REF_FORMAT_QUICK_REFNAME_OBJECTNAME;
+	else if (!strcmp(format->format, "%(objectname) %(refname)"))
+		format->quick = REF_FORMAT_QUICK_OBJECTNAME_REFNAME;
+}
+
 /*
  * Make sure the format string is well formed, and parse out
  * the used atoms.
@@ -1047,6 +1078,9 @@ int verify_ref_format(struct ref_format *format)
 	}
 	if (format->need_color_reset_at_eol && !want_color(format->use_color))
 		format->need_color_reset_at_eol = 0;
+
+	set_up_quick_format(format);
+
 	return 0;
 }
 
@@ -2617,6 +2651,32 @@ static void append_literal(const char *cp, const char *ep, struct ref_formatting
 	}
 }
 
+static int quick_ref_format(const struct ref_format *format,
+			    const char *refname,
+			    const struct object_id *oid)
+{
+	switch(format->quick) {
+	case REF_FORMAT_QUICK_NONE:
+		return -1;
+	case REF_FORMAT_QUICK_VERBATIM:
+		printf("%s\n", format->format);
+		return 0;
+	case REF_FORMAT_QUICK_REFNAME:
+		printf("%s\n", refname);
+		return 0;
+	case REF_FORMAT_QUICK_OBJECTNAME:
+		printf("%s\n", oid_to_hex(oid));
+		return 0;
+	case REF_FORMAT_QUICK_REFNAME_OBJECTNAME:
+		printf("%s %s\n", refname, oid_to_hex(oid));
+		return 0;
+	case REF_FORMAT_QUICK_OBJECTNAME_REFNAME:
+		printf("%s %s\n", oid_to_hex(oid), refname);
+		return 0;
+	}
+	BUG("unknown ref_format_quick value: %d", format->quick);
+}
+
 int format_ref_array_item(struct ref_array_item *info,
 			  struct ref_format *format,
 			  struct strbuf *final_buf,
@@ -2670,6 +2730,9 @@ void pretty_print_ref(const char *name, const struct object_id *oid,
 	struct strbuf output = STRBUF_INIT;
 	struct strbuf err = STRBUF_INIT;
 
+	if (!quick_ref_format(format, name, oid))
+		return;
+
 	ref_item = new_ref_array_item(name, oid);
 	ref_item->kind = ref_kind_from_refname(name);
 	if (format_ref_array_item(ref_item, format, &output, &err))
diff --git a/ref-filter.h b/ref-filter.h
index ecea1837a2..fde5c3a1cb 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -87,6 +87,19 @@ struct ref_format {
 
 	/* Internal state to ref-filter */
 	int need_color_reset_at_eol;
+
+	/*
+	 * Set by verify_ref_format(); if not NONE, we can skip the usual
+	 * formatting and use an optimized routine.
+	 */
+	enum ref_format_quick {
+		REF_FORMAT_QUICK_NONE = 0,
+		REF_FORMAT_QUICK_VERBATIM,
+		REF_FORMAT_QUICK_REFNAME,
+		REF_FORMAT_QUICK_OBJECTNAME,
+		REF_FORMAT_QUICK_REFNAME_OBJECTNAME,
+		REF_FORMAT_QUICK_OBJECTNAME_REFNAME,
+	} quick;
 };
 
 #define REF_FORMAT_INIT { .use_color = -1 }
-- 
2.33.0.618.g5b11852304

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-04 12:40 [hacky PATCH 0/2] speeding up trivial for-each-ref invocations Jeff King
  2021-09-04 12:41 ` [PATCH 1/2] ref-filter: hacky "streaming" mode Jeff King
  2021-09-04 12:42 ` [PATCH 2/2] ref-filter: implement "quick" formats Jeff King
@ 2021-09-05  8:19 ` ZheNing Hu
  2021-09-05 12:49   ` Jeff King
  2021-09-06  6:54 ` Patrick Steinhardt
  3 siblings, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-05  8:19 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月4日周六 下午8:40写道:
>
> Somebody complained to me off-list recently that for-each-ref was slow
> when doing a trivial listing (like refname + objectname) of a large
> number of refs, even though you could get mostly the same output by
> just dumping the packed-refs file.
>
> So I was nerd-sniped into making this horrible series, which does speed
> up some cases. It was a combination of "how fast can we easily get it",
> plus I was curious _which_ parts of for-each-ref were actually slow.
>
> In this version there are 2 patches, tested against 'git for-each-ref
> --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> refs:
>

Regarding this 500k refs, is there any way I can reproduce it?

>   - directly outputting items rather than building up a ref_array yields
>     about a 1.5x speedup
>
>   - avoiding the whole atom-formatting system yields a 2.5x speedup on
>     top of that
>
> I had originally written it against a slightly older version of Git,
> before show_ref_array_item() was inlined. In that version, there was a
> middle ground where we still created a ref_array_item for each ref, and
> then fed it to the "quick" formatter (so we could see the cost of
> having to malloc/free a bunch of ref_array_item structs). The numbers
> there wre:
>
>   - streaming out items gave a 1.5x speedup
>
>   - using the "quick" formatter gave a 1.8x speedup
>
>   - avoiding the extra malloc/free for each item gave a 1.4x
>
> which makes sense; 1.8 * 1.4 is ~2.5, so it's the same speedup just
> broken down further.
>
> I'm not sure I'm really advocating that we should do something like
> this, though it is tempting because it does make some common queries
> much faster. But I wanted to share it here to give some insight on where
> the time may be going in ref-filter / for-each-ref.
>

Well, this acceleration looks gratifying. But so far I haven't seen
its effect on
git cat-file --batch | --batch-check.


>   [1/2]: ref-filter: hacky "streaming" mode
>   [2/2]: ref-filter: implement "quick" formats
>
>  builtin/for-each-ref.c |   7 +++
>  ref-filter.c           | 113 +++++++++++++++++++++++++++++++++++++----
>  ref-filter.h           |  21 ++++++++
>  3 files changed, 132 insertions(+), 9 deletions(-)
>
> -Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-04 12:41 ` [PATCH 1/2] ref-filter: hacky "streaming" mode Jeff King
@ 2021-09-05  8:20   ` ZheNing Hu
  2021-09-05 13:04     ` Jeff King
  2021-09-05 13:15     ` Jeff King
  0 siblings, 2 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-05  8:20 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月4日周六 下午8:41写道:
>
> The ref-filter code is very keen to collect all of the refs in an array
> before writing any output. This makes things slower than necessary when
> using the default sort order (which is already sorted by refname when we
> call for_each_ref()), and when no filtering options require it.
>
> This commit adds a mildly-ugly interface to detect this case and stream
> directly from filter_refs(). The caller just needs to call the
> "maybe_stream" function. Either way, they can call the usual sort/print
> functions; they'll just be noops if we did stream instead of collecting.
>
> Here are some timings on a fully-packed 500k-ref repo:
>
>   Benchmark #1: ./git.orig for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):     340.2 ms ±   5.3 ms    [User: 300.5 ms, System: 39.6 ms]
>     Range (min … max):   332.9 ms … 347.0 ms    10 runs
>
>   Benchmark #2: ./git.stream for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):     224.0 ms ±   3.4 ms    [User: 222.7 ms, System: 1.3 ms]
>     Range (min … max):   218.1 ms … 228.5 ms    13 runs
>
>   Summary
>     './git.stream for-each-ref --format='%(objectname) %(refname)'' ran
>       1.52 ± 0.03 times faster than './git.orig for-each-ref --format='%(objectname) %(refname)''
>
> So we definitely shave off some time, though we're still _much_ slower
> than a simple `wc -l <packed-refs` (which is around 10ms, though of
> course it isn't actually doing as much work).
>
> The point here is to reduce overall effort, though of course the time to
> first output is much improved in the streaming version, too (about 250ms
> versus 4ms).
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  builtin/for-each-ref.c |  7 ++++++
>  ref-filter.c           | 50 ++++++++++++++++++++++++++++++++++--------
>  ref-filter.h           |  8 +++++++
>  3 files changed, 56 insertions(+), 9 deletions(-)
>
> diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
> index 89cb6307d4..fe0b92443f 100644
> --- a/builtin/for-each-ref.c
> +++ b/builtin/for-each-ref.c
> @@ -70,6 +70,13 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
>         if (verify_ref_format(&format))
>                 usage_with_options(for_each_ref_usage, opts);
>
> +       /*
> +        * try streaming, but only without maxcount; in theory the ref-filter
> +        * code could learn about maxcount, but for now it is our own thing
> +        */
> +       if (!maxcount)
> +               ref_filter_maybe_stream(&filter, sorting, icase, &format);
> +

Yes, I think this maxcount is easy to support.

>         if (!sorting)
>                 sorting = ref_default_sorting();
>         ref_sorting_set_sort_flags_all(sorting, REF_SORTING_ICASE, icase);
> diff --git a/ref-filter.c b/ref-filter.c
> index 93ce2a6ef2..17b78b1d30 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -2283,15 +2283,19 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
>                         return 0;
>         }
>
> -       /*
> -        * We do not open the object yet; sort may only need refname
> -        * to do its job and the resulting list may yet to be pruned
> -        * by maxcount logic.
> -        */
> -       ref = ref_array_push(ref_cbdata->array, refname, oid);
> -       ref->commit = commit;
> -       ref->flag = flag;
> -       ref->kind = kind;
> +       if (ref_cbdata->filter->streaming_format) {
> +               pretty_print_ref(refname, oid, ref_cbdata->filter->streaming_format);

So we directly use pretty_print_ref() in streaming mode, OK.

> +       } else {
> +               /*
> +                * We do not open the object yet; sort may only need refname
> +                * to do its job and the resulting list may yet to be pruned
> +                * by maxcount logic.
> +                */
> +               ref = ref_array_push(ref_cbdata->array, refname, oid);
> +               ref->commit = commit;
> +               ref->flag = flag;
> +               ref->kind = kind;
> +       }
>
>         return 0;
>  }

Therefore, in streaming mode, there is no need to push ref to
ref_array, which can
reduce the overhead of malloc(), free(), which makes sense.

But here is a terrible fact: we did not use ref_array_sort() for sorting here.
So in fact, for_each_fullref_in() does the sorting work () for us by
default sort (%(refname)),
This may be due to the file system or some implementation of ref_iterator.
But this limit the application of this optimization when we use other
atoms to sort.

> @@ -2563,6 +2567,34 @@ void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)
>         QSORT_S(array->items, array->nr, compare_refs, sorting);
>  }
>
> +void ref_filter_maybe_stream(struct ref_filter *filter,
> +                            const struct ref_sorting *sort, int icase,
> +                            struct ref_format *format)
> +{
> +       /* streaming only works with default for_each_ref sort order */
> +       if (sort || icase)
> +               return;
> +

Yes, this really can only be optimized on the default sort.

> +       /* these filters want to see all candidates up front */
> +       if (filter->reachable_from || filter->unreachable_from)
> +               return;
> +

Make Sence.

> +       /*
> +        * the %(symref) placeholder is broken with pretty_print_ref(),
> +        * which our streaming code uses. I suspect this is a sign of breakage
> +        * in other callers like verify_tag(), which should be fixed. But for
> +        * now just disable streaming.
> +        *
> +        * Note that this implies we've parsed the format already with
> +        * verify_ref_format().
> +        */
> +       if (need_symref)
> +               return;
> +

I haven’t taken a closer look at why pretty_print_ref() does not
support %(symref),
we can skip it first.

> +       /* OK to stream */
> +       filter->streaming_format = format;
> +}
> +
>  static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)
>  {
>         struct strbuf *s = &state->stack->output;
> diff --git a/ref-filter.h b/ref-filter.h
> index c15dee8d6b..ecea1837a2 100644
> --- a/ref-filter.h
> +++ b/ref-filter.h
> @@ -69,6 +69,9 @@ struct ref_filter {
>                 lines;
>         int abbrev,
>                 verbose;
> +
> +       /* if non-NULL, streaming output during filter_refs() is enabled */
> +       struct ref_format *streaming_format;
>  };
>
>  struct ref_format {
> @@ -135,6 +138,11 @@ char *get_head_description(void);
>  /*  Set up translated strings in the output. */
>  void setup_ref_filter_porcelain_msg(void);
>
> +/* enable streaming during filter_refs() if options allow it */
> +void ref_filter_maybe_stream(struct ref_filter *filter,
> +                            const struct ref_sorting *sort, int icase,
> +                            struct ref_format *format);
> +
>  /*
>   * Print a single ref, outside of any ref-filter. Note that the
>   * name must be a fully qualified refname.
> --
> 2.33.0.618.g5b11852304
>

Unfortunately, this optimization may not be helpful for git cat-file --batch,
see [1], batch_object_write() directly constructs a ref_array_item and call
format_ref_array_item() to grab data, It does not use ref_array. So it also
does not have this malloc() | free() overhead.

[1]: https://lore.kernel.org/git/9c5fddf6885875ccd3ce3f047bb938c77d9bbca2.1628842990.git.gitgitgadget@gmail.com/

--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 2/2] ref-filter: implement "quick" formats
  2021-09-04 12:42 ` [PATCH 2/2] ref-filter: implement "quick" formats Jeff King
@ 2021-09-05  8:20   ` ZheNing Hu
  2021-09-05 13:07     ` Jeff King
  0 siblings, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-05  8:20 UTC (permalink / raw)
  To: Jeff King
  Cc: Git List, Junio C Hamano, Christian Couder,
	Ævar Arnfjörð Bjarmason

Jeff King <peff@peff.net> 于2021年9月4日周六 下午8:42写道:
>
> Some commonly-used formats can be output _much_ faster than going
> through the usual atom-formatting code. E.g., "%(objectname) %(refname)"
> can just be a simple printf. This commit detects a few easy cases and
> uses a hard-coded output function instead.
>
> Note two things about the implementation:
>
>  - we could probably go further here. E.g., %(refname:lstrip) should be
>    easy-ish to optimize, too. Likewise, mixed-text like "delete
>    %(refname)" would be nice to have.
>
>  - the code is repetitive and enumerates all the cases, and it feels
>    like we ought to be able to generalize it more. But that's exactly
>    what the current formatting tries to do!
>
> So this whole thing is pretty horrible, and is a hack around the
> slowness of the whole used_atom system. It _should_ be possible to
> refactor that system to have roughly the same cost, but this will serve
> in the meantime.
>
> Here are some numbers ("stream" is Git with the streaming optimization
> from the previous commit, and "quick" is this commit):
>
>   Benchmark #1: ./git.stream for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):     229.2 ms ±   6.6 ms    [User: 228.3 ms, System: 0.9 ms]
>     Range (min … max):   220.4 ms … 242.6 ms    13 runs
>
>   Benchmark #2: ./git.quick for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):      94.8 ms ±   2.2 ms    [User: 93.5 ms, System: 1.4 ms]
>     Range (min … max):    90.8 ms …  98.2 ms    32 runs
>
>   Summary
>     './git.quick for-each-ref --format='%(objectname) %(refname)'' ran
>       2.42 ± 0.09 times faster than './git.stream for-each-ref --format='%(objectname) %(refname)''
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  ref-filter.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  ref-filter.h | 13 +++++++++++
>  2 files changed, 76 insertions(+)
>
> diff --git a/ref-filter.c b/ref-filter.c
> index 17b78b1d30..1efa3aadc8 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -1009,6 +1009,37 @@ static int reject_atom(enum atom_type atom_type)
>         return atom_type == ATOM_REST;
>  }
>
> +static void set_up_quick_format(struct ref_format *format)
> +{
> +       /* quick formats don't handle any special quoting */
> +       if (format->quote_style)
> +               return;
> +
> +       /*
> +        * no atoms at all; this should be uncommon in real life, but it may be
> +        * interesting for benchmarking
> +        */
> +       if (!used_atom_cnt) {
> +               format->quick = REF_FORMAT_QUICK_VERBATIM;
> +               return;
> +       }
> +
> +       /*
> +        * It's tempting to look at used_atom here, but it's wrong to do so: we
> +        * need not only to be sure of the needed atoms, but also their order
> +        * and any verbatim parts of the format. So instead, let's just
> +        * hard-code some specific formats.
> +        */
> +       if (!strcmp(format->format, "%(refname)"))
> +               format->quick = REF_FORMAT_QUICK_REFNAME;
> +       else if (!strcmp(format->format, "%(objectname)"))
> +               format->quick = REF_FORMAT_QUICK_OBJECTNAME;
> +       else if (!strcmp(format->format, "%(refname) %(objectname)"))
> +               format->quick = REF_FORMAT_QUICK_REFNAME_OBJECTNAME;
> +       else if (!strcmp(format->format, "%(objectname) %(refname)"))
> +               format->quick = REF_FORMAT_QUICK_OBJECTNAME_REFNAME;
> +}
> +
>  /*
>   * Make sure the format string is well formed, and parse out
>   * the used atoms.
> @@ -1047,6 +1078,9 @@ int verify_ref_format(struct ref_format *format)
>         }
>         if (format->need_color_reset_at_eol && !want_color(format->use_color))
>                 format->need_color_reset_at_eol = 0;
> +
> +       set_up_quick_format(format);
> +
>         return 0;
>  }
>
> @@ -2617,6 +2651,32 @@ static void append_literal(const char *cp, const char *ep, struct ref_formatting
>         }
>  }
>
> +static int quick_ref_format(const struct ref_format *format,
> +                           const char *refname,
> +                           const struct object_id *oid)
> +{
> +       switch(format->quick) {
> +       case REF_FORMAT_QUICK_NONE:
> +               return -1;
> +       case REF_FORMAT_QUICK_VERBATIM:
> +               printf("%s\n", format->format);
> +               return 0;
> +       case REF_FORMAT_QUICK_REFNAME:
> +               printf("%s\n", refname);
> +               return 0;
> +       case REF_FORMAT_QUICK_OBJECTNAME:
> +               printf("%s\n", oid_to_hex(oid));
> +               return 0;
> +       case REF_FORMAT_QUICK_REFNAME_OBJECTNAME:
> +               printf("%s %s\n", refname, oid_to_hex(oid));
> +               return 0;
> +       case REF_FORMAT_QUICK_OBJECTNAME_REFNAME:
> +               printf("%s %s\n", oid_to_hex(oid), refname);
> +               return 0;
> +       }
> +       BUG("unknown ref_format_quick value: %d", format->quick);
> +}
> +

So as a fast path, we actually avoided format_ref_array_item() when we are using
%(objectname) and %(refname). But the problem is that it’s not very elegant
(using string compare), and it is no optimization for other atoms that
require in-depth
parsing. I remember the "fast path" used by Ævar last time, and it
seems that Junio doesn't
like them. [1][2]

>  int format_ref_array_item(struct ref_array_item *info,
>                           struct ref_format *format,
>                           struct strbuf *final_buf,
> @@ -2670,6 +2730,9 @@ void pretty_print_ref(const char *name, const struct object_id *oid,
>         struct strbuf output = STRBUF_INIT;
>         struct strbuf err = STRBUF_INIT;
>
> +       if (!quick_ref_format(format, name, oid))
> +               return;
> +
>         ref_item = new_ref_array_item(name, oid);
>         ref_item->kind = ref_kind_from_refname(name);
>         if (format_ref_array_item(ref_item, format, &output, &err))
> diff --git a/ref-filter.h b/ref-filter.h
> index ecea1837a2..fde5c3a1cb 100644
> --- a/ref-filter.h
> +++ b/ref-filter.h
> @@ -87,6 +87,19 @@ struct ref_format {
>
>         /* Internal state to ref-filter */
>         int need_color_reset_at_eol;
> +
> +       /*
> +        * Set by verify_ref_format(); if not NONE, we can skip the usual
> +        * formatting and use an optimized routine.
> +        */
> +       enum ref_format_quick {
> +               REF_FORMAT_QUICK_NONE = 0,
> +               REF_FORMAT_QUICK_VERBATIM,
> +               REF_FORMAT_QUICK_REFNAME,
> +               REF_FORMAT_QUICK_OBJECTNAME,
> +               REF_FORMAT_QUICK_REFNAME_OBJECTNAME,
> +               REF_FORMAT_QUICK_OBJECTNAME_REFNAME,
> +       } quick;
>  };
>
>  #define REF_FORMAT_INIT { .use_color = -1 }
> --
> 2.33.0.618.g5b11852304

[1]: https://lore.kernel.org/git/5903d02324f3275b3aa442bb3ca2602564c543dc.1626363626.git.gitgitgadget@gmail.com/
[2]: https://lore.kernel.org/git/87eecf8ork.fsf@evledraar.gmail.com/

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-05  8:19 ` [hacky PATCH 0/2] speeding up trivial for-each-ref invocations ZheNing Hu
@ 2021-09-05 12:49   ` Jeff King
  2021-09-06 13:30     ` ZheNing Hu
  0 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-05 12:49 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Sun, Sep 05, 2021 at 04:19:53PM +0800, ZheNing Hu wrote:

> > In this version there are 2 patches, tested against 'git for-each-ref
> > --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> > refs:
> >
> 
> Regarding this 500k refs, is there any way I can reproduce it?

Try this in a clone of linux.git (or any other repo):

  git rev-list HEAD |
  head -500000 |
  perl -lne 'print "create refs/foo/$. $_"' |
  git update-ref --stdin

  git pack-refs --all --prune

Though I actually think for these tests that it is not important that
each ref point to a unique commit (we are not opening up the objects at
all, and just treating the oids as strings).

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-05  8:20   ` ZheNing Hu
@ 2021-09-05 13:04     ` Jeff King
  2021-09-07  5:28       ` ZheNing Hu
  2021-09-05 13:15     ` Jeff King
  1 sibling, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-05 13:04 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Sun, Sep 05, 2021 at 04:20:02PM +0800, ZheNing Hu wrote:

> But here is a terrible fact: we did not use ref_array_sort() for sorting here.
> So in fact, for_each_fullref_in() does the sorting work () for us by
> default sort (%(refname)),
> This may be due to the file system or some implementation of ref_iterator.
> But this limit the application of this optimization when we use other
> atoms to sort.

Right. This technique does not help at all if you use --sort. I do think
it's reasonable to rely on the sorted output of the for_each_ref()
functions; other parts of Git likely do as well, so I think we'd try
pretty hard to maintain that (and no, it's not a filesystem thing; we do
make sure to sort it ourselves; see the calls to sort_ref_dir()).

> > +       /*
> > +        * the %(symref) placeholder is broken with pretty_print_ref(),
> > +        * which our streaming code uses. I suspect this is a sign of breakage
> > +        * in other callers like verify_tag(), which should be fixed. But for
> > +        * now just disable streaming.
> > +        *
> > +        * Note that this implies we've parsed the format already with
> > +        * verify_ref_format().
> > +        */
> > +       if (need_symref)
> > +               return;
> > +
> 
> I haven’t taken a closer look at why pretty_print_ref() does not
> support %(symref),
> we can skip it first.

I think it's just because pretty_print_ref() does not take a "flag"
parameter for the caller. So it never sees that REF_ISSYMREF is set.

There aren't many callers of that function, so I think nobody ever
really noticed. But you can see the bug like this:

  git init repo
  cd repo
  
  git commit --allow-empty -m foo
  git tag -s -m bar annotated &&
  git symbolic-ref refs/tags/symref refs/tags/annotated
  
  # this is ok; ref-filter handles the flags
  git tag --list --format='list: %(refname) %(symref)'
  
  # not ok; we do not tell the formatter about the flags, so it does
  # not notice that "symref" is a symref
  git tag --verify --format='verify: %(refname) %(symref)' annotated symref

I notice that the --verify output also shows the short refname, which
makes me wonder if %(symref) would have other bugs there (because it
has to re-resolve the ref to come up with the symref destination).

> Unfortunately, this optimization may not be helpful for git cat-file --batch,
> see [1], batch_object_write() directly constructs a ref_array_item and call
> format_ref_array_item() to grab data, It does not use ref_array. So it also
> does not have this malloc() | free() overhead.

Right. It would only be helped by the "quick" formats in the second
patch (and by skipping the malloc/free of the individual
ref_array_items).

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 2/2] ref-filter: implement "quick" formats
  2021-09-05  8:20   ` ZheNing Hu
@ 2021-09-05 13:07     ` Jeff King
  2021-09-06 13:34       ` ZheNing Hu
  2021-09-07 20:06       ` Junio C Hamano
  0 siblings, 2 replies; 26+ messages in thread
From: Jeff King @ 2021-09-05 13:07 UTC (permalink / raw)
  To: ZheNing Hu
  Cc: Git List, Junio C Hamano, Christian Couder,
	Ævar Arnfjörð Bjarmason

On Sun, Sep 05, 2021 at 04:20:07PM +0800, ZheNing Hu wrote:

> > +       case REF_FORMAT_QUICK_OBJECTNAME_REFNAME:
> > +               printf("%s %s\n", oid_to_hex(oid), refname);
> > +               return 0;
> > +       }
> > +       BUG("unknown ref_format_quick value: %d", format->quick);
> > +}
> > +
> 
> So as a fast path, we actually avoided format_ref_array_item() when we are using
> %(objectname) and %(refname). But the problem is that it’s not very elegant
> (using string compare), and it is no optimization for other atoms that
> require in-depth
> parsing. I remember the "fast path" used by Ævar last time, and it
> seems that Junio doesn't
> like them. [1][2]

Yes, I did say it was "pretty horrible". :)

It was mostly meant as a proof-of-concept to see where the time was
going, and what was possible. It _could_ be used as a stop-gap while
improving the general performance, but it's gross enough that it's
probably not a good idea (it's increased maintenance, but also it
dis-incentivizes fixing the real problems).

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-05  8:20   ` ZheNing Hu
  2021-09-05 13:04     ` Jeff King
@ 2021-09-05 13:15     ` Jeff King
  2021-09-07  5:42       ` ZheNing Hu
  1 sibling, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-05 13:15 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Sun, Sep 05, 2021 at 04:20:02PM +0800, ZheNing Hu wrote:

> > +       if (ref_cbdata->filter->streaming_format) {
> > +               pretty_print_ref(refname, oid, ref_cbdata->filter->streaming_format);
> 
> So we directly use pretty_print_ref() in streaming mode, OK.
> 
> > +       } else {
> > +               /*
> > +                * We do not open the object yet; sort may only need refname
> > +                * to do its job and the resulting list may yet to be pruned
> > +                * by maxcount logic.
> > +                */
> > +               ref = ref_array_push(ref_cbdata->array, refname, oid);
> > +               ref->commit = commit;
> > +               ref->flag = flag;
> > +               ref->kind = kind;
> > +       }
> >
> >         return 0;
> >  }
> 
> Therefore, in streaming mode, there is no need to push ref to
> ref_array, which can
> reduce the overhead of malloc(), free(), which makes sense.

By the way, one thing I wondered here: how much of the benefit is from
avoiding the ref_array, and how much is from skipping the sort entirely.

It turns out that most of it is from the latter. If I do this:

diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 89cb6307d4..037d5db814 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c
@@ -78,7 +78,11 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	filter.name_patterns = argv;
 	filter.match_as_path = 1;
 	filter_refs(&array, &filter, FILTER_REFS_ALL | FILTER_REFS_INCLUDE_BROKEN);
-	ref_array_sort(sorting, &array);
+	/*
+	 * we should skip this only when we are using the default refname
+	 * sorting, but as an experimental hack, we'll just comment it out.
+	 */
+	// ref_array_sort(sorting, &array);
 
 	if (!maxcount || array.nr < maxcount)
 		maxcount = array.nr;

then the timings I get are:

  Benchmark #1: ./git.old for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):     341.4 ms ±   7.4 ms    [User: 299.8 ms, System: 41.6 ms]
    Range (min … max):   333.5 ms … 355.1 ms    10 runs
   
  Benchmark #2: ./git.new for-each-ref --format='%(objectname) %(refname)'
    Time (mean ± σ):     249.1 ms ±   5.7 ms    [User: 211.8 ms, System: 37.2 ms]
    Range (min … max):   245.9 ms … 267.0 ms    12 runs
   
  Summary
    './git.new for-each-ref --format='%(objectname) %(refname)'' ran
      1.37 ± 0.04 times faster than './git.old for-each-ref --format='%(objectname) %(refname)''

So of the 1.5x improvement that the original patch showed, 1.37x is from
skipping the sort of the already-sorted data. I suspect that has less to
do with sorting at all, and more to do with the fact that even just
formatting "%(refname)" for each entry takes a non-trivial amount of
time.

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-04 12:40 [hacky PATCH 0/2] speeding up trivial for-each-ref invocations Jeff King
                   ` (2 preceding siblings ...)
  2021-09-05  8:19 ` [hacky PATCH 0/2] speeding up trivial for-each-ref invocations ZheNing Hu
@ 2021-09-06  6:54 ` Patrick Steinhardt
  3 siblings, 0 replies; 26+ messages in thread
From: Patrick Steinhardt @ 2021-09-06  6:54 UTC (permalink / raw)
  To: Jeff King; +Cc: git, ZheNing Hu

[-- Attachment #1: Type: text/plain, Size: 3332 bytes --]

On Sat, Sep 04, 2021 at 08:40:35AM -0400, Jeff King wrote:
> Somebody complained to me off-list recently that for-each-ref was slow
> when doing a trivial listing (like refname + objectname) of a large
> number of refs, even though you could get mostly the same output by
> just dumping the packed-refs file.
> 
> So I was nerd-sniped into making this horrible series, which does speed
> up some cases. It was a combination of "how fast can we easily get it",
> plus I was curious _which_ parts of for-each-ref were actually slow.
> 
> In this version there are 2 patches, tested against 'git for-each-ref
> --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> refs:
> 
>   - directly outputting items rather than building up a ref_array yields
>     about a 1.5x speedup
> 
>   - avoiding the whole atom-formatting system yields a 2.5x speedup on
>     top of that

Interesting, thanks for the PoC. Your 500k refs naturally triggered me
given that I have recently been trying to optimize such repos with lots
of refs, too. So I ran your series on my gitlab-org/gitlab repository
with 2.3M ref and saw similar speedups:

    Benchmark #1: jk-for-each-ref-speedup~2: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):      2.756 s ±  0.013 s    [User: 2.416 s, System: 0.339 s]
      Range (min … max):    2.740 s …  2.774 s    5 runs

    Benchmark #2: jk-for-each-ref-speedup~: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):      2.009 s ±  0.015 s    [User: 1.974 s, System: 0.035 s]
      Range (min … max):    1.984 s …  2.020 s    5 runs

    Benchmark #3: jk-for-each-ref-speedup: git-for-each-ref --format='%(objectname) %(refname)'
      Time (mean ± σ):     701.8 ms ±   4.2 ms    [User: 661.3 ms, System: 40.4 ms]
      Range (min … max):   696.1 ms … 706.9 ms    5 runs

    Summary
      'jk-for-each-ref-speedup: git-for-each-ref --format='%(objectname) %(refname)'' ran
        2.86 ± 0.03 times faster than 'jk-for-each-ref-speedup~: git-for-each-ref --format='%(objectname) %(refname)''
        3.93 ± 0.03 times faster than 'jk-for-each-ref-speedup~2: git-for-each-ref --format='%(objectname) %(refname)''

[snip]
> I'm not sure I'm really advocating that we should do something like
> this, though it is tempting because it does make some common queries
> much faster. But I wanted to share it here to give some insight on where
> the time may be going in ref-filter / for-each-ref.

Well, avoiding the sort like you do in #1 feels like the right thing to
do to me. I saw similar wins when optimizing the connectivity checks,
and it only makes sense that sorting becomes increasingly expensive as
your number of refs grows. And if we do skip the sort, then decreasing
the initial latency feels like the logical next step because we know we
can stream out things directly.

The quick-formatting is a different story altogether, as you rightly
point out. Having to explain why '%(objectname) %(refname)' is 2.5x
faster than '%(refname) %(objectname)' is probably nothing we'd want to
do. But in any case, your patch does point out that the current
formatting code could use some tweaking.

In any case, this is only my 2c. Thanks for this series!

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-05 12:49   ` Jeff King
@ 2021-09-06 13:30     ` ZheNing Hu
  2021-09-07 17:28       ` Jeff King
  0 siblings, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-06 13:30 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月5日周日 下午8:49写道:
>
> On Sun, Sep 05, 2021 at 04:19:53PM +0800, ZheNing Hu wrote:
>
> > > In this version there are 2 patches, tested against 'git for-each-ref
> > > --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> > > refs:
> > >
> >
> > Regarding this 500k refs, is there any way I can reproduce it?
>
> Try this in a clone of linux.git (or any other repo):
>
>   git rev-list HEAD |
>   head -500000 |
>   perl -lne 'print "create refs/foo/$. $_"' |
>   git update-ref --stdin
>
>   git pack-refs --all --prune
>

Sorry, It seems that the above command is difficult to complete on my
machine (it took more than ten minutes). It may be stuck on git update-ref.
So I tried to reproduce it in a repo which containing 76K refs:

Benchmark #1: jk-for-each-ref-speedup~2: git for-each-ref
--format='%(refname) %(objectname)'
 Time (mean ± σ):     108.0 ms ±   1.9 ms    [User: 55.2 ms, System: 52.1 ms]
 Range (min … max):   105.7 ms … 112.4 ms    26 runs

Benchmark #2: jk-for-each-ref-speedup~1: git for-each-ref
--format='%(refname) %(objectname)'
 Time (mean ± σ):      88.2 ms ±   1.7 ms    [User: 44.8 ms, System: 43.1 ms]
 Range (min … max):    85.8 ms …  93.2 ms    32 runs

Benchmark #3:jk-for-each-ref-speedup: git for-each-ref
--format='%(refname) %(objectname)'
  Time (mean ± σ):      69.0 ms ±   2.0 ms    [User: 22.7 ms, System: 46.1 ms]
 Range (min … max):    66.2 ms …  74.1 ms    41 runs

For %(refname) and %(objectname), this performance optimization is
indeed amazing.

> Though I actually think for these tests that it is not important that
> each ref point to a unique commit (we are not opening up the objects at
> all, and just treating the oids as strings).
>
> -Peff

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 2/2] ref-filter: implement "quick" formats
  2021-09-05 13:07     ` Jeff King
@ 2021-09-06 13:34       ` ZheNing Hu
  2021-09-07 20:06       ` Junio C Hamano
  1 sibling, 0 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-06 13:34 UTC (permalink / raw)
  To: Jeff King
  Cc: Git List, Junio C Hamano, Christian Couder,
	Ævar Arnfjörð Bjarmason

Jeff King <peff@peff.net> 于2021年9月5日周日 下午9:07写道:
>
> On Sun, Sep 05, 2021 at 04:20:07PM +0800, ZheNing Hu wrote:
>
> > > +       case REF_FORMAT_QUICK_OBJECTNAME_REFNAME:
> > > +               printf("%s %s\n", oid_to_hex(oid), refname);
> > > +               return 0;
> > > +       }
> > > +       BUG("unknown ref_format_quick value: %d", format->quick);
> > > +}
> > > +
> >
> > So as a fast path, we actually avoided format_ref_array_item() when we are using
> > %(objectname) and %(refname). But the problem is that it’s not very elegant
> > (using string compare), and it is no optimization for other atoms that
> > require in-depth
> > parsing. I remember the "fast path" used by Ævar last time, and it
> > seems that Junio doesn't
> > like them. [1][2]
>
> Yes, I did say it was "pretty horrible". :)
>
> It was mostly meant as a proof-of-concept to see where the time was
> going, and what was possible. It _could_ be used as a stop-gap while
> improving the general performance, but it's gross enough that it's
> probably not a good idea (it's increased maintenance, but also it
> dis-incentivizes fixing the real problems).
>

Agree. Like you said, these performance gaps are caused by the used_atom
system.

> -Peff

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-05 13:04     ` Jeff King
@ 2021-09-07  5:28       ` ZheNing Hu
  2021-09-07 18:01         ` Jeff King
  0 siblings, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-07  5:28 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月5日周日 下午9:04写道:
>
> On Sun, Sep 05, 2021 at 04:20:02PM +0800, ZheNing Hu wrote:
>
> > But here is a terrible fact: we did not use ref_array_sort() for sorting here.
> > So in fact, for_each_fullref_in() does the sorting work () for us by
> > default sort (%(refname)),
> > This may be due to the file system or some implementation of ref_iterator.
> > But this limit the application of this optimization when we use other
> > atoms to sort.
>
> Right. This technique does not help at all if you use --sort. I do think
> it's reasonable to rely on the sorted output of the for_each_ref()
> functions; other parts of Git likely do as well, so I think we'd try
> pretty hard to maintain that (and no, it's not a filesystem thing; we do
> make sure to sort it ourselves; see the calls to sort_ref_dir()).
>
> > > +       /*
> > > +        * the %(symref) placeholder is broken with pretty_print_ref(),
> > > +        * which our streaming code uses. I suspect this is a sign of breakage
> > > +        * in other callers like verify_tag(), which should be fixed. But for
> > > +        * now just disable streaming.
> > > +        *
> > > +        * Note that this implies we've parsed the format already with
> > > +        * verify_ref_format().
> > > +        */
> > > +       if (need_symref)
> > > +               return;
> > > +
> >
> > I haven’t taken a closer look at why pretty_print_ref() does not
> > support %(symref),
> > we can skip it first.
>
> I think it's just because pretty_print_ref() does not take a "flag"
> parameter for the caller. So it never sees that REF_ISSYMREF is set.
>

yeah, pretty_print_ref() does not set the flag, this is a defect of
pretty_print_ref(), maybe we need to find a way to set this flag.
I also deliberately avoided %(symref) when refactoring git cat-file --batch,
perhaps the improvements here can also be applied to git cat-file --batch

> There aren't many callers of that function, so I think nobody ever
> really noticed. But you can see the bug like this:
>
>   git init repo
>   cd repo
>
>   git commit --allow-empty -m foo
>   git tag -s -m bar annotated &&
>   git symbolic-ref refs/tags/symref refs/tags/annotated
>
>   # this is ok; ref-filter handles the flags
>   git tag --list --format='list: %(refname) %(symref)'
>
>   # not ok; we do not tell the formatter about the flags, so it does
>   # not notice that "symref" is a symref
>   git tag --verify --format='verify: %(refname) %(symref)' annotated symref
>
> I notice that the --verify output also shows the short refname, which
> makes me wonder if %(symref) would have other bugs there (because it
> has to re-resolve the ref to come up with the symref destination).
>

This may be easy to fix:

diff --git a/builtin/tag.c b/builtin/tag.c
index 452558ec95..4be5d36366 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -152,11 +152,11 @@ static int verify_tag(const char *name, const char *ref,
        if (format->format)
                flags = GPG_VERIFY_OMIT_STATUS;

-       if (gpg_verify_tag(oid, name, flags))
+       if (gpg_verify_tag(oid, ref, flags))
                return -1;

        if (format->format)
-               pretty_print_ref(name, oid, format);
+               pretty_print_ref(ref, oid, format);

        return 0;
 }

> > Unfortunately, this optimization may not be helpful for git cat-file --batch,
> > see [1], batch_object_write() directly constructs a ref_array_item and call
> > format_ref_array_item() to grab data, It does not use ref_array. So it also
> > does not have this malloc() | free() overhead.
>
> Right. It would only be helped by the "quick" formats in the second
> patch (and by skipping the malloc/free of the individual
> ref_array_items).
>

Yes, your test is indeed worth thinking about: how to avoid
intermediate data to reduce overhead.

> -Peff

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-05 13:15     ` Jeff King
@ 2021-09-07  5:42       ` ZheNing Hu
  0 siblings, 0 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-07  5:42 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月5日周日 下午9:15写道:
>
> On Sun, Sep 05, 2021 at 04:20:02PM +0800, ZheNing Hu wrote:
>
> > > +       if (ref_cbdata->filter->streaming_format) {
> > > +               pretty_print_ref(refname, oid, ref_cbdata->filter->streaming_format);
> >
> > So we directly use pretty_print_ref() in streaming mode, OK.
> >
> > > +       } else {
> > > +               /*
> > > +                * We do not open the object yet; sort may only need refname
> > > +                * to do its job and the resulting list may yet to be pruned
> > > +                * by maxcount logic.
> > > +                */
> > > +               ref = ref_array_push(ref_cbdata->array, refname, oid);
> > > +               ref->commit = commit;
> > > +               ref->flag = flag;
> > > +               ref->kind = kind;
> > > +       }
> > >
> > >         return 0;
> > >  }
> >
> > Therefore, in streaming mode, there is no need to push ref to
> > ref_array, which can
> > reduce the overhead of malloc(), free(), which makes sense.
>
> By the way, one thing I wondered here: how much of the benefit is from
> avoiding the ref_array, and how much is from skipping the sort entirely.
>
> It turns out that most of it is from the latter. If I do this:
>
> diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
> index 89cb6307d4..037d5db814 100644
> --- a/builtin/for-each-ref.c
> +++ b/builtin/for-each-ref.c
> @@ -78,7 +78,11 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
>         filter.name_patterns = argv;
>         filter.match_as_path = 1;
>         filter_refs(&array, &filter, FILTER_REFS_ALL | FILTER_REFS_INCLUDE_BROKEN);
> -       ref_array_sort(sorting, &array);
> +       /*
> +        * we should skip this only when we are using the default refname
> +        * sorting, but as an experimental hack, we'll just comment it out.
> +        */
> +       // ref_array_sort(sorting, &array);
>
>         if (!maxcount || array.nr < maxcount)
>                 maxcount = array.nr;
>
> then the timings I get are:
>
>   Benchmark #1: ./git.old for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):     341.4 ms ±   7.4 ms    [User: 299.8 ms, System: 41.6 ms]
>     Range (min … max):   333.5 ms … 355.1 ms    10 runs
>
>   Benchmark #2: ./git.new for-each-ref --format='%(objectname) %(refname)'
>     Time (mean ± σ):     249.1 ms ±   5.7 ms    [User: 211.8 ms, System: 37.2 ms]
>     Range (min … max):   245.9 ms … 267.0 ms    12 runs
>
>   Summary
>     './git.new for-each-ref --format='%(objectname) %(refname)'' ran
>       1.37 ± 0.04 times faster than './git.old for-each-ref --format='%(objectname) %(refname)''
>
> So of the 1.5x improvement that the original patch showed, 1.37x is from
> skipping the sort of the already-sorted data. I suspect that has less to
> do with sorting at all, and more to do with the fact that even just
> formatting "%(refname)" for each entry takes a non-trivial amount of
> time.
>

Yes, I think this overhead may come from get_ref_atom_value() instead
of QSORT_S().

> -Peff

Thanks.
--
ZheNing

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-06 13:30     ` ZheNing Hu
@ 2021-09-07 17:28       ` Jeff King
  2021-09-09 13:20         ` ZheNing Hu
  0 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-07 17:28 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Mon, Sep 06, 2021 at 09:30:45PM +0800, ZheNing Hu wrote:

> Jeff King <peff@peff.net> 于2021年9月5日周日 下午8:49写道:
> >
> > On Sun, Sep 05, 2021 at 04:19:53PM +0800, ZheNing Hu wrote:
> >
> > > > In this version there are 2 patches, tested against 'git for-each-ref
> > > > --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> > > > refs:
> > > >
> > >
> > > Regarding this 500k refs, is there any way I can reproduce it?
> >
> > Try this in a clone of linux.git (or any other repo):
> >
> >   git rev-list HEAD |
> >   head -500000 |
> >   perl -lne 'print "create refs/foo/$. $_"' |
> >   git update-ref --stdin
> >
> >   git pack-refs --all --prune
> >
> 
> Sorry, It seems that the above command is difficult to complete on my
> machine (it took more than ten minutes). It may be stuck on git update-ref.
> So I tried to reproduce it in a repo which containing 76K refs:

Mine didn't take nearly that wrong, but it does depend on filesystem and
disk performance. It's going to create 500k lock files in refs/foo. :)

You can cheat a bit like this:

  {
    # grab existing packed refs; don't worry about peel lines or the
    # header comment, we're producing a lowest-common denominator
    # version of the file
    grep '^[0-9a-f]' packed-refs

    # now make our new fake refs
    git rev-list HEAD |
    head -500000 |
    perl -lne 'print "$_ refs/foo/$."'
  } >packed-refs.tmp
  mv packed-refs.tmp packed-refs

  # and now ask Git to repack to get everything sorted, etc
  git pack-refs --all --prune

It sounds like you were able to come up with a smaller version to play
with anyway, but I enjoy coming up with such hacks. :)

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-07  5:28       ` ZheNing Hu
@ 2021-09-07 18:01         ` Jeff King
  2021-09-09 14:45           ` ZheNing Hu
  0 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-07 18:01 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Tue, Sep 07, 2021 at 01:28:33PM +0800, ZheNing Hu wrote:

> > I think it's just because pretty_print_ref() does not take a "flag"
> > parameter for the caller. So it never sees that REF_ISSYMREF is set.
> >
> 
> yeah, pretty_print_ref() does not set the flag, this is a defect of
> pretty_print_ref(), maybe we need to find a way to set this flag.

In general, I think it could take a flag parameter from its caller. But
its caller comes indirectly from for_each_tag_name(), which isn't a
regular ref-iterator. It would probably need to switch to using
read_ref_full() to get the flags.

> > I notice that the --verify output also shows the short refname, which
> > makes me wonder if %(symref) would have other bugs there (because it
> > has to re-resolve the ref to come up with the symref destination).
> >
> 
> This may be easy to fix:
> 
> diff --git a/builtin/tag.c b/builtin/tag.c
> index 452558ec95..4be5d36366 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -152,11 +152,11 @@ static int verify_tag(const char *name, const char *ref,
>         if (format->format)
>                 flags = GPG_VERIFY_OMIT_STATUS;
> 
> -       if (gpg_verify_tag(oid, name, flags))
> +       if (gpg_verify_tag(oid, ref, flags))
>                 return -1;
> 
>         if (format->format)
> -               pretty_print_ref(name, oid, format);
> +               pretty_print_ref(ref, oid, format);
> 
>         return 0;
>  }

Yeah, I think that would work, although:

  - there's another caller in cmd_verify_tag() which seems to just pass
    whatever was on the command line. It doesn't even resolve the ref
    itself!

  - I suspect people may be relying on the current behavior. The
    original was added to be able to compare the internal tagname to the
    refname. I.e., that:

      git tag -v --format='%(refname) %(tag)' foo

    would show "foo foo". Now that _should_ be "%(refname:strip=2)", I
    think, but we'd probably be breaking scripts. OTOH, it really feels
    like _not_ handing over a real, fully-qualified refname to the
    ref-filter code will mean other things are broken (e.g.,
    ATOM_UPSTREAM is assuming we have a fully-qualified ref).

    I think a backwards-compatible way of fixing it would be to have
    this call hand over the full refname to the ref-filter code, but
    tell it that %(refname) should default to strip=2. And then anybody
    who wants the full name can use %(refname:strip=0).

    It makes the behavior confusing and quirky, but we can't avoid that
    without breaking compatibility.

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 2/2] ref-filter: implement "quick" formats
  2021-09-05 13:07     ` Jeff King
  2021-09-06 13:34       ` ZheNing Hu
@ 2021-09-07 20:06       ` Junio C Hamano
  1 sibling, 0 replies; 26+ messages in thread
From: Junio C Hamano @ 2021-09-07 20:06 UTC (permalink / raw)
  To: Jeff King
  Cc: ZheNing Hu, Git List, Christian Couder,
	Ævar Arnfjörð Bjarmason

Jeff King <peff@peff.net> writes:

> It was mostly meant as a proof-of-concept to see where the time was
> going, and what was possible. It _could_ be used as a stop-gap while
> improving the general performance, but it's gross enough that it's
> probably not a good idea (it's increased maintenance, but also it
> dis-incentivizes fixing the real problems).

Thanks.  I have to agree with the assessment.

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [hacky PATCH 0/2] speeding up trivial for-each-ref invocations
  2021-09-07 17:28       ` Jeff King
@ 2021-09-09 13:20         ` ZheNing Hu
  0 siblings, 0 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-09 13:20 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月8日周三 上午1:28写道:
>
> On Mon, Sep 06, 2021 at 09:30:45PM +0800, ZheNing Hu wrote:
>
> > Jeff King <peff@peff.net> 于2021年9月5日周日 下午8:49写道:
> > >
> > > On Sun, Sep 05, 2021 at 04:19:53PM +0800, ZheNing Hu wrote:
> > >
> > > > > In this version there are 2 patches, tested against 'git for-each-ref
> > > > > --format="%(objectname) %(refname)"' on a fully packed repo with 500k
> > > > > refs:
> > > > >
> > > >
> > > > Regarding this 500k refs, is there any way I can reproduce it?
> > >
> > > Try this in a clone of linux.git (or any other repo):
> > >
> > >   git rev-list HEAD |
> > >   head -500000 |
> > >   perl -lne 'print "create refs/foo/$. $_"' |
> > >   git update-ref --stdin
> > >
> > >   git pack-refs --all --prune
> > >
> >
> > Sorry, It seems that the above command is difficult to complete on my
> > machine (it took more than ten minutes). It may be stuck on git update-ref.
> > So I tried to reproduce it in a repo which containing 76K refs:
>
> Mine didn't take nearly that wrong, but it does depend on filesystem and
> disk performance. It's going to create 500k lock files in refs/foo. :)
>
> You can cheat a bit like this:
>
>   {
>     # grab existing packed refs; don't worry about peel lines or the
>     # header comment, we're producing a lowest-common denominator
>     # version of the file
>     grep '^[0-9a-f]' packed-refs
>
>     # now make our new fake refs
>     git rev-list HEAD |
>     head -500000 |
>     perl -lne 'print "$_ refs/foo/$."'
>   } >packed-refs.tmp
>   mv packed-refs.tmp packed-refs
>
>   # and now ask Git to repack to get everything sorted, etc
>   git pack-refs --all --prune
>
> It sounds like you were able to come up with a smaller version to play
> with anyway, but I enjoy coming up with such hacks. :)
>

Thanks, this method really works. :-)

> -Peff

--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-07 18:01         ` Jeff King
@ 2021-09-09 14:45           ` ZheNing Hu
  2021-09-10 14:26             ` Jeff King
  0 siblings, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-09 14:45 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月8日周三 上午2:01写道:
>
> On Tue, Sep 07, 2021 at 01:28:33PM +0800, ZheNing Hu wrote:
>
> > > I think it's just because pretty_print_ref() does not take a "flag"
> > > parameter for the caller. So it never sees that REF_ISSYMREF is set.
> > >
> >
> > yeah, pretty_print_ref() does not set the flag, this is a defect of
> > pretty_print_ref(), maybe we need to find a way to set this flag.
>
> In general, I think it could take a flag parameter from its caller. But
> its caller comes indirectly from for_each_tag_name(), which isn't a
> regular ref-iterator. It would probably need to switch to using
> read_ref_full() to get the flags.
>

Yeah, I think using read_ref_full() with verify_tag() changes can
solve this BUG:

$ git.fix tag --verify --format='verify: %(refname) %(symref)' annotated symref
verify: refs/tags/annotated
verify: refs/tags/symref refs/tags/annotated

diff --git a/ref-filter.c b/ref-filter.c
index 1efa3aadc8..71b1d7da4f 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -2613,18 +2613,6 @@ void ref_filter_maybe_stream(struct ref_filter *filter,
        if (filter->reachable_from || filter->unreachable_from)
                return;

-       /*
-        * the %(symref) placeholder is broken with pretty_print_ref(),
-        * which our streaming code uses. I suspect this is a sign of breakage
-        * in other callers like verify_tag(), which should be fixed. But for
-        * now just disable streaming.
-        *
-        * Note that this implies we've parsed the format already with
-        * verify_ref_format().
-        */
-       if (need_symref)
-               return;
-
        /* OK to stream */
        filter->streaming_format = format;
 }
@@ -2735,6 +2723,7 @@ void pretty_print_ref(const char *name, const
struct object_id *oid,

        ref_item = new_ref_array_item(name, oid);
        ref_item->kind = ref_kind_from_refname(name);
+       read_ref_full(name, 0, NULL, &ref_item->flag);
        if (format_ref_array_item(ref_item, format, &output, &err))
                die("%s", err.buf);
        fwrite(output.buf, 1, output.len, stdout);

> > > I notice that the --verify output also shows the short refname, which
> > > makes me wonder if %(symref) would have other bugs there (because it
> > > has to re-resolve the ref to come up with the symref destination).
> > >
> >
> > This may be easy to fix:
> >
> > diff --git a/builtin/tag.c b/builtin/tag.c
> > index 452558ec95..4be5d36366 100644
> > --- a/builtin/tag.c
> > +++ b/builtin/tag.c
> > @@ -152,11 +152,11 @@ static int verify_tag(const char *name, const char *ref,
> >         if (format->format)
> >                 flags = GPG_VERIFY_OMIT_STATUS;
> >
> > -       if (gpg_verify_tag(oid, name, flags))
> > +       if (gpg_verify_tag(oid, ref, flags))
> >                 return -1;
> >
> >         if (format->format)
> > -               pretty_print_ref(name, oid, format);
> > +               pretty_print_ref(ref, oid, format);
> >
> >         return 0;
> >  }
>
> Yeah, I think that would work, although:
>
>   - there's another caller in cmd_verify_tag() which seems to just pass
>     whatever was on the command line. It doesn't even resolve the ref
>     itself!
>

We can modify get_oid() --> read_ref_full() in cmd_verify_tag()...
Yes, the inconsistency between cmd_verify_tag() and verify_tag() makes
me feel very strange.

>   - I suspect people may be relying on the current behavior. The
>     original was added to be able to compare the internal tagname to the
>     refname. I.e., that:
>
>       git tag -v --format='%(refname) %(tag)' foo
>
>     would show "foo foo". Now that _should_ be "%(refname:strip=2)", I
>     think, but we'd probably be breaking scripts. OTOH, it really feels
>     like _not_ handing over a real, fully-qualified refname to the
>     ref-filter code will mean other things are broken (e.g.,
>     ATOM_UPSTREAM is assuming we have a fully-qualified ref).
>

This is indeed a sad thing: A bug becomes a feature.

>     I think a backwards-compatible way of fixing it would be to have
>     this call hand over the full refname to the ref-filter code, but
>     tell it that %(refname) should default to strip=2. And then anybody
>     who wants the full name can use %(refname:strip=0).
>

Doesn't this make things more complicated? Those callers of git for-each-ref,
wouldn't our changes like this destroy them?


>     It makes the behavior confusing and quirky, but we can't avoid that
>     without breaking compatibility.
>

Eh, I think we may need other solutions.

> -Peff

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-09 14:45           ` ZheNing Hu
@ 2021-09-10 14:26             ` Jeff King
  2021-09-15 12:27               ` ZheNing Hu
  0 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-10 14:26 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Thu, Sep 09, 2021 at 10:45:15PM +0800, ZheNing Hu wrote:

> @@ -2735,6 +2723,7 @@ void pretty_print_ref(const char *name, const
> struct object_id *oid,
> 
>         ref_item = new_ref_array_item(name, oid);
>         ref_item->kind = ref_kind_from_refname(name);
> +       read_ref_full(name, 0, NULL, &ref_item->flag);
>         if (format_ref_array_item(ref_item, format, &output, &err))
>                 die("%s", err.buf);
>         fwrite(output.buf, 1, output.len, stdout);

IMHO this is the wrong place to do it, since the caller may already have
the flags (and looking up the ref again is a non-trivial cost).

The caller in builtin/tag.c should switch to using read_ref_full() and
pass in the flags.

The caller in builtin/verify-tag.c _probably_ should resolve the ref in
the same way and pass in that full refname and flags. I do worry that
this may be a compatibility problem, but the current behavior seems so
broken to me.

> >   - I suspect people may be relying on the current behavior. The
> >     original was added to be able to compare the internal tagname to the
> >     refname. I.e., that:
> >
> >       git tag -v --format='%(refname) %(tag)' foo
> >
> >     would show "foo foo". Now that _should_ be "%(refname:strip=2)", I
> >     think, but we'd probably be breaking scripts. OTOH, it really feels
> >     like _not_ handing over a real, fully-qualified refname to the
> >     ref-filter code will mean other things are broken (e.g.,
> >     ATOM_UPSTREAM is assuming we have a fully-qualified ref).
> >
> 
> This is indeed a sad thing: A bug becomes a feature.
> 
> >     I think a backwards-compatible way of fixing it would be to have
> >     this call hand over the full refname to the ref-filter code, but
> >     tell it that %(refname) should default to strip=2. And then anybody
> >     who wants the full name can use %(refname:strip=0).
> >
> 
> Doesn't this make things more complicated? Those callers of git for-each-ref,
> wouldn't our changes like this destroy them?

My proposal was that we'd have a specific flag in ref-filter to say
"default refname:strip to this value". And then _only_ "tag --verify"
would set that (to "2"), leaving for-each-ref, etc unaffected.

So yes, it's complicated. And it must be explained to the user that
"%(refname)" behaves slightly differently with "git tag --verify", but
that is unavoidable if we do not want to break scripts (it _already_
behaves slightly differently, and we just never told anyone).

The other option is to declare the current behavior a bug and fix it. I
am quite tempted by that route, given the inconsistency with other
formatters, including even "git tag --list --format=%(refname)"!

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-10 14:26             ` Jeff King
@ 2021-09-15 12:27               ` ZheNing Hu
  2021-09-15 14:23                 ` ZheNing Hu
  2021-09-16 21:31                 ` Jeff King
  0 siblings, 2 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-15 12:27 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月10日周五 下午10:26写道:
>
> On Thu, Sep 09, 2021 at 10:45:15PM +0800, ZheNing Hu wrote:
>
> > @@ -2735,6 +2723,7 @@ void pretty_print_ref(const char *name, const
> > struct object_id *oid,
> >
> >         ref_item = new_ref_array_item(name, oid);
> >         ref_item->kind = ref_kind_from_refname(name);
> > +       read_ref_full(name, 0, NULL, &ref_item->flag);
> >         if (format_ref_array_item(ref_item, format, &output, &err))
> >                 die("%s", err.buf);
> >         fwrite(output.buf, 1, output.len, stdout);
>
> IMHO this is the wrong place to do it, since the caller may already have
> the flags (and looking up the ref again is a non-trivial cost).
>

Well, but not doing this means that we have to pass the flag from the
pretty_print_ref() call stack.

> The caller in builtin/tag.c should switch to using read_ref_full() and
> pass in the flags.
>

Agree.

> The caller in builtin/verify-tag.c _probably_ should resolve the ref in
> the same way and pass in that full refname and flags. I do worry that
> this may be a compatibility problem, but the current behavior seems so
> broken to me.
>

Yeah.

> > >   - I suspect people may be relying on the current behavior. The
> > >     original was added to be able to compare the internal tagname to the
> > >     refname. I.e., that:
> > >
> > >       git tag -v --format='%(refname) %(tag)' foo
> > >
> > >     would show "foo foo". Now that _should_ be "%(refname:strip=2)", I
> > >     think, but we'd probably be breaking scripts. OTOH, it really feels
> > >     like _not_ handing over a real, fully-qualified refname to the
> > >     ref-filter code will mean other things are broken (e.g.,
> > >     ATOM_UPSTREAM is assuming we have a fully-qualified ref).
> > >
> >
> > This is indeed a sad thing: A bug becomes a feature.
> >
> > >     I think a backwards-compatible way of fixing it would be to have
> > >     this call hand over the full refname to the ref-filter code, but
> > >     tell it that %(refname) should default to strip=2. And then anybody
> > >     who wants the full name can use %(refname:strip=0).
> > >
> >
> > Doesn't this make things more complicated? Those callers of git for-each-ref,
> > wouldn't our changes like this destroy them?
>
> My proposal was that we'd have a specific flag in ref-filter to say
> "default refname:strip to this value". And then _only_ "tag --verify"
> would set that (to "2"), leaving for-each-ref, etc unaffected.
>

Indeed this may be a feasible solution. I will try to do this first.

> So yes, it's complicated. And it must be explained to the user that
> "%(refname)" behaves slightly differently with "git tag --verify", but
> that is unavoidable if we do not want to break scripts (it _already_
> behaves slightly differently, and we just never told anyone).
>
> The other option is to declare the current behavior a bug and fix it. I
> am quite tempted by that route, given the inconsistency with other
> formatters, including even "git tag --list --format=%(refname)"!

I don't know, I think both fix methods are okay.

>
> -Peff

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-15 12:27               ` ZheNing Hu
@ 2021-09-15 14:23                 ` ZheNing Hu
  2021-09-16 21:45                   ` Jeff King
  2021-09-16 21:31                 ` Jeff King
  1 sibling, 1 reply; 26+ messages in thread
From: ZheNing Hu @ 2021-09-15 14:23 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

ZheNing Hu <adlternative@gmail.com> 于2021年9月15日周三 下午8:27写道:
>
> > So yes, it's complicated. And it must be explained to the user that
> > "%(refname)" behaves slightly differently with "git tag --verify", but
> > that is unavoidable if we do not want to break scripts (it _already_
> > behaves slightly differently, and we just never told anyone).
> >

$ git tag --verify --format='verify: %(refname) %(symref)' annotated symref
verify: annotated
verify: symref
$ git tag --verify --format='verify: %(refname) %(symref)'
refs/tags/annotated refs/tags/symref
error: tag 'refs/tags/annotated' not found.
error: tag 'refs/tags/symref' not found.

$ git verify-tag --format='verify: %(refname) %(symref)' annotated
symref
verify: annotated
verify: symref
$ git verify-tag --format='verify: %(refname) %(symref)'
refs/tags/annotated refs/tags/symref
verify: refs/tags/annotated
verify: refs/tags/symref

As we can see, there is a slight difference between git tag --verify and
git verify-tag: git tag --verify can not handle refs' fullname refs/tags/*
(because read_ref_full() | read_ref() can't handle them). So, as a standard,
which characteristics should we keep?

> > The other option is to declare the current behavior a bug and fix it. I
> > am quite tempted by that route, given the inconsistency with other
> > formatters, including even "git tag --list --format=%(refname)"!
>
> I don't know, I think both fix methods are okay.
>
> >
> > -Peff
>
> Thanks.
> --
> ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-15 12:27               ` ZheNing Hu
  2021-09-15 14:23                 ` ZheNing Hu
@ 2021-09-16 21:31                 ` Jeff King
  1 sibling, 0 replies; 26+ messages in thread
From: Jeff King @ 2021-09-16 21:31 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Wed, Sep 15, 2021 at 08:27:15PM +0800, ZheNing Hu wrote:

> > > @@ -2735,6 +2723,7 @@ void pretty_print_ref(const char *name, const
> > > struct object_id *oid,
> > >
> > >         ref_item = new_ref_array_item(name, oid);
> > >         ref_item->kind = ref_kind_from_refname(name);
> > > +       read_ref_full(name, 0, NULL, &ref_item->flag);
> > >         if (format_ref_array_item(ref_item, format, &output, &err))
> > >                 die("%s", err.buf);
> > >         fwrite(output.buf, 1, output.len, stdout);
> >
> > IMHO this is the wrong place to do it, since the caller may already have
> > the flags (and looking up the ref again is a non-trivial cost).
> >
> 
> Well, but not doing this means that we have to pass the flag from the
> pretty_print_ref() call stack.

Right. But there are only two callers of that function, so I don't think
it's a big imposition to require it.

> > My proposal was that we'd have a specific flag in ref-filter to say
> > "default refname:strip to this value". And then _only_ "tag --verify"
> > would set that (to "2"), leaving for-each-ref, etc unaffected.
> >
> 
> Indeed this may be a feasible solution. I will try to do this first.

Great, thanks for taking a look at it.

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-15 14:23                 ` ZheNing Hu
@ 2021-09-16 21:45                   ` Jeff King
  2021-09-20  7:42                     ` ZheNing Hu
  0 siblings, 1 reply; 26+ messages in thread
From: Jeff King @ 2021-09-16 21:45 UTC (permalink / raw)
  To: ZheNing Hu; +Cc: Git List

On Wed, Sep 15, 2021 at 10:23:43PM +0800, ZheNing Hu wrote:

> ZheNing Hu <adlternative@gmail.com> 于2021年9月15日周三 下午8:27写道:
> >
> > > So yes, it's complicated. And it must be explained to the user that
> > > "%(refname)" behaves slightly differently with "git tag --verify", but
> > > that is unavoidable if we do not want to break scripts (it _already_
> > > behaves slightly differently, and we just never told anyone).
> > >
> 
> $ git tag --verify --format='verify: %(refname) %(symref)' annotated symref
> verify: annotated
> verify: symref
> $ git tag --verify --format='verify: %(refname) %(symref)'
> refs/tags/annotated refs/tags/symref
> error: tag 'refs/tags/annotated' not found.
> error: tag 'refs/tags/symref' not found.

This is expected. When you provide a tag name on the command line of
"git tag" it is assumed to be a non-qualified name in refs/tags/ (and
ditto for git-branch and refs/heads/). It is tempting to try to be
friendly and accept fully-qualified refs there, but it would create
ambiguities (e.g., you could really have refs/tags/refs/tags/foo as a
ref).

I think we can ignore that for our purposes here, though. It's a
question of input from the command-line, and we focus on just the output
that we produce.

> $ git verify-tag --format='verify: %(refname) %(symref)' annotated
> symref
> verify: annotated
> verify: symref
> $ git verify-tag --format='verify: %(refname) %(symref)'
> refs/tags/annotated refs/tags/symref
> verify: refs/tags/annotated
> verify: refs/tags/symref
> 
> As we can see, there is a slight difference between git tag --verify and
> git verify-tag: git tag --verify can not handle refs' fullname refs/tags/*
> (because read_ref_full() | read_ref() can't handle them). So, as a standard,
> which characteristics should we keep?

Whereas are you notice here, verify-tag takes any name (which could be
fully qualified), and uses it as-is. In fact, it might not even be a ref
at all! You can say "git verify-tag c06b72d02" if you want to. And as a
plumbing tool, we should make sure this continues to work. For example,
careful scripts may resolve a ref into an object, and want to continue
talking about that object without worrying about the ref being changed
simultaneously.

But it also creates a weirdness for "git verify-tag --format". We do not
necessarily even have a ref to show. So IMHO the feature is somewhat
mis-designed in the first place. But we should probably continue to
support it as best we can.

The best I can come up with is:

  - when we resolve the name, if it was a ref, we should record that.
    I think this is hard to do now. It would probably require
    get_oid_with_context() learning to report on the results it got from
    dwim_ref().

  - if we have a refname, then feed it to pretty_print_ref() as a
    fully-qualified name. And pass whatever "default lstrip=2" magic we
    come up with for "git tag --verify". That would mean that "git
    verify-tag --format=%(refname) v2.33.0" would behave the same before
    and after.

  - if we didn't get a refname, then...I guess continue to pass the name
    the user gave us into pretty_print_ref()? That would keep "git
    verify-tag --format=%(refname) c06b72d02" working as it does today.

The alternative is to do none of those things, and just document that
"verify-tag" is weird:

  - its %(refname) reports whatever you gave it, whether it is a ref or
    not

  - some advanced format placeholders like %(symref) may not work if you
    don't pass a fully-qualified ref

-Peff

^ permalink raw reply	[flat|nested] 26+ messages in thread

* Re: [PATCH 1/2] ref-filter: hacky "streaming" mode
  2021-09-16 21:45                   ` Jeff King
@ 2021-09-20  7:42                     ` ZheNing Hu
  0 siblings, 0 replies; 26+ messages in thread
From: ZheNing Hu @ 2021-09-20  7:42 UTC (permalink / raw)
  To: Jeff King; +Cc: Git List

Jeff King <peff@peff.net> 于2021年9月17日周五 上午5:45写道:
>
> On Wed, Sep 15, 2021 at 10:23:43PM +0800, ZheNing Hu wrote:
>
> > ZheNing Hu <adlternative@gmail.com> 于2021年9月15日周三 下午8:27写道:
> > >
> > > > So yes, it's complicated. And it must be explained to the user that
> > > > "%(refname)" behaves slightly differently with "git tag --verify", but
> > > > that is unavoidable if we do not want to break scripts (it _already_
> > > > behaves slightly differently, and we just never told anyone).
> > > >
> >
> > $ git tag --verify --format='verify: %(refname) %(symref)' annotated symref
> > verify: annotated
> > verify: symref
> > $ git tag --verify --format='verify: %(refname) %(symref)'
> > refs/tags/annotated refs/tags/symref
> > error: tag 'refs/tags/annotated' not found.
> > error: tag 'refs/tags/symref' not found.
>
> This is expected. When you provide a tag name on the command line of
> "git tag" it is assumed to be a non-qualified name in refs/tags/ (and
> ditto for git-branch and refs/heads/). It is tempting to try to be
> friendly and accept fully-qualified refs there, but it would create
> ambiguities (e.g., you could really have refs/tags/refs/tags/foo as a
> ref).
>

Yeah, maybe you are right, for git tag --verify, there may have ambiguities.
But for git verify-tag, if we have tags like "refs/tags/refs/tags/foo" and
"refs/tags/foo":

$ git verify-tag --format='verify: %(refname) %(symref)' refs/tags/foo
warning: refname 'refs/tags/foo' is ambiguous.

We see the ambiguities too here.

> I think we can ignore that for our purposes here, though. It's a
> question of input from the command-line, and we focus on just the output
> that we produce.
>

Yeah, but using different functions (read_ref_full(), get_oid()) will
affect what
kind of input we can provide.

> > $ git verify-tag --format='verify: %(refname) %(symref)' annotated
> > symref
> > verify: annotated
> > verify: symref
> > $ git verify-tag --format='verify: %(refname) %(symref)'
> > refs/tags/annotated refs/tags/symref
> > verify: refs/tags/annotated
> > verify: refs/tags/symref
> >
> > As we can see, there is a slight difference between git tag --verify and
> > git verify-tag: git tag --verify can not handle refs' fullname refs/tags/*
> > (because read_ref_full() | read_ref() can't handle them). So, as a standard,
> > which characteristics should we keep?
>
> Whereas are you notice here, verify-tag takes any name (which could be
> fully qualified), and uses it as-is. In fact, it might not even be a ref
> at all! You can say "git verify-tag c06b72d02" if you want to. And as a
> plumbing tool, we should make sure this continues to work. For example,
> careful scripts may resolve a ref into an object, and want to continue
> talking about that object without worrying about the ref being changed
> simultaneously.
>

Yes, this feature is very bad. %(refname) seems to do the %(objectname)
work.


> But it also creates a weirdness for "git verify-tag --format". We do not
> necessarily even have a ref to show. So IMHO the feature is somewhat
> mis-designed in the first place. But we should probably continue to
> support it as best we can.
>
> The best I can come up with is:
>
>   - when we resolve the name, if it was a ref, we should record that.
>     I think this is hard to do now. It would probably require
>     get_oid_with_context() learning to report on the results it got from
>     dwim_ref().
>
>   - if we have a refname, then feed it to pretty_print_ref() as a
>     fully-qualified name. And pass whatever "default lstrip=2" magic we
>     come up with for "git tag --verify". That would mean that "git
>     verify-tag --format=%(refname) v2.33.0" would behave the same before
>     and after.
>
>   - if we didn't get a refname, then...I guess continue to pass the name
>     the user gave us into pretty_print_ref()? That would keep "git
>     verify-tag --format=%(refname) c06b72d02" working as it does today.
>
> The alternative is to do none of those things, and just document that
> "verify-tag" is weird:
>
>   - its %(refname) reports whatever you gave it, whether it is a ref or
>     not
>
>   - some advanced format placeholders like %(symref) may not work if you
>     don't pass a fully-qualified ref
>
> -Peff

This is my solution according to your above suggection:
https://lore.kernel.org/git/pull.1042.git.1632123476.gitgitgadget@gmail.com/

Thanks.
--
ZheNing Hu

^ permalink raw reply	[flat|nested] 26+ messages in thread

end of thread, other threads:[~2021-09-20  7:42 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-04 12:40 [hacky PATCH 0/2] speeding up trivial for-each-ref invocations Jeff King
2021-09-04 12:41 ` [PATCH 1/2] ref-filter: hacky "streaming" mode Jeff King
2021-09-05  8:20   ` ZheNing Hu
2021-09-05 13:04     ` Jeff King
2021-09-07  5:28       ` ZheNing Hu
2021-09-07 18:01         ` Jeff King
2021-09-09 14:45           ` ZheNing Hu
2021-09-10 14:26             ` Jeff King
2021-09-15 12:27               ` ZheNing Hu
2021-09-15 14:23                 ` ZheNing Hu
2021-09-16 21:45                   ` Jeff King
2021-09-20  7:42                     ` ZheNing Hu
2021-09-16 21:31                 ` Jeff King
2021-09-05 13:15     ` Jeff King
2021-09-07  5:42       ` ZheNing Hu
2021-09-04 12:42 ` [PATCH 2/2] ref-filter: implement "quick" formats Jeff King
2021-09-05  8:20   ` ZheNing Hu
2021-09-05 13:07     ` Jeff King
2021-09-06 13:34       ` ZheNing Hu
2021-09-07 20:06       ` Junio C Hamano
2021-09-05  8:19 ` [hacky PATCH 0/2] speeding up trivial for-each-ref invocations ZheNing Hu
2021-09-05 12:49   ` Jeff King
2021-09-06 13:30     ` ZheNing Hu
2021-09-07 17:28       ` Jeff King
2021-09-09 13:20         ` ZheNing Hu
2021-09-06  6:54 ` Patrick Steinhardt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).