Fix extraneous lstat's in 'git checkout -f'

Fix extraneous lstat's in 'git checkout -f'

[Linus Torvalds]

In our 'oneway_merge()' we always do an 'lstat()' to see if we might need 
to mark the entry for updating. 

We really shouldn't need to do that when the cache entry is already marked 
as being ce_uptodate(). However, since this function will actually match 
the lstat() information with the CE_MATCH_IGNORE_VALID, we need to be a 
bit more careful: it's not sufficient to check ce_uptodate(), we need to 
also double-check that the ce_uptodate() isn't because of CE_VALID (which 
will be "uptodate" regardless of whether the lstat() matches or not).

This explains why it's not sufficient to check _just_ the CE_UPTODATE bit.

But if both CE_UPTODATE is set, and CE_VALID is clear, then we know that 
the lstat() will always match the cache entry information, and there's no 
point in doing another one.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Quite frankly, I'd like for us to at least think about removing CE_VALID. 

Does anybody use it (and "core.ignorestat" that turns it on, along with 
the "--assume-unchanged" flag to update-index)

I wonder if we have other places where we have optimized away the lstat() 
just because we decided that it was already up-to-date - without 
realizing that something could have been marked up-to-date just because 
it was marked CE_VALID.

The original reasoning behind CE_VALID was to avoid the cost of lstat's on 
operating systems where it is slow, but we are now so good at optimizing 
them away (thanks to CE_UPTODATE) that I wonder whether it's not better to 
just always rely on CE_UPTODATE.

In fact, a quick grep made me just look at "verify_uptodate()", and how it 
does ie_match_stat(CE_MATCH_IGNORE_VALID). But look at how we've already 
short-circuited this if ce_uptodate() is true, and we never get there if 
we've preloaded the index or done any other operation that might have 
already validated the entry?

I dunno. This at least doesn't make things worse, since I started thinking 
about this _after_ having first done a patch that just did the 
"ce_uptodate()" test.

 unpack-trees.c |   14 +++++++++++++-
 1 files changed, 13 insertions(+), 1 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index f9d12aa..9920a6f 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -985,6 +985,18 @@ int bind_merge(struct cache_entry **src,
 }
 
 /*
+ * Do we _know_ the stat information will match?
+ *
+ * Note that if CE_VALID is set, then we might have a
+ * uptodate cache entry even if the stat info might not
+ * match.
+ */
+static inline int known_uptodate(struct cache_entry *ce)
+{
+	return ce_uptodate(ce) && !(ce->ce_flags & CE_VALID);
+}
+
+/*
  * One-way merge.
  *
  * The rule is:
@@ -1004,7 +1016,7 @@ int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o)
 
 	if (old && same(old, a)) {
 		int update = 0;
-		if (o->reset) {
+		if (o->reset && !known_uptodate(old)) {
 			struct stat st;
 			if (lstat(old->name, &st) ||
 			    ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID))

Re: Fix extraneous lstat's in 'git checkout -f'

[Linus Torvalds]

On Mon, 13 Jul 2009, Linus Torvalds wrote:
> 
> But if both CE_UPTODATE is set, and CE_VALID is clear, then we know that 
> the lstat() will always match the cache entry information, and there's no 
> point in doing another one.

Perf data on the kernel tree and my machine with index preloading:

 - run-of-ten "git checkout -f" before:
	real	0m0.131s
	real	0m0.130s
	real	0m0.128s
	real	0m0.127s
	real	0m0.129s
	real	0m0.135s
	real	0m0.129s
	real	0m0.126s
	real	0m0.128s
	real	0m0.127s

 - run-of-ten "git checkout -f" after:
	real	0m0.105s
	real	0m0.098s
	real	0m0.098s
	real	0m0.116s
	real	0m0.099s
	real	0m0.104s
	real	0m0.097s
	real	0m0.107s
	real	0m0.105s
	real	0m0.101s

so this makes about a 25% performance difference.

HOWEVER! Without preloading, there is bsically no difference what-so-ever, 
because the index won't have been preloaded (duh), so the CE_UPTODATE bit 
won't be set, so we'll do the lstat() in that oneway_merge() function 
regardless.

S for that non-preloading case, I get

 - run-of-ten "git checkout -f" without preloading:
	real	0m0.115s
	real	0m0.116s
	real	0m0.117s
	real	0m0.118s
	real	0m0.120s
	real	0m0.116s
	real	0m0.110s
	real	0m0.110s
	real	0m0.119s
	real	0m0.117s

so what happens is that with that patch the preloading is finally actually 
faster, because now it really helps do the lstat() in parallel (and I have 
lots of cores).

Before the patch, it would do the lstat first in parallel, but then it 
would do _another_ lstat() in the serial code anyway due to the silly 
oneway_merge() thing wasting time on the lstat() even if it didn't need 
to.

I guess I should have made this issue with preloading clear in the commit 
message. 

In other words - the patch should be _much_ more noticeable if you're 
doing something like NFS and are using core.preloadindex=true. My numbers 
above are all hot-cache, so there's no IO, just the fast multi-core CPU.

			Linus

Re: Fix extraneous lstat's in 'git checkout -f'

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Quite frankly, I'd like for us to at least think about removing CE_VALID. 

This is heavy.  I personally do not use this flag, nor know anybody who
does, but deviating from the original purpose of CE_VALID, which was to
avoid lstat() on slow filesystems, people have advised/advocated its use
for "narrow checkout".  These people may not even have a file checked out
to the CE_VALID path in the work tree, and they depend on us not running
lstat() on them and instead always answering that the work tree has the
necessary blob.

> I wonder if we have other places where we have optimized away the lstat() 
> just because we decided that it was already up-to-date - without 
> realizing that something could have been marked up-to-date just because 
> it was marked CE_VALID.

That is a very valid concern, but I think fixing them may break the
"narrow checkout" people.

We may need to add ce_uptodate(ce) check instead of doing lstat() in
some places (like the one you modified in this patch), not because we want
to avoid lstat(), but because we do not want to lstat() paths that are
marked as CE_VALID.

There are some mechanisms, such as REFRESH_REALLY flag, to give an escape
hatch to break out of the CE_VALID illusion, but I have to admit that when
we did CE_VALID we did not quite clarified its ramifications with respect
to merging and branch switching.

Re: Fix extraneous lstat's in 'git checkout -f'

[Linus Torvalds]

On Tue, 14 Jul 2009, Junio C Hamano wrote:

> Linus Torvalds <torvalds@linux-foundation.org> writes:
> 
> > Quite frankly, I'd like for us to at least think about removing CE_VALID. 
> 
> This is heavy.  I personally do not use this flag, nor know anybody who
> does, but deviating from the original purpose of CE_VALID, which was to
> avoid lstat() on slow filesystems, people have advised/advocated its use
> for "narrow checkout".

Ahh. I kind of was aware of that, but had totally forgotten.

And in that case, I guess it's also fine. In fact, for that case CE_VALID 
would tend to really mean "always assume CE_UPTODATE", so then the patch I 
sent out doesn't really necessarily need the whole "known_uptodate()" 
thing, and could just use

	if (o->reset && !ce_valid(old)) {

instead.

Which also makes my other worries go away.

			Linus

[PATCH v2] Fix extraneous lstat's in 'git checkout -f'

[Linus Torvalds]

In our 'oneway_merge()' we always do an 'lstat()' to see if we might
need to mark the entry for updating.

But we really shouldn't need to do that when the cache entry is already
marked as being ce_uptodate(), and this makes us do unnecessary lstat()
calls if we have index preloading enabled.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

As Junio noticed, I meant "ce_uptodate()", not "ce_valid()", but this is 
basically the simplified version that replaces the one that cared about 
CE_VALID.

On Tue, 14 Jul 2009, Linus Torvalds wrote:
> 
> And in that case, I guess it's also fine. In fact, for that case CE_VALID 
> would tend to really mean "always assume CE_UPTODATE", so then the patch I 
> sent out doesn't really necessarily need the whole "known_uptodate()" 
> thing, and could just use
> 
> 	if (o->reset && !ce_valid(old)) {
> 
> instead.
> 
> Which also makes my other worries go away.
> 
> 			Linus
> 

 unpack-trees.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index f9d12aa..48d862d 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -1004,7 +1004,7 @@ int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o)
 
 	if (old && same(old, a)) {
 		int update = 0;
-		if (o->reset) {
+		if (o->reset && !ce_uptodate(old)) {
 			struct stat st;
 			if (lstat(old->name, &st) ||
 			    ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID))