inotify daemon speedup for git [POC/HACK]

Reading through the thread about subtree I noticed Avery mentioning
using inotify to speed up git status & co.

Here is a quick hack I did some time ago to test this out, to use it
call "igit" instead of "git" for all commmands you want to speed up.

There is one minor nit: The speedup gain is zero :) git still
traverses all directories to look for .gitignore files, which seems to
totally kill the optimisation.

To use it, put igit and git-inotify-daemon.pl in path, and do git
config core.ignorestat=true in the repositories you want to test it
with. The igit wrapper will run git update-index --no-assume-unchanged
on all modified files before running any real git commands.

To get inotify to ignore all changes that the git commands themselves
perform, the "igit" wrapper kills the currently running daemon. Then
it reads the list of updates files, and does git-update-index
--no-assume-unchanged on them. Then the git command is run, and
finally the daemon is fired up again.

I had to do one tiny modification to git to make update-index ignore
bad paths.


igit - a git wrapper with an inotify daemon

Linux only - requires inotifytools installed. This is juct a quick hack/proof
of concept!
update-index: Do not error out on bad paths, just warn
---
 .gitignore             |    1 +
 builtin/update-index.c |    2 +-
 git-inotify-daemon.pl  |   28 ++++++++++++++++++++++++++++
 igit                   |   22 ++++++++++++++++++++++
 4 files changed, 52 insertions(+), 1 deletions(-)
 create mode 100755 git-inotify-daemon.pl
 create mode 100755 igit

diff --git a/.gitignore b/.gitignore
index 14e2b6b..fa67132 100644
--- a/.gitignore
+++ b/.gitignore

@@ -204,3 +204,4 @@
 *.pdb
 /Debug/
 /Release/
+.igit-*

diff --git a/builtin/update-index.c b/builtin/update-index.c
index 3ab214d..c905d78 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c

@@ -282,7 +282,7 @@ static void update_one(const char *path, const char *prefix, int prefix_length)
 	}
 	if (mark_valid_only) {
 		if (mark_ce_flags(p, CE_VALID, mark_valid_only == MARK_FLAG))
-			die("Unable to mark file %s", path);
+			fprintf(stderr, "Unable to mark file %s\n", path);
 		goto free_return;
 	}
 	if (mark_skip_worktree_only) {

diff --git a/git-inotify-daemon.pl b/git-inotify-daemon.pl
new file mode 100755
index 0000000..a57ceef
--- /dev/null
+++ b/git-inotify-daemon.pl

@@ -0,0 +1,28 @@
+#!/usr/bin/env perl
+# Run from igit
+
+use warnings;
+use strict;
+
+die "Usage: $0 <output-file>" unless $#ARGV == 0;
+my $output = $ARGV[0];
+my $pid = open(INOTIFY, "exec inotifywait -q --monitor --recursive --exclude .git -e attrib,moved_to,moved_from,move,create,delete,modify --format '%w%f' .|") or die "Cannot run inotifywait: $!\n";
+
+$| = 1;
+print "$pid\n";
+
+my %modified_files;
+while (<INOTIFY>) {
+    s=^./==;
+    chomp;
+    $modified_files{$_} = 1;
+}
+
+# Output file must be opened as late as possible, it is a named pipe
+# and the listener won't be here before inotifywait exits.
+# open would just hang if it was done earlier.
+open(OUT, ">$output");
+foreach my $key (sort keys %modified_files) {
+    print OUT "$key\000";
+}
+exit 0;

diff --git a/igit b/igit
new file mode 100755
index 0000000..60c5bb2
--- /dev/null
+++ b/igit

@@ -0,0 +1,22 @@
+#!/bin/sh
+
+TOPDIR=`git rev-parse --show-cdup` || exit 1
+
+if [ ! "$TOPDIR" ]; then
+    TOPDIR="./"
+fi
+
+PIPE=.igit-pipe
+PIDFILE=.igit-pid
+
+if [ -p ${TOPDIR}${PIPE} ] && kill -TERM `cat ${TOPDIR}${PIDFILE}`; then
+    ( cd $TOPDIR && git update-index --verbose --no-assume-unchanged -z --stdin < $PIPE )
+fi
+
+git "$@"
+
+cd $TOPDIR
+rm -f $PIPE
+mkfifo $PIPE
+git-inotify-daemon.pl $PIPE > $PIDFILE 2>> .igit-errors </dev/null &
+

-- 
1.7.2.rc0


- Finn Arne

On Tue, Jul 27, 2010 at 8:20 AM, Finn Arne Gangstad [off-list ref] wrote:

Reading through the thread about subtree I noticed Avery mentioning
using inotify to speed up git status & co.

Here is a quick hack I did some time ago to test this out, to use it
call "igit" instead of "git" for all commmands you want to speed up.

There is one minor nit: The speedup gain is zero :) git still
traverses all directories to look for .gitignore files, which seems to
totally kill the optimisation.

Hey, this is kind of cool.  Except for that last part :)

Actually I think the problem is a little worse than .gitignore files.
'git status', for example (which is called by git commit), wants to
generate a list of the files it *doesn't* know about.  Unfortunately,
those files aren't in the index at all.  So it resorts to doing
recursive readdir() across the entire repository.  The net result is
about as slow as doing that plus one stat() per file in the index.

An inotify daemon could easily keep track of which files have been
added that aren't in the index... but where would it put the list of
files git doesn't know about?  Do they go in the index with a special
NOT_REALLY_INDEXED flag?

This is the main question that has so far prevented me from trying to
solve the problem myself.

Thanks,

Avery

On Jul 27, 2010, at 4:29 PM, Avery Pennarun wrote:

An inotify daemon could easily keep track of which files have been
added that aren't in the index... but where would it put the list of
files git doesn't know about?  Do they go in the index with a special
NOT_REALLY_INDEXED flag?

One option is not to write it to disk at all.  The client could  
consult the daemon directly.

Josh

On Tue, Jul 27, 2010 at 7:39 PM, Joshua Juran [off-list ref] wrote:

On Jul 27, 2010, at 4:29 PM, Avery Pennarun wrote:

quoted

An inotify daemon could easily keep track of which files have been
added that aren't in the index... but where would it put the list of
files git doesn't know about?  Do they go in the index with a special
NOT_REALLY_INDEXED flag?

One option is not to write it to disk at all.  The client could consult the
daemon directly.

True.  What would the client-server protocol look like, though?  "Give
me the list of unknown files?"  Does the daemon need to understand
.gitignore or will it send back a list of all my million *.o files
every time?  etc.

Offhandedly, I think it would be nice to have an inotify daemon just
maintain (something like) the git index file where it just has a list
of *all* the files in a form that's a) random access, not just
sequential, and b) really fast when accessed sequentially.

Knowing that large numbers of files can cause slowness, I was planning
ahead for inotify when I designed bup's index file format, and it
meets the above criteria.  Unfortunately I screwed up other stuff
(adding new files is too slow) and it still needs to be rewritten
anyway.  Oh well.

While we're here, it's probably worth mentioning that git's index file
format (which stores a sequential list of full paths in alphabetical
order, instead of an actual hierarchy) does become a bottleneck when
you actually have a huge number of files in your repo (like literally
a million).  You can't actually binary search through the index!  The
current implementation of submodules allows you to dodge that
scalability problem since you end up with multiple smaller index
files.  Anyway, that's fixable too.

Have fun,

Avery

Heya,

On Tue, Jul 27, 2010 at 07:20, Finn Arne Gangstad [off-list ref] wrote:

There is one minor nit: The speedup gain is zero :) git still
traverses all directories to look for .gitignore files, which seems to
totally kill the optimisation.

This is very true. In my experience with ginormous trees even if you
'git update-index --assume-unchanged' every file and directory it's
still unbearably slow due to the .gitignore files. Any solution that
aims to solve this problem should also address the .gitignore file
problem. Note: a safe assumption here is that to solve the problem it
needs to work if there are more .gitignore files than regular files
:).

-- 
Cheers,

Sverre Rabbelier

Avery Pennarun [off-list ref] wrote:

While we're here, it's probably worth mentioning that git's index file
format (which stores a sequential list of full paths in alphabetical
order, instead of an actual hierarchy) does become a bottleneck when
you actually have a huge number of files in your repo (like literally
a million).  You can't actually binary search through the index!  The
current implementation of submodules allows you to dodge that
scalability problem since you end up with multiple smaller index
files.  Anyway, that's fixable too.

Yes.

More than once I've been tempted to rewrite the on-disk (and I guess
in-memory) format of the index.  And then I remember how painful that
stuff is in either C git.git or JGit, and I back away slowly.  :-)

Ideally the index is organized the same way the trees are, but
you still can't do a really good binary search because of the
ass-backwards name sorting rule for trees.  But for performance
reasons you still want to keep the entire index in a single file,
an index per directory (aka SVN/CVS) is too slow for the common
case of <30k files.

-- 
Shawn.

On Tue, Jul 27, 2010 at 8:00 PM, Shawn O. Pearce [off-list ref] wrote:

Avery Pennarun [off-list ref] wrote:

quoted

While we're here, it's probably worth mentioning that git's index file
format (which stores a sequential list of full paths in alphabetical
order, instead of an actual hierarchy) does become a bottleneck when
you actually have a huge number of files in your repo (like literally
a million).  You can't actually binary search through the index!  The
current implementation of submodules allows you to dodge that
scalability problem since you end up with multiple smaller index
files.  Anyway, that's fixable too.

Yes.

More than once I've been tempted to rewrite the on-disk (and I guess
in-memory) format of the index.  And then I remember how painful that
stuff is in either C git.git or JGit, and I back away slowly.  :-)

Ideally the index is organized the same way the trees are, but
you still can't do a really good binary search because of the
ass-backwards name sorting rule for trees.  But for performance
reasons you still want to keep the entire index in a single file,
an index per directory (aka SVN/CVS) is too slow for the common
case of <30k files.

Really?  What's wrong with the name sorting rule?  I kind of like it.

bup's current index - after I abandoned my clone of the git one since
it was too slow with insane numbers of files - is very fast for reads
and in-place updates using mmap.

Essentially, it's a tree, starting from the outermost leafs and
leading toward the entry at the very end of the file, which is the
root.  (The idea of doing it backwards was that I could write the file
sequentially.  In retrospect, that was probably an unnecessarily
brain-bending waste of time and the root should have been the first
entry instead.)

For speed, the bup index can just mark entries as deleted using a flag
rather than actually rewriting the whole indexfile.  Unfortunately, I
failed to make it sufficiently flexible to *add* new entries without
needing to rewrite the whole thing.  In bup, that's a big deal
(especially since python is kind of slow and there are typically >1
million files in the index).  In git, it's maybe not so bad; after
all, the current implementation rewrites the index *every* time and
nobody notices.

Anyway, the code for it isn't too hairy, in case you want to steal some ideas:
http://github.com/apenwarr/bup/blob/master/lib/bup/index.py

(Disclaimer: I say this after actually spending a couple of late
nights pulling my hair out over it.  So I'm not so hairy anymore
either, but that doesn't prove much.)

I've considered just tossing the whole thing and using sqlite instead.
 Eventually I'll do it as a benchmark to see what happens.  My past
experiments with sqlite have demonstrated that its performance is
rather mind boggling (> 100k rows inserted per second as long as you
prepare() your SQL statements).  Reading from the index would be fast,
adding entries would be much faster than presently, but I'm not sure
about mass updates.  For bup sqlite would be okay, though I doubt git
wants to take on a whole sqlite dependency.  Then again, you never
know.

Have fun,

Avery

On Jul 27, 2010, at 5:18 PM, Avery Pennarun wrote:

On Tue, Jul 27, 2010 at 8:00 PM, Shawn O. Pearce  
[off-list ref] wrote:

quoted

Avery Pennarun [off-list ref] wrote:

quoted

While we're here, it's probably worth mentioning that git's index  
file
format (which stores a sequential list of full paths in alphabetical
order, instead of an actual hierarchy) does become a bottleneck when
you actually have a huge number of files in your repo (like  
literally
a million).  You can't actually binary search through the index!   
The
current implementation of submodules allows you to dodge that
scalability problem since you end up with multiple smaller index
files.  Anyway, that's fixable too.

Yes.

More than once I've been tempted to rewrite the on-disk (and I guess
in-memory) format of the index.  And then I remember how painful that
stuff is in either C git.git or JGit, and I back away slowly.  :-)

Ideally the index is organized the same way the trees are, but
you still can't do a really good binary search because of the
ass-backwards name sorting rule for trees.  But for performance
reasons you still want to keep the entire index in a single file,
an index per directory (aka SVN/CVS) is too slow for the common
case of <30k files.

Really?  What's wrong with the name sorting rule?  I kind of like it.

bup's current index - after I abandoned my clone of the git one since
it was too slow with insane numbers of files - is very fast for reads
and in-place updates using mmap.

Essentially, it's a tree, starting from the outermost leafs and
leading toward the entry at the very end of the file, which is the
root.  (The idea of doing it backwards was that I could write the file
sequentially.  In retrospect, that was probably an unnecessarily
brain-bending waste of time and the root should have been the first
entry instead.)

For speed, the bup index can just mark entries as deleted using a flag
rather than actually rewriting the whole indexfile.  Unfortunately, I
failed to make it sufficiently flexible to *add* new entries without
needing to rewrite the whole thing.  In bup, that's a big deal
(especially since python is kind of slow and there are typically >1
million files in the index).  In git, it's maybe not so bad; after
all, the current implementation rewrites the index *every* time and
nobody notices.

Okay, I have an idea.  If I understand correctly, the index is a flat  
database of records including a pathname and several fixed-length  
fields.  Since the records are not fixed-length, only sequential  
search is possible, even though the records are sorted by pathname.

Here's the idea:  Divide the database into blocks.  Each block  
contains a block header and the records belonging to a single  
directory.  The block header contains the length of the block and also  
the offset to the next block, in bytes.  In addition to a record for  
each indexed file in a directory, a directory's block also contains  
records for subdirectories. The mode flags in a record indicate the  
record type.  Directory records contain an offset in bytes to the  
block for that directory (in place of the SHA-1 hash).  The block list  
is preceded by a file header, which includes the offset in bytes of  
the root block.  All offsets are from the beginning of the file.

Instead of having to search among every file in the repository, the  
search space now includes only the immediate descendants of each  
directory in the target file's path.  If a directory is modified then  
it can either be rewritten in place (if there's sufficient room) or  
appended to the end of the file (requiring the old and new  
sequentially preceding blocks and the parent directory's block to  
update their offsets).

Is this useful?

Josh

On Tue, Jul 27, 2010 at 9:14 PM, Joshua Juran [off-list ref] wrote:

Okay, I have an idea.  If I understand correctly, the index is a flat
database of records including a pathname and several fixed-length fields.
 Since the records are not fixed-length, only sequential search is possible,
even though the records are sorted by pathname.

Here's the idea:  Divide the database into blocks.  Each block contains a
block header and the records belonging to a single directory.  The block
header contains the length of the block and also the offset to the next
block, in bytes.  In addition to a record for each indexed file in a
directory, a directory's block also contains records for subdirectories. The
mode flags in a record indicate the record type.  Directory records contain
an offset in bytes to the block for that directory (in place of the SHA-1
hash).  The block list is preceded by a file header, which includes the
offset in bytes of the root block.  All offsets are from the beginning of
the file.

Instead of having to search among every file in the repository, the search
space now includes only the immediate descendants of each directory in the
target file's path.  If a directory is modified then it can either be
rewritten in place (if there's sufficient room) or appended to the end of
the file (requiring the old and new sequentially preceding blocks and the
parent directory's block to update their offsets).

Yeah, that's pretty much what bup's current format does, minus
appending rewritten dirs at the end when files are added.  I've
thought of that, but sooner or later, the file would need to be
rewritten anyway, and then you end up with odd performance
characteristics where the file expands in random ways and then shrinks
again when you decide it's gotten too big.  And if you do try to reuse
empty blocks - which should mostly avoid the endless growth problem -
you basically just have a database, including fragmentation problems
and multi-user concerns and all.  That's what made me think that
sqlite might be a sensible choice, since it's already a database :)

But maybe there's some simpler way.

Have fun,

Avery

Heya,

On Tue, Jul 27, 2010 at 20:31, Avery Pennarun [off-list ref] wrote:

That's what made me think that
sqlite might be a sensible choice, since it's already a database :)

Sounds very sensible to me, especially the fact that (if it is indeed
fast enough, which I can't imagine it not being) it would make
development so much easier. At least, I think that having sqlite deal
with backwards comparability of your schema is easier than having to
manually do that? Also, sqlite is known to scale, is exactly one file
worth of dependency, what's not to love (other than having to support
upgrading to 'index vSqlite').

-- 
Cheers,

Sverre Rabbelier

Sverre Rabbelier wrote:

Also, sqlite is known to scale, is exactly one file
worth of dependency, what's not to love (other than having to support
upgrading to 'index vSqlite').

The frequent fsync()-ing.  Though that seems to be a problem with
pretty much anything that does not involve rewriting the index
with each change.

Maybe filesystems will cope better soon. :)

On Wed, Jul 28, 2010 at 06:06, Jonathan Nieder [off-list ref] wrote:

Sverre Rabbelier wrote:

quoted

Also, sqlite is known to scale, is exactly one file
worth of dependency, what's not to love (other than having to support
upgrading to 'index vSqlite').

The frequent fsync()-ing.  Though that seems to be a problem with
pretty much anything that does not involve rewriting the index
with each change.

SQLite has an option to turn that off [1], but I don't know if it has
an equivalent feature to manually call fsync when you need that.

Anyway, I've been very impressed by SQLite in every way. I'd try it
before designing my own fileformat, especially something involving
binary/sequential search. It's not a large dependency, and can easily
be bundled in compat/.

1. http://www.sqlite.org/pragma.html#pragma_synchronous

On Wed, Jul 28, 2010 at 4:03 PM, Sverre Rabbelier [off-list ref] wrote:

Heya,

On Tue, Jul 27, 2010 at 20:31, Avery Pennarun [off-list ref] wrote:

quoted

That's what made me think that
sqlite might be a sensible choice, since it's already a database :)

Sounds very sensible to me, especially the fact that (if it is indeed
fast enough, which I can't imagine it not being) it would make
development so much easier. At least, I think that having sqlite deal
with backwards comparability of your schema is easier than having to
manually do that? Also, sqlite is known to scale, is exactly one file
worth of dependency, what's not to love (other than having to support
upgrading to 'index vSqlite').

Even more sensible to replace all pack index with a single database.
But then we could as well drop git object store in favor of Fossil (OK
I'm going to far).
-- 
Duy

On Jul 28, 2010, at 3:44 AM, Ævar Arnfjörð Bjarmason wrote:

SQLite has an option to turn that off [1], but I don't know if it has
an equivalent feature to manually call fsync when you need that.

The right way to use SQLite is to have a memory-packed database which you check first, and where you do al of your work.  Then once you hit a stable stopping point, you commit those changes to your on-disk SQLite database, which can have proper transaction support.   That way you don't lose your database when your crappy binary-only video driver crashes on you, but you don't trash your disk performance because of the fsync() calls....

It only took a few years for firefox developers to figure this out, but the next version is supposed to finally get this right....  it'll be nice to have it NOT chewing up a third of a megabyte of SSD write endurance on every URL click....

-- Ted

"Shawn O. Pearce" [off-list ref] writes:

Avery Pennarun [off-list ref] wrote:

quoted

While we're here, it's probably worth mentioning that git's index file
format (which stores a sequential list of full paths in alphabetical
order, instead of an actual hierarchy) does become a bottleneck when
you actually have a huge number of files in your repo (like literally
a million).  You can't actually binary search through the index!  The
current implementation of submodules allows you to dodge that
scalability problem since you end up with multiple smaller index
files.  Anyway, that's fixable too.

Yes.

More than once I've been tempted to rewrite the on-disk (and I guess
in-memory) format of the index.  And then I remember how painful that
stuff is in either C git.git or JGit, and I back away slowly.  :-)

Ideally the index is organized the same way the trees are, but
you still can't do a really good binary search because of the
ass-backwards name sorting rule for trees.  But for performance
reasons you still want to keep the entire index in a single file,
an index per directory (aka SVN/CVS) is too slow for the common
case of <30k files.

I guess that modern filesystems solve the problem of very many files
in a single directory somehow (hash tables?).  Perhaps the index file
could borrow some such mechanism as an extension.

Index for index?
-- 
Jakub Narebski
Poland
ShadeHawk on #git

Avery Pennarun [off-list ref] writes:

For speed, the bup index can just mark entries as deleted using a flag
rather than actually rewriting the whole indexfile.  Unfortunately, I
failed to make it sufficiently flexible to *add* new entries without
needing to rewrite the whole thing.  In bup, that's a big deal
(especially since python is kind of slow and there are typically >1
million files in the index).  In git, it's maybe not so bad; after
all, the current implementation rewrites the index *every* time and
nobody notices.

Sidenote: couldn't you do what e.g. Mercurial did, i.e. rewrite
critical for performance parts in C?

-- 
Jakub Narebski
Poland
ShadeHawk on #git

* Nguyen Thai Ngoc Duy [off-list ref] wrote:

But then we could as well drop git object store in favor of Fossil (OK
I'm going to far).

You mean venti ?

Actually: that's an idea I'm thinking about for quite a while :)

But venti is yet lacking delete operations and differential
compression. The first is unproblematic (even it would require
rewriting the log areas in some ways to reclaim space), but
for differential compression, the venti store would have to
know a lot about the object's internal structure.

I'm doing some bit reasearch in the area of distributed 
content-addressed objects stores , designing an superstore 
called "Nebulon" [1] with things like strong encryption and
on-demand fetching/syncing. But getting git into it seems
to be a bit tricky, at least the hashes would change ...


cu

[1] http://www.metux.de/index.php/de/nebulon-storage-cloud.html
-- 
----------------------------------------------------------------------
 Enrico Weigelt, metux IT service -- http://www.metux.de/

 phone:  +49 36207 519931  email: weigelt@metux.de
 mobile: +49 151 27565287  icq:   210169427         skype: nekrad666
----------------------------------------------------------------------
 Embedded-Linux / Portierung / Opensource-QM / Verteilte Systeme
----------------------------------------------------------------------

* Jakub Narebski [off-list ref] wrote:

I guess that modern filesystems solve the problem of very many files
in a single directory somehow (hash tables?).  Perhaps the index file
could borrow some such mechanism as an extension.

Index for index?

hmm, if an index gets too large, it could be split into several
ones by an pathname prefix (but not necessarily one per directory)
so when having the subdirs "a", "b", "c", we'll three separate 
index files and a master index telling:

    a/	index.001
    b/	index.002
    c/	index.003

or even:

    a/		index.001
    b/		index.002
    b/foo	index.004
    c/		index.005

this would just add one indirection in the index-lookup by
comparing the key w/ index indice's prefix.


cu
-- 
----------------------------------------------------------------------
 Enrico Weigelt, metux IT service -- http://www.metux.de/

 phone:  +49 36207 519931  email: weigelt@metux.de
 mobile: +49 151 27565287  icq:   210169427         skype: nekrad666
----------------------------------------------------------------------
 Embedded-Linux / Portierung / Opensource-QM / Verteilte Systeme
----------------------------------------------------------------------