Re: inotify to minimize stat() calls

From: Jeff King <peff@peff.net>
Date: Feb 13, 2013, 18:18 UTC
Message-ID: <20130213181851.GA5603@sigill.intra.peff.net>
In-Reply-To: <CACsJy8C=2xKcsby048WWCFNhgKObGwrzeCOJPVVqgj88AfSHQw@mail.gmail.com>

On Wed, Feb 13, 2013 at 07:15:47PM +0700, Nguyen Thai Ngoc Duy wrote:

Show 11 quoted lines

> On Wed, Feb 13, 2013 at 3:48 AM, Karsten Blees <karsten.blees@gmail.com> wrote:
> > 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.

Yeah, the problem that commit tried to solve is that linking to a single cache entry through the hash is not enough, because we may remove cache items. Imagine you have "dir/one" and "dir/two", and you add them to the in-memory index in that order. The original code hashed "dir/" and inserted a link to the "dir/one" cache entry. When it came time to put in the "dir/two" entry, we noticed that there was already a "dir/" entry and did nothing. Then later, if we remove "dir/one", we do so by marking it with CE_UNHASHED. So a later query for "dir/" will see "nope, nothing here that wasn't CE_UNHASHED", which is wrong. We never recorded that "dir/two" existed under the hash for "dir/", so we can't know about it.

My patch just stores the cache_entry for both under the "dir/" hash. As Karsten noticed, that can lead to a large number of hash entries, because adding "some/deep/hierarchy/with/files" will add 4 directory entries for just that single file. 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.

And of course that still leaves the existing correctness problem I mentioned above.

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.

-Peff