threads / discuss / 20104

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

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

## tl;dr

5 messages between Jul 14, 2009 and Jul 14, 2009.

replies: 4people: 2as markdown or json

Linus Torvalds· Jul 14, 2009, 04:01 UTC · lore

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))
Linus Torvalds· Jul 14, 2009, 04:18 UTC · re: Linus Torvalds · lore

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

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
Junio C Hamano· Jul 14, 2009, 08:59 UTC · re: Linus Torvalds · lore

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

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.

Linus Torvalds· Jul 14, 2009, 14:50 UTC · re: Junio C Hamano · lore

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

On Tue, 14 Jul 2009, Junio C Hamano wrote:
Show 8 quoted lines
> 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
Linus Torvalds· Jul 14, 2009, 21:19 UTC · re: Linus Torvalds · lore

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

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:
Show 14 quoted lines
> 
> 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))

← back to recent threads