patch, 4 partsInvalidate cache-tree entries for touched paths in git-apply.

This updates git-apply to maintain cache-tree information. With this and the previous write-tree patch, repeated "apply --index" followed by "write-tree" on a huge tree will hopefully become faster.

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

 * ... then the big rock falls.  With this, I tried to apply and
   then write-tree "diff-tree -p $commit^1 $commit" on top of
   "$commit^1" for the last 20 or so commits in the kernel tree.
   The "master" version takes 0.15 second per patch on my Duron
   750 with 700MB, while this one does that in 0.06 second.
   This also helps the memory pressure because we do not have to
   regenerate unchanged trees.  810 minor faults with the patch
   vs 2150 minor faults without.

 apply.c |   16 ++++++++++++++--
 1 files changed, 14 insertions(+), 2 deletions(-)

94005d7bb4b55e9984f6505a8916d23d304ccc4d

Junio C Hamano <junkio@cox.net> writes:

Sorry, but not really. The patch is wrong and the measurement was flawed.

It was doing unnecessarily more work in git-apply, which made git-write-tree a no-op, and I was measuring only git-write-tree.

The following goes on top of the series to remove that unnecessary work from git-apply. Unfortunately this makes the overall combination a bit slower than before X-<.

But I have not optimized cache-tree.c for speed; for example, its subtree lists are not even sorted. Once that is done we may get decent speedups from the combo.

---

Junio C Hamano <junkio@cox.net> writes:

Again, sorry, but there are some more bugs in the cache-tree code that I need to fix and re-measure.

In the meantime, please do not use it on your production repositories. It does not seem to produce corrupt trees, but it creates broken index.aux for no good reason.

The first hunk is the repeat of the previous "oops". The second is a real fix.

With this applied, 100-patch series (going from present to past at the Linux 2.6 kernel tip) applies correctly with the following stats:

Trying w/o the patch... 24.57user 4.48system 0:34.47elapsed 84%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+322156minor)pagefaults 0swaps Trying w/ the patch... 15.81user 3.00system 0:20.84elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+252063minor)pagefaults 0swaps

So there definitely is an improvement.  *Grin*.

The script used to bench this is attached at the end. "linus" is the tracking branch and currently it points at v2.6.17-rc2-g6b426e7 $HOME/git-master/bin is where I installed the "master" version, and $J (aka ../git.junio/) is the freshly compiled area with the patch series applied (all five of four ;-).

-- >8 -- Minimum fixups to make things usable.

---

I've fixed-up the series and they are now sitting near the tip of "pu" branch tonight. With some more testing I am hoping to merge it in "next" soon.

I should recap the overall idea for general public here.

When applying a series of patches to your working tree and making commits out of the results, what happens is roughly this:

 1. Your index file exactly matches your HEAD commit; you may
    have local modifications to some paths in your working tree
    as long as they do not interfere with the patch application.

 2. "git-apply --index" reads the index file, reads the patch,
    applies them to both index and the working tree, and writes
    the updated index file out.

 3. "git-write-tree" reads the index file, writes the index
    entries out as a set of hierarchical tree objects, the top
    of which is wrapped in a new commit object that has the
    current HEAD as the parent, and the commit becomes the new
    HEAD.

You repeat 1-3 as many times as you apply patches.

When dealing with a huge tree, with a typical patch touching only a handful paths, this is not very efficient. A recent kernel source tree has about 1200 directories, each of which needs to be made into the "tree" object format in-core from the data in the index file, and we hash it to see if we already have that tree, and if not we write it out after compression (if we do have it, we do not do anything after checking).

The updated code does this:

 (1) When git-write-tree writes out trees from the index, we
     store <directory, tree SHA1> pair for all the trees we
     compute, in .git/index.aux file.

 (2) When git-write-tree starts up, it reads the index file, and
     also reads the .git/index.aux file.  The latter file
     contains a fingerprint of the former, so if the index was
     updated without updating the index.aux, what is read is
     discarded.  However, if .git/index.aux is up-to-date, what
     it records can be reused when we scan the index.

 (3) There are a few commands that updates the index file.
     git-update-index is the most well-known one, but read-tree
     and apply also update it.

     No command other than apply updates index.aux when writing
     out index (yet).  However, git-apply has been told about
     it.  It reads index and index.aux file, and when it updates
     an index entry, it _invalidates_ the directory information
     it read from index.aux file, and writes the updated
     index.aux file out when it is done.

     Note.  Earlier I sent out a fix ([PATCH 5/4]) that
     contained a two-line removal from apply.c; the code was
     doing more than just invalidating entries, but actually
     recomputing the tree.  The fixed code does not hash tree
     information when git-apply writes index out.

 (4) When git-write-tree starts up after git-apply finishes its
     job, it notices index.aux file matches the fingerprint of
     the index (so it is up-to-date) and some entries have been
     _invalidated_.  When it writes out the index, the parts of
     the directory hierarchy that have not been invalidated do
     not have to be formatted in-core into "tree" -- we already
     know what tree object they are.  Only the parts that were
     invalidated need to be computed.

For this, a new data structure "cache_tree" is introduced. The way to use the API is very simple. You initialize it like this:

	struct cache_tree *active_cache_tree;
	unsigned char sha1[20];
	read_cache_1(sha1);
        active_cache_tree = read_cache_tree(sha1);
     
The new function read_cache_1() is similar to the traditional
read_cache(), but it gives back the index file fingerprint.
This is given to read_cache_tree() to make sure index.aux is not
stale.  Then, when you touch a path in the cache, you invalidate
the paths in the cache_tree with:

	cache_tree_invalidate_path(active_cache_tree, path);

For example, if you are updating an index entry "fs/ext3/inode.c", it invalidates the cached tree SHA1 information for top-level tree, "fs" tree and "fs/ext3" tree. All other information you read from index.aux are still valid (IOW, three out of 1200 are invalidated).

When you are done, you write out the index file and the updated index.aux file like this:

        if (write_cache_1(newfd, active_cache, active_nr, active_cache_sha1) ||
            commit_index_file(&cache_file))
                die("Unable to write new cachefile");
        write_cache_tree(active_cache_sha1, active_cache_tree);

Again, write_cache_1() has one extra parameter to receive the updated index file fingerprint, and you call write_cache_tree() with it. It updates index.aux file (with invalidated entries).

One thing write-tree does different is this (note that it does not update the index file, it just reads from it):

	if (cache_tree_update(active_cache_tree, active_cache, active_nr,
			      missing_ok))
		die("git-write-tree: error building trees");
	write_cache_tree(active_cache_sha1, active_cache_tree);

The call to cache_tree_update() takes the (possibly partially invalidated) cache_tree, fills in the invalidated parts from the index file (this involves creation of new "tree" objects as needed). So the above call to write_cache_tree() writes a complete index.aux file out without any invalidated entries.

Obviously, the change similar to what I did to apply.c in this series can be done to other index-updating commands. That's "low hanging fruit" for the week ;-).

Junio C Hamano <junkio@cox.net> writes:

There are two reasons I did not make this extra information part of the index file.

The number one reason was because the current index file format is pretty dense, and I did not find an obvious hole in the front, in the middle or at the tail to sneak extra data in without upsetting existing code and without updating index file version. If this were a change to add a great new feature, that might have warranted bumping the version up, but the cache-tree is an optimization and if you lose that information, all you have lost is that now your write-tree needs to recompute the whole tree as before (IOW, not much).

The second reason was I wanted to do this step-by-step, and wanted to do a demonstration of an end-to-end workflow that gains from this set of changes (apply followed by write-tree was an obvious minimum set of commands), and while doing so I did not have to disrupt other commands that are unaware of this extension.

Having said that, cache-tree.c has an internal interface to serialize the cache-tree data in-core, primarily because I was unsure if I wanted to append this information somewhere inside the main index file or have it external when I did it; so we could later push it into the index if we wanted to.

Ideally, everybody who writes index should be converted to update cache-tree to help eventual write-tree. Right now, if a command updates index without updating a matching cache-tree, the whole thing is invalidated; this way, you do not risk using stale "cached" data.

Currently the command that primes the cache-tree is write-tree. This may be counterintuitive -- even I myself would expect that read-tree would prime it, and various index-updaters invalidate subtrees they touch, and write-tree to use the surviving parts to speed up what it needs to do, and write out an updated, fully-vaild cache-tree. I did not do it only because it was not necessary for "apply then write-tree" cycle, but read-tree should be taught about cache-tree to help others, _and_ to help itself.

When "read-tree -m O A B" merges three trees, we iterate over all index entries, even when only a small part of the tree has changed. This could be helped in a big way if the current index has valid cache-tree information for the parts unaffected by the merge. If all three trees have identical tree in higher level subdirectory (e.g. "fs/" in the kernel source), and if the index has not touched anything in "fs/" since it read from our tree (i.e. "A"), then we do not even have to descend into that directory in the working tree to see which index entries are dirty. We can just keep index entries that begin with "fs/" intact, keep the cache-tree entry for that directory as it was read from "A". This would be a big win -- we do not have to read tree objects under "fs/" (there are 62 trees under "fs/", so we save uncompressing and undeltifying 180 objects). This operation would need to invalidate entries in cache-tree that are involved in the actual merge. Branch-switching two-tree form "read-tree -m OLD NEW" probably can benefit from the same optimization.

Obviously, a single-tree form of read-tree should be able to prime the cache-tree with fully valid data before writing the index out.

Having said that, I am not touching read-tree myself for now; I am lazy.

Junio C Hamano <junkio@cox.net> writes:

Well, I was blind ;-). As long as the whole-file SHA1 matches, read_cache() does not care if we have extra data after the series of active_nr cache entry data in the index file.

I'm working on a patch now.

Junio C Hamano <junkio@cox.net> writes:

So I did.

There is one bad thing; so far "write-tree" was a read-only consumer of the index file, but now it primes the cache-tree structure and needs to update the index. But that is minor.

While I was at it, I made this "stuffing extra cruft in the index" slightly more generic than I needed it for this particular application. What I see this _might_ be useful for are:

 - We would want to store which commit of a subproject a
   particular subdirectory came from.  This was one missing
   piece from the "bind commit" proposal that wasn't implemented
   in the jc/bind branch.

 - We might want to record "at this path there is a directory,
   albeit empty"; this cannot be expressed with an usual index
   entry.

   We might be able to use cache-tree for that, but I think this
   is something different at the logical level.  While
   cache-tree is to be fully populated (by write-tree and
   perhaps read-tree later) and invalidated partially when
   update-index and friends smudge part of the tree, this is not
   something we would want to even invalidate (IOW, it should
   always be up-to-date), so they serve different purposes.

I still haven't looked at the read-tree yet, but as I outlined in a previous message, its intra-index merge could take advantage of cache-tree. "diff-index", especially "--cached" kind, also could use it to skip unchanged subtrees altogether.