inotify to minimize stat() calls

... Will Git ever
consider using inotify on Linux? What is the downside?

Quoted 2 lines · Ramkumar Ramachandra

... Will Git ever
consider using inotify on Linux? What is the downside?

I think this has come up from time to time, but my understanding is that nobody thought things through to find a good layer in the codebase to interface to an external daemon that listens to inotify events yet. It is not something like "somebody decreed that we would never consider because of such and such downsides." We are not there yet.

I checked read-cache.c and preload-index.c code. To get the discussion rolling, I think something like the outline below may be a good starting point and a feasible weekend hack for somebody competent:

* At the beginning of preload_index(), instead of spawning the worker thread and doing the lstat() check ourselves, we open a socket to our daemon (see below) that watches this repository and make a request for lstat update. The request will contain:

- The SHA1 checksum of the index file we just read (to ensure that we and our daemon share the same baseline to communicate); and

- the pathspec data.

Our daemon, if it already has a fresh data available, will give us a list of <path, lstat result>. Our main process runs a loop that is equivalent to what preload_thread() runs but uses the lstat() data we obtained from the daemon. If our daemon says it does not have a fresh data (or somehow our daemon is dead), we do the work ourselves.

* Our daemon watches the index file and the working tree, and waits for the above consumer. First it reads the index (and remembers what it read), and whenever an inotify event comes, does the lstat() and remembers the result. It never writes to the index, and does not hold the index lock. Whenever the index file changes, it needs to reload the index, and discard lstat() data it already has for paths that are lost from the updated index.

From the description so far, I have some question: how does the daemon get started and stopped? Is there one per repository --- this seems to be implied by putting the unix domain socket in $GIT_DIR. Could we automatically reject connections from anything other than localhost when using TCP?

Quoted 23 lines · Junio C Hamano

I checked read-cache.c and preload-index.c code. To get the discussion rolling, I think something like the outline below may be a good starting point and a feasible weekend hack for somebody competent:

* At the beginning of preload_index(), instead of spawning the worker thread and doing the lstat() check ourselves, we open a socket to our daemon (see below) that watches this repository and make a request for lstat update. The request will contain:

- The SHA1 checksum of the index file we just read (to ensure that we and our daemon share the same baseline to communicate); and

- the pathspec data.

Our daemon, if it already has a fresh data available, will give us a list of <path, lstat result>. Our main process runs a loop that is equivalent to what preload_thread() runs but uses the lstat() data we obtained from the daemon. If our daemon says it does not have a fresh data (or somehow our daemon is dead), we do the work ourselves.

Quoted 8 lines

* Our daemon watches the index file and the working tree, and waits for the above consumer. First it reads the index (and remembers what it read), and whenever an inotify event comes, does the lstat() and remembers the result. It never writes to the index, and does not hold the index lock. Whenever the index file changes, it needs to reload the index, and discard lstat() data it already has for paths that are lost from the updated index.

I left the details unsaid in thee above because I thought it was fairly obvious from the nature of the "outline", but let me spend a few more lines to avoid confusion.

- The way the daemon "watches" the changes to the working tree and the index may well be very platform dependent. I said "inotify" above, but the mechanism does not have to be inotify.

- The channel the daemon and the client communicates would also be system dependent. UNIX domain socket in $GIT_DIR/ with a well-known name would be one possibility but it does not have to be the only option.

- The data given from the daemon to the client does not have to include full lstat() information. They start from the same index info, and the only thing preload_index() wants to know is for which paths it should call ce_mark_uptodate(ce), so the answer given by our daemon can be a list of paths.
--
To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

From the description so far, I have some question: how does the daemon get started and stopped? Is there one per repository ...

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 3 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

On Sat, Feb 9, 2013 at 1:35 PM, Junio C Hamano

Quoted 6 lines

Quoted 4 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 8 lines

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

What if instead of communicating over a socket, the daemon dumped a file containing all of the lstat information after git wrote a file? By definition the daemon should know about file writes.

Quoted 1 line · Robert Zeh

On Sat, Feb 9, 2013 at 1:35 PM, Junio C Hamano

Quoted 15 lines · <[email protected]> wrote:

Quoted 6 lines

Quoted 4 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 8 lines

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

Quoted 4 lines

What if instead of communicating over a socket, the daemon dumped a file containing all of the lstat information after git wrote a file? By definition the daemon should know about file writes.

But git doesn't, how will it know when the file is written? Will it use inotify, or poll (kind of defeats the point)?

-Martin

Quoted 6 lines · Junio C Hamano

Quoted 3 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 6 lines

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

What if instead of communicating over a socket, the daemon dumped a file containing all of the lstat information after git wrote a file? By definition the daemon should know about file writes.

There would be no network communication, which I think would make things more secure. It would simplify the rendezvous by insisting on well known locations in $GIT_DIR.

Quoted 14 lines · Robert Zeh

Quoted 6 lines · Junio C Hamano

Quoted 3 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 6 lines

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

Quoted 7 lines

What if instead of communicating over a socket, the daemon dumped a file containing all of the lstat information after git wrote a file? By definition the daemon should know about file writes.

There would be no network communication, which I think would make things more secure. It would simplify the rendezvous by insisting on well known locations in $GIT_DIR.

We need some sort of interactive communication to the daemon anyway, to validate that the information is uptodate. Assume that a user makes some changes to his worktree before starting the daemon, git needs to know that what the daemon provides does not represent a complete file-change picture and it better refreshes the index the old way once, then trust the daemon.

I think we could solve that by storing a "session id", provided by the daemon, in .git/index. If the session id is not present (or does not match what the current daemon gives), refresh the old way. After refreshing, it may ask the daemon for new session id and store it. Next time if the session id is still valid, trust the daemon's data. This session id should be different every time the daemon restarts for this to work.

Quoted 30 lines · Duy Nguyen

Quoted 14 lines · Robert Zeh

Quoted 6 lines · Junio C Hamano

Quoted 3 lines · Ramkumar Ramachandra

This is much better than Junio's suggestion to study possible implementations on all platforms and designing a generic daemon/ communication channel. That's no weekend project.

Quoted 6 lines

It appears that you misunderstood what I wrote. That was not "here is a design; I want it in my system. Go implemment it".

It was "If somebody wants to discuss it but does not know where to begin, doing a small experiment like this and reporting how well it worked here may be one way to do so.", nothing more.

Quoted 7 lines

What if instead of communicating over a socket, the daemon dumped a file containing all of the lstat information after git wrote a file? By definition the daemon should know about file writes.

There would be no network communication, which I think would make things more secure. It would simplify the rendezvous by insisting on well known locations in $GIT_DIR.

We need some sort of interactive communication to the daemon anyway, to validate that the information is uptodate. Assume that a user makes some changes to his worktree before starting the daemon, git needs to know that what the daemon provides does not represent a complete file-change picture and it better refreshes the index the old way once, then trust the daemon.

Quoted 7 lines

I think we could solve that by storing a "session id", provided by the daemon, in .git/index. If the session id is not present (or does not match what the current daemon gives), refresh the old way. After refreshing, it may ask the daemon for new session id and store it. Next time if the session id is still valid, trust the daemon's data. This session id should be different every time the daemon restarts for this to work.

I think we could do this without interactive communication,
if we did the following:
1) The Daemon waits to see $GIT_DIR/lstat_request, and atomically writes out $GIT_DIR/lstat_cache. By atomically I mean that it writes things out to a temporary file, and then does a rename.

2) The client erases $GIT_DIR/lstat_cache, and writes $GIT_DIR/lstat_request

I think this is better than socket based communication because there are fewer places to check
for failures.

Here is a patch that creates a daemon that tracks file state with inotify, writes it out to a file upon request, and changes most of the calls to stat to use said cache.

It has bugs, but I figured it would be smarter to see if the approach was acceptable at all before spending the time to root the bugs out.

I've implemented the communication with a file, and not a socket, because I think implementing a socket is going to create security issues on multiuser systems. For example, would a socket allow stat information to cross user boundaries?

 filechange-cache.c   | 203

+++++++++++++++++++++++++++++++++++++++++++++++++++

filechange-daemon.c new file +10 -0

+static void watch_directory(int inotify_fd)
+{
+	char buf[PATH_MAX];
+
+	if (!getcwd(buf, sizeof(buf)))
+		die_errno("Unable to get current directory");
+
+	int i = 0;
+	struct dir_struct dir;
+	const char *pathspec[1] = { buf, NULL };

filechange-daemon.c new file +6 -0

+	while (1) {
+		int i = 0;
+		length = read(inotify_fd, buffer, sizeof(buffer));
+		for(i = 0; i < length; ) {
+			struct inotify_event *event =
+				(struct inotify_event*)(buffer+i);

Quoted 7 lines · Robert Zeh

Here is a patch that creates a daemon that tracks file state with inotify, writes it out to a file upon request, and changes most of the calls to stat to use said cache.

It has bugs, but I figured it would be smarter to see if the approach was acceptable at all before spending the time to root the bugs out.

Thanks for tackling this; it's probably about time we got a inotify support :-(

Quoted 4 lines

I've implemented the communication with a file, and not a socket, because I think implementing a socket is going to create security issues on multiuser systems. For example, would a socket allow stat information to cross user boundaries?

This ties in with an issue discussed in an earlier thread:

http://thread.gmane.org/gmane.comp.version-control.git/217817/focus=218307

The conclusion there was that the default limits are set such that it is not feasible to run one daemon per repository (that would quickly hit the limits when e.g. iterating all repos in a typical android tree using repo).

So whatever you use for communication needs to work as a global daemon.

I'd just trust the SSH folks to know about security; on my system ssh-agent creates

/tmp/ssh-RANDOMSTRING/agent.PID

where the directory has mode 0700, and the file is a unit socket with mode 0600. That should make doubly sure that no other user can open the socket.

Quoted 2 lines

 filechange-cache.c   | 203

+++++++++++++++++++++++++++++++++++++++++++++++++++

Is your MUA wrapping the patch?

Quoted 16 lines

filechange-daemon.c new file +16 -0

+static void watch_directory(int inotify_fd)
+{
+     char buf[PATH_MAX];
+
+     if (!getcwd(buf, sizeof(buf)))
+             die_errno("Unable to get current directory");
+
+     int i = 0;
+     struct dir_struct dir;
+     const char *pathspec[1] = { buf, NULL };
+
+     memset(&dir, 0, sizeof(dir));
+     setup_standard_excludes(&dir);
+
+     fill_directory(&dir, pathspec);
+     for(i = 0; i < dir.nr; i++) {

filechange-daemon.c line 92

Quoted 4 lines

filechange-daemon.c new file +4 -0

+             struct dir_entry *ent = dir.entries[i];
+             watch_file(inotify_fd, ent->name);
+             free(ent);
+     }

I don't get this bit. The lstat() are run over all files listed in the index. So shouldn't your daemon watch exactly those (or rather, all dirnames of such files)?

The actual directory contents are only needed to find untracked files, and there would be a lot of complication surrounding that, so I suggest saving that for later (and for now measuring the speedup with 'git status -uno'!).

For example, you'd have to actually watch and re-read all .gitignore files, and the .git/info/exclude, and the core.excludesfile, to see if your notion of an ignored file became stale.

Also, you seem to call watch_directory() only on the current(?) dir, but you need to recursively set up watches for all directories in the repository.

Quoted 6 lines

filechange-daemon.c new file +6 -0

+     while (1) {
+             int i = 0;
+             length = read(inotify_fd, buffer, sizeof(buffer));
+             for(i = 0; i < length; ) {
+                     struct inotify_event *event =
+                             (struct inotify_event*)(buffer+i);

filechange-daemon.c line 142

Quoted 10 lines

filechange-daemon.c new file +10 -0

+                     /* printf("event: %d %x %d %s\n", event->wd, event->mask,
+                        event->len, event->name); */
+                     if (request_watch_descriptor == event->wd) {
+                             write_stat_cache();
+                     } else if (root_directory_watch_descriptor
+                                == event->wd) {
+                             printf("root directory died!\n");
+                             exit(0);
+                     } else if (event->mask & IN_Q_OVERFLOW) {
+                             restart();

Good.

filechange-daemon.c line 146

Quoted 4 lines

filechange-daemon.c new file +4 -0

+                     } else if (event->mask & IN_MODIFY) {
+                             if (event->len)
+                                     update_stat_cache(event->name);
+                     }

So whenever a file changes, you stat() it. That's good for simplicity now, but I suspect it will provide some optimization opportunities later.

On some design aspects, I'd want:

* a toggle to run the test suite with the daemons, or without

* if you go with a user-wide daemon, a way to ensure that the test-suite daemon is not the same as my "real" daemon, and make sure it is killed after the test runs finish

* a test that triggers IN_Q_OVERFLOW, e.g. by sending SIGSTOP and doing a large repository operation

* a test that renames directories

The last one is just based on my personal experience with messing with inotify; renaming directories is the "hard" case for that API. We may already cover this in the test suite, or we may not; but it must be tested.

Other than that last point, focus your tests not on small tests but on the test suite. It would seem rather unlikely to me that you could manage to pass the entire test suite with this daemon active but broken.

--
Thomas Rast
trast@{inf,student}.ethz.ch

Quoted 4 lines · Thomas Rast

I don't get this bit. The lstat() are run over all files listed in the index. So shouldn't your daemon watch exactly those (or rather, all dirnames of such files)?

I believe that fill_directory is handling watching only files in the index. I had some problems a while back when I was only watching the directory with some of the inotify structures coming back empty, which is why I started watching each individual file.

Quoted 9 lines · Robert Zeh

Quoted 4 lines · Thomas Rast

I don't get this bit. The lstat() are run over all files listed in the index. So shouldn't your daemon watch exactly those (or rather, all dirnames of such files)?

I believe that fill_directory is handling watching only files in the index. I had some problems a while back when I was only watching the directory with some of the inotify structures coming back empty, which is why I started watching each individual file.

This probably doesn't scale well enough. For example on my system the maximum number of watches I can set[1] is 64k. linux.git contains 38k files and the total number of files in all repos of an android clone I have lying around is almost 300k.

Here is a patch that creates a daemon that tracks file state with inotify, writes it out to a file upon request, and changes most of the calls to stat to use said cache.

It has bugs, but I figured it would be smarter to see if the approach was acceptable at all before spending the time to root the bugs out.

I've implemented the communication with a file, and not a socket, because I think implementing a socket is going to create
security issues on multiuser systems. For example, would a socket allow stat information to cross user boundaries?

 abspath.c            |   9 ++-
 bisect.c             |   3 +-
 check-racy.c         |   2 +-
 combine-diff.c       |   3 +-
 command-list.txt     |   1 +
 config.c             |   3 +-
 copy.c               |   3 +-
 diff-lib.c           |   3 +-
 diff-no-index.c      |   3 +-
 diff.c               |   9 ++-
 diffcore-order.c     |   3 +-
 dir.c                |   4 +-
 filechange-cache.c   | 203
+++++++++++++++++++++++++++++++++++++++++++++++++++
 filechange-cache.h   |  20 +++++
 filechange-daemon.c  | 164 +++++++++++++++++++++++++++++++++++++++++
 filechange-printer.c |  13 ++++
 git.c                |  27 +++++++
 ll-merge.c           |   3 +-
 merge-recursive.c    |   5 +-
 name-hash.c          |   3 +-
 name-hash.h          |   1 +
 notes-merge.c        |   3 +-
 path.c               |   5 +-
 read-cache.c         |  11 +--
 rerere.c             |   7 +-
 setup.c              |   5 +-
 test-chmtime.c       |   2 +-

 test-wildmatch.c     |   2 +-
 unpack-trees.c       |   6 +-
 29 files changed, 486 insertions(+), 40 deletions(-)
 create mode 100644 filechange-cache.c
 create mode 100644 filechange-cache.h
 create mode 100644 filechange-daemon.c
 create mode 100644 filechange-printer.c
 create mode 100644 name-hash.h

Quoted 4 lines · Robert Zeh

Here is a patch that creates a daemon that tracks file state with inotify, writes it out to a file upon request, and changes most of the calls to stat to use said cache.

Quoted 3 lines

It has bugs, but I figured it would be smarter to see if the approach was acceptable at all before spending the time to root the bugs out.

Any preliminary performance numbers? How does it do compared to no-inotify version? When only a few files are changed? When half the repo is changed?

Quoted 4 lines

I've implemented the communication with a file, and not a socket, because I think implementing a socket is going to create
security issues on multiuser systems. For example, would a socket allow stat information to cross user boundaries?

I think UNIX socket on Linux at least respects file permissions. But unix(7) follows with "This behavior differs from many BSD-derived systems which ignore permissions for Unix sockets". Sighh

Quoted 28 lines

 abspath.c            |   9 ++-
 bisect.c             |   3 +-
 check-racy.c         |   2 +-
 combine-diff.c       |   3 +-
 command-list.txt     |   1 +
 config.c             |   3 +-
 copy.c               |   3 +-
 diff-lib.c           |   3 +-
 diff-no-index.c      |   3 +-
 diff.c               |   9 ++-
 diffcore-order.c     |   3 +-
 dir.c                |   4 +-
 filechange-cache.c   | 203
+++++++++++++++++++++++++++++++++++++++++++++++++++
 filechange-cache.h   |  20 +++++
 filechange-daemon.c  | 164 +++++++++++++++++++++++++++++++++++++++++
 filechange-printer.c |  13 ++++
 git.c                |  27 +++++++
 ll-merge.c           |   3 +-
 merge-recursive.c    |   5 +-
 name-hash.c          |   3 +-
 name-hash.h          |   1 +
 notes-merge.c        |   3 +-
 path.c               |   5 +-
 read-cache.c         |  11 +--
 rerere.c             |   7 +-
 setup.c              |   5 +-
 test-chmtime.c       |   2 +-

Quoted 8 lines

 test-wildmatch.c     |   2 +-
 unpack-trees.c       |   6 +-
 29 files changed, 486 insertions(+), 40 deletions(-)
 create mode 100644 filechange-cache.c
 create mode 100644 filechange-cache.h
 create mode 100644 filechange-daemon.c
 create mode 100644 filechange-printer.c
 create mode 100644 name-hash.h

Can you just replace lstat/stat with cached_lstat/stat inside git-compat-util.h and not touch all files at once? I think you may need to deal with paths outside working directory. But because you're using lookup table, that should be no problem.

Quoted 4 lines

Can you just replace lstat/stat with cached_lstat/stat inside git-compat-util.h and not touch all files at once? I think you may need to deal with paths outside working directory. But because you're using lookup table, that should be no problem.

That's a good idea; but there are a few places where you want to call the uncached stat because calling the cache leads to recursion or you bump into things that haven't been setup yet. Any ideas how to handle that?

Quoted 9 lines · Robert Zeh

Quoted 4 lines

Can you just replace lstat/stat with cached_lstat/stat inside git-compat-util.h and not touch all files at once? I think you may need to deal with paths outside working directory. But because you're using lookup table, that should be no problem.

That's a good idea; but there are a few places where you want to call the uncached stat because calling the cache leads to recursion or you bump into things that haven't been setup yet. Any ideas how to handle that?

On second thought, no my idea was stupid. We only need to optimize lstat for certain cases and naming cached_lstat is much clearer. I suspect read-cache.c and maybe dir.c and unpack-trees.c are the only places that need cached_lstat. Other places should not issue many lstats and we don't need to touch them.

filechange-cache.c new file +8 -0

+int cached_lstat(const char *path, struct stat *buf)
+{
+       int stat_return_value = 0;
+       struct stat_cache_entry *entry = 0;
+
+       read_stat_cache();
+
+       entry = get_stat_cache_entry(path);

The call to lstat is only there for testing and should not be in there for the final version. Is there an easy way to only enable it for tests?

What about getting systemd to watch everything for us? Then we can just have one daemon reporting filesystem changes over one global socket. It's API should be the inotify subset:

What about getting systemd to watch everything for us?

Quoted 1 line · Ramkumar Ramachandra

What about getting systemd to watch everything for us?

systemd is the perfect candidate!

How about this as a start? I did not really check what it does, but it does not look complicate enough to pull systemd in.

http://article.gmane.org/gmane.comp.version-control.git/151934

Youo may want to search the mail archive. This topic has come up a few times before, there may be other similar patches.

Finn notes in the commit message that it offers no speedup, because .gitignore files in every directory still have to be read. I think this is silly: we really should be caching .gitignore, and touching it only when lstat() reports that the file has changed.

...

Really, the elephant in the room right now seems to be .gitignore. Until that is fixed, there is really no use of writing this inotify daemon, no? Can someone enlighten me on how exactly .gitignore files are processed?

Quoted 11 lines · Ramkumar Ramachandra

Finn notes in the commit message that it offers no speedup, because .gitignore files in every directory still have to be read. I think this is silly: we really should be caching .gitignore, and touching it only when lstat() reports that the file has changed.

...

Really, the elephant in the room right now seems to be .gitignore. Until that is fixed, there is really no use of writing this inotify daemon, no? Can someone enlighten me on how exactly .gitignore files are processed?

.gitignore is a different issue. I think it's mainly used with read_directory/fill_directory to collect ignored files (or not-ignored files). And it's not always used (well, status and add does, but diff should not). I think wee need to measure how much mass lstat elimination gains us (especially on big repos) and how much .gitignore/.gitattributes caching does.

The following patch eliminates untracked search code. As we can see, open+getdents also disappears with this patch:

0.462909 40950 lstat   0.462909 40950 lstat
0.003417 129 brk       0.003417 129 brk
0.000762 53 read       0.000762 53 read
0.000720 36 open       0.000720 36 open
0.000544 12 munmap     0.000454 33 close

Quoted 8 lines · Duy Nguyen

The following patch eliminates untracked search code. As we can see, open+getdents also disappears with this patch:

0.462909 40950 lstat   0.462909 40950 lstat
0.003417 129 brk       0.003417 129 brk
0.000762 53 read       0.000762 53 read
0.000720 36 open       0.000720 36 open
0.000544 12 munmap     0.000454 33 close

.. and the patch is missing:

-- 8< --

dir.c +0 -0

index 57394e4..1963c6f 100644

The other "lstat()" experiment was a very interesting one, but this is not yet an interesting experiment to see where in the "ignore" codepath we are spending times.

We know that we can tell wt_status_collect_untracked() not to bother with the untracked or ignored files with !s->show_untracked_files already, but I think the more interesting question is if we can show the untracked files with less overhead.

If we want to show untrackedd files, it is a given that we need to read directories to see what paths there are on the filesystem. Is the opendir/readdir cost dominating in the process? Are we spending a lot of time sifting the result of opendir/readdir via the ignore mechanism? Is reading the "ignore" files costing us much to prime the ignore mechanism?

If readdir cost is dominant, then that makes "cache gitignore" a nonsense proposition, I think. If you really want to "cache" something, you need to have somebody (i.e. a daemon) who constantly keeps an eye on the filesystem changes and can respond with the up to date result directly to fill_directory(). I somehow doubt that it is a direction we would want to go in, though.

        unmodified  dir.c
real    0m0.550s    0m0.287s
user    0m0.305s    0m0.201s
sys     0m0.240s    0m0.084s

Yeah, it did not cut out syscall cost, I also cut a lot of user-space processing (plus .gitignore content access). From the timings I posted earlier,

Quoted 4 lines

        unmodified  dir.c
real    0m0.550s    0m0.287s
user    0m0.305s    0m0.201s
sys     0m0.240s    0m0.084s

sys time is reduced from 0.24s to 0.08s, so readdir+opendir definitely has something to do with it (and perhaps reading .gitignore). But it also reduces user time from 0.305 to 0.201s. I don't think avoiding readdir+openddir will bring us this gain. It's probably the cost of matching .gitignore. I'll try to replace opendir+readdir with a no-syscall version. At this point "untracked caching" sounds more feasible (and less complex) than ".gitignore cachine".

Quoted 16 lines · Junio C Hamano

The other "lstat()" experiment was a very interesting one, but this is not yet an interesting experiment to see where in the "ignore" codepath we are spending times.

We know that we can tell wt_status_collect_untracked() not to bother with the untracked or ignored files with !s->show_untracked_files already, but I think the more interesting question is if we can show the untracked files with less overhead.

If we want to show untrackedd files, it is a given that we need to read directories to see what paths there are on the filesystem. Is the opendir/readdir cost dominating in the process? Are we spending a lot of time sifting the result of opendir/readdir via the ignore mechanism? Is reading the "ignore" files costing us much to prime the ignore mechanism?

Quoted 6 lines

If readdir cost is dominant, then that makes "cache gitignore" a nonsense proposition, I think. If you really want to "cache" something, you need to have somebody (i.e. a daemon) who constantly keeps an eye on the filesystem changes and can respond with the up to date result directly to fill_directory(). I somehow doubt that it is a direction we would want to go in, though.

Yeah, it did not cut out syscall cost, I also cut a lot of user-space processing (plus .gitignore content access). From the timings I posted earlier,

Quoted 4 lines

        unmodified  dir.c
real    0m0.550s    0m0.287s
user    0m0.305s    0m0.201s
sys     0m0.240s    0m0.084s

sys time is reduced from 0.24s to 0.08s, so readdir+opendir definitely has something to do with it (and perhaps reading .gitignore). But it also reduces user time from 0.305 to 0.201s. I don't think avoiding readdir+openddir will bring us this gain. It's probably the cost of matching .gitignore. I'll try to replace opendir+readdir with a no-syscall version. At this point "untracked caching" sounds more feasible (and less complex) than ".gitignore cachine".

builtin/commit.c int cmd_status(int argc, const char **argv, const char *prefix) · line 1162

Quoted 10 lines · Torsten Bögershausen

builtin/commit.c +2 -0

index d6dd3df..6a5ba11 100644
@@ -1158,6 +1158,8 @@ int cmd_status(int argc, const char **argv, const char *prefix)
 	unsigned char sha1[20];
 	static struct option builtin_status_options[] = {
 		OPT__VERBOSE(&verbose, N_("be verbose")),
+		OPT_BOOLEAN('c', "changed-only", &s.check_changed_only,
+			    N_("Ignore untracked files. Check if files known to git are modified")),

Doesn't this make one wonder why a separate bit and implementation is necessary to say "I am not interested in untracked files" when "-uno" option is already there?

--
To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 3 lines

Doesn't this make one wonder why a separate bit and implementation is necessary to say "I am not interested in untracked files" when "-uno" option is already there?

...
I need to admit that I wasn't aware about "git status -uno".

Thinking about it, how many git users are aware of the speed penalty when running git status to find out which (tracked) files they had changed?

Or to put it the other way, when a developer wants a quick overview about the files she changed, then git status -uno may be a good and fast friend.

Does it make sence to stress put that someway in the documentation?

Documentation/git-status.txt +0 -0

index 9f1ef9a..360d813 100644

Quoted 5 lines · Torsten Bögershausen

Quoted 3 lines

Doesn't this make one wonder why a separate bit and implementation is necessary to say "I am not interested in untracked files" when "-uno" option is already there?

...
I need to admit that I wasn't aware about "git status -uno".

Not so fast. I did not ask you "Why do you need a new one to solve the same problem -uno already solves?"

Quoted 13 lines

Thinking about it, how many git users are aware of the speed penalty when running git status to find out which (tracked) files they had changed?

Or to put it the other way, when a developer wants a quick overview about the files she changed, then git status -uno may be a good and fast friend.

Does it make sence to stress put that someway in the documentation?

Documentation/git-status.txt +0 -0

index 9f1ef9a..360d813 100644

Documentation/git-status.txt default is 'normal', i.e. show untracked files and directori · line 54

Quoted 5 lines

Documentation/git-status.txt +1 -1

@@ -51,13 +51,18 @@ default is 'normal', i.e. show untracked files and directori
 +
 The possible options are:
 +
-       - 'no'     - Show no untracked files
+       - 'no'     - Show no untracked files (this is fastest)

There is a trade-off around the use of -uno between safety and performance. The default is not to use -uno so that you will not forget to add a file you newly created (i.e safety). You would pay for the safety with the cost to find such untracked files (i.e. performance).

I suspect that the documentation was written with the assumption that at least for the people who are reading this part of the documentation, the trade-off is obvious. In order to find more information, you naturally need to spend more cycles.

If the trade-off is not so obvious, however, I do not object at all to describing it. But if we are to do so, I do object to mentioning only one side of the trade-off. People who choose "fastest" needs to be made very aware that they are disabling "safety".

That brings us back to the "Why a separate implementation when -uno is there?" question.

Documentation/git-status.txt default is 'normal', i.e. show untracked files and directori · line 54

Quoted 4 lines

The possible options are:
+

Documentation/git-status.txt +1 -1

-       - 'no'     - Show no untracked files
+       - 'no'     - Show no untracked files (this is fastest)

There is a trade-off around the use of -uno between safety and performance. The default is not to use -uno so that you will not forget to add a file you newly created (i.e safety). You would pay for the safety with the cost to find such untracked files (i.e. performance).

I suspect that the documentation was written with the assumption that at least for the people who are reading this part of the documentation, the trade-off is obvious. In order to find more information, you naturally need to spend more cycles.

If the trade-off is not so obvious, however, I do not object at all to describing it. But if we are to do so, I do object to mentioning only one side of the trade-off. People who choose "fastest" needs to be made very aware that they are disabling "safety".

Quoted 16 lines · Junio C Hamano

Documentation/git-status.txt default is 'normal', i.e. show untracked files and directori · line 54

Quoted 4 lines

The possible options are:
+

Documentation/git-status.txt +1 -1

-       - 'no'     - Show no untracked files
+       - 'no'     - Show no untracked files (this is fastest)

There is a trade-off around the use of -uno between safety and performance. The default is not to use -uno so that you will not forget to add a file you newly created (i.e safety). You would pay for the safety with the cost to find such untracked files (i.e. performance).

I suspect that the documentation was written with the assumption that at least for the people who are reading this part of the documentation, the trade-off is obvious. In order to find more information, you naturally need to spend more cycles.

Quoted 4 lines

If the trade-off is not so obvious, however, I do not object at all to describing it. But if we are to do so, I do object to mentioning only one side of the trade-off. People who choose "fastest" needs to be made very aware that they are disabling "safety".

On the topic of trading off, I was thinking about new -uauto as default that is like -uall if it takes less than a certan amount of time (e.g. 0.5 seconds), if it exceeds that limit, the operation is aborted (i.e. it turns to -uno). The safety net is still there, "git status" advices to use -u to show full information.

Or a less intrusive approach: measure the time and advice the user to (read doc and) use -uno.

But it's probably worth waiting for the first cut of inotify support from Ram. It's better with inotify anyway.

This patch attempts to advertise -uno to the users who tolerate slow "git status" on large repositories (or slow machines/disks). The 2 seconds limit is quite arbitrary but is probably long enough to start using -uno.

Signed-off-by Nguyễn Thái Ngọc Duy <[email protected]>

---
 Documentation/config.txt |  4 ++++
 advice.c                 |  2 ++
 advice.h                 |  1 +
 t/t7060-wtstatus.sh      |  2 ++
 t/t7508-status.sh        |  4 ++++
 t/t7512-status-help.sh   |  1 +
 wt-status.c              | 20 +++++++++++++++++++-
 wt-status.h              |  1 +
 8 files changed, 34 insertions(+), 1 deletion(-)

Documentation/config.txt +0 -0

index bbba728..e91d06f 100644

wt-status.c +1 -1

index ef405d0..6fde08b 100644
@@ -540,7 +540,16 @@ void wt_status_collect(struct wt_status *s)
 		wt_status_collect_changes_initial(s);
 	else
 		wt_status_collect_changes_index(s);
-	wt_status_collect_untracked(s);
+	if (s->show_untracked_files && advice_status_uno) {

wt-status.c +0 -0

 static void wt_status_print_unmerged(struct wt_status *s)

@@ -1097,6 +1106,15 @@ void wt_status_print(struct wt_status *s)
 		wt_status_print_other(s, &s->untracked, _("Untracked files"), "add");
 		if (s->show_ignored_files)

Documentation/config.txt advice.*:: · line 184

Quoted 4 lines

Documentation/config.txt +4 -0

+     statusUno::
+             If collecting untracked files in linkgit:git-status[1]
+             takes more than 2 seconds, hint the user that the option
+             `-uno` could be used to stop collecting untracked files.

Thanks, I like the idea
could we make a "de-Luxe" version where

statusUno is an integer, counting in milliseconds?

The noise this introduces to the test suite is a bit irritating and makes us think twice if this really a good change.

wt-status.c void wt_status_print(struct wt_status *s) · line 1117

Quoted 10 lines

static void wt_status_print_unmerged(struct wt_status *s)

wt-status.c +9 -0

+             if (advice_status_uno && s->untracked_in_ms > 2000) {
+                     status_printf_ln(s, GIT_COLOR_NORMAL,
+                                      _("It took %.2f seconds to collect untracked files."),
+                                      (float)s->untracked_in_ms / 1000);
+                     status_printf_ln(s, GIT_COLOR_NORMAL,
+                                      _("If it happens often, you may want to use option -uno"));
+                     status_printf_ln(s, GIT_COLOR_NORMAL,
+                                      _("to speed up by stopping displaying untracked files"));
+             }

"to speed up by stopping displaying untracked files" does not look like giving a balanced suggestion. It is increasing the risk of forgetting about newly created files the user may want to add, but the risk is not properly warned.

I tend to agree that the new advice would help users if phrased in a right way. Do we want them in COLOR_NORMAL, or do we want to make them stand out a bit more (do we have COLOR_BLINK ;-)?

Quoted 8 lines · Torsten Bögershausen

Documentation/config.txt advice.*:: · line 184

Quoted 4 lines

Documentation/config.txt +4 -0

+     statusUno::
+             If collecting untracked files in linkgit:git-status[1]
+             takes more than 2 seconds, hint the user that the option
+             `-uno` could be used to stop collecting untracked files.

Thanks, I like the idea
could we make a "de-Luxe" version where

statusUno is an integer, counting in milliseconds?

No problem.

Quoted 4 lines

"to speed up by stopping displaying untracked files" does not look like giving a balanced suggestion. It is increasing the risk of forgetting about newly created files the user may want to add, but the risk is not properly warned.

How about "It took X ms to collect untracked files.\nCheck out the option -u for a potential speedup"? I deliberately hide "no" so that the user cannot blindly type and run it without reading document first. We can give full explanation and warning there in the document.

Quoted 5 lines

Quoted 4 lines

"to speed up by stopping displaying untracked files" does not look like giving a balanced suggestion. It is increasing the risk of forgetting about newly created files the user may want to add, but the risk is not properly warned.

Quoted 4 lines

How about "It took X ms to collect untracked files.\nCheck out the option -u for a potential speedup"? I deliberately hide "no" so that the user cannot blindly type and run it without reading document first. We can give full explanation and warning there in the document.

But it makes the advise much less useful to introduce more levels of indirections, no?

Quoted 8 lines · Junio C Hamano

Quoted 8 lines

Quoted 4 lines

"to speed up by stopping displaying untracked files" does not look like giving a balanced suggestion. It is increasing the risk of forgetting about newly created files the user may want to add, but the risk is not properly warned.

How about "It took X ms to collect untracked files.\nCheck out the option -u for a potential speedup"? I deliberately hide "no" so that the user cannot blindly type and run it without reading document first. We can give full explanation and warning there in the document.

Quoted 2 lines

But it makes the advise much less useful to introduce more levels of indirections, no?

To me the message's value is the pointer to -uno that not many people know about. And I don't want it to be too verbose as there'll be false positives (cold cache, busy disks, low memory..), 2-3 lines should be max. So indirections are not a concern. You want to speed up, you need to pay some time. Anyway how do you put it to suggest -uno in git-status with all the implications?

[PATCH] git status: Document that git status -uno is faster

In some repostories users expere that "git status" command takes long time.

The command spends some time searching the file system for untracked files. Document that searching for untracked file may take some time, and docuemnt the option -uno better.

Signed-off-by Torsten Bögershausen <[email protected]>

---
 Documentation/git-status.txt | 7 +++++++
 1 file changed, 7 insertions(+)

Documentation/git-status.txt +5 -0

index 0412c40..fd36bbd 100644
@@ -58,6 +58,13 @@ The possible options are:
 The default can be changed using the status.showUntrackedFiles
 configuration variable documented in linkgit:git-config[1].
 
++
+Note: Searching the file system for untracked files may take some time.
+git status -uno is faster than git status -uall.
+There is a trade-off around the use of -uno between safety and performance.
+The default is not to use -uno so that you will not forget to add a

file you newly created (i.e safety).
+You would pay for the safety with the cost to find such untracked files (i.e. performance).
+

Quoted 3 lines · Torsten Bögershausen

[PATCH] git status: Document that git status -uno is faster

In some repostories users expere that "git status" command takes long time.

expere??? Certainly you did not mean "expect". "observe", "experience", or "see", perhaps?

Quoted 3 lines

The command spends some time searching the file system for untracked files. Document that searching for untracked file may take some time, and docuemnt the option -uno better.

Good intentions.

Quoted 18 lines

Signed-off-by Torsten Bögershausen<[email protected]>

---
  Documentation/git-status.txt | 7 +++++++
  1 file changed, 7 insertions(+)

Documentation/git-status.txt +5 -0

index 0412c40..fd36bbd 100644
@@ -58,6 +58,13 @@ The possible options are:
  The default can be changed using the status.showUntrackedFiles
  configuration variable documented in linkgit:git-config[1].
 
++
+Note: Searching the file system for untracked files may take some time.
+git status -uno is faster than git status -uall.
+There is a trade-off around the use of -uno between safety and performance.
+The default is not to use -uno so that you will not forget to add a

Quoted 4 lines

file you newly created (i.e safety).
+You would pay for the safety with the cost to find such untracked files (i.e. performance).
+

The second sentence looks out of flow, and the last sentence, while technically not incorrect, is unclear what it is trying to convey in the larger picture.

Perhaps it is just me.

In any case, I think it is a good idea to explain the reason why the user might want to use a non-default setting, and the criteria the user may want to base the choice on (which is the gist of your addition), and it is a good idea to do so _before_ saying "The default can be changed using ...".

How about this?

  Documentation/git-status.txt | 14 ++++++++++----
  1 file changed, 10 insertions(+), 4 deletions(-)

Documentation/git-status.txt +1 -3

index 0412c40..9046df9 100644
@@ -46,15 +46,21 @@ OPTIONS
  	Show untracked files.
  +
  The mode parameter is optional (defaults to 'all'), and is used to
-specify the handling of untracked files; when -u is not used, the
-default is 'normal', i.e. show untracked files and directories.
+specify the handling of untracked files.
  +
  The possible options are:
  +
-	- 'no'     - Show no untracked files

Thanks, I like that much better than mine
(and expere is probably a word not yet invented)

Quoted 2 lines · Torsten Bögershausen

Quoted 2 lines

Thanks, I like that much better than mine
(and expere is probably a word not yet invented)

OK, then how about redoing Duy's patch like this on top?

I've moved the timing collection from the caller to callee, and I think the result is more readable. The message looked easier to see with a leading blank line, so I added one.

-- >8 --
From: Nguyễn Thái Ngọc Duy <[email protected]>
Date: Wed, 13 Mar 2013 19:59:16 +0700
Subject: [PATCH] status: advise to consider use of -u when read_directory takes too long

Introduce advice.statusUoption to suggest considering use of -u to strike different trade-off when it took more than 2 seconds to enumerate untracked/ignored files.

Signed-off-by Nguyễn Thái Ngọc Duy <[email protected]>

Signed-off-by Junio C Hamano <[email protected]>

---
 Documentation/config.txt |  4 ++++
 advice.c                 |  2 ++
 advice.h                 |  1 +
 t/t7060-wtstatus.sh      |  1 +
 t/t7508-status.sh        |  1 +
 t/t7512-status-help.sh   |  1 +
 wt-status.c              | 21 +++++++++++++++++++++
 wt-status.h              |  1 +
 8 files changed, 32 insertions(+)

Documentation/config.txt +4 -0

index d1de857..a16eda5 100644
@@ -163,6 +163,10 @@ advice.*::
 		state in the output of linkgit:git-status[1] and in
 		the template shown when writing commit messages in
 		linkgit:git-commit[1].
+	statusUoption::
+		Advise to consider using the `-u` option to linkgit:git-status[1]
+		when the command takes more than 2 seconds to enumerate untracked
+		files.
 	commitBeforeMerge::
 		Advice shown when linkgit:git-merge[1] refuses to
 		merge to avoid overwriting local changes.

advice.c +2 -0

index edfbd4a..015011f 100644
@@ -5,6 +5,7 @@ int advice_push_non_ff_current = 1;
 int advice_push_non_ff_default = 1;
 int advice_push_non_ff_matching = 1;
 int advice_status_hints = 1;
+int advice_status_u_option = 1;
 int advice_commit_before_merge = 1;
 int advice_resolve_conflict = 1;
 int advice_implicit_identity = 1;

@@ -19,6 +20,7 @@ static struct {
 	{ "pushnonffdefault", &advice_push_non_ff_default },
 	{ "pushnonffmatching", &advice_push_non_ff_matching },
 	{ "statushints", &advice_status_hints },
+	{ "statusuoption", &advice_status_u_option },
 	{ "commitbeforemerge", &advice_commit_before_merge },
 	{ "resolveconflict", &advice_resolve_conflict },
 	{ "implicitidentity", &advice_implicit_identity },

advice.h +1 -0

index f3cdbbf..e3e665d 100644
@@ -8,6 +8,7 @@ extern int advice_push_non_ff_current;
 extern int advice_push_non_ff_default;
 extern int advice_push_non_ff_matching;
 extern int advice_status_hints;
+extern int advice_status_u_option;
 extern int advice_commit_before_merge;
 extern int advice_resolve_conflict;
 extern int advice_implicit_identity;

t/t7060-wtstatus.sh +1 -0

index f4f38a5..52ef06b 100755
@@ -5,6 +5,7 @@ test_description='basic work tree status reporting'
 . ./test-lib.sh
 
 test_expect_success setup '
+	git config --global advice.statusuoption false &&
 	test_commit A &&
 	test_commit B oneside added &&
 	git checkout A^0 &&

t/t7508-status.sh +1 -0

index e313ef1..15e063a 100755
@@ -8,6 +8,7 @@ test_description='git status'
 . ./test-lib.sh
 
 test_expect_success 'status -h in broken repository' '
+	git config --global advice.statusuoption false &&
 	mkdir broken &&
 	test_when_finished "rm -fr broken" &&
 	(

t/t7512-status-help.sh +1 -0

index b3f6eb9..2d53e03 100755
@@ -14,6 +14,7 @@ test_description='git status advices'
 set_fake_editor
 
 test_expect_success 'prepare for conflicts' '
+	git config --global advice.statusuoption false &&
 	test_commit init main.txt init &&
 	git branch conflicts &&
 	test_commit on_master main.txt on_master &&

wt-status.c +21 -0

index 2a9658b..6e75468 100644
@@ -496,9 +496,14 @@ static void wt_status_collect_untracked(struct wt_status *s)
 {
 	int i;
 	struct dir_struct dir;
+	struct timeval t_begin;
 
 	if (!s->show_untracked_files)
 		return;
+
+	if (advice_status_u_option)
+		gettimeofday(&t_begin, NULL);
+
 	memset(&dir, 0, sizeof(dir));
 	if (s->show_untracked_files != SHOW_ALL_UNTRACKED_FILES)
 		dir.flags |=

@@ -528,6 +533,14 @@ static void wt_status_collect_untracked(struct wt_status *s)
 	}
 
 	free(dir.entries);
+
+	if (advice_status_u_option) {
+		struct timeval t_end;
+		gettimeofday(&t_end, NULL);
+		s->untracked_in_ms =
+			(uint64_t)t_end.tv_sec * 1000 + t_end.tv_usec / 1000 -
+			((uint64_t)t_begin.tv_sec * 1000 + t_begin.tv_usec / 1000);
+	}
 }
 
 void wt_status_collect(struct wt_status *s)

@@ -1011,6 +1024,14 @@ void wt_status_print(struct wt_status *s)
 		wt_status_print_other(s, &s->untracked, _("Untracked files"), "add");
 		if (s->show_ignored_files)
 			wt_status_print_other(s, &s->ignored, _("Ignored files"), "add -f");
+		if (advice_status_u_option && 2000 < s->untracked_in_ms) {
+			status_printf_ln(s, GIT_COLOR_NORMAL, "");
+			status_printf_ln(s, GIT_COLOR_NORMAL,
+				 _("It took %.2f seconds to enumerate untracked files."),
+				 s->untracked_in_ms / 1000.0);
+			status_printf_ln(s, GIT_COLOR_NORMAL,
+				 _("Consider the -u option for a possible speed-up?"));
+		}
 	} else if (s->commitable)
 		status_printf_ln(s, GIT_COLOR_NORMAL, _("Untracked files not listed%s"),
 			advice_status_hints

wt-status.h +0 -0

index 236b41f..09420d0 100644

Thanks, that looks good to me:

# It took 2.58 seconds to enumerate untracked files. # Consider the -u option for a possible speed-up?

But:
If I follow the advice as is given and use "git status -u", the result is the same.

If I think loud, would it be better to say:

# It took 2.58 seconds to search for untracked files. # Consider the -uno option for a possible speed-up?

or

# It took 2.58 seconds to search for untracked files. # Consider the -u option for a possible speed-up? # Please see git help status

Quoted 7 lines · Torsten Bögershausen

Thanks, that looks good to me:

# It took 2.58 seconds to enumerate untracked files. # Consider the -u option for a possible speed-up?

But:
If I follow the advice as is given and use "git status -u", the result is the same.

Yeah, that was taken from

    http://thread.gmane.org/gmane.comp.version-control.git/215820/focus=218125

to which I said something about "more levels of indirections". This episode shows that even a user who was very well aware of the issue did not follow a single level of indirection.

Quoted 10 lines

If I think loud, would it be better to say:

# It took 2.58 seconds to search for untracked files. # Consider the -uno option for a possible speed-up?

or

# It took 2.58 seconds to search for untracked files. # Consider the -u option for a possible speed-up? # Please see git help status

The former actively hurts the users, but the latter would be good, given that your documentation updates clarifies the trade off.

Or we can be more explicit and say

# It took 2.58 seconds to search for untracked files. 'status -uno'

# may speed it up, but you have to be careful not to forget to add
# new files yourself (see 'git help status').

Quoted 6 lines

Or we can be more explicit and say

# It took 2.58 seconds to search for untracked files. 'status -uno'

# may speed it up, but you have to be careful not to forget to add
# new files yourself (see 'git help status').

Thanks, that looks good for me

[PATCH] git status: Document that git status -uno is faster

In some repostories users expere that "git status" command takes long time. The command spends some time searching the file system for untracked files. Document that searching for untracked file may take some time, and docuemnt the option -uno better.

Signed-off-by Torsten Bögershausen <[email protected]>

---
 Documentation/git-status.txt | 7 +++++++
 1 file changed, 7 insertions(+)

Documentation/git-status.txt +5 -0

index 0412c40..fd36bbd 100644
@@ -58,6 +58,13 @@ The possible options are:
 The default can be changed using the status.showUntrackedFiles
 configuration variable documented in linkgit:git-config[1].
 
++
+Note: Searching the file system for untracked files may take some time.
+git status -uno is faster than git status -uall.
+There is a trade-off around the use of -uno between safety and performance.
+The default is not to use -uno so that you will not forget to add a file

you newly created (i.e safety).
+You would pay for the safety with the cost to find such untracked files (i.e. performance).

Quoted 2 lines · Junio C Hamano

The noise this introduces to the test suite is a bit irritating and makes us think twice if this really a good change.

I originally thought of two options, this or add an env flag in git binary that turns this off in the test suite. The latter did not sound good. But I forgot that we set a fake $HOME in the test suite, we could disable this in $HOME/.gitconfig, less clutter in individual tests.

Quoted 14 lines · Duy Nguyen

Quoted 11 lines · Ramkumar Ramachandra

Finn notes in the commit message that it offers no speedup, because .gitignore files in every directory still have to be read. I think this is silly: we really should be caching .gitignore, and touching it only when lstat() reports that the file has changed.

...

Really, the elephant in the room right now seems to be .gitignore. Until that is fixed, there is really no use of writing this inotify daemon, no? Can someone enlighten me on how exactly .gitignore files are processed?

Quoted 6 lines

.gitignore is a different issue. I think it's mainly used with read_directory/fill_directory to collect ignored files (or not-ignored files). And it's not always used (well, status and add does, but diff should not). I think wee need to measure how much mass lstat elimination gains us (especially on big repos) and how much .gitignore/.gitattributes caching does.

OK let's count. I start with a "standard" repository, linux-2.6. This is the number from strace -T on "git status" (*). The first column is accumulated time, the second the number of syscalls.

top syscalls sorted top syscalls sorted
by acc. time by number
----------------------------------------------

0.401906 40950 lstat    0.401906 40950 lstat
0.190484 5343 getdents  0.150055 5374 open
0.150055 5374 open      0.190484 5343 getdents
0.074843 2806 close     0.074843 2806 close
0.003216 157 read       0.003216 157 read

The following patch pretends every entry is uptodate without lstat. With the patch, we can see refresh code is the cause of mass lstat, as lstat disappears:

0.185347 5343 getdents  0.144173 5374 open
0.144173 5374 open      0.185347 5343 getdents
0.071844 2806 close     0.071844 2806 close
0.004918 135 brk        0.003378 157 read
0.003378 157 read       0.004918 135 brk

-- 8< --

read-cache.c +4 -1

index 827ae55..94d8ed8 100644
@@ -1018,6 +1018,10 @@ static struct cache_entry *refresh_cache_ent(struct index_state *istate,
        if (ce_uptodate(ce))
                return ce;
 
+#if 1
+       ce_mark_uptodate(ce);
+       return ce;
+#endif
        /*
         * CE_VALID or CE_SKIP_WORKTREE means the user promised us
         * that the change to the work tree does not matter and told
-- 8< --

The following patch eliminates untracked search code. As we can see, open+getdents also disappears with this patch:

0.462909 40950 lstat   0.462909 40950 lstat
0.003417 129 brk       0.003417 129 brk
0.000762 53 read       0.000762 53 read
0.000720 36 open       0.000720 36 open
0.000544 12 munmap     0.000454 33 close

So from syscalls point of view, we know what code issues most of them. Let's see how much time we gain be these patches, which is an approximate of the gain by inotify support. This time I measure on gentoo-x86.git [1] because this one has really big worktree (100k files)

        unmodified  read-cache.c  dir.c     both
real    0m0.550s    0m0.479s      0m0.287s  0m0.213s
user    0m0.305s    0m0.315s      0m0.201s  0m0.182s
sys     0m0.240s    0m0.157s      0m0.084s  0m0.030s

and the syscall picture on gentoo-x86.git:

1.106615 101942 lstat    1.106615 101942 lstat
0.667235 47083 getdents  0.641604 47114 open
0.641604 47114 open      0.667235 47083 getdents
0.286711 23573 close     0.286711 23573 close
0.005842 350 brk         0.005842 350 brk

We can see that shortcuting untracked code gives bigger gain than index refresh code. So I have to agree that .gitignore may be the big elephant in this particular case.

Bear in mind though this is Linux, where lstat is fast. On systems with slow lstat, these timings could look very different due to the large number of lstat calls compared to open+getdents. I really like to see similar numbers on Windows.

Karsten Blees has done something similar-ish on Windows, and he posted the results here:

https://groups.google.com/forum/#!topic/msysgit/fL_jykUmUNE/discussion

I also seem to remember he doing a ReadDirectoryChangesW version, but I don't remember what happened with that.

Quoted 5 lines

Karsten Blees has done something similar-ish on Windows, and he posted the results here:

https://groups.google.com/forum/#!topic/msysgit/fL_jykUmUNE/discussion

Quoted 2 lines

I also seem to remember he doing a ReadDirectoryChangesW version, but I don't remember what happened with that.

Thanks. I came across that but did not remember. For one thing, we know the inotify alternative for Windows: ReadDirectoryChangesW.

I copy "git status"'s (impressive) numbers from fscache-v0 for those who are interested in:

preload | -u | normal | cached | gain
--------+-----+--------+--------+------

false   | all | 25.144 | 3.055  |  8.2
false   | no  | 22.822 | 1.748  | 12.8
true    | all |  9.234 | 2.179  |  4.2
true    | no  |  6.833 | 0.955  |  7.2

However, the difference between git status -uall and -uno was always about 1.3 s in all fscache versions, even though opendir/readdir/closedir was served entirely from the cache. I added a bit of performance tracing to find the cause, and I think most of the time spent in wt_status_collect_untracked can be eliminated:

1.) 0.939 s is spent in dir.c/excluded (i.e. checking .gitignore). This check is done for *every* file in the working copy, including files in the index. Checking the index first could eliminate most of that, i.e.:

(Note: patches are for discussion only, I'm aware that they may have unintended side effects...)

2.) 0.135 s is spent in name-hash.c/hash_index_entry_directories, reindexing the same directories over and over again. In the end, the hashtable contains 939k directory entries, even though the WebKit test repo only has 7k directories. Checking if a directory entry already exists could reduce that, i.e.:

(quoted diff) +16 -7

@@ -53,14 +55,23 @@ static void hash_index_entry_directories(struct index_state *istate, struct cach
        unsigned int hash;
        void **pos;
        double t = ticks();
+       struct cache_entry *ce2;
+       int len = ce_namelen(ce);
 
-       const char *ptr = ce->name;
-       while (*ptr) {
-               while (*ptr && *ptr != '/')
-                       ++ptr;
-               if (*ptr == '/') {
-                       ++ptr;
-                       hash = hash_name(ce->name, ptr - ce->name);
+       while (len > 0) {
+               while (len > 0 && ce->name[len - 1] != '/')
+                       len--;
+               if (len > 0) {
+                       hash = hash_name(ce->name, len);
+                       ce2 = lookup_hash(hash, &istate->name_hash);
+                       while (ce2) {
+                               if (same_name(ce2, ce->name, len, ignore_case)) {
+                                       add_since(t, &hash_dirs);
+                                       return;
+                               }
+                               ce2 = ce2->dir_next;
+                       }
+                       len--;
                        pos = insert_hash(hash, ce, &istate->name_hash);
                        if (pos) {
                                ce->dir_next = *pos;

Quoted 1 line · Karsten Blees

2.) 0.135 s is spent in name-hash.c/hash_index_entry_directories, reindexing the same directories over and over again. In the end, the hashtable contains 939k directory entries, even though the WebKit test repo only has 7k directories. Checking if a directory entry already exists could reduce that, i.e.:

This function is only used when core.ignorecase = true. I probably won't be able to test this, so I'll leave this to other people who care about ignorecase.

This function used to have lookup_hash, but it was removed by Jeff in 2548183 (fix phantom untracked files when core.ignorecase is set - 2011-10-06). There's a looong commit message which I'm too lazy to read. Anybody who works on this should though.

I think the best way forward is to actually create a separate hash table for the directory lookups. I note that we only care about these entries in directory_exists_in_index_icase, which is really about whether something is there, versus what exactly is there. So could we maybe get by with a separate hash table that stores a count of entries at each directory, and increment/decrement the count when we add/remove entries?

The biggest problem I see with that is that we do indeed care a little bit what is at the directory: we check the mode to see if it is a gitdir or not. But I think we can maybe sneak around that: gitdirs have actual entries in the index, whereas the directories do not. So we would find them via index_name_exists; anything that is not there, but _is_ in the special directory hash would therefore be a directory.

I realize it got pretty esoteric there in the middle. I'll see if I can work up a patch that expresses what I'm thinking.

Moreover, looking at it again, I
don't think my patch produces the right behavior: we have a single dir_next pointer, even though the same ce_entry may appear under many directory hashes. So the cache_entries that has to "dir/foo/" and those that hash to "dir/bar/" may get confused, because they will also both be found under "dir/", and both try to create a linked list from the dir_next pointer.

Looking at Karsten's patch, it seems like it will not add a cache entry if there is one of the same name. But I'm not sure if that is right, as the old one might be CE_UNHASHED (or it might get removed later). You actually want to be able to find each cache_entry that has a file under the directory at the hash of that directory, so you can make sure it is still valid.

I think the best way forward is to actually create a separate hash table for the directory lookups. I note that we only care about these entries in directory_exists_in_index_icase, which is really about whether something is there, versus what exactly is there. So could we maybe get by with a separate hash table that stores a count of entries at each directory, and increment/decrement the count when we add/remove entries?

Am 13.02.2013 19:18, schrieb Jeff King:

Quoted 8 lines

Moreover, looking at it again, I
don't think my patch produces the right behavior: we have a single dir_next pointer, even though the same ce_entry may appear under many directory hashes. So the cache_entries that has to "dir/foo/" and those that hash to "dir/bar/" may get confused, because they will also both be found under "dir/", and both try to create a linked list from the dir_next pointer.

Indeed. In the worst case, this causes an endless loop if ce->dir_next == ce ---8<---
mkdir V
mkdir V/XQANY
mkdir WURZAUP
touch V/XQANY/test
git init
git config core.ignorecase true
git add .
git status
---8<---

Note: "V/", "V/XQANY/" and "WURZAUP/" all have the same hash_name. Although I found those strange values by brute force, hash collisions in 32 bit values are not that uncommon in real life :-)

Alternatively, we could simply create normal cache_entries for the directories that are linked via ce->next, but have a trailing '/' in their name?

Reference counting sounds good to me, at least better than allocating directory entries per cache entry * parent dirs.

Quoted 7 lines

Alternatively, we could simply create normal cache_entries for the directories that are linked via ce->next, but have a trailing '/' in their name?

Reference counting sounds good to me, at least better than allocating directory entries per cache entry * parent dirs.

I think that is more or less what my patch does, but it splits the ref-counted fake cache_entries out into a separate hash of "struct dir_hash_entry" rather than storing it in the regular hash. Which IMHO is a bit cleaner for two reasons:

1. You do not have to pay the memory price of storing fake cache_entries (the name+refcount struct for each directory is much smaller than a real cache_entry).

2. It makes the code a bit simpler, as you do not have to do any "check for trailing /" magic on the result of index_name_exists to determine if it is a "real" name or just a fake dir entry.

With core.ignorecase=true, name-hash.c builds a case insensitive index of all tracked directories. Currently, the existing cache entry structures are added multiple times to the same hashtable (with different name lengths and hash codes). However, there's only one dir_next pointer, which gets completely messed up in case of hash collisions. In the worst case, this causes an endless loop if ce == ce->dir_next:

---8<---
# "V/", "V/XQANY/" and "WURZAUP/" all have the same hash_name mkdir V
mkdir V/XQANY
mkdir WURZAUP
touch V/XQANY/test
git init
git config core.ignorecase true
git add .
git status
---8<---

name-hash.c +12 -0

+	 * closing slash.
 	 */
+	struct dir_entry *dir, *p;
+
+	/* get length of parent directory */
+	while (namelen > 0 && !is_dir_sep(ce->name[namelen - 1]))
+		namelen--;
+	if (namelen <= 0)
+		return NULL;
+
+	/* lookup existing entry for that directory */
+	dir = find_dir_entry(istate, ce->name, namelen);
+	if (add && !dir) {
...
 	}

name-hash.c +5 -3

+
+	return dir;
 }
 
 static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)

@@ -74,7 +111,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 	if (ce->ce_flags & CE_HASHED)
 		return;
 	ce->ce_flags |= CE_HASHED;
-	ce->next = ce->dir_next = NULL;
+	ce->next = NULL;
 	hash = hash_name(ce->name, ce_namelen(ce));
 	pos = insert_hash(hash, ce, &istate->name_hash);
 	if (pos) {

@@ -82,8 +119,8 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 		*pos = ce;
 	}
 
-	if (ignore_case)
-		hash_index_entry_directories(istate, ce);
+	if (ignore_case && !(ce->ce_flags & CE_UNHASHED))
+		hash_dir_entry(istate, ce, ce_namelen(ce), 1);
 }
 
 static void lazy_init_name_hash(struct index_state *istate)

name-hash.c +4 -0

 	ce->ce_flags &= ~CE_UNHASHED;
 	if (istate->name_hash_initialized)
 		hash_index_entry(istate, ce);
 }
 
+/*
+ * We don't actually *remove* it, we can just mark it invalid so that
+ * we won't find it in lookups.
+ *

name-hash.c +4 -3

+
+	ce->ce_flags |= CE_UNHASHED;
+}
+
 static int slow_same_name(const char *name1, int len1, const char *name2, int len2)
 {
 	if (len1 != len2)

@@ -137,18 +196,7 @@ static int same_name(const struct cache_entry *ce, const char *name, int namelen
 	if (!icase)
 		return 0;
 
-	/*
-	 * If the entry we're comparing is a filename (no trailing slash), then compare
-	 * the lengths exactly.

Quoted 7 lines · Karsten Blees

With core.ignorecase=true, name-hash.c builds a case insensitive index of all tracked directories. Currently, the existing cache entry structures are added multiple times to the same hashtable (with different name lengths and hash codes). However, there's only one dir_next pointer, which gets completely messed up in case of hash collisions. In the worst case, this causes an endless loop if ce == ce->dir_next:

Quoted 11 lines

---8<---
# "V/", "V/XQANY/" and "WURZAUP/" all have the same hash_name mkdir V
mkdir V/XQANY
mkdir WURZAUP
touch V/XQANY/test
git init
git config core.ignorecase true
git add .
git status
---8<---

Instead of using the scissors mark to confuse "am -c", indenting this block would have been easier to later readers.

Also it is somewhat a shame that we do not use the above sample collisions in a new test case.

name-hash.c static unsigned int hash_name(const char *name, int namelen) · line 42

Quoted 9 lines

name-hash.c +2 -3

+static struct dir_entry *hash_dir_entry(struct index_state *istate,
+		struct cache_entry *ce, int namelen, int add)
 {
 	/*
 	 * Throw each directory component in the hash for quick lookup
 	 * during a git status. Directory components are stored with their
-	 * closing slash.  Despite submodules being a directory, they never
-	 * reach this point, because they are stored without a closing slash
-	 * in the cache.

Is the description of submodule no longer relevant?