patch, 4 partspeel_ref: use faster deref_tag_noverify

On Thu, Oct 04, 2012 at 01:54:47AM +0200, Ævar Arnfjörð Bjarmason wrote:

Here's a cleaned-up version. I realized that peel_ref actually is quite close to what we want; the key thing is that when you are calling it from a for_each_ref loop it will not only use peeled information from packed-refs (if available), but it will also short-circuit the ref lookup for non-packed refs. So it really does what we want.

I put some timings into the final patch. The results are very satisfying from a pure numbers standpoint. However, I'm not 100% sure this is all that useful a benchmark. The repos where you get a noticeable benefit are quite big, so I suspect the time to send the advertisements out over the wire will dominate. Still, a CPU second saved is a CPU second earned.

And the series actually ends up making the code cleaner and shares some of the optimizations I put into upload-pack with other users of peel_ref. So I think I'd be inclined to use it, even if the speedup doesn't help that much in practice. We'll see what others think.

  [1/4]: peel_ref: use faster deref_tag_noverify
  [2/4]: peel_ref: do not return a null sha1
  [3/4]: peel_ref: check object type before loading
  [4/4]: upload-pack: use peel_ref for ref advertisements

-Peff

When we are asked to peel a ref to a sha1, we internally call deref_tag, which will recursively parse each tagged object until we reach a non-tag. This has the benefit that we will verify our ability to load and parse the pointed-to object.

However, there is a performance downside: we may not need to load that object at all (e.g., if we are listing peeled simply listing peeled refs), or it may be a large object that should follow a streaming code path (e.g., an annotated tag of a large blob).

It makes more sense for peel_ref to choose the fast thing rather than performing the extra check, for two reasons:

  1. We will already sometimes short-circuit the tag parsing
     in favor of a peeled entry from a packed-refs file. So
     we are already favoring speed in some cases, and it is
     not wise for a caller to rely on peel_ref to detect
     corruption.

  2. We already silently ignore much larger corruptions,
     like a ref that points to a non-existent object, or a
     tag object that exists but is corrupted.

  2. peel_ref is not the right place to check for such a
     database corruption. It is returning only the sha1
     anyway, not the actual object. Any callers which use
     that sha1 to load an object will soon discover the
     corruption anyway, so we are really just pushing back
     the discovery to later in the program.

Signed-off-by: Jeff King <peff@peff.net>
---
This is basically bringing the optimization from 90108a2 (upload-pack:
avoid parsing tag destinations, 2012-01-06) to users of peel_ref.

 refs.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Jeff King <peff@peff.net> writes:

Both correct.

I checked the existing callsites and nobody seems to assume that it can use the pointed-to object without checking because peel_ref has already checked, so it makes sense.

The idea of the peel_ref function is to dereference tag objects recursively until we hit a non-tag, and return the sha1. Conceptually, it should return 0 if it is successful (and fill in the sha1), or -1 if there was nothing to peel.

However, the current behavior is much more confusing. For a regular loose ref, the behavior is as described above. But there is an optimization to reuse the peeled-ref value for a ref that came from a packed-refs file. If we have such a ref, we return its peeled value, even if that peeled value is null (indicating that we know the ref definitely does _not_ peel).

It might seem like such information is useful to the caller, who would then know not to bother loading and trying to peel the object. Except that they should not bother loading and trying to peel the object _anyway_, because that fallback is already handled by peel_ref. In other words, the whole point of calling this function is that it handles those details internally, and you either get a sha1, or you know that it is not peel-able.

This patch catches the null sha1 case internally and converts it into a -1 return value (i.e., there is nothing to peel). This simplifies callers, which do not need to bother checking themselves.

Two callers are worth noting:

  - in pack-objects, a comment indicates that there is a
    difference between non-peelable tags and unannotated
    tags. But that is not the case (before or after this
    patch). Whether you get a null sha1 has to do with
    internal details of how peel_ref operated.

  - in show-ref, if peel_ref returns a failure, the caller
    tries to decide whether to try peeling manually based on
    whether the REF_ISPACKED flag is set. But this doesn't
    make any sense. If the flag is set, that does not
    necessarily mean the ref came from a packed-refs file
    with the "peeled" extension. But it doesn't matter,
    because even if it didn't, there's no point in trying to
    peel it ourselves, as peel_ref would already have done
    so. In other words, the fallback peeling is guaranteed
    to fail.

Signed-off-by: Jeff King <peff@peff.net>
---
Sorry for the long-winded explanation. I'd love it if somebody could
eyeball the code and make sure what I wrote above is correct. I was
mightily confused at first by the way that some of the callers treated
the return value. I think it is simply a case of code growing crufty as
features were added (originally the packed-refs optimization did not
exist, and was bolted on later), but I may have mis-read something.

 builtin/describe.c     |  2 +-
 builtin/pack-objects.c |  1 -
 builtin/show-ref.c     | 23 +++--------------------
 refs.c                 |  2 ++
 4 files changed, 6 insertions(+), 22 deletions(-)

Jeff King <peff@peff.net> writes:

Yeah, this is what I was wondering while reviewing [1/4].

We traditionally said both HEAD^0 and HEAD^0^0 peel to HEAD, but this at least at the internal API level redefines them to "these do not peel at all and is a failure". In other words, peel_ref(ref, sha1) that returns 0 is a way to see if ref points at a real tag object, and if the function returns non-zero, the caller cannot tell if the failure is because it was a valid commit or a corrupt object.

The check !is_null_sha1(peeled) always looked fishy to me. Good riddance.

The point of peel_ref is to dereference tags; if the base object is not a tag, then we can return early without even loading the object into memory.

This patch accomplishes that by checking sha1_object_info for the type. For a packed object, we can get away with just looking in the pack index. For a loose object, we only need to inflate the first couple of header bytes.

This is a bit of a gamble; if we do find a tag object, then we will end up loading the content anyway, and the extra lookup will have been wasteful. However, if it is not a tag object, then we save loading the object entirely. Depending on the ratio of non-tags to tags in the input, this can be a minor win or minor loss.

However, it does give us one potential major win: if a ref points to a large blob (e.g., via an unannotated tag), then we can avoid looking at it entirely.

Signed-off-by: Jeff King <peff@peff.net>
---
This optimization is the one that gave me the most pause. While
upload-pack does call peel_ref on everything, the other callers all
constrain themselves to refs/tags/. So for many projects, we will be
calling it mostly on annotated tags, and it may be a very small net
loss. But in practice, it will not matter for most projects with a sane
number of normal tags, and saving even one accidental giant blob load
can have a huge impact.

 refs.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

Jeff King <peff@peff.net> writes:

We look at the pack index and have to follow its delta chain down to the base to find its type; if the object is deeply deltified, this certainly is an overall loss.

The only case sha1_object_info() could work well for an object near the tip of a deep delta chain is to find its size, as the diff-delta encodes the size of the base and the size of the result of applying the delta to the base, so you do not have to follow the chain when you are only interested in the final size.

But alas nobody calls sha1_object_info() for only size but not type (there are some callers that are interested in only type but not size).

I may be missing something, but the above description is not convincing to me. When was the last time you pointed a blob directly with a ref, whether large or small, and whether within refs/tags or outside?

On Thu, Oct 04, 2012 at 12:06:16PM -0700, Junio C Hamano wrote:

Yes. Although in practice I would expect most things pointed to by refs to not be delta'd. And indeed, comparing "git index-pack -v" to "git for-each-ref" in my git.git repository yields 950 non-delta tips and only 42 delta (and those are mostly rebased commit objects). In my linux-2.6 repo, I have 0 delta ref tips (probably because I do not actually do kernel work, but keep it around for querying).

The numbers I mentioned in 926f1dd (which did this exact same optimization for upload-pack) showed a slight improvement in practice. Because keep in mind that the alternative to this multi-step delta lookup for the type is to load the object. Which will do the _same_ lookup, but will also have to actually compute the delta.

So the only real loss is that you have to repeat the lookup (or in the case of a loose object, re-open and re-inflate the first 32 bytes). The best way to do this would be to have sha1_object_info return some kind of handle to the object where we could get the meta info cheaply, and then reuse the handle to get the actual object data later (so for a packed object, cache the actual pack location; for a loose object, keep the descriptor and zlib stream open).

Of course, the speed up in 926f1dd probably won't matter anymore because the whole point of this series is to avoid touching the object at all. So hitting sha1_object_info in peel_ref is already the slow path. On most objects, an optimization like this will not be noticeable either way. The interesting thing is that we can avoid touching a large or expensive object at all.

Not often (though you have such a ref in git.git). I started down this road because just applying patch 4/4 produces a regression in the test suite. t1050 tries to clone a tag pointing to a large object with GIT_ALLOC_LIMIT set. Using peel_ref regresses this to actually load the whole object into memory.

That particular regression is fixed by 1/1 (because it's an annotated tag pointing to the large object). This would fix the same case if it were an unannotated tag.

Now is that a real-world test? No, I'm not sure it is. But I consider it a win for large-object git[1] every time we can avoid loading an object, because it only takes one unnecessary load to ruin the user experience. So even if it's unlikely, if it isn't hurting the regular code path, I think it's worth doing (and I'm not sure it is hurting; my numbers showed that it be helping, though I suspect it is doing nothing after my 4/4).

-Peff

[1] One thing I've been toying is with "external alternates"; dumping
    your large objects in some realtively slow data store (e.g., a
    RESTful HTTP service). You could cache and cheaply query a list of
    "sha1 / size / type" for each object from the store, but getting the
    actual objects would be much more expensive. But again, it would
    depend on whether you would actually have such a store directly
    accessible by a ref.

Jeff King <peff@peff.net> writes:

Yeah, that actually has been another thing we were discussing locally, without coming to something concrete enough to present to the list.

The basic idea is to mark such paths with attributes, and use a variant of smudge/clean filter that is _not_ a filter (as we do not want to have the interface to this external helper to be "we feed the whole big blob to you"). Instead, these smudgex/cleanx things work on a pathname.

 - Your in-tree objects store a blob that records a description of
   the large thing.  Call such a blob a surrogate.  "clone", "fetch"
   and "push" all deal only with surrogates so your in-history data
   will stay small.

 - When checking out, the attributes mechanism kicks in and runs the
   "not filter" variant of smudge with the data in the surrogate.

   The surrogate records how to get the real thing from where, and
   how to validate what you got is correct.  A hand-wavy example may
   look like this:

   	get: download http://cdn.example.com/67def20
        sha1sum: f84667def209e4a84e37e8488a08e9eca3f208c1

   to tell you to download a single URL with whatever means suitable
   for your platform (perhaps curl or wget), and verify the result
   by running sha1sum.  Or it may involve

	get: git-fetch git://git.example.com/images.git/ master
        object: 85a094f22f02c54c740448f6716da608a5e89a80

   to tell you to "git fetch" from the given git-reachable resource
   into some place and grab the object via "git cat-file", possibly
   streaming it out.  The details do not matter at this point in the
   design process.

   The smudgex helper is responsible for caching previously fetched
   large contents, maintaining association between the surrogate
   blob and its real data, so that once the real thing is
   downloaded, and the contents of the path needs to change to
   something else (e.g. user checks out a different branch) and
   then change to the previous thing again (e.g. user comes back to
   the original branch), it does not download it again.

 - When checking if the working tree is clean relative to the index,
   the smudgex/cleanx helper will be consulted.  It will be given
   the surrogate data in the index and the path in the working tree.
   We may want to allow the helper implementation to give a read-only
   hardlink directly into helper's cache storage, so that it can
   consult its database of surrogate-to-real mapping and perform
   this verification cheaply by inode comparison, or something.

 - When running "git add" a modified large stuff prepared in the
   working tree, cleanx helper is called to prepare a new surrogate,
   and that is what is registered in the index.  The helper is also
   responsible for storing the new large stuff away and arrange it
   to be retrievable when others see and use this surrogate.

The initial scope of supporting something like that in core-git would be to add the necessary infrastracture to arrange such smudgex and cleanx helpers are called when a path is marked as a surrogate in the attribute system, and supply a sample helper.

On Thu, Oct 04, 2012 at 01:41:40PM -0700, Junio C Hamano wrote:

There are a few ways that smudge/clean filters are not up to the task currently. One is definitely the efficiency of the interface.

Another is that this distinction is not "canonical in-repo versus working tree representation". Yes, part of it is about what you store in the repo versus what you checkout. But you may also want to diff or merge these large items. Almost certainly not with the internal text tools, but you might want to feed the _real_ blobs (not the fake surrogates) to external tools, and smudge and clean are not a natural fit for that. If you teach the external tools to dereference the surrogates, it would work. I think you could also get around it by giving these smudgex/cleanx filters slightly different semantics.

But the thing I most dislike about a solution like this is that the representation pollutes git's data model. That is, git stores a blob representing the surrogate, and that is the official sha1 that goes into the tree. That means your surrogate decisions are locked into history forever, which has a few implications:

  1. If I store a surrogate and you store the real blob, we do not get
     the same tree (and in fact get conflicts).

  2. Once I store a blob, I can never revise my decision not to store
     that blob in every subsequent clone without rewriting history. I
     can convert it into a surrogate, but old versions of that blob will
     always be required for object connectivity.

  3. If your surrogate contains more than just the sha1 (e.g., if it
     points to http://cdn.example.com), your history is forever tied to
     that (and you are stuck with configuring run-time redirects if your
     URL changes).

My thinking was to make it all happen below the git object level, at the same level as packs and loose objects. This is more invasive to git, but much more flexible.

The basic implementation is pretty straightforward. You configure one or more helpers which have two operations: provide a list of sha1s, and fetch a single sha1. Whenever an object lookup fails in the packs and loose objects, we check the helper lists. We can cache the lists in some mmap'able format similar to a pack index, so we can do quick checks for object existence, type, and size. And if the lookup actually needs the object, we fetch and cache (where the caching policy would all be determined by the external script).

The real challenges are:

  1. It is expensive to meet normal reachability guarantees. So you
     would not want a remote to delta against a blob that you _could_
     get, but do not have.

  2. You need to tell remotes that you can access some objects in a
     different way, and not to send them as part of an object transfer.

  3. Many commands need to be taught not to load objects carelessly. For
     the most part, we do well with this because it's already expensive
     to load large objects from disk. I think we've got most of them on
     the diff code path, but I wouldn't be surprised if one or two more
     crop up. Fsck would need to learn to handle these objects
     differently.

Item (3) is really just about trying it and seeing where the problems come up. For items (1) and (2), we'd need a protocol extension.

Having the receiver send something like "I have these blobs from my external source, don't send them" is a nice idea, but it doesn't scale well (you have to advertise the whole list for each transfer, because the receiver doesn't know which ones are actually referenced).

Having the receiver say "I have access to external database $FOO, go check the list of objects there and don't send anything it has" unnecessarily ties the sender to the external database (i.e., they have to implement $FOO for it to work).

Something simple like "do not send blobs larger than N bytes, nor make deltas against such blobs" would work. It does mean that your value of N really needs to match up with what goes into your external database, but I don't think that will be a huge problem in practice (after the transfer you can do a consistency check that between the fetched objects and the external db, you have everything).

All of what you wrote seems very sane; I think the real question is whether this should be "above" or "below" git's user-visible data model layer.

-Peff

When upload-pack advertises refs, we attempt to peel tags and advertise the peeled version. We currently hand-roll the tag dereferencing, and use as many optimizations as we can to avoid loading non-tag objects into memory.

Not only has peel_ref recently learned these optimizations, too, but it also contains an even more important one: it has access to the "peeled" data from the pack-refs file. That means we can avoid not only loading annotated tags entirely, but also avoid doing any kind of object lookup at all.

This cut the CPU time to advertise refs by 50% in the linux-2.6 repo, as measured by:

  echo 0000 | git-upload-pack . >/dev/null

best-of-five, warm cache, objects and refs fully packed:

  [before]             [after]
  real    0m0.026s     real    0m0.013s
  user    0m0.024s     user    0m0.008s
  sys     0m0.000s     sys     0m0.000s

Those numbers are irrelevantly small compared to an actual fetch. Here's a larger repo (400K refs, of which 12K are unique, and of which only 107 are unique annotated tags):

  [before]             [after]
  real    0m0.704s     real    0m0.596s
  user    0m0.600s     user    0m0.496s
  sys     0m0.096s     sys     0m0.092s

This shows only a 15% speedup (mostly because it has fewer actual tags to parse), but a larger absolute value (100ms, which isn't a lot compared to a real fetch, but this advertisement happens on every fetch, even if the client is just finding out they are completely up to date).

In truly pathological cases, where you have a large number of unique annotated tags, it can make an even bigger difference. Here are the numbers for a linux-2.6 repository that has had every seventh commit tagged (so about 50K tags):

  [before]             [after]
  real    0m0.443s     real    0m0.097s
  user    0m0.416s     user    0m0.080s
  sys     0m0.024s     sys     0m0.012s

Signed-off-by: Jeff King <peff@peff.net>
---
 upload-pack.c | 14 +++-----------
 1 file changed, 3 insertions(+), 11 deletions(-)

On Thu, Oct 04, 2012 at 03:56:09AM -0400, Jeff King wrote:

I included my own timings in the final one, but my "pathological" case at the end is a somewhat made-up attempt to emulate what you described. Can you double-check that this series still has a nice impact on your real-world repository?

-Peff

On Thu, Oct 4, 2012 at 10:04 AM, Jeff King <peff@peff.net> wrote:

It does, here's best of five for, all compiled with -g -O3:

v1.7.8:

    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)
    3.49MB 0:00:00 [ 5.3MB/s] [  <=>

           ]

    real    0m0.660s
    user    0m0.604s
    sys     0m0.248s

master without your patches:

    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)
    3.49MB 0:00:00 [10.2MB/s] [  <=>

           ]

    real    0m0.344s
    user    0m0.300s
    sys     0m0.172s

master with your patches:

    $ time (echo 0000 | ~/g/git/git-upload-pack . | pv >/dev/null)
    3.49MB 0:00:00 [31.8MB/s] [  <=>

           ]

    real    0m0.113s
    user    0m0.088s
    sys     0m0.088s

On Thu, Oct 4, 2012 at 5:01 PM, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Totally off-topic, but ...

Thanks for making me look up what pv is. I remember checking it out quiet sometime ago and have forgotten about it altogether.

Now I can replace my poorly written, half-assed attempt at a shell script to do something similar to what pv is already capable of!

Nazri.