diff mbox series

[2/2] ref-filter: implement "quick" formats

Message ID YTNps0YBOaRNvPzk@coredump.intra.peff.net (mailing list archive)
State New, archived
Headers show
Series speeding up trivial for-each-ref invocations | expand

Commit Message

Jeff King Sept. 4, 2021, 12:42 p.m. UTC 
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(+)

Comments

ZheNing Hu Sept. 5, 2021, 8:20 a.m. UTC | #1 
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/
Jeff King Sept. 5, 2021, 1:07 p.m. UTC | #2 
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
ZheNing Hu Sept. 6, 2021, 1:34 p.m. UTC | #3 
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
Junio C Hamano Sept. 7, 2021, 8:06 p.m. UTC | #4 
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.
diff mbox series

Patch

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 }