patch, 3 partsfast textconv

The normal textconv procedure is to dump the binary file to a tempfile (optionally using a working tree file if available), then run the textconv helper to produce a textual version on stdout. This is a very convenient interface, as helpers don't need to be aware of git at all and many standard commands can be used without wrappers.

Unfortunately, it can be slow for large binary files. We spool the file to disk before invoking the textconv helper, so the helper has no way to do any optimizations. For example, the helper may need only part of the file (e.g., when showing metadata at the beginning of a media file), or it may implement a caching scheme to avoid repeating expensive conversions.

This series introduces a "fast textconv", which does not automatically spool a tempfile, but instead gives the helper program the sha1 of the blob to be converted.

Here are some timings from my photo repository, on a commit with 37 JPEGs and 8 AVIs. Each file had two lines added to its exif metadata. My textconv helper is a perl script that dumps the exif tags, and implements its own caching scheme.

  $ time git show >/dev/null ;# before patch
  real    0m13.818s
  user    0m12.137s
  sys     0m1.552s

  $ time git show >/dev/null ;# after patch, first run
  real    0m15.076s
  user    0m13.321s
  sys     0m1.772s

  $ time git show >/dev/null ;# after patch, subsequent runs
  real    0m2.502s
  user    0m1.820s
  sys     0m0.592s

So you can see a 5.5x speedup. The first run is a little bit slower, presumably due to the extra git-cat-file calls by the helper.

The speedup is purely from caching; I am not using the "we only need to read the first part of the file" optimization. My files are only a few megabytes. Probably that would be more useful for people storing files in the hundreds of megabytes, where a full cat-file will cause a lot of unwanted I/O.

There are two things I'm still not 100% happy with:

 1. 2.5 seconds is still a little slower than I would like. The slowness
    comes from the fact that my helper is written in perl, and therefore
    perl gets invoked for each diff. I could try collecting all of the
    to-be-textconv'd files at the beginning of the diff process and just
    invoking the helper once. But that means we need to store the
    results in core, and they could potentially be long (in my case,
    they are only a few hundred bytes, but somebody could potentially be
    textconv'ing a large documents).

 2. It is up to the helper to implement a caching layer. This offers a
    lot of flexibility, but it means each helper must implement its own.
    It also means we have to run the helper even for a cache hit, which
    causes slowness.

    An alternative would be for git to support textconv caching
    natively, probably by using the notes mechanism to map blob sha1's
    to their textconv'd contents. But that opens a whole can of worms
    with how the cache is managed. If I change my textconv helper to
    produce different results, how do I invalidate the cache? Should it
    happen automatically if I change the contents of
    diff.$method.textconv? Or do I need to do it manually (you will
    still need to do it manually if, e.g., you upgrade your textconv
    helper. Git can't know about that). How do I evict entries if the
    cache gets too large when notes are stored as a history?

So I'm not sure. This series works and is simple from git's perspective. But caching textconv results in notes would be faster, and easier for people to write helper scripts.

The patches are:

  [1/3]: textconv: refactor calls to run_textconv
  [2/3]: textconv: refactor to handle multiple textconv types
  [3/3]: diff: add "fasttextconv" config option

-Peff

This patch adds a fill_textconv wrapper, which centralizes some minor logic like error checking and handling the case of no-textconv.

In addition to dropping the number of lines, this will make it easier in future patches to handle multiple types of textconv.

Signed-off-by: Jeff King <peff@peff.net>
---
 diff.c |   58 ++++++++++++++++++++++++----------------------------------
 1 files changed, 24 insertions(+), 34 deletions(-)

We pass around textconv information as a string which is either NULL (no textconv) or not (and contains the textconv command). In preparation for handling multiple types of textconv interface, this patch converts it into a struct with an "interface" field.

Signed-off-by: Jeff King <peff@peff.net>
---
 diff.c     |   26 ++++++++++++++++----------
 userdiff.c |    9 ++++++++-
 userdiff.h |   12 +++++++++++-
 3 files changed, 35 insertions(+), 12 deletions(-)

The normal textconv procedure is to dump the binary file to a tempfile (optionally using a working tree file if available), then run the textconv helper to produce a textual version on stdout. This is a very convenient interface, as helpers don't need to be aware of git at all and many standard commands can be used without wrappers.

Unfortunately, it can be slow for large binary files. We spool the file to disk before invoking the textconv helper, so the helper has no way to do any optimizations. For example, the helper may need only part of the file (e.g., when showing metadata at the beginning of a media file), or it may implement a caching scheme to avoid repeating expensive conversions.

This patch introduces diff.*.fasttextconv, which invokes the textconv helper with the sha1 of the blob to be converted. The helper can then retrieve the file with git-cat-file if necessary.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/gitattributes.txt |   11 +++++++++++
 diff.c                          |   32 ++++++++++++++++++++++++++++++++
 t/t4030-diff-textconv.sh        |   15 +++++++++++++++
 userdiff.c                      |    8 +++++---
 userdiff.h                      |    1 +
 5 files changed, 64 insertions(+), 3 deletions(-)

On Sonntag, 28. März 2010, Jeff King wrote:

This conditional is somewhat dubious. If strbuf_read fails, you do not wait for the child, and a zombie remains.

The have this sequence already in run_textconv().

-- Hannes

On Sun, Mar 28, 2010 at 08:23:00PM +0200, Johannes Sixt wrote:

Ugh. I would blame the author of run_textconv, but that is also me. :)

I doubt it is a big deal in practice, as the read() call is the least likely to produce an error, and even if we do get a zombie, it will die along with the diffing process. But it is still worth fixing. Thanks for noticing.

Junio, can you apply the patch below to maint?

-- >8 --
Subject: [PATCH] diff: fix textconv error zombies

To make the code simpler, run_textconv lumps all of its error checking into one conditional. However, the short-circuit means that an error in reading will prevent us from calling finish_command, leaving a zombie child.

The cleanup requirements are actually different for each of the three error checks, so let's just write them out longhand.

Signed-off-by: Jeff King <peff@peff.net>
---
Yes, there are clever ways to make this shorter, but I think it is
clearer just written out.

 diff.c |   16 +++++++++++++---
 1 files changed, 13 insertions(+), 3 deletions(-)

To make the code simpler, run_textconv lumps all of its error checking into one conditional. However, the short-circuit means that an error in reading will prevent us from calling finish_command, leaving a zombie child. Clean up properly after errors.

Based-on-work-by: Jeff King <peff@peff.net>
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
Jeff,

Thanks for your work, but I'm worried that in your version the close() call is not before the finish_command (but that's really not _that_ important in this case). My version is perhaps not as easy to read, but has a slightly better diff-stat.

Oh, I removed the error messages after start_command and finish_command, because these two print one themselves; Junio, if you disagree with this change, ditch my version and take Jeff's.

-- Hannes

 diff.c |   17 +++++++++++------
 1 files changed, 11 insertions(+), 6 deletions(-)

Johannes Sixt <j6t@kdbg.org> writes:

Are you referring to this part in api-run-command.txt?

    This describes the arguments, redirections, and environment of a
    command to run in a sub-process.

    The caller:

    1. allocates and clears (memset(&chld, 0, sizeof(chld));) a
       struct child_process variable;
    2. initializes the members;
    3. calls start_command();
    4. processes the data;
    5. closes file descriptors (if necessary; see below);
    6. calls finish_command().

In "if necessary; see below", I tried to find something to help me judge why you said "That's really not _that_ important in this case", but I think I failed. Perhaps we would want a bit more detailed discussion in the document there?

The patch looks fine.  Thanks; will queue this one.

On Dienstag, 30. März 2010, Junio C Hamano wrote:

The "if necessary; see below" refers to the cases where the caller requests a file descriptor from start_command(). It is safe to follow the recipe. But I actually would not want to expand on the special case like we have in run_textconv, where it is not strictly necessary to close the fd before finish_command(), namely when we know that the writer will exit after it has closed its end of the pipe and the reader reads until EOF.

This could deadlock in the theoretical case that the read() in the parent returns an error even though the child is still writing data; the child would hang while waiting for the pipe being drained by the parent; but the parent would wait for the child to exit, which never happens. Doing the close() before finish_command() avoids this situation because the child dies of SIGPIPE.

But since the communication is via a pipe, and read failures are highly unlikely (and a read failure in a way that the writer does not fail, too, is even more unlikely, I think), the close() before finish_command() is "not important".

-- Hannes

On Wed, Mar 31, 2010 at 12:17:24AM +0200, Johannes Sixt wrote:

Yeah, I actually thought about that while writing the error case for strbuf_read (I do close(child.out) before finish_command). But I didn't consider it in the success case. I don't think it matters here because we will already have gotten EOF from child.out, which should mean the child is no longer writing and will not block.

So I am not sure there is any deadlock, but I am fine with your version of the patch.

-Peff

Jeff King venit, vidit, dixit 28.03.2010 16:53:

Really, "Notes!" was my first thought even before reading 2. Happy to have found a like mind :)

This would still need a mechanism where the conv helper gets the blob's SHA1 - hey, it's there in your patch...

How about:

Set fasttextconv=notestextconv

notestextconv does the following:

- If $sha1 has a note in refs/notes/bikeshed display it.
- If not create one and then display it.

In fact, the creation could be done using the textconv setting!

Pruning the cache is done be deleting the refs/notes/bikeshed ref, truncating it by truncating it's DAG (filter-branch...).

Cheers, Michael

On Sun, Mar 28, 2010 at 06:09:35PM +0200, Michael J Gruber wrote:

If I understand you right, you are proposing a separate program that you would pass as a fasttextconv helper, and that would look in a notes tree. So you would still have a per-diff fork/exec, and pipe all the data.

I was thinking of actually doing it in-core, so cache hits would be as lightweight as a notes lookup (and cache misses obviously would still fork/exec a helper, but we don't care too much since the helper's time to convert will dominate in that path).

Yeah, that would work. It just means it's one more thing the user has to deal with. I didn't want to have to introduce a "git textconv" management helper. ;)

-Peff

On Sun, Mar 28, 2010 at 12:17:28PM -0400, Jeff King wrote:

Side note: I think I might prototype it as a separate program and see what kind of speed I can get.

Other side note: it's not even that it's that hard to prune. It's that you might tweak your config, and then you have to _remember_ to prune.

-Peff

On Sun, Mar 28, 2010 at 12:19:21PM -0400, Jeff King wrote:

Better, but not perfect. My script is below. I get:

  $ time git show >/dev/null
  real    0m1.036s
  user    0m0.412s
  sys     0m0.672s

which is still a 2.5x speedup (versus my other fast-textconv solution earlier in the thread), but I suspect we can do better. The notes mechanism does some up-front work to get very fast lookups, but because we invoke git-notes repeatedly, we never get the amortized benefit of that up-front work. Doing it in-core would fix that.

My script was:

-- >8 -- #!/bin/sh

type=$1; shift program=$1; shift sha1=$1; shift filename=$1; shift

GIT_NOTES_REF=refs/notes/textconv/$type; export GIT_NOTES_REF

# try the cache git notes show $sha1 2>/dev/null && exit 0

# otherwise, insert the cache entry. # We can be as slow as we like. ext=`echo "$filename" | sed 's/.*\.//'` tmp=`mktemp notes-textconv-XXXXXX.$ext` git cat-file blob $sha1 >$tmp $program $tmp | git notes add -f -F - $sha1 git notes show $sha1 rm -f $tmp -- 8< --

and my config is:

  $ git config diff.mfo.textconv /home/peff/fast mfo mfo-tags

where "mfo-tags" is the program to display metadata and "mfo" is a user-selected shorthand name for it.

-Peff

On Sun, Mar 28, 2010 at 12:56:46PM -0400, Jeff King wrote:

Here is a quick and dirty in-core implementation. The most notable defect is that all textconvs store under refs/notes/textconv, which is obviously bogus if you might textconv the same blob in two different ways.

It was relatively easy to code thanks to a very nice notes interface from Johan Herland. That same commit is now:

  $ time git show >/dev/null
  real    0m0.350s
  user    0m0.172s
  sys     0m0.176s

which is starting to feel sufficiently snappy.

Patch is on top of 1/3 from my earlier series (it uses some of the centralizing cleanup).

Heya,

On Sun, Mar 28, 2010 at 11:34, Jeff King <peff@peff.net> wrote:

What I did for the implementation of remote helpers is hash the url of the remote when storing it locally, that way you don't have to worry about escaping urls etc. You could do the same with the textconvs, store it under refs/notes/textconv/<hash of textconv filter>?

On Sun, Mar 28, 2010 at 12:13:10PM -0600, Sverre Rabbelier wrote:

I thought about something like that, but we want to keep something that is comprehensible to the user. If my install of "exif" changes, I need to be able to say "invalidate the cache for exif". If it's human-readable, I know I need to clear refs/notes/textconv/exif. But if it's a hash, then I need a special tool to figure out which ref is relevant.

Instead, my plan is to use refs/notes/textconv/$TYPE, where $TYPE is the same string used by the config (e.g., "diff.$TYPE.textconv") and the gitattributes file (e.g., "*.jpg diff=$TYPE"). The user has already provided us a with a short, unique, meaningful name.

-Peff

Jeff King <peff@peff.net> writes:

This made me wonder if the end result might be easier to use if the interface does not change "textconv", but adds some property to the filter, i.e. "the output from this filter is stable and it is safe to reuse a cached conversion result for a given blob object", boolean. E.g.

        [diff "jpg"]
                textconv = exif
                textconv_stable = true

and let the calling side handle the caching. I further suspect that an unstable textconv filter would be an anomaly, so this could even be on by default.

If we do so, stock conversion filters people have accumulated in the past could be sped up without any additional change from the end user's side.

I guess that I am suggesting to postpone the potential speed-up that could come from being able to inspect the header information as a separate topic. Besides, some file format has metadata at the end, which won't help you.

About the caching scheme; to help invalidating the cache, it probably is a good idea to use not just the blob object name but also at least the name (command line) of the textconv filter as the key for the caching layer.

Instead of the "textconv_stable" boolean depicted above, you could add a "textconv_filter_version" variable there, compute a hash over blob object name, textconv filter name and textconv filter version, and use that as the key to look into the cache (filters lacking textconv_filter_version would then get no caching, and if you update your "exif" program you bump the "textconv_filter_version" variable).

On Mon, Mar 29, 2010 at 08:52:04PM -0700, Junio C Hamano wrote:

Yep, that is the conclusion I came to later in the thread. I am tempted not to even make it configurable, but it is a space-time tradeoff, so I can see how certain corner cases would want to disable.

So consider "fasttextconv" (and this series) scrapped, and I'll work on a new series that does internal caching via notes.

Yes, I agree that the "header only" speed-up is not worth pursuing at this point. With caching, actually looking at the file at all becomes the slow path, and you just don't care as much. It might help if you have 2G files or something where even just spooling the file the first time is awful, but I will leave that as a later itch to be scratched if people want.

For metadata at the end (or other spots), probably it would need to be accompanied by an extension to cat-file to peek at random positions within the file.

I was thinking of having a separate notes tree for each textconv helper. Most projects will only have a small number, so the extra tree setup cost is negligible. And because we know which helper we are using, we can look in each tree separately, which means you may not even need to load cache entries at all for filetypes which are not being diffed.

For cache validity, I'm planning to store a special "validity" entry (either keyed by the null sha1 in a cache tree, or to wrap the tree in a parentless commit with that information in the comment field). The entry would contain the command line used to run the helper. If it matches, the cache is valid. If not, we clear the notes tree.

I think this ends up being slightly simpler for the user to manage the cache, and it has better cache growth characteristics.

In both schemes, git will automatically correctly handle:

  $ git config diff.foo.textconv foo-helper
  $ git show
  $ git config diff.foo.textconv "foo-helper --options"
  $ git show

In my case, by clearing refs/notes/textconv/foo, and in your case by storing under a different key sha1. I would argue my scheme is better here, because it actually _throws away_ the now useless cache entries. So the cache is automatically pruned (and if you really want to go back in time to salvage an old cache, you can do it via the reflog).

They will also both automatically handle:

  $ echo '*.jpg diff=foo' >.gitattributes
  $ git show
  $ echo '*.jpg diff=bar' >.gitattributes
  $ git show

In my case, by using a totally different tree. In your case, again a different key sha1. Which means I'm now leaving the old "foo" tree in place with stale entries for '*.jpg' files. But this is the same data wastage as with your scheme. In both cases, you can clean things out by blowing away the cache. But in my scheme, you are allowed to blow away only the "foo" cache. The cache data for other helpers isn't precious, obviously, but it does make things slower.

Neither scheme will automatically handle the semantics of a helper changing (e.g., upgrade of the "foo" helper). In my scheme, the solution is to clear the "foo" cache (git update-ref -d refs/notes/textconv/foo). In yours, it would be to update the textconv_filter_version field in the config. I would argue that mine is conceptually simpler for the user. It's a cache. When a cache is in a broken or invalid state, you clear it and start again.

You could try to get very fancy and include the stat() data for the helper script in the cache validity information to detect version changes, but I doubt that it's worth it. It's much more complex (we run helpers with the shell, so it may not be a single program), and it still isn't foolproof (your environment, dynamic libraries, or other factors may be what's changing the answer).

I'll see if I can work up some patches in the next day or two.

-Peff