cache-tree revisited
cover cache-tree revisited
Quoted 7 lines · Junio C Hamano
Ahh, I forgot all about that exchange.
http://thread.gmane.org/gmane.comp.version-control.git/178480/focus=178515
The cache-tree mechanism has traditionally been one of the more important optimizations and it would be very nice if we can resurrect the behaviour for "git commit" too.
Oh, I buried that. Let's try something other than the aggressive strategy I had there: only compute cache-tree if
* we know we're going to need it soon, and we're about to write out the index anyway (as in git-commit)
* we know we can rebuild it from a tree, and we're about to write out the index anyway (as in git-reset)
Both of these are essentially free, so I'm not sure I should even bother with timings, but I ran the silly script at the end on my favourite linux v2.6.37-rc2 repo, and it takes
before-: real 0m29.103s user 0m17.335s sys 0m8.415s before+: real 0m30.860s user 0m9.741s sys 0m7.287s after-: real 0m28.798s user 0m17.367s sys 0m8.435s after+: real 0m17.563s user 0m8.246s sys 0m7.122s
where the + signifies starting out with fully valid cache-tree data, and - means starting out with none at all.
So it's really free when it's starting out in bad shape, and it's much faster when it starts out with valid data.
If you insist on writing cache-tree at *every* (except --only) commit, then we might make it so that it writes out the index again at the very end if it didn't already update it earlier. It would (and does, I've tried... ok ok, patch is at the end) of course give the + performance in the - case, but it's not free so other operations may be affected.
---- 8< ---- test script for the above timings ---- 8< ---- #!/bin/sh
for i in $(seq 1 100); do
echo $i > arch/alpha/boot/foo
git add arch/alpha/boot/foo
git commit -m$i
done
---- >8 ----
---- 8< ---- patch to let git-commit always write the index ---- 8< ----
builtin/commit.c +11 -0
@@ -333,6 +333,8 @@ static void refresh_cache_or_die(int refresh_flags)die_resolve_conflict ("commit" ); } +static int wrote_index_already =0 ; +static char *prepare_index (int argc,const char **argv,const char *prefix,const struct commit *current_head,int is_status) {
@@ -395,6 +397,7 @@ static char *prepare_index(int argc, const char **argv, const char *prefix,add_files_to_cache (also ? prefix :NULL , pathspec,0 );refresh_cache_or_die (refresh_flags);update_main_cache_tree (1 ); + wrote_index_already =1 ;if (write_cache (fd, active_cache, active_nr) ||close_lock_file (&index_lock))die (_ ("unable to write new_index file" ));
@@ -415,6 +418,7 @@ static char *prepare_index(int argc, const char **argv, const char *prefix, fd =hold_locked_index (&index_lock,1 );refresh_cache_or_die (refresh_flags);if (active_cache_changed) { + wrote_index_already =1 ;update_main_cache_tree (1 );if (write_cache (fd, active_cache, active_nr) ||commit_locked_index (&index_lock))
@@ -639,6 +643,7 @@ static int prepare_to_commit(const char *index_file, const char *prefix,const char *hook_arg2 =NULL ;int ident_shown =0 ;int clean_message_contents = (cleanup_mode !=CLEANUP_NONE ); +int fd;if (!no_verify &&run_hook (index_file,"pre-commit" ,NULL ))return 0 ;
@@ -863,11 +868,17 @@ static int prepare_to_commit(const char *index_file, const char *prefix,* the editor and after we invoke run_status above. */ discard_cache (); +if (!wrote_index_already) + fd =hold_locked_index (&index_lock,1 );read_cache_from (index_file);if (update_main_cache_tree (0 )) {error (_ ("Error building trees" ));return 0 ; } +if (!wrote_index_already && commit_style !=COMMIT_PARTIAL ) +if (write_cache (fd, active_cache, active_nr) || +close_lock_file (&index_lock)) +die (_ ("unable to write new_index file" ));if (run_hook (index_file,"prepare-commit-msg" ,git_path (commit_editmsg), hook_arg1, hook_arg2,NULL ))
---- >8 ----
Thomas Rast (5):
Add test-scrap-cache-tree
Test the current state of the cache-tree optimization Refactor cache_tree_update idiom from commit
commit: write cache-tree data when writing index anyway
reset: update cache-tree data when appropriate
.gitignore | 1 + Makefile | 1 + builtin/commit.c | 7 +-- builtin/reset.c | 7 +++ cache-tree.c | 19 +++++++-- cache-tree.h | 4 +- merge-recursive.c | 2 +- t/t0090-cache-tree.sh | 95 +++++++++++++++++++++++++++++++++++++++++++++++ test-dump-cache-tree.c | 2 +- test-scrap-cache-tree.c | 17 ++++++++ 10 files changed, 144 insertions(+), 11 deletions(-) create mode 100755 t/t0090-cache-tree.sh create mode 100644 test-scrap-cache-tree.c
Signature · 1 line
1.7.8.425.ga639d3
PATCH 1/5 Add test-scrap-cache-tree
A simple utility that invalidates all existing cache-tree data. We need this for tests. (We don't need a tool to rebuild the cache-tree data; git read-tree HEAD works for that.)
--- .gitignore | 1 + Makefile | 1 + test-scrap-cache-tree.c | 17 +++++++++++++++++ 3 files changed, 19 insertions(+), 0 deletions(-) create mode 100644 test-scrap-cache-tree.c
.gitignore +1 -0
@@ -171,6 +171,7 @@ /test-date /test-delta /test-dump-cache-tree +/test-scrap-cache-tree /test-genrandom /test-index-version /test-line-buffer
Makefile +1 -0
@@ -436,6 +436,7 @@ TEST_PROGRAMS_NEED_X += test-ctype TEST_PROGRAMS_NEED_X += test-date TEST_PROGRAMS_NEED_X += test-delta TEST_PROGRAMS_NEED_X += test-dump-cache-tree +TEST_PROGRAMS_NEED_X += test-scrap-cache-tree TEST_PROGRAMS_NEED_X += test-genrandom TEST_PROGRAMS_NEED_X += test-index-version TEST_PROGRAMS_NEED_X += test-line-buffer
test-scrap-cache-tree.c new file +17 -0
@@ -0,0 +1,17 @@ +#include "cache.h" +#include "tree.h" +#include "cache-tree.h" + +static struct lock_file index_lock; + +int main (int ac,char **av) +{ +int fd =hold_locked_index (&index_lock,1 ); +if (read_cache () <0 ) +die ("unable to read index file" ); + active_cache_tree =NULL ; +if (write_cache (fd, active_cache, active_nr) + ||commit_lock_file (&index_lock)) +die ("unable to write index file" ); +return 0 ; +}
Signature · 1 line
1.7.8.425.ga639d3
Re: [PATCH 1/5] Add test-scrap-cache-tree
Quoted 3 lines · Thomas Rast
A simple utility that invalidates all existing cache-tree data. We need this for tests. (We don't need a tool to rebuild the cache-tree data; git read-tree HEAD works for that.)
"git read-tree -m HEAD HEAD" would work for that, I suspect ;-)
But that can be improved later, so it is very sensible to add a test tool like this.
PATCH 2/5 Test the current state of the cache-tree optimization
In reply to Thomas RastThe cache-tree optimization originally helped speed up write-tree operation. However, many commands no longer properly maintain -- or use an opportunity to cheaply generate -- the cache-tree data. In particular, this affects commit, checkout and reset. The notable examples that *do* write cache-tree data are read-tree and write-tree.
This sadly means most people no longer benefit from the optimization, as they would not normally use the plumbing commands.
Document the current state of affairs in a test file, in preparation for improvements in the area.
--- t/t0090-cache-tree.sh | 95 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 95 insertions(+), 0 deletions(-) create mode 100755 t/t0090-cache-tree.sh
t/t0090-cache-tree.sh new file +95 -0
@@ -0,0 +1,95 @@ +#!/bin/sh + +test_description="Test whether cache-tree is properly updated + +Tests whether various commands properly update and/or rewrite the +cache-tree extension. +" + . ./test-lib.sh + +cmp_cache_tree () { + test-dump-cache-tree >actual && + sed "s/$_x40/SHA/" <actual >filtered && + test_cmp "$1" filtered +} + +# We don't bother with actually checking the SHA1: +# test-dump-cache-tree already verifies that all existing data is +# correct. +test_shallow_cache_tree () { + echo "SHA " \ + "($(git ls-files|wc -l) entries, 0 subtrees)" >expect && + cmp_cache_tree expect +} + +test_invalid_cache_tree () { + echo "invalid (0 subtrees)" >expect && + echo "SHA #(ref) " \ + "($(git ls-files|wc -l) entries, 0 subtrees)" >>expect && + cmp_cache_tree expect +} + +test_no_cache_tree () { + : >expect && + cmp_cache_tree expect +} + +test_expect_failure 'initial commit has cache-tree' ' + test_commit foo && + test_shallow_cache_tree +' + +test_expect_success 'read-tree HEAD establishes cache-tree' ' + git read-tree HEAD && + test_shallow_cache_tree +' + +test_expect_success 'git-add invalidates cache-tree' ' + test_when_finished "git reset --hard; git read-tree HEAD" && + echo "I changed this file" > foo && + git add foo && + test_invalid_cache_tree +' + +test_expect_success 'update-index invalidates cache-tree' ' + test_when_finished "git reset --hard; git read-tree HEAD" && + echo "I changed this file" > foo && + git update-index --add foo && + test_invalid_cache_tree +' + +test_expect_success 'write-tree establishes cache-tree' ' + test-scrap-cache-tree && + git write-tree && + test_shallow_cache_tree +' + +test_expect_success 'test-scrap-cache-tree works' ' + git read-tree HEAD && + test-scrap-cache-tree && + test_no_cache_tree +' + +test_expect_failure 'second commit has cache-tree' ' + test_commit bar && + test_shallow_cache_tree +' + +test_expect_failure 'reset --hard gives cache-tree' ' + test-scrap-cache-tree && + git reset --hard && + test_shallow_cache_tree +' + +test_expect_failure 'reset --hard without index gives cache-tree' ' + rm -f .git/index && + git reset --hard && + test_shallow_cache_tree +' + +test_expect_failure 'checkout gives cache-tree' ' + git checkout HEAD^ && + test_shallow_cache_tree +' + +test_done
Signature · 1 line
1.7.8.425.ga639d3
PATCH 3/5 Refactor cache_tree_update idiom from commit
In reply to Thomas RastWe'll need to safely create or update the cache-tree data of the_index from other places. While at it, give it an argument that lets us silence the messages produced by unmerged entries (which prevent it from working).
--- builtin/commit.c | 5 +---- cache-tree.c | 19 +++++++++++++++---- cache-tree.h | 4 +++- merge-recursive.c | 2 +- test-dump-cache-tree.c | 2 +- 5 files changed, 21 insertions(+), 11 deletions(-)
builtin/commit.c +1 -4
@@ -862,10 +862,7 @@ static int prepare_to_commit(const char *index_file, const char *prefix,*/ discard_cache ();read_cache_from (index_file); -if (!active_cache_tree) - active_cache_tree =cache_tree (); -if (cache_tree_update (active_cache_tree, - active_cache, active_nr,0 ,0 ) <0 ) { +if (update_main_cache_tree (0 )) {error (_ ("Error building trees" ));return 0 ; }
cache-tree.c +15 -4
@@ -150,7 +150,7 @@ void cache_tree_invalidate_path(struct cache_tree *it, const char *path) }static int verify_cache (struct cache_entry **cache, -int entries) +int entries,int silent) {int i, funny;
@@ -159,6 +159,8 @@ static int verify_cache(struct cache_entry **cache,for (i =0 ; i < entries; i++) {struct cache_entry *ce = cache[i];if (ce_stage (ce) || (ce->ce_flags &CE_INTENT_TO_ADD )) { +if (silent) +return -1 ;if (10 < ++funny) {fprintf (stderr,"...\n" );break ;
@@ -370,10 +372,11 @@ int cache_tree_update(struct cache_tree *it,struct cache_entry **cache, int entries, int missing_ok, - int dryrun) + int dryrun, + int silent) { int i; - i =verify_cache (cache, entries); + i =verify_cache (cache, entries, silent);if (i)return i; i =update_one (it, cache, entries,"" ,0 , missing_ok, dryrun);
@@ -573,7 +576,7 @@ int write_cache_as_tree(unsigned char *sha1, int flags, const char *prefix)if (cache_tree_update (active_cache_tree, active_cache, active_nr, - missing_ok,0 ) <0 ) + missing_ok,0 ,0 ) <0 )return WRITE_TREE_UNMERGED_INDEX ;if (0 <= newfd) { if (!write_cache(newfd, active_cache, active_nr) &&
@@ -668,3 +671,11 @@ int cache_tree_matches_traversal(struct cache_tree *root,return it->entry_count;return 0 ; } + +int update_main_cache_tree (int silent) +{ +if (!the_index.cache_tree) + the_index.cache_tree =cache_tree (); +return cache_tree_update (the_index.cache_tree, + the_index.cache, the_index.cache_nr,0 ,0 , silent); +}
cache-tree.h +3 -1
@@ -29,7 +29,9 @@ struct cache_tree {struct cache_tree *cache_tree_read (const char *buffer,unsigned long size);int cache_tree_fully_valid (struct cache_tree *); -int cache_tree_update (struct cache_tree *,struct cache_entry **,int ,int ,int ); +int cache_tree_update (struct cache_tree *,struct cache_entry **,int ,int ,int ,int ); + +int update_main_cache_tree (int );/* bitmasks to write_cache_as_tree flags */ #define WRITE_TREE_MISSING_OK 1
merge-recursive.c +1 -1
@@ -264,7 +264,7 @@ struct tree *write_tree_from_memory(struct merge_options *o)if (!cache_tree_fully_valid (active_cache_tree) &&cache_tree_update (active_cache_tree, - active_cache, active_nr,0 ,0 ) <0 ) + active_cache, active_nr,0 ,0 ,0 ) <0 )die ("error building trees" ); result =lookup_tree (active_cache_tree->sha1);
test-dump-cache-tree.c +1 -1
@@ -59,6 +59,6 @@ int main(int ac, char **av)struct cache_tree *another =cache_tree ();if (read_cache () <0 )die ("unable to read index file" ); -cache_tree_update (another, active_cache, active_nr,0 ,1 ); +cache_tree_update (another, active_cache, active_nr,0 ,1 ,0 );return dump_cache_tree (active_cache_tree, another,"" ); }
Signature · 1 line
1.7.8.425.ga639d3
PATCH 4/5 commit: write cache-tree data when writing index anyway
In reply to Thomas RastIn prepare_index(), we refresh the index, and then write it to disk if this changed the index data. After running hooks we re-read the index and compute the root tree sha1 with the cache-tree machinery.
This gives us a mostly free opportunity to write up-to-date cache-tree
data: we can compute it in prepare_index() immediately before writing the index to disk.
If we do this, we were going to write the index anyway, and the later cache-tree update has no further work to do. If we don't do it, we don't do any extra work, though we still don't have have cache-tree data after the commit.
The only case that suffers badly is when the pre-commit hook changes many trees in the index. I'm writing this off as highly unusual.
---
Don't ask me why git thinks the index has been changed only when already building upon an earlier commit. I don't know. I suspect it's some raciness issue though.
builtin/commit.c | 2 ++ t/t0090-cache-tree.sh | 2 +- 2 files changed, 3 insertions(+), 1 deletions(-)
builtin/commit.c +2 -0
@@ -394,6 +394,7 @@ static char *prepare_index(int argc, const char **argv, const char *prefix, fd =hold_locked_index (&index_lock,1 );add_files_to_cache (also ? prefix :NULL , pathspec,0 );refresh_cache_or_die (refresh_flags); +update_main_cache_tree (1 );if (write_cache (fd, active_cache, active_nr) ||close_lock_file (&index_lock))die (_ ("unable to write new_index file" ));
@@ -414,6 +415,7 @@ static char *prepare_index(int argc, const char **argv, const char *prefix, fd =hold_locked_index (&index_lock,1 );refresh_cache_or_die (refresh_flags);if (active_cache_changed) { +update_main_cache_tree (1 );if (write_cache (fd, active_cache, active_nr) ||commit_locked_index (&index_lock))die (_ ("unable to write new_index file" ));
t/t0090-cache-tree.sh +1 -1
@@ -70,7 +70,7 @@ test_expect_success 'test-scrap-cache-tree works' ' test_no_cache_tree ' -test_expect_failure 'second commit has cache-tree' ' +test_expect_success 'second commit has cache-tree' ' test_commit bar && test_shallow_cache_tree '
Signature · 1 line
1.7.8.425.ga639d3
PATCH 5/5 reset: update cache-tree data when appropriate
In reply to Thomas RastIn the case of --mixed and --hard, we throw away the old index and rebuild everything from the tree argument (or HEAD). So we have an opportunity here to fill in the cache-tree data, just as read-tree did.
--- builtin/reset.c | 7 +++++++ t/t0090-cache-tree.sh | 4 ++-- 2 files changed, 9 insertions(+), 2 deletions(-)
builtin/reset.c +7 -0
@@ -43,6 +43,7 @@ static int reset_index_file(const unsigned char *sha1, int reset_type, int quietint nr =1 ;int newfd;struct tree_desc desc[2 ]; +struct tree *tree;struct unpack_trees_options opts;struct lock_file *lock =xcalloc (1 ,sizeof (struct lock_file ));
@@ -84,6 +85,12 @@ static int reset_index_file(const unsigned char *sha1, int reset_type, int quietreturn error (_ ("Failed to find tree of %s." ),sha1_to_hex (sha1));if (unpack_trees (nr, desc, &opts))return -1 ; + +if (reset_type ==MIXED || reset_type ==HARD ) { + tree =parse_tree_indirect (sha1); +prime_cache_tree (&active_cache_tree, tree); + } +if (write_cache (newfd, active_cache, active_nr) ||commit_locked_index (lock))return error (_ ("Could not write new index file." ));
t/t0090-cache-tree.sh +2 -2
@@ -75,13 +75,13 @@ test_expect_success 'second commit has cache-tree' ' test_shallow_cache_tree ' -test_expect_failure 'reset --hard gives cache-tree' ' +test_expect_success 'reset --hard gives cache-tree' ' test-scrap-cache-tree && git reset --hard && test_shallow_cache_tree ' -test_expect_failure 'reset --hard without index gives cache-tree' ' +test_expect_success 'reset --hard without index gives cache-tree' ' rm -f .git/index && git reset --hard && test_shallow_cache_tree
Signature · 1 line
1.7.8.425.ga639d3
Re: [PATCH 5/5] reset: update cache-tree data when appropriate
Quoted 24 lines · Thomas Rast
In the case of --mixed and --hard, we throw away the old index and rebuild everything from the tree argument (or HEAD). So we have an opportunity here to fill in the cache-tree data, just as read-tree did.
Signed-off-by Thomas Rast <[email protected]>--- builtin/reset.c | 7 +++++++ t/t0090-cache-tree.sh | 4 ++-- 2 files changed, 9 insertions(+), 2 deletions(-)builtin/reset.c +1
-0@@ -43,6 +43,7 @@ static int reset_index_file(const unsigned char *sha1, int reset_type, int quietint nr =1 ;int newfd;struct tree_desc desc[2 ]; +struct tree *tree;struct unpack_trees_options opts;struct lock_file *lock =xcalloc (1 ,sizeof (struct lock_file ));
builtin/reset.c static int reset_index_file(const unsigned char *sha1, int reset_type, int quiet · line 92
Quoted 8 lines
builtin/reset.c +5
-0@@ -84,6 +85,12 @@ static int reset_index_file(const unsigned char *sha1, int reset_type, int quietreturn error (_ ("Failed to find tree of %s." ),sha1_to_hex (sha1));if (unpack_trees (nr, desc, &opts))return -1 ; + +if (reset_type ==MIXED || reset_type ==HARD ) { + tree =parse_tree_indirect (sha1); +prime_cache_tree (&active_cache_tree, tree); + }
The basic idea that MIXED or HARD should result in a cache-tree that match the tree we just read is sound, but how expensive is prime_cache_tree()? I think it reads the same tree once again. Admittedly, the data needed to reconstruct the tree is likely to be hot in core, but it may be necessary to measure before deciding if this is a good change.
Re: [PATCH 5/5] reset: update cache-tree data when appropriate
Quoted 16 lines · Junio C Hamano
builtin/reset.c static int reset_index_file(const unsigned char *sha1, int reset_type, int quiet · line 92
Quoted 9 lines · Thomas Rast
builtin/reset.c +5
-0@@ -84,6 +85,12 @@ static int reset_index_file(const unsigned char *sha1, int reset_type, int quietreturn error (_ ("Failed to find tree of %s." ),sha1_to_hex (sha1));if (unpack_trees (nr, desc, &opts))return -1 ; + +if (reset_type ==MIXED || reset_type ==HARD ) { + tree =parse_tree_indirect (sha1); +prime_cache_tree (&active_cache_tree, tree); + }The basic idea that MIXED or HARD should result in a cache-tree that match the tree we just read is sound, but how expensive is
prime_cache_tree()? I think it reads the same tree once again. Admittedly, the data needed to reconstruct the tree is likely to be hot in core, but it may be necessary to measure before deciding if this is a good change.
Oh, I just didn't bother with timings because it's the same strategy that read-tree follows, so I assumed if it was worth it back then, it should again be a win.
For linux-2.6 as usual and best-of-10:
git reset before: 0:00.25real 0.12user 0.11system
after: 0:00.28real 0.14user 0.12system
git reset --hard before: 0:00.21real 0.13user 0.06system
after: 0:00.18real 0.10user 0.07systemSo we spend ~30ms of extra user time, at a possible gain of 30% in future git-commit invocations, as mentioned in the cover letter. I think that's worth it :-)
Signature · 2 lines
Thomas Rast
trast@{inf,student}.ethz.chQuoted 9 lines · Thomas Rast
Quoted 7 lines · Junio C Hamano
Ahh, I forgot all about that exchange.
http://thread.gmane.org/gmane.comp.version-control.git/178480/focus=178515
The cache-tree mechanism has traditionally been one of the more important optimizations and it would be very nice if we can resurrect the behaviour for "git commit" too.
Quoted 5 lines
Oh, I buried that. Let's try something other than the aggressive strategy I had there: only compute cache-tree if
* we know we're going to need it soon, and we're about to write out the index anyway (as in git-commit)
I had another idea: we could write out *just* a new cache-tree data set at the end of git-commit.
Doing it the cheap way would mean rehashing the on-disk data without actually touching it. (That might not be so bad, but then if your index is small, why is writing it from scratch expensive?)
Doing it efficiently requires making the sha1 restartable, which is entirely doable withblock-sha1/sha1.h (I haven't looked into ppc/sha1.h). As far as I can see it's not feasible with openssl's sha1.
That is, we would add a new index extension (say PSHA: partial SHA) and structure the index as
signature
header
cache data
PSHA <sha state up until just before PSHA>
TREE ...
[REUC ...]
sha1 footer
Then it's easy to cheaply replace only the extensions, by restarting the hashing from the PSHA data and re-emitting only the extension data.
I think all the bits are in place, and it would be easy to do. However, for it to make sense, we would have to make BLK_SHA1 the default for the most-used platforms and also not mind extending the SHA1 API. Do you think that would fly?
I thought about other ways to make the index writing restartable from the middle, but the only clean approach I came up with would require a format change to something like
signature
0 header 1 cache data 2 sha1 of 0..1 3 extension data A 4 sha1 of 2..3 5 extension data B 6 sha1 of 4..5
[possibly more]
7 end-of-index marker
8 sha1 of 6..7
etc.
Signature · 2 lines
Thomas Rast
trast@{inf,student}.ethz.ch