[RFC] On watchman support

[RFC] On watchman support

[Duy Nguyen]

I've come to the last piece to speed up "git status", watchman
support. And I realized it's not as good as I thought.

Watchman could be used for two things: to avoid refreshing the index,
and to avoid searching for ignored files. The first one can be done
(with the patch below as demonstration). And it should keep refresh
cost to near zero in the best case, the cost is proportional to the
number of modified files.

For avoiding searching for ignored files. My intention was to build on
top of untracked cache. If watchman can tell me what files are added
or deleted since last observed time, then I can invalidate just
directories that contain them, or even better, calculate ignore status
for those files only.

This is important because in reality compilers and editors tend to
update files by creating a new version then rename them, updating
directory mtime and invalidating untracked cache as a consequence. As
you edit more files (or your rebuild touches more dirs), untracked
cache performance drops (until the next "git status"). The numbers I
posted so far are the best case.

The problem with watchman is it cannot tell me "new" files since the
last observed time (let's say 'T'). If a file exists at 'T', gets
deleted then recreated, then watchman tells me it's a new file. I want
to separate those from ones that do not exist before 'T'.

David's watchman approach does not have this problem because he keeps
track of all entries under $GIT_WORK_TREE and knows which files are
truely new. But I don't really want to keep the whole file list around,
especially when watchman already manages the same list.

So we got a few options:

1) Convince watchman devs to add something to make it work

2) Fork watchman

3) Make another daemon to keep file list around, or put it in a shared
   memory.

4) Move David's watchman series forward (and maybe make use of shared
   mem for fs_cache).

5) Go with something similar to the patch below and accept untracked
   cache performance degrades from time to time

6) ??

I'm working on 1). 2) is just bad taste, listed for completeness
only. If we go with 3) and watchman starts to support Windows (seems
to be in their plan), we'll need to rework some how. And I really
don't like 3)

If 1-3 does not work out, we're left without 4) and 5). We could
support both, but proobably not worth the code complexity and should
just go with one.

And if we go with 4) we should probably think of dropping untracked
cache if watchman will support Windows in the end. 4) also has another
advantage over untracked cache, that it could speed up listing ignored
files as well as untracked files.

Comments?

-- 8< --
diff --git a/Makefile b/Makefile
index fa58a53..a2be728 100644
--- a/Makefile
+++ b/Makefile
@@ -406,6 +406,7 @@ TCLTK_PATH = wish
 XGETTEXT = xgettext
 MSGFMT = msgfmt
 PTHREAD_LIBS = -lpthread
+WATCHMAN_LIBS = -lwatchman
 PTHREAD_CFLAGS =
 GCOV = gcov
 
@@ -1453,6 +1454,13 @@ else
 	LIB_OBJS += thread-utils.o
 endif
 
+ifdef USE_WATCHMAN
+	LIB_H += watchman-support.h
+	LIB_OBJS += watchman-support.o
+	EXTLIBS += $(WATCHMAN_LIBS)
+	BASIC_CFLAGS += -DUSE_WATCHMAN
+endif
+
 ifdef HAVE_PATHS_H
 	BASIC_CFLAGS += -DHAVE_PATHS_H
 endif
@@ -2222,6 +2230,7 @@ GIT-BUILD-OPTIONS: FORCE
 	@echo NO_PERL=\''$(subst ','\'',$(subst ','\'',$(NO_PERL)))'\' >>$@
 	@echo NO_PYTHON=\''$(subst ','\'',$(subst ','\'',$(NO_PYTHON)))'\' >>$@
 	@echo NO_UNIX_SOCKETS=\''$(subst ','\'',$(subst ','\'',$(NO_UNIX_SOCKETS)))'\' >>$@
+	@echo USE_WATCHMAN=\''$(subst ','\'',$(subst ','\'',$(USE_WATCHMAN)))'\' >>$@
 ifdef TEST_OUTPUT_DIRECTORY
 	@echo TEST_OUTPUT_DIRECTORY=\''$(subst ','\'',$(subst ','\'',$(TEST_OUTPUT_DIRECTORY)))'\' >>$@
 endif
diff --git a/builtin/update-index.c b/builtin/update-index.c
index f23ec83..1da2b15 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -882,6 +882,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 {
 	int newfd, entries, has_errors = 0, line_termination = '\n';
 	int untracked_cache = -1;
+	int use_watchman = -1;
 	int read_from_stdin = 0;
 	int prefix_length = prefix ? strlen(prefix) : 0;
 	int preferred_index_format = 0;
@@ -977,6 +978,8 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 			N_("enable/disable untracked cache")),
 		OPT_SET_INT(0, "force-untracked-cache", &untracked_cache,
 			    N_("enable untracked cache without testing the filesystem"), 2),
+		OPT_BOOL(0, "watchman", &use_watchman,
+			N_("use or not use watchman to reduce refresh cost")),
 		OPT_END()
 	};
 
@@ -1102,6 +1105,14 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)
 		the_index.cache_changed |= UNTRACKED_CHANGED;
 	}
 
+	if (use_watchman > 0) {
+		the_index.last_update    = xstrdup("");
+		the_index.cache_changed |= WATCHMAN_CHANGED;
+	} else if (!use_watchman) {
+		the_index.last_update    = NULL;
+		the_index.cache_changed |= WATCHMAN_CHANGED;
+	}
+
 	if (active_cache_changed) {
 		if (newfd < 0) {
 			if (refresh_args.flags & REFRESH_QUIET)
diff --git a/cache.h b/cache.h
index 201b22e..e1d6e21 100644
--- a/cache.h
+++ b/cache.h
@@ -161,6 +161,8 @@ struct cache_entry {
 #define CE_VALID     (0x8000)
 #define CE_STAGESHIFT 12
 
+#define CE_NO_WATCH  (0x0001)
+
 /*
  * Range 0xFFFF0FFF in ce_flags is divided into
  * two parts: in-memory flags and on-disk ones.
@@ -296,6 +298,7 @@ static inline unsigned int canon_mode(unsigned int mode)
 #define CACHE_TREE_CHANGED	(1 << 5)
 #define SPLIT_INDEX_ORDERED	(1 << 6)
 #define UNTRACKED_CHANGED       (1 << 7)
+#define WATCHMAN_CHANGED	(1 << 8)
 
 struct split_index;
 struct untracked_cache;
@@ -314,6 +317,7 @@ struct index_state {
 	struct hashmap dir_hash;
 	unsigned char sha1[20];
 	struct untracked_cache *untracked;
+	char *last_update;
 };
 
 extern struct index_state the_index;
@@ -637,6 +641,8 @@ extern int check_replace_refs;
 
 extern int fsync_object_files;
 extern int core_preload_index;
+extern int core_use_watchman;
+extern int core_watchman_sync_timeout;
 extern int core_apply_sparse_checkout;
 extern int precomposed_unicode;
 
diff --git a/config.c b/config.c
index 9e42d38..72b9223 100644
--- a/config.c
+++ b/config.c
@@ -860,6 +860,16 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.usewatchman")) {
+		core_use_watchman = git_config_bool(var, value);
+		return 0;
+	}
+
+	if (!strcmp(var, "core.watchmansynctimeout")) {
+		core_watchman_sync_timeout = git_config_int(var, value);
+		return 0;
+	}
+
 	if (!strcmp(var, "core.createobject")) {
 		if (!strcmp(value, "rename"))
 			object_creation_mode = OBJECT_CREATION_USES_RENAMES;
diff --git a/configure.ac b/configure.ac
index 4b1ae7c..2ee5356 100644
--- a/configure.ac
+++ b/configure.ac
@@ -970,6 +970,12 @@ GIT_CONF_SUBST([NO_INITGROUPS])
 #
 # Define NO_ICONV if your libc does not properly support iconv.
 
+# Check for watchman client library
+
+AC_CHECK_LIB([watchman], [watchman_connect],
+	[USE_WATCHMAN=YesPlease],
+	[USE_WATCHMAN=])
+GIT_CONF_SUBST([USE_WATCHMAN])
 
 ## Other checks.
 # Define USE_PIC if you need the main git objects to be built with -fPIC
diff --git a/environment.c b/environment.c
index 565f652..dfaea4e 100644
--- a/environment.c
+++ b/environment.c
@@ -74,6 +74,11 @@ int auto_comment_line_char;
 /* Parallel index stat data preload? */
 int core_preload_index = 1;
 
+/* Use Watchman for faster status queries */
+int core_use_watchman = 0;
+int core_watchman_sync_timeout = 300;
+
+
 /* This is set by setup_git_dir_gently() and/or git_default_config() */
 char *git_work_tree_cfg;
 static char *work_tree;
diff --git a/read-cache.c b/read-cache.c
index 21ae963..46566f5 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -16,6 +16,7 @@
 #include "varint.h"
 #include "split-index.h"
 #include "sigchain.h"
+#include "ewah/ewok.h"
 
 static struct cache_entry *refresh_cache_entry(struct cache_entry *ce,
 					       unsigned int options);
@@ -38,11 +39,13 @@ static struct cache_entry *refresh_cache_entry(struct cache_entry *ce,
 #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* "REUC" */
 #define CACHE_EXT_LINK 0x6c696e6b	  /* "link" */
 #define CACHE_EXT_UNTRACKED 0x554E5452	  /* "UNTR" */
+#define CACHE_EXT_WATCHMAN 0x57414D41	  /* "WAMA" */
 
 /* changes that can be kept in $GIT_DIR/index (basically all extensions) */
 #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \
 		 CE_ENTRY_ADDED | CE_ENTRY_REMOVED | CE_ENTRY_CHANGED | \
-		 SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED)
+		 SPLIT_INDEX_ORDERED | UNTRACKED_CHANGED | \
+		 WATCHMAN_CHANGED)
 
 struct index_state the_index;
 static const char *alternate_index_output;
@@ -1217,8 +1220,13 @@ int refresh_index(struct index_state *istate, unsigned int flags,
 			continue;
 
 		new = refresh_cache_ent(istate, ce, options, &cache_errno, &changed);
-		if (new == ce)
+		if (new == ce) {
+			if (ce->ce_flags & CE_NO_WATCH) {
+				ce->ce_flags          &= ~CE_NO_WATCH;
+				istate->cache_changed |= WATCHMAN_CHANGED;
+			}
 			continue;
+		}
 		if (!new) {
 			const char *fmt;
 
@@ -1370,6 +1378,55 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
 	return 0;
 }
 
+static void mark_no_watchman(size_t pos, void *data)
+{
+	struct index_state *istate = data;
+	assert(pos < istate->cache_nr);
+	istate->cache[pos]->ce_flags |= CE_NO_WATCH;
+}
+
+static int read_watchman_ext(struct index_state *istate, const void *data,
+			      unsigned long sz)
+{
+	struct ewah_bitmap *bitmap;
+	int ret, len;
+
+	if (memchr(data, 0, sz) == NULL)
+		return error("invalid extension");
+	len = strlen(data) + 1;
+	bitmap = ewah_new();
+	ret = ewah_read_mmap(bitmap, (const char *)data + len, sz - len);
+	if (ret != sz - len) {
+		ewah_free(bitmap);
+		return error("fail to parse ewah bitmap");
+	}
+	istate->last_update = xstrdup(data);
+	ewah_each_bit(bitmap, mark_no_watchman, istate);
+	ewah_free(bitmap);
+	return 0;
+}
+
+static int write_strbuf(void *user_data, const void *data, size_t len)
+{
+	struct strbuf *sb = user_data;
+	strbuf_add(sb, data, len);
+	return len;
+}
+
+static void write_watchman_ext(struct strbuf *sb, struct index_state* istate)
+{
+	struct ewah_bitmap *bitmap;
+	int i;
+
+	strbuf_add(sb, istate->last_update, strlen(istate->last_update) + 1);
+	bitmap = ewah_new();
+	for (i = 0; i < istate->cache_nr; i++)
+		if (istate->cache[i]->ce_flags & CE_NO_WATCH)
+			ewah_set(bitmap, i);
+	ewah_serialize_to(bitmap, write_strbuf, sb);
+	ewah_free(bitmap);
+}
+
 static int read_index_extension(struct index_state *istate,
 				const char *ext, void *data, unsigned long sz)
 {
@@ -1387,6 +1444,11 @@ static int read_index_extension(struct index_state *istate,
 	case CACHE_EXT_UNTRACKED:
 		istate->untracked = read_untracked_extension(data, sz);
 		break;
+
+	case CACHE_EXT_WATCHMAN:
+		read_watchman_ext(istate, data, sz);
+		break;
+
 	default:
 		if (*ext < 'A' || 'Z' < *ext)
 			return error("index uses %.4s extension, which we do not understand",
@@ -1600,10 +1662,10 @@ int read_index_from(struct index_state *istate, const char *path)
 	ret = do_read_index(istate, path, 0);
 	split_index = istate->split_index;
 	if (!split_index)
-		return ret;
+		goto done;
 
 	if (is_null_sha1(split_index->base_sha1))
-		return ret;
+		goto done;
 
 	if (split_index->base)
 		discard_index(split_index->base);
@@ -1619,6 +1681,12 @@ int read_index_from(struct index_state *istate, const char *path)
 				     sha1_to_hex(split_index->base_sha1)),
 		    sha1_to_hex(split_index->base->sha1));
 	merge_base_index(istate);
+
+done:
+#ifdef USE_WATCHMAN
+	if (istate->last_update && !getenv("GIT_NO_WATCHMAN"))
+		check_watchman(istate);
+#endif
 	return ret;
 }
 
@@ -1654,6 +1722,8 @@ int discard_index(struct index_state *istate)
 	discard_split_index(istate);
 	free_untracked_cache(istate->untracked);
 	istate->untracked = NULL;
+	free(istate->last_update);
+	istate->last_update = NULL;
 	return 0;
 }
 
@@ -2051,6 +2121,16 @@ static int do_write_index(struct index_state *istate, int newfd,
 		if (err)
 			return -1;
 	}
+	if (istate->last_update) {
+		struct strbuf sb = STRBUF_INIT;
+
+		write_watchman_ext(&sb, istate);
+		err = write_index_ext_header(&c, newfd, CACHE_EXT_WATCHMAN, sb.len) < 0
+			|| ce_write(&c, newfd, sb.buf, sb.len) < 0;
+		strbuf_release(&sb);
+		if (err)
+			return -1;
+	}
 
 	if (ce_flush(&c, newfd, istate->sha1) || fstat(newfd, &st))
 		return -1;
diff --git a/t/test-lib.sh b/t/test-lib.sh
index b1bc65b..0080f47 100644
--- a/t/test-lib.sh
+++ b/t/test-lib.sh
@@ -897,6 +897,7 @@ test -z "$NO_PERL" && test_set_prereq PERL
 test -z "$NO_PYTHON" && test_set_prereq PYTHON
 test -n "$USE_LIBPCRE" && test_set_prereq LIBPCRE
 test -z "$NO_GETTEXT" && test_set_prereq GETTEXT
+test -z "$USE_WATCHMAN" && test_set_prereq WATCHMAN
 
 # Can we rely on git's output in the C locale?
 if test -n "$GETTEXT_POISON"
diff --git a/watchman-support.c b/watchman-support.c
new file mode 100644
index 0000000..f608457
--- /dev/null
+++ b/watchman-support.c
@@ -0,0 +1,132 @@
+#include "cache.h"
+#include "watchman-support.h"
+#include "strbuf.h"
+#include <watchman.h>
+
+static struct watchman_query *make_query(const char *last_update)
+{
+	struct watchman_query *query = watchman_query();
+	watchman_query_set_fields(query, WATCHMAN_FIELD_NAME |
+					 WATCHMAN_FIELD_EXISTS |
+					 WATCHMAN_FIELD_NEWER);
+	/* watchman_query_set_fields(query, WATCHMAN_FIELD_CCLOCK); */
+	watchman_query_set_empty_on_fresh(query, 1);
+	query->sync_timeout = core_watchman_sync_timeout;
+	if (*last_update)
+		watchman_query_set_since_oclock(query, last_update);
+	return query;
+}
+
+static struct watchman_query_result* query_watchman(
+	struct index_state *istate, struct watchman_connection *connection,
+	const char *fs_path, const char *last_update)
+{
+	struct watchman_error wm_error;
+	struct watchman_query *query;
+	struct watchman_expression *expr;
+	struct watchman_query_result *result;
+	struct stat st;
+
+	if (lstat(get_git_dir(), &st)) {
+		/*
+		 * Watchman gets confused if we delete the .git
+		 * directory out from under it, since that's where it
+		 * stores its cookies.  So we'll need to delete the
+		 * watch and then recreate it. It's OK for this to
+		 * fail, as the watch might have already been deleted.
+		 */
+		watchman_watch_del(connection, fs_path, &wm_error);
+
+		if (watchman_watch(connection, fs_path, &wm_error)) {
+			warning("Watchman watch error: %s", wm_error.message);
+			return NULL;
+		}
+	}
+
+	query = make_query(last_update);
+	expr = watchman_true_expression();
+	result = watchman_do_query(connection, fs_path, query, expr, &wm_error);
+	watchman_free_query(query);
+	watchman_free_expression(expr);
+
+	if (!result)
+		warning("Watchman query error: %s (at %s)",
+			wm_error.message,
+			*last_update ? last_update : "the beginning");
+
+	return result;
+}
+
+static void update_index(struct index_state *istate,
+			 struct watchman_query_result *result)
+{
+	int i;
+
+	if (result->is_fresh_instance) {
+		/* let refresh clear them later */
+		for (i = 0; i < istate->cache_nr; i++)
+			istate->cache[i]->ce_flags |= CE_NO_WATCH;
+		goto done;
+	}
+
+	for (i = 0; i < result->nr; i++) {
+		struct watchman_stat *wm = result->stats + i;
+		int pos;
+
+		if (!strncmp(wm->name, ".git/", 5) ||
+		    strstr(wm->name, "/.git/"))
+			continue;
+
+		pos = index_name_pos(istate, wm->name, strlen(wm->name));
+		if (pos < 0)
+			continue;
+		/* FIXME: ignore staged entries and gitlinks too? */
+
+		istate->cache[pos]->ce_flags |= CE_NO_WATCH;
+	}
+
+	/*
+	 * we have marked all modified files with CE_NO_WATCH
+	 * according to watchman. All other files are supposed to be
+	 * uptodate. Those with CE_NO_WATCH will be refreshed
+	 * eventually and get that bit cleared.
+	 */
+	for (i = 0; i < istate->cache_nr; i++) {
+		struct cache_entry *ce = istate->cache[i];
+		if (ce_stage(ce) || (ce->ce_flags & CE_NO_WATCH))
+			continue;
+		ce_mark_uptodate(ce);
+	}
+
+done:
+	free(istate->last_update);
+	istate->last_update    = xstrdup(result->clock);
+	istate->cache_changed |= WATCHMAN_CHANGED;
+}
+
+int check_watchman(struct index_state *istate)
+{
+	struct watchman_error wm_error;
+	struct watchman_connection *connection;
+	struct watchman_query_result *result;
+	const char *fs_path;
+
+	fs_path = get_git_work_tree();
+	if (!fs_path)
+		return -1;
+
+	connection = watchman_connect(&wm_error);
+
+	if (!connection) {
+		warning("Watchman watch error: %s", wm_error.message);
+		return -1;
+	}
+
+	result = query_watchman(istate, connection, fs_path, istate->last_update);
+	watchman_connection_close(connection);
+	if (!result)
+		return -1;
+	update_index(istate, result);
+	watchman_free_query_result(result);
+	return 0;
+}
diff --git a/watchman-support.h b/watchman-support.h
new file mode 100644
index 0000000..5610409
--- /dev/null
+++ b/watchman-support.h
@@ -0,0 +1,8 @@
+#ifndef WATCHMAN_SUPPORT_H
+#define WATCHMAN_SUPPORT_H
+
+struct index_state;
+int check_watchman(struct index_state *index);
+
+
+#endif /* WATCHMAN_SUPPORT_H */
-- 8< --

Re: [RFC] On watchman support

[Torsten Bögershausen]

On 2014-11-11 13.49, Duy Nguyen wrote:
> I've come to the last piece to speed up "git status", watchman
> support. And I realized it's not as good as I thought.
> 
> Watchman could be used for two things: to avoid refreshing the index,
> and to avoid searching for ignored files. The first one can be done
> (with the patch below as demonstration). And it should keep refresh
> cost to near zero in the best case, the cost is proportional to the
> number of modified files.
> 
> For avoiding searching for ignored files. My intention was to build on
> top of untracked cache. If watchman can tell me what files are added
> or deleted since last observed time, then I can invalidate just
> directories that contain them, or even better, calculate ignore status
> for those files only.
> 
> This is important because in reality compilers and editors tend to
> update files by creating a new version then rename them, updating
> directory mtime and invalidating untracked cache as a consequence. As
> you edit more files (or your rebuild touches more dirs), untracked
> cache performance drops (until the next "git status"). The numbers I
> posted so far are the best case.
> 
> The problem with watchman is it cannot tell me "new" files since the
> last observed time (let's say 'T'). If a file exists at 'T', gets
> deleted then recreated, then watchman tells me it's a new file. I want
> to separate those from ones that do not exist before 'T'.
> 
> David's watchman approach does not have this problem because he keeps
> track of all entries under $GIT_WORK_TREE and knows which files are
> truely new. But I don't really want to keep the whole file list around,
> especially when watchman already manages the same list.
> 
> So we got a few options:
> 
> 1) Convince watchman devs to add something to make it work
> 
> 2) Fork watchman
> 
> 3) Make another daemon to keep file list around, or put it in a shared
>    memory.
> 
> 4) Move David's watchman series forward (and maybe make use of shared
>    mem for fs_cache).
> 
> 5) Go with something similar to the patch below and accept untracked
>    cache performance degrades from time to time
> 
> 6) ??
> 
> I'm working on 1). 2) is just bad taste, listed for completeness
> only. If we go with 3) and watchman starts to support Windows (seems
> to be in their plan), we'll need to rework some how. And I really
> don't like 3)
> 
> If 1-3 does not work out, we're left without 4) and 5). We could
> support both, but proobably not worth the code complexity and should
> just go with one.
> 
> And if we go with 4) we should probably think of dropping untracked
> cache if watchman will support Windows in the end. 4) also has another
> advantage over untracked cache, that it could speed up listing ignored
> files as well as untracked files.
> 
> Comments?
> 
[remove the patch]
From a Git user perspective it could be good to have something like this:

a) git status -u
b) git status -uno
c) git status -umtime
d) git status -uwatchman

We know that a) and b) already exist.
c) Can be convenient to have, in order to do benchmarking and testing.
  When the UNTR extension is not found, Git can give an error,
  saying something like this:
  No mtime information found, use "git update-index --untracked-cache"
d) does not yet exist

Of course we may want to configure the default for "git status" in a default variable,
like status.findUntrackedFiles, which can be empty "", "mtime" or "watchman",
and we may add other backends later.

A short test showed that watchman compiles under Mac OS.
The patch did not compile out of the box (both Git and watchman declare
there own version of usage(), some C99 complaints from the compiler in watchman,
nothing that can not be fixed easily)


I will test the mtime patch under networked file systems the next weeks.


The short version:
Go with c), d) then 5) until we have something better :-) 

Re: [RFC] On watchman support

[Duy Nguyen]

On Thu, Nov 13, 2014 at 12:05 PM, Torsten Bögershausen <tboegi@web.de> wrote:
> From a Git user perspective it could be good to have something like this:
>
> a) git status -u
> b) git status -uno
> c) git status -umtime
> d) git status -uwatchman
>
> We know that a) and b) already exist.
> c) Can be convenient to have, in order to do benchmarking and testing.
>   When the UNTR extension is not found, Git can give an error,
>   saying something like this:
>   No mtime information found, use "git update-index --untracked-cache"
> d) does not yet exist
>
> Of course we may want to configure the default for "git status" in a default variable,
> like status.findUntrackedFiles, which can be empty "", "mtime" or "watchman",
> and we may add other backends later.

While "git status" is in the spotlight, these optimizations have wider
impact. Faster index read/refresh/write helps the majority of
commands. Faster untracked listing hits git-status, git-add,
git-commit -A... This is why I go with environment variable for
temporarily disabling something, or we'll need many config and command
line options, one per command.

> A short test showed that watchman compiles under Mac OS.
> The patch did not compile out of the box (both Git and watchman declare
> there own version of usage(), some C99 complaints from the compiler in watchman,
> nothing that can not be fixed easily)

Yeah it's not perfect. It's mainly to show speeding up refresh with
watchman could be done easily and with low impact

> I will test the mtime patch under networked file systems the next weeks.

Hmm.. you remind me mtime series may have this as an advantage over watchman..
-- 
Duy

Re: [RFC] On watchman support

[Torsten Bögershausen]

On 11/13/2014 01:22 PM, Duy Nguyen wrote:
> On Thu, Nov 13, 2014 at 12:05 PM, Torsten Bögershausen <tboegi@web.de> wrote:
>> From a Git user perspective it could be good to have something like this:
>>
>> a) git status -u
>> b) git status -uno
>> c) git status -umtime
>> d) git status -uwatchman
>>
>> We know that a) and b) already exist.
>> c) Can be convenient to have, in order to do benchmarking and testing.
>>   When the UNTR extension is not found, Git can give an error,
>>   saying something like this:
>>   No mtime information found, use "git update-index --untracked-cache"
>> d) does not yet exist
>>
>> Of course we may want to configure the default for "git status" in a default variable,
>> like status.findUntrackedFiles, which can be empty "", "mtime" or "watchman",
>> and we may add other backends later.
> While "git status" is in the spotlight, these optimizations have wider
> impact. Faster index read/refresh/write helps the majority of
> commands. Faster untracked listing hits git-status, git-add,
> git-commit -A... This is why I go with environment variable for
> temporarily disabling something, or we'll need many config and command
> line options, one per command.
>
>> A short test showed that watchman compiles under Mac OS.
>> The patch did not compile out of the box (both Git and watchman declare
>> there own version of usage(), some C99 complaints from the compiler in watchman,
>> nothing that can not be fixed easily)
> Yeah it's not perfect. It's mainly to show speeding up refresh with
> watchman could be done easily and with low impact
>
>> I will test the mtime patch under networked file systems the next weeks.


Thinks become to get a little bit clearer.
What I can understand is that we have 2 different "update-helpers" for Git,
thanks for that.

just in case there is re-roll, does the following makes sense:
We want to enable them (probably only one at a time) either by command line or
persistent in a repo.

As I think we have 2 different update helpers
(and may be more in the future)
GIT_UPDATE_HELPER=dirmtime git status
GIT_UPDATE_HELPER=watchman git status
GIT_UPDATE_HELPER=none git status

of course we want to be able to configure it:
git config core.updatehelper dirmtime


After configuring we may want to override it:
GIT_UPDATE_HELPER=none git status
or
git -c core.updatehelper=none status

> Hmm.. you remind me mtime series may have this as an advantage over watchman..
I had the time to do a short test, sharing a copy of git.git under NFS:
The time for git status dropped from 0.4 seconds to 0.15 seconds or so.
Very nice.
The next test will be to share the same repo under samba to Windows
and Mac OS and see how this works.

Re: [RFC] On watchman support

[David Turner]

On Tue, 2014-11-11 at 19:49 +0700, Duy Nguyen wrote:
> I've come to the last piece to speed up "git status", watchman
> support. And I realized it's not as good as I thought.
> 
> Watchman could be used for two things: to avoid refreshing the index,
> and to avoid searching for ignored files. The first one can be done
> (with the patch below as demonstration). And it should keep refresh
> cost to near zero in the best case, the cost is proportional to the
> number of modified files.
> 
> For avoiding searching for ignored files. My intention was to build on
> top of untracked cache. If watchman can tell me what files are added
> or deleted since last observed time, then I can invalidate just
> directories that contain them, or even better, calculate ignore status
> for those files only.
> 
> This is important because in reality compilers and editors tend to
> update files by creating a new version then rename them, updating
> directory mtime and invalidating untracked cache as a consequence. As
> you edit more files (or your rebuild touches more dirs), untracked
> cache performance drops (until the next "git status"). The numbers I
> posted so far are the best case.
> 
> The problem with watchman is it cannot tell me "new" files since the
> last observed time (let's say 'T'). If a file exists at 'T', gets
> deleted then recreated, then watchman tells me it's a new file. I want
> to separate those from ones that do not exist before 'T'.
> 
> David's watchman approach does not have this problem because he keeps
> track of all entries under $GIT_WORK_TREE and knows which files are
> truely new. But I don't really want to keep the whole file list around,
> especially when watchman already manages the same list.
> 
> So we got a few options:
> 
> 1) Convince watchman devs to add something to make it work

Based on the thread on the watchman github it looks like this won't
happen. 

> 2) Fork watchman
> 
> 3) Make another daemon to keep file list around, or put it in a shared
>    memory.
> 
> 4) Move David's watchman series forward (and maybe make use of shared
>    mem for fs_cache).
> 
> 5) Go with something similar to the patch below and accept untracked
>    cache performance degrades from time to time
> 
> 6) ??
> 
> I'm working on 1). 2) is just bad taste, listed for completeness
> only. If we go with 3) and watchman starts to support Windows (seems
> to be in their plan), we'll need to rework some how. And I really
> don't like 3)
> 
> If 1-3 does not work out, we're left without 4) and 5). We could
> support both, but proobably not worth the code complexity and should
> just go with one.
> 
> And if we go with 4) we should probably think of dropping untracked
> cache if watchman will support Windows in the end. 4) also has another
> advantage over untracked cache, that it could speed up listing ignored
> files as well as untracked files.
> 
> Comments?

I don't think it would be impossible to add Windows support to watchman;
the necessary functions exist, although I don't know how well they work.
My experience with watchman is that it is something of a stress test of
a filesystem's notification layer.  It has exposed bugs in inotify, and
caused system instability on OS X.

My patches are not the world's most beautiful, but they do work.  I
think some improvement might be possible by keeping info about tracked
files in the index, and only storing the tree of ignored and untracked
files separately.  But I have not thought this through fully.  In any
case, making use of shared memory for the fs_cache (as some of your
other patches do for the index) would definitely save time.

Re: [RFC] On watchman support

[Duy Nguyen]

On Tue, Nov 18, 2014 at 7:25 AM, David Turner <dturner@twopensource.com> wrote:
>> So we got a few options:
>>
>> 1) Convince watchman devs to add something to make it work
>
> Based on the thread on the watchman github it looks like this won't
> happen.

Yeah. I came to the conclusion that I needed an extra daemon. And
because I would need an extra daemon anyway to speed up index read
time, that one could be used for caching something else like watchman.
It works out quite nice: because watchman is not tied to the main
'git' binary, people don't need libwatchman and libjansson by default.
When people want watchman, they can install an extra package that
includes the index-helper and its dependencies. This only matters for
binary-based distros of course.

>> Comments?
>
> I don't think it would be impossible to add Windows support to watchman;
> the necessary functions exist, although I don't know how well they work.
> My experience with watchman is that it is something of a stress test of
> a filesystem's notification layer.  It has exposed bugs in inotify, and
> caused system instability on OS X.

The way i'm adding watchman to index-helper should work on Windows as
well, IPC is really simple. But let's wait and see.

> My patches are not the world's most beautiful, but they do work.  I
> think some improvement might be possible by keeping info about tracked
> files in the index, and only storing the tree of ignored and untracked
> files separately.  But I have not thought this through fully.  In any
> case, making use of shared memory for the fs_cache (as some of your
> other patches do for the index) would definitely save time.

By the way, what happened to your sse optimization in refs.c? I see
it's reverted but I didn't follow closely to know why. Or will you go
with cityhash now.. I ask because you have another sse optimization
for hashmap on your watchman branch and that could reduce init time
for name-hash. Name-hash is used often on case-insensitive fs (less
often on case-sensitive fs).

I did a simple test and your optimization could init name-hash (on
webkit) in 35ms, while unmodified hashmap took 88ms. Loading index on
this machine took 360ms for reference (probably down too 100ms with
index-helper running, when that 88ms starts to become significant).
-- 
Duy

Re: [RFC] On watchman support

[David Turner]

On Tue, 2014-11-18 at 17:48 +0700, Duy Nguyen wrote:
> > My patches are not the world's most beautiful, but they do work.  I
> > think some improvement might be possible by keeping info about tracked
> > files in the index, and only storing the tree of ignored and untracked
> > files separately.  But I have not thought this through fully.  In any
> > case, making use of shared memory for the fs_cache (as some of your
> > other patches do for the index) would definitely save time.
> 
> By the way, what happened to your sse optimization in refs.c? I see
> it's reverted but I didn't follow closely to know why. 

I don't know why either -- it works just fine.  There was a bug, but I
fixed it.  Junio?

> Or will you go
> with cityhash now.. I ask because you have another sse optimization
> for hashmap on your watchman branch and that could reduce init time
> for name-hash. Name-hash is used often on case-insensitive fs (less
> often on case-sensitive fs).

Cityhash would be better, because it has actual engineering effort put
into it; what I did on my branch is a hack that happens to work
decently.  As the comment notes, I did not spend much effort on tuning
my implementation.  Also, Cityhash doesn't require SSE, so it's more
portable.

> I did a simple test and your optimization could init name-hash (on
> webkit) in 35ms, while unmodified hashmap took 88ms. Loading index on
> this machine took 360ms for reference (probably down too 100ms with
> index-helper running, when that 88ms starts to become significant).

OK, that sounds like a big win.  

Re: [RFC] On watchman support

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> On Tue, 2014-11-18 at 17:48 +0700, Duy Nguyen wrote:
>> > My patches are not the world's most beautiful, but they do work.  I
>> > think some improvement might be possible by keeping info about tracked
>> > files in the index, and only storing the tree of ignored and untracked
>> > files separately.  But I have not thought this through fully.  In any
>> > case, making use of shared memory for the fs_cache (as some of your
>> > other patches do for the index) would definitely save time.
>> 
>> By the way, what happened to your sse optimization in refs.c? I see
>> it's reverted but I didn't follow closely to know why. 
>
> I don't know why either -- it works just fine.  There was a bug, but I
> fixed it.  Junio?

I vaguely recall that the reason why we dropped it was because it
was too much code churn in an area that was being worked on in
parallel, but you may need to go back to the list archive for
details.

Re: [RFC] On watchman support

[David Turner]

On Tue, 2014-11-18 at 12:55 -0800, Junio C Hamano wrote:
> David Turner <dturner@twopensource.com> writes:
> 
> > On Tue, 2014-11-18 at 17:48 +0700, Duy Nguyen wrote:
> >> > My patches are not the world's most beautiful, but they do work.  I
> >> > think some improvement might be possible by keeping info about tracked
> >> > files in the index, and only storing the tree of ignored and untracked
> >> > files separately.  But I have not thought this through fully.  In any
> >> > case, making use of shared memory for the fs_cache (as some of your
> >> > other patches do for the index) would definitely save time.
> >> 
> >> By the way, what happened to your sse optimization in refs.c? I see
> >> it's reverted but I didn't follow closely to know why. 
> >
> > I don't know why either -- it works just fine.  There was a bug, but I
> > fixed it.  Junio?
> 
> I vaguely recall that the reason why we dropped it was because it
> was too much code churn in an area that was being worked on in
> parallel, but you may need to go back to the list archive for
> details.

OK, in that case I'll try to remember to reroll it once the rest of the
refs stuff lands.

Re: [RFC] On watchman support

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> On Tue, 2014-11-18 at 12:55 -0800, Junio C Hamano wrote:
>> I vaguely recall that the reason why we dropped it was because it
>> was too much code churn in an area that was being worked on in
>> parallel, but you may need to go back to the list archive for
>> details.
>
> OK, in that case I'll try to remember to reroll it once the rest of the
> refs stuff lands.

Sure.  But I would much prefer to see us explore an arch independent
optimisation of the caller before starting to micro-optimize a leaf
function.  

It is not check_refname_format() that is the real problem. It's the
fact that we do O(# of refs) work whenever we have to access the
packed-refs file. check_refname_format() is part of that, surely,
but so is reading the file, creating all of the refname structs in
memory, etc. (credit to peff@).

Re: [RFC] On watchman support

[Jeff King]

On Tue, Nov 18, 2014 at 01:26:56PM -0800, Junio C Hamano wrote:

> It is not check_refname_format() that is the real problem. It's the
> fact that we do O(# of refs) work whenever we have to access the
> packed-refs file. check_refname_format() is part of that, surely,
> but so is reading the file, creating all of the refname structs in
> memory, etc. (credit to peff@).

Yeah, I'd agree very much with that. I am not sure if I am cc'd here
because of my general complaining about packed-refs, or if I have said
something clever on the subject.

I did implement at one point a packed-refs reader that does a binary
search on the mmap'd packed-refs file, and can return a single value or
even locate the first entry matching a prefix (like "refs/tags/") and
iterate until we're out of the prefix. Unfortunately this runs very
contrary to the caching design of the refs.c code. It is focused on
caching _loose_ refs, where we may read an outer directory (like
"refs/"), and would like to avoid descending into an inner directory
(likes "refs/foo/") unless we are interested in what is in it. But
caching partial reads of packed-refs like this is "inside out"; we might
read all of "refs/tags/*", but have no clue what else is in "refs/". So
integrating it into refs.c would take pretty major surgery.

-Peff

Re: [RFC] On watchman support

[Paolo Ciarrocchi]

On Tue, Nov 18, 2014 at 1:25 AM, David Turner <dturner@twopensource.com> wrote:
>
> My patches are not the world's most beautiful, but they do work.

Out of curiosity: do you run the patches at twitter?

Thanks.

-- Paolo


-- 
Paolo

Re: [RFC] On watchman support

[David Turner]

On Wed, 2014-11-19 at 16:26 +0100, Paolo Ciarrocchi wrote:
> On Tue, Nov 18, 2014 at 1:25 AM, David Turner <dturner@twopensource.com> wrote:
> >
> > My patches are not the world's most beautiful, but they do work.
> 
> Out of curiosity: do you run the patches at twitter?

An increasing number of us do, yes. 

Re: [RFC] On watchman support

[Duy Nguyen]

On Wed, Nov 19, 2014 at 1:12 AM, David Turner <dturner@twopensource.com> wrote:
>> Or will you go
>> with cityhash now.. I ask because you have another sse optimization
>> for hashmap on your watchman branch and that could reduce init time
>> for name-hash. Name-hash is used often on case-insensitive fs (less
>> often on case-sensitive fs).
>
> Cityhash would be better, because it has actual engineering effort put
> into it; what I did on my branch is a hack that happens to work
> decently.  As the comment notes, I did not spend much effort on tuning
> my implementation.  Also, Cityhash doesn't require SSE, so it's more
> portable.

Cityhash looks less appealing to me. For one thing it's C++ so linking
to C can't be done. I could add a few "extern "C"" to make it work.
But if we plan to support it eventually, cityhash must support C out
of the box.

Then cityhash does not support case-insensitive hashing. I had to make
a CityHash32i version based on CityHash32. It's probably my bugs
there, but performance is worse (~120ms) than original hashmap.c
(90ms). Enabling sse4.2 helps a bit, but still worse. Using the
case-sensitive version in place for memihash and strihash does make
cityhash win over hashmap.c, around 50ms (with or without sse4.2). But
that's still not as good as your version (~35ms)..
-- 
Duy

Re: [RFC] On watchman support

[David Turner]

On Fri, 2014-11-28 at 18:13 +0700, Duy Nguyen wrote:
> On Wed, Nov 19, 2014 at 1:12 AM, David Turner <dturner@twopensource.com> wrote:
> >> Or will you go
> >> with cityhash now.. I ask because you have another sse optimization
> >> for hashmap on your watchman branch and that could reduce init time
> >> for name-hash. Name-hash is used often on case-insensitive fs (less
> >> often on case-sensitive fs).
> >
> > Cityhash would be better, because it has actual engineering effort put
> > into it; what I did on my branch is a hack that happens to work
> > decently.  As the comment notes, I did not spend much effort on tuning
> > my implementation.  Also, Cityhash doesn't require SSE, so it's more
> > portable.
> 
> Cityhash looks less appealing to me. For one thing it's C++ so linking
> to C can't be done. I could add a few "extern "C"" to make it work.
> But if we plan to support it eventually, cityhash must support C out
> of the box.
> 
> Then cityhash does not support case-insensitive hashing. I had to make
> a CityHash32i version based on CityHash32. It's probably my bugs
> there, but performance is worse (~120ms) than original hashmap.c
> (90ms). Enabling sse4.2 helps a bit, but still worse. Using the
> case-sensitive version in place for memihash and strihash does make
> cityhash win over hashmap.c, around 50ms (with or without sse4.2). But
> that's still not as good as your version (~35ms)..

Can you post your CityHash32i?  

Have you tried this C port of Cityhash?

https://github.com/santeri-io/cityhash-c