Re: [PATCH 2/2] --pretty=format: on-demand format expansion

On Fri, Nov 09, 2007 at 01:49:42AM +0100, René Scharfe wrote:

I think this is definitely the right approach, but there are some format strings where the performance will be worse. Specifically:

  - formatting expensive items multiple times will incur work
    proportional to the number of times the item is used (in the old
    code, it was calculated just once).  e.g., "%h%h%h%h"

  - formatting some items goes to some work that can be re-used by other
    items (e.g., %ad and %ar both need to parse the author date)

And we could obviously overcome both by caching the results of expensive operations. I'm not sure if these will be a problem in practice. For the first one, the new code is so much faster that I needed to do

  git-log --pretty=format:%h%h%h%h%h%h%h%h

to get a performance regression from the old code, which seems rather unlikely. For the second, it is easy to imagine multiple "person" items being used together, although their cost to produce is not all that high. It looks like about .05 seconds to parse a date (over all commits in git.git):

$ time ./git-log --pretty='format:' >/dev/null real 0m0.441s user 0m0.424s sys 0m0.004s

$ time ./git-log --pretty='format:%ad' >/dev/null real 0m0.477s user 0m0.472s sys 0m0.000s

$ time ./git-log --pretty='format:%ad %aD' >/dev/null real 0m0.527s user 0m0.520s sys 0m0.004s

where the last two could probably end up costing about the same if we cached the author parsing (but the caching will have a cost, too, so it might not end up being a big win).

So it might make sense to cache some items as we figure them out. This should be done by the calling code and not by strbuf_expand (since it doesn't know which things are worth caching (and for fast things, allocating memory for a cache entry is likely to be slower), or how the expansions relate to each other).

A partial patch on top of yours is below (it caches commit and tree abbreviations; parent abbreviations and person-parsing are probably worth doing). Some timings:

Null format (these are average-looking runs; the differences got lost in the noise):

# your patch $ time git-log --pretty=format: >/dev/null real 0m0.409s user 0m0.384s sys 0m0.012s

# with my patch $ time ./git-log --pretty=format: >/dev/null real 0m0.413s user 0m0.404s sys 0m0.004s

Single abbrev lookup (mine should be slightly slower because of malloc/free of cache):

# your patch $ time git-log --pretty=format:%h >/dev/null real 0m0.536s user 0m0.456s sys 0m0.080s

# with my patch $ time ./git-log --pretty=format:%h >/dev/null real 0m0.553s user 0m0.464s sys 0m0.088s

Two abbrev lookups (I win by a little bit, but definitely not lost in the noise):

# your patch $ time git-log --pretty=format:%h%h >/dev/null real 0m0.671s user 0m0.496s sys 0m0.144s

# my patch $ time ./git-log --pretty=format:%h%h >/dev/null real 0m0.567s user 0m0.480s sys 0m0.080s

And of course I can make pathological cases where mine wins hands down (on "%h%h%h%h%h%h%h%h", mine stays the same but yours bumps to 1.2s).

So I think this is probably worth doing. Even if doubled work isn't the
common case,
  1. It doesn't hurt the common case much at all (I think on average it
     is slower, but the timings were totally lost in the noise)
  2. It has a measurable impact on reasonable cases (like just using an
     expensive substitution twice)
  3. It has a huge impact on pathological cases (though I'm not sure we
     care about those that much)
  4. It's very little extra code, and it should be obvious to read. It
     also documents the technique for other users of strbuf_expand,
     where the "doubled" cases may be more common.

-Peff

---
 pretty.c |   47 ++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 40 insertions(+), 7 deletions(-)