{"thread":{"id":"36429","subject":"[RFC] Speed up \"git status\" by caching untracked file info","startedAt":"2014-04-17T05:51:58Z","lastAt":"2014-04-23T00:52:46Z","messageCount":8,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen","Karsten Blees"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"239005","messageId":"1397713918-22829-1-git-send-email-pclouds@gmail.com","threadId":"36429","inReplyTo":null,"subject":"[RFC] Speed up \"git status\" by caching untracked file info","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-17T05:51:58Z","receivedAt":"2014-04-17T05:51:58Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This patch serves as a heads up about a feature I'm working on. I hope\nthat by posting it early, people could double check if I have made\nsome fundamental mistakes that completely ruin the idea. It's about\nspeeding up \"git status\" by caching untracked file info in the index\n_if_ your file system supports it (more below).\n\nThe whole WIP series is at\n\nhttps://github.com/pclouds/git/commits/untracked-cache\n\nI only post the real meat here. I'm aware of a few incomplete details\nin this patch, but nothing fundamentally wrong. So far the numbers are\npromising.  ls-files is updated to run fill_directory() twice in a\nrow and \"ls-files -o --directory --no-empty-directory --exclude-standard\"\n(with gcc -O0) gives me:\n\n           first run  second (cached) run\ngentoo-x86    500 ms             71.6  ms\nwine          140 ms              9.72 ms\nwebkit        125 ms              6.88 ms\nlinux-2.6     106 ms             16.2  ms\n\nBasically untracked time is cut to one tenth in the best case\nscenario. The final numbers would be a bit higher because I haven't\nstored or read the cache from index yet. Real commit message follows..\n\n\nread_directory() plays a bit part in the slowness of \"git status\"\nbecause it has to read every directory and check for excluded entries,\nwhich is really expensive. This patch adds an option to cache the\nresults so that after the first slow read_directory(), the following\ncalls should be cheap and fast.\n\nThe following inputs are sufficient to determine what files in a\ndirectory are excluded:\n\n - The list of files and directories of the direction in question\n - The $GIT_DIR/index\n - The content of $GIT_DIR/info/exclude\n - The content of core.excludesfile\n - The content (or the lack) of .gitignore of all parent directories\n   from $GIT_WORK_TREE\n\nIf we can cheaply validate all those inputs for a certain directory,\nwe are sure that the current code will always produce the same\nresults, so we can cache and reuse those results.\n\nThis is not a silver bullet approach. When you compile a C file, for\nexample, the old .o file is removed and a new one with the same name\ncreated, effectively invalidating the containing directory's\ncache. But at least with a large enough work tree, there could be many\ndirectories you never touch. The cache could help there.\n\nThe first input can be checked using directory mtime. In many\nfilesystems, directory mtime is updated when direct files/dirs are\nadded or removed (*). If you do not use such a file system, this\nfeature is not for you.\n\nThe second one can be hooked from read-cache.c. Whenever a file (or a\nsubmodule) is added or removed from a directory, we invalidate that\ndirectory. This will be done in a later patch.\n\nThe remaining inputs are easy, their SHA-1 could be used to verify\ntheir contents. We do need to read .gitignore files and digest\nthem. But they are usually few and small, so the overhead should not\nbe much.\n\nAt the implementation level, the whole directory structure is saved,\neach directory corresponds to one struct untracked_dir. Each directory\nholds SHA-1 of the .gitignore underneath (or null if it does not\nexist) and the list of untracked \"files\" and subdirs that need to\nrecurse into if all is well. Untracked subdirectories are saved in the\nfile queue and are the reason of quoting \"files\" in the previous\nsentence.\n\nOn the first run, no untracked_dir is valid, the default code path is\nrun. prep_exclude() is updated to record SHA-1 of .gitignore along the\nway. read_directory_recursive() is updated to record untracked files.\n\nOn subsequent runs, read_directory_recursive() reads stat info of the\ndirectory in question and verifies if files/dirs have been added or\nremoved. With the help of prep_exclude() to verify .gitignore chain,\nit may decide \"all is well\" and enable the fast path in\ntreat_path(). read_directory_recursive() is still called for\nsubdirectories even in fast path, because a directory mtime does not\ncover all subdirs recursively.\n\nSo if all is really well, read_directory() becomes a series of\nopen(\".gitignore\"), read(\".gitignore\"), close(), hash_sha1_file() and\nstat(<dir>) _without_ heavyweight exclude filtering. There should be\nno overhead if this feature is disabled.\n\n(*) Looking at the code in linux-2.6, ext* family seems to expose this\nbehavior. vfat also does (but not so sure about fat). btrfs probably\ndoes. statfs() could be used to detect file system.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n dir.c | 336 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----\n dir.h |  31 ++++++\n 2 files changed, 343 insertions(+), 24 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex bd58c14..f5d6315 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -31,8 +31,23 @@ enum path_treatment {\n \tpath_untracked\n };\n \n+struct cached_dir {\n+\tDIR *fdir;\n+\tstruct untracked_dir *untracked;\n+\tint nr_files;\n+\tint nr_dirs;\n+\n+\t/*\n+\t * return data from read_cached_dir(). name and state are only\n+\t * valid if de is NULL\n+\t */\n+\tstruct dirent *de;\n+\tstruct strbuf name;\n+\tenum path_treatment state;\n+};\n+\n static enum path_treatment read_directory_recursive(struct dir_struct *dir,\n-\tconst char *path, int len,\n+\tconst char *path, int len, struct untracked_dir *untracked,\n \tint check_only, const struct path_simplify *simplify);\n static int get_dtype(struct dirent *de, const char *path, int len);\n \n@@ -796,6 +811,56 @@ static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir,\n \treturn NULL;\n }\n \n+static struct untracked_dir *lookup_untracked(struct untracked_dir *dir,\n+\t\t\t\t\t      const char *name, int len)\n+{\n+\tint first, last;\n+\tstruct untracked_dir *d;\n+\tif (!dir)\n+\t\treturn NULL;\n+\tif (len && name[len - 1] == '/')\n+\t\tlen--;\n+\tfirst = 0;\n+\tlast = dir->dirs_nr;\n+\twhile (last > first) {\n+\t\tint cmp, next = (last + first) >> 1;\n+\t\td = dir->dirs[next];\n+\t\tcmp = strncmp(name, d->name, len);\n+\t\tif (!cmp && strlen(d->name) > len)\n+\t\t\tcmp = -1;\n+\t\tif (!cmp)\n+\t\t\treturn d;\n+\t\tif (cmp < 0) {\n+\t\t\tlast = next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfirst = next+1;\n+\t}\n+\n+\td = xmalloc(sizeof(*d) + len);\n+\tmemset(d, 0, sizeof(*d) + len);\n+\td->untracked_nr = -1;\n+\tmemcpy(d->name, name, len);\n+\n+\tALLOC_GROW(dir->dirs, dir->dirs_nr + 1, dir->dirs_alloc);\n+\tmemmove(dir->dirs + first + 1, dir->dirs + first,\n+\t\t(dir->dirs_nr - first) * sizeof(*dir->dirs));\n+\tdir->dirs_nr++;\n+\tdir->dirs[first] = d;\n+\treturn d;\n+}\n+\n+static void invalidate_untracked(struct untracked_dir *dir)\n+{\n+\tint i;\n+\tif (dir->untracked_nr == -1)\n+\t\t/* it is assumed that all subdirs are already invalidated */\n+\t\treturn;\n+\tdir->untracked_nr = -1;\n+\tfor (i = 0; i < dir->dirs_nr; i++)\n+\t\tinvalidate_untracked(dir->dirs[i]);\n+}\n+\n /*\n  * Loads the per-directory exclude list for the substring of base\n  * which has a char length of baselen.\n@@ -805,6 +870,7 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \tstruct exclude_list_group *group;\n \tstruct exclude_list *el;\n \tstruct exclude_stack *stk = NULL;\n+\tstruct untracked_dir *untracked = NULL;\n \tint current;\n \n \tgroup = &dir->exclude_list_group[EXC_DIRS];\n@@ -842,18 +908,35 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \t/* Read from the parent directories and push them down. */\n \tcurrent = stk ? stk->baselen : -1;\n \tstrbuf_setlen(&dir->basebuf, current < 0 ? 0 : current);\n+\n+\tif (dir->untracked && current >= 0 && current < baselen) {\n+\t\tconst char *start = base;\n+\t\tconst char *end = base + current;\n+\t\tuntracked = &dir->untracked->root;\n+\t\twhile (start < end) {\n+\t\t\tconst char *cp = strchrnul(start, '/');\n+\t\t\tuntracked = lookup_untracked(untracked, start, cp - start);\n+\t\t\tstart = *cp == '/' ? cp + 1 : cp;\n+\t\t}\n+\t}\n+\n \twhile (current < baselen) {\n \t\tstruct exclude_stack *stk = xcalloc(1, sizeof(*stk));\n \t\tconst char *cp;\n+\t\tunsigned char sha1[20];\n \n \t\tif (current < 0) {\n \t\t\tcp = base;\n \t\t\tcurrent = 0;\n+\t\t\tif (dir->untracked)\n+\t\t\t\tuntracked = &dir->untracked->root;\n \t\t} else {\n \t\t\tcp = strchr(base + current + 1, '/');\n \t\t\tif (!cp)\n \t\t\t\tdie(\"oops in prep_exclude\");\n \t\t\tcp++;\n+\t\t\tuntracked = lookup_untracked(untracked, base + current,\n+\t\t\t\t\t\t     cp - base - current);\n \t\t}\n \t\tstk->prev = dir->exclude_stack;\n \t\tstk->baselen = cp - base;\n@@ -880,7 +963,22 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \t\t}\n \n \t\t/* Try to read per-directory file */\n-\t\tif (dir->exclude_per_dir) {\n+\t\thashclr(sha1);\n+\t\tif (dir->exclude_per_dir &&\n+\t\t    /*\n+\t\t     * If we know that no files have been added in\n+\t\t     * this directory (i.e. valid_cached_dir() has\n+\t\t     * been executed and untracked_nr is non-zero) ..\n+\t\t     */\n+\t\t    (!untracked || untracked->untracked_nr < 0 ||\n+\t\t     /*\n+\t\t      * .. and .gitignore does not exist before\n+\t\t      * (i.e. null exclude_sha1 and skip_worktree is\n+\t\t      * not set). Then we can skip loading .gitignore,\n+\t\t      * which would result in ENOENT anyway.\n+\t\t      * skip_worktree is taken care in read_directory()\n+\t\t      */\n+\t\t     !is_null_sha1(untracked->exclude_sha1))) {\n \t\t\t/*\n \t\t\t * dir->basebuf gets reused by the traversal, but we\n \t\t\t * need fname to remain unchanged to ensure the src\n@@ -895,7 +993,13 @@ static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n \t\t\tel->src = strbuf_detach(&sb, NULL);\n \t\t\tadd_excludes_from_file_to_list(el->src, el->src,\n \t\t\t\t\t\t       stk->baselen, el, 1,\n-\t\t\t\t\t\t       NULL);\n+\t\t\t\t\t\t       untracked ? sha1 : NULL);\n+\t\t}\n+\t\tif (untracked) {\n+\t\t\tif (untracked->untracked_nr >= 0 &&\n+\t\t\t    hashcmp(sha1, untracked->exclude_sha1))\n+\t\t\t\tinvalidate_untracked(untracked);\n+\t\t\thashcpy(untracked->exclude_sha1, sha1);\n \t\t}\n \t\tdir->exclude_stack = stk;\n \t\tcurrent = stk->baselen;\n@@ -1076,6 +1180,7 @@ static enum exist_status directory_exists_in_index(const char *dirname, int len)\n  *  (c) otherwise, we recurse into it.\n  */\n static enum path_treatment treat_directory(struct dir_struct *dir,\n+\tstruct untracked_dir *untracked,\n \tconst char *dirname, int len, int exclude,\n \tconst struct path_simplify *simplify)\n {\n@@ -1103,7 +1208,9 @@ static enum path_treatment treat_directory(struct dir_struct *dir,\n \tif (!(dir->flags & DIR_HIDE_EMPTY_DIRECTORIES))\n \t\treturn exclude ? path_excluded : path_untracked;\n \n-\treturn read_directory_recursive(dir, dirname, len, 1, simplify);\n+\treturn read_directory_recursive(dir, dirname, len,\n+\t\t\t\t\tlookup_untracked(untracked, dirname, len),\n+\t\t\t\t\t1, simplify);\n }\n \n /*\n@@ -1219,6 +1326,7 @@ static int get_dtype(struct dirent *de, const char *path, int len)\n }\n \n static enum path_treatment treat_one_path(struct dir_struct *dir,\n+\t\t\t\t\t  struct untracked_dir *untracked,\n \t\t\t\t\t  struct strbuf *path,\n \t\t\t\t\t  const struct path_simplify *simplify,\n \t\t\t\t\t  int dtype, struct dirent *de)\n@@ -1271,7 +1379,7 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n \t\treturn path_none;\n \tcase DT_DIR:\n \t\tstrbuf_addch(path, '/');\n-\t\treturn treat_directory(dir, path->buf, path->len, exclude,\n+\t\treturn treat_directory(dir, untracked, path->buf, path->len, exclude,\n \t\t\tsimplify);\n \tcase DT_REG:\n \tcase DT_LNK:\n@@ -1280,13 +1388,28 @@ static enum path_treatment treat_one_path(struct dir_struct *dir,\n }\n \n static enum path_treatment treat_path(struct dir_struct *dir,\n-\t\t\t\t      struct dirent *de,\n+\t\t\t\t      struct untracked_dir *untracked,\n+\t\t\t\t      struct cached_dir *cdir,\n \t\t\t\t      struct strbuf *path,\n \t\t\t\t      int baselen,\n \t\t\t\t      const struct path_simplify *simplify)\n {\n \tint dtype;\n+\tstruct dirent *de = cdir->de;\n \n+\t/* fast path after verifying cached data is still valid */\n+\tif (!de) {\n+\t\tstrbuf_setlen(path, baselen);\n+\t\tstrbuf_addbuf(path, &cdir->name);\n+\t\t/*\n+\t\t * treat_one_path() does this before it calls\n+\t\t * treat_directory()\n+\t\t */\n+\t\tif (cdir->state == path_recurse &&\n+\t\t    path->buf[path->len - 1] != '/')\n+\t\t\tstrbuf_addch(path, '/');\n+\t\treturn cdir->state;\n+\t}\n \tif (is_dot_or_dotdot(de->d_name) || !strcmp(de->d_name, \".git\"))\n \t\treturn path_none;\n \tstrbuf_setlen(path, baselen);\n@@ -1295,7 +1418,122 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n \t\treturn path_none;\n \n \tdtype = DTYPE(de);\n-\treturn treat_one_path(dir, path, simplify, dtype, de);\n+\treturn treat_one_path(dir, untracked, path, simplify, dtype, de);\n+}\n+\n+static void add_untracked(struct untracked_dir *dir, const char *name)\n+{\n+\tif (!dir)\n+\t\treturn;\n+\tif (dir->untracked_nr < 0)\n+\t\tdir->untracked_nr = 0;\n+\tALLOC_GROW(dir->untracked, dir->untracked_nr + 1,\n+\t\t   dir->untracked_alloc);\n+\tdir->untracked[dir->untracked_nr++] = xstrdup(name);\n+}\n+\n+static int valid_cached_dir(struct dir_struct *dir,\n+\t\t\t    struct untracked_dir *untracked,\n+\t\t\t    struct strbuf *path)\n+{\n+\tstruct stat st;\n+\tif (stat(path->len ? path->buf : \".\", &st)) {\n+\t\tmemset(&untracked->stat_data, 0, sizeof(untracked->stat_data));\n+\t\tinvalidate_untracked(untracked);\n+\t\treturn 0;\n+\t}\n+\tif (untracked->untracked_nr < 0 ||\n+\t    match_stat_data(&untracked->stat_data, &st)) {\n+\t\tfill_stat_data(&untracked->stat_data, &st);\n+\t\t/*\n+\t\t * We could leave subdirs validated if .gitignore is\n+\t\t * not added or removed, but for now just invalidate\n+\t\t * recursively for safety, there's the an assumption\n+\t\t * elsewhere that if dir X is invalidated, then\n+\t\t * everything inside must be invalidated.\n+\t\t */\n+\t\tinvalidate_untracked(untracked);\n+\t\treturn 0;\n+\t}\n+\n+\t/*\n+\t * prep_exclude will be called eventually, but it's called\n+\t * much later in last_exclude_matching(), deep in\n+\t * treat_path(), We need it now to determine the validity of\n+\t * the cache. The next call is nearly no-op, the way\n+\t * prep_exclude() is designed.\n+\t */\n+\tif (path->len && path->buf[path->len - 1] != '/') {\n+\t\tstrbuf_addch(path, '/');\n+\t\tprep_exclude(dir, path->buf, path->len);\n+\t\tstrbuf_setlen(path, path->len - 1);\n+\t} else\n+\t\tprep_exclude(dir, path->buf, path->len);\n+\n+\t/* hopefully prep_exclude() will not invalidate this entry... */\n+\treturn untracked->untracked_nr >= 0;\n+}\n+\n+static int open_cached_dir(struct cached_dir *cdir,\n+\t\t\t   struct dir_struct *dir,\n+\t\t\t   struct untracked_dir *untracked,\n+\t\t\t   struct strbuf *path)\n+{\n+\tmemset(cdir, 0, sizeof(*cdir));\n+\tstrbuf_init(&cdir->name, 100);\n+\tcdir->untracked = untracked;\n+\tif (!untracked || !valid_cached_dir(dir, untracked, path)) {\n+\t\tcdir->fdir = opendir(path->len ? path->buf : \".\");\n+\t\tif (!cdir->fdir)\n+\t\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+int read_cached_dir(struct cached_dir *cdir)\n+{\n+\tif (cdir->fdir) {\n+\t\tcdir->de = readdir(cdir->fdir);\n+\t\tif (!cdir->de)\n+\t\t\treturn -1;\n+\t\treturn 0;\n+\t}\n+\tif (cdir->nr_files < cdir->untracked->untracked_nr) {\n+\t\tstruct untracked_dir *d = cdir->untracked;\n+\t\tstrbuf_reset(&cdir->name);\n+\t\tstrbuf_addstr(&cdir->name, d->untracked[cdir->nr_files]);\n+\t\tcdir->nr_files++;\n+\t\tcdir->de = NULL;\n+\t\tcdir->state = path_untracked;\n+\t\treturn 0;\n+\t}\n+\twhile (cdir->nr_dirs < cdir->untracked->dirs_nr) {\n+\t\tstruct untracked_dir *d = cdir->untracked->dirs[cdir->nr_dirs];\n+\t\tif (!d->recurse) {\n+\t\t\tcdir->nr_dirs++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tstrbuf_reset(&cdir->name);\n+\t\tstrbuf_addstr(&cdir->name, d->name);\n+\t\tcdir->nr_dirs++;\n+\t\tcdir->de = NULL;\n+\t\tcdir->state = path_recurse;\n+\t\treturn 0;\n+\t}\n+\treturn -1;\n+}\n+\n+static void close_cached_dir(struct cached_dir *cdir)\n+{\n+\tif (cdir->fdir)\n+\t\tclosedir(cdir->fdir);\n+\t/*\n+\t * We have gone through this directory and found no untracked\n+\t * entries. Set untracked_nr to zero to make it valid.\n+\t */\n+\tif (cdir->untracked && cdir->untracked->untracked_nr < 0)\n+\t\tcdir->untracked->untracked_nr = 0;\n+\tstrbuf_release(&cdir->name);\n }\n \n /*\n@@ -1311,30 +1549,35 @@ static enum path_treatment treat_path(struct dir_struct *dir,\n  */\n static enum path_treatment read_directory_recursive(struct dir_struct *dir,\n \t\t\t\t    const char *base, int baselen,\n-\t\t\t\t    int check_only,\n+\t\t\t\t    struct untracked_dir *untracked, int check_only,\n \t\t\t\t    const struct path_simplify *simplify)\n {\n-\tDIR *fdir;\n+\tstruct cached_dir cdir;\n \tenum path_treatment state, subdir_state, dir_state = path_none;\n-\tstruct dirent *de;\n \tstruct strbuf path = STRBUF_INIT;\n \n \tstrbuf_add(&path, base, baselen);\n \n-\tfdir = opendir(path.len ? path.buf : \".\");\n-\tif (!fdir)\n+\tif (open_cached_dir(&cdir, dir, untracked, &path))\n \t\tgoto out;\n \n-\twhile ((de = readdir(fdir)) != NULL) {\n+\twhile (!read_cached_dir(&cdir)) {\n \t\t/* check how the file or directory should be treated */\n-\t\tstate = treat_path(dir, de, &path, baselen, simplify);\n+\t\tstate = treat_path(dir, untracked, &cdir, &path, baselen, simplify);\n+\n \t\tif (state > dir_state)\n \t\t\tdir_state = state;\n \n \t\t/* recurse into subdir if instructed by treat_path */\n \t\tif (state == path_recurse) {\n-\t\t\tsubdir_state = read_directory_recursive(dir, path.buf,\n-\t\t\t\tpath.len, check_only, simplify);\n+\t\t\tstruct untracked_dir *ud;\n+\t\t\tud = lookup_untracked(untracked, path.buf + baselen,\n+\t\t\t\t\t      path.len - baselen);\n+\t\t\tif (ud)\n+\t\t\t\tud->recurse = 1;\n+\t\t\tsubdir_state =\n+\t\t\t\tread_directory_recursive(dir, path.buf, path.len,\n+\t\t\t\t\t\t\t ud, check_only, simplify);\n \t\t\tif (subdir_state > dir_state)\n \t\t\t\tdir_state = subdir_state;\n \t\t}\n@@ -1360,15 +1603,18 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,\n \t\t\tbreak;\n \n \t\tcase path_untracked:\n-\t\t\tif (!(dir->flags & DIR_SHOW_IGNORED))\n-\t\t\t\tdir_add_name(dir, path.buf, path.len);\n+\t\t\tif (dir->flags & DIR_SHOW_IGNORED)\n+\t\t\t\tbreak;\n+\t\t\tdir_add_name(dir, path.buf, path.len);\n+\t\t\tif (cdir.fdir)\n+\t\t\t\tadd_untracked(untracked, path.buf + baselen);\n \t\t\tbreak;\n \n \t\tdefault:\n \t\t\tbreak;\n \t\t}\n \t}\n-\tclosedir(fdir);\n+\tclose_cached_dir(&cdir);\n  out:\n \tstrbuf_release(&path);\n \n@@ -1439,7 +1685,7 @@ static int treat_leading_path(struct dir_struct *dir,\n \t\t\tbreak;\n \t\tif (simplify_away(sb.buf, sb.len, simplify))\n \t\t\tbreak;\n-\t\tif (treat_one_path(dir, &sb, simplify,\n+\t\tif (treat_one_path(dir, NULL, &sb, simplify,\n \t\t\t\t   DT_DIR, NULL) == path_none)\n \t\t\tbreak; /* do not recurse into it */\n \t\tif (len <= baselen) {\n@@ -1455,6 +1701,7 @@ static int treat_leading_path(struct dir_struct *dir,\n int read_directory(struct dir_struct *dir, const char *path, int len, const struct pathspec *pathspec)\n {\n \tstruct path_simplify *simplify;\n+\tstruct untracked_dir *untracked = NULL;\n \n \t/*\n \t * Check out create_simplify()\n@@ -1478,8 +1725,47 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const stru\n \t * create_simplify().\n \t */\n \tsimplify = create_simplify(pathspec ? pathspec->_raw : NULL);\n-\tif (!len || treat_leading_path(dir, path, len, simplify))\n-\t\tread_directory_recursive(dir, path, len, 0, simplify);\n+\t/* dir->untracked->dir_flags = DIR_SHOW_OTHER_DIRECTORIES | DIR_HIDE_EMPTY_DIRECTORIES; */\n+\t/* if EXC_CMDL is loaded, ignore untracked cache */\n+\tif ((!pathspec || !pathspec->nr) && dir->untracked &&\n+\t    dir->flags == dir->untracked->dir_flags &&\n+\t    (dir->exclude_per_dir == dir->untracked->exclude_per_dir || /* both are NULL? */\n+\t     !strcmp(dir->exclude_per_dir, dir->untracked->exclude_per_dir))) {\n+\t\tint i;\n+\t\tuntracked = &dir->untracked->root;\n+\t\tif (hashcmp(dir->info_exclude_sha1,\n+\t\t\t    dir->untracked->info_exclude_sha1)) {\n+\t\t\tinvalidate_untracked(untracked);\n+\t\t\thashcpy(dir->untracked->info_exclude_sha1,\n+\t\t\t\tdir->info_exclude_sha1);\n+\t\t}\n+\t\tif (hashcmp(dir->excludes_file_sha1,\n+\t\t\t    dir->untracked->excludes_file_sha1)) {\n+\t\t\tinvalidate_untracked(untracked);\n+\t\t\thashcpy(dir->untracked->excludes_file_sha1,\n+\t\t\t\tdir->excludes_file_sha1);\n+\t\t}\n+\t\tuntracked->recurse = 1;\n+\n+\t\t/*\n+\t\t * An optimization in prep_exclude() does not play\n+\t\t * well with CE_SKIP_WORKTREE. It's a rare case\n+\t\t * anyway, if a single entry has that bit set, disable\n+\t\t * the whole untracked cache.\n+\t\t */\n+\t\tfor (i = 0; i < active_nr; i++)\n+\t\t\tif (ce_skip_worktree(active_cache[i])) {\n+\t\t\t\tdir->untracked = NULL;\n+\t\t\t\tuntracked = NULL;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t} else\n+\t\t/* make sure untracked cache code path is disabled */\n+\t\tdir->untracked = NULL;\n+\tif (!len || treat_leading_path(dir, path, len, simplify)) {\n+\t\tread_directory_recursive(dir, path, len, untracked,\n+\t\t\t\t\t 0, simplify);\n+\t}\n \tfree_simplify(simplify);\n \tqsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);\n \tqsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);\n@@ -1646,9 +1932,11 @@ void setup_standard_excludes(struct dir_struct *dir)\n \t\texcludes_file = xdg_path;\n \t}\n \tif (!access_or_warn(path, R_OK, 0))\n-\t\tadd_excludes_from_file(dir, path, NULL);\n+\t\tadd_excludes_from_file(dir, path,\n+\t\t\t\t       dir->untracked ? dir->info_exclude_sha1 : NULL);\n \tif (excludes_file && !access_or_warn(excludes_file, R_OK, 0))\n-\t\tadd_excludes_from_file(dir, excludes_file, NULL);\n+\t\tadd_excludes_from_file(dir, excludes_file,\n+\t\t\t\t       dir->untracked ? dir->excludes_file_sha1 : NULL);\n }\n \n int remove_path(const char *name)\ndiff --git a/dir.h b/dir.h\nindex 71ad8c6..d293744 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -73,6 +73,31 @@ struct exclude_list_group {\n \tstruct exclude_list *el;\n };\n \n+struct untracked_dir {\n+\t/* null SHA-1 means this directory does not have .gitignore */\n+\tunsigned char exclude_sha1[20];\n+\tstruct stat_data stat_data;\n+\tint recurse;\n+\tstruct untracked_dir **dirs;\n+\tchar **untracked;\n+\tunsigned dirs_nr, dirs_alloc;\n+\t/* untracked_nr == -1 means this entry is invalid */\n+\tint untracked_nr, untracked_alloc;\n+\tchar name[1];\n+};\n+\n+struct untracked_cache {\n+\tunsigned char info_exclude_sha1[20];\n+\tunsigned char excludes_file_sha1[20];\n+\tconst char *exclude_per_dir;\n+\t/*\n+\t * dir_struct#flags must match dir_flags or the untracked\n+\t * cache is ignored.\n+\t */\n+\tunsigned dir_flags;\n+\tstruct untracked_dir root;\n+};\n+\n struct dir_struct {\n \tint nr, alloc;\n \tint ignored_nr, ignored_alloc;\n@@ -120,6 +145,12 @@ struct dir_struct {\n \tstruct exclude_stack *exclude_stack;\n \tstruct exclude *exclude;\n \tstruct strbuf basebuf;\n+\n+\t/* Enable untracked file cache if set */\n+\tstruct untracked_cache *untracked;\n+\t/* temporary data for validating untracked->[same field name] */\n+\tunsigned char info_exclude_sha1[20];\n+\tunsigned char excludes_file_sha1[20];\n };\n \n /*\n-- \n1.9.1.346.ga2b5940\n"},{"id":"239034","messageId":"xmqqy4z3d9t0.fsf@gitster.dls.corp.google.com","threadId":"36429","inReplyTo":"1397713918-22829-1-git-send-email-pclouds@gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-17T19:40:11Z","receivedAt":"2014-04-17T19:40:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n>            first run  second (cached) run\n> gentoo-x86    500 ms             71.6  ms\n> wine          140 ms              9.72 ms\n> webkit        125 ms              6.88 ms\n> linux-2.6     106 ms             16.2  ms\n>\n> Basically untracked time is cut to one tenth in the best case\n> scenario. The final numbers would be a bit higher because I haven't\n> stored or read the cache from index yet. Real commit message follows..\n\nAs you allude to later with \"if you recompile a single file, the\nwhole hierarchy in that directory is lost\", two back-to-back runs of\n\"git status\" is not very interesting.\n\n>  - The list of files and directories of the direction in question\n>  - The $GIT_DIR/index\n>  - The content of $GIT_DIR/info/exclude\n>  - The content of core.excludesfile\n>  - The content (or the lack) of .gitignore of all parent directories\n>    from $GIT_WORK_TREE\n>\n> If we can cheaply validate all those inputs for a certain directory,\n> we are sure that the current code will always produce the same\n> results, so we can cache and reuse those results.\n>\n> This is not a silver bullet approach. When you compile a C file, for\n> example, the old .o file is removed and a new one with the same name\n> created, effectively invalidating the containing directory's\n> cache. But at least with a large enough work tree, there could be many\n> directories you never touch. The cache could help there.\n>\n> The first input can be checked using directory mtime. In many\n> filesystems, directory mtime is updated when direct files/dirs are\n> added or removed (*).\n\nAn important thing is that creation of new cruft or deletion of\nexisting cruft can be detected without any false negative with the\nmechanism, and mtime on directory would be a good way to check it.\n\n> The second one can be hooked from read-cache.c. Whenever a file (or a\n> submodule) is added or removed from a directory, we invalidate that\n> directory. This will be done in a later patch.\n\nI would imagine that it would be done at the same places as we\ninvalidate cache-trees, with the same \"invalidation percolates up\"\nlogic.\n\n> On subsequent runs, read_directory_recursive() reads stat info of the\n> directory in question and verifies if files/dirs have been added or\n> removed.\n\nHmph.  If you have a two-level hierarchy D1/D2 and you change the\nlist of crufts in D2 but not in D1, the mtime of D1/D2 changes but\nnot the mtime of D1, as you observed below.\n\n> With the help of prep_exclude() to verify .gitignore chain,\n> it may decide \"all is well\" and enable the fast path in\n> treat_path(). read_directory_recursive() is still called for\n> subdirectories even in fast path, because a directory mtime does not\n> cover all subdirs recursively.\n\nI wonder if you can avoid recursing into D1 when no cached mtime\n(and .gitignore) information has changed in any subdirectory of it\n(e.g. both D1 and D1/D2 match the cache).\n"},{"id":"239057","messageId":"CACsJy8BrPZ8LDwN5cK9MgBcbtP0rK-TZ3wo=Jpc0V9YyaSyuXg@mail.gmail.com","threadId":"36429","inReplyTo":"xmqqy4z3d9t0.fsf@gitster.dls.corp.google.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-17T23:27:44Z","receivedAt":"2014-04-17T23:27:44Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Apr 18, 2014 at 2:40 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n>\n>>            first run  second (cached) run\n>> gentoo-x86    500 ms             71.6  ms\n>> wine          140 ms              9.72 ms\n>> webkit        125 ms              6.88 ms\n>> linux-2.6     106 ms             16.2  ms\n>>\n>> Basically untracked time is cut to one tenth in the best case\n>> scenario. The final numbers would be a bit higher because I haven't\n>> stored or read the cache from index yet. Real commit message follows..\n>\n> As you allude to later with \"if you recompile a single file, the\n> whole hierarchy in that directory is lost\", two back-to-back runs of\n> \"git status\" is not very interesting.\n\nNo, if you recompile in directory A, then we need to recompute exclude\nfiles for A only, not A/B, A/B/C... We only need to invalidate the\nwhole hierarchy when A/.gitignore (or worse $GIT_DIR/info/exclude) is\nchanged.\n\n>> The second one can be hooked from read-cache.c. Whenever a file (or a\n>> submodule) is added or removed from a directory, we invalidate that\n>> directory. This will be done in a later patch.\n>\n> I would imagine that it would be done at the same places as we\n> invalidate cache-trees, with the same \"invalidation percolates up\"\n> logic.\n\nYep yep.\n\n>> On subsequent runs, read_directory_recursive() reads stat info of the\n>> directory in question and verifies if files/dirs have been added or\n>> removed.\n>\n> Hmph.  If you have a two-level hierarchy D1/D2 and you change the\n> list of crufts in D2 but not in D1, the mtime of D1/D2 changes but\n> not the mtime of D1, as you observed below.\n>\n>> With the help of prep_exclude() to verify .gitignore chain,\n>> it may decide \"all is well\" and enable the fast path in\n>> treat_path(). read_directory_recursive() is still called for\n>> subdirectories even in fast path, because a directory mtime does not\n>> cover all subdirs recursively.\n>\n> I wonder if you can avoid recursing into D1 when no cached mtime\n> (and .gitignore) information has changed in any subdirectory of it\n> (e.g. both D1 and D1/D2 match the cache).\n\nThe problem if when we need to decide to recurse into D1, we have no\nidea if any of its subdirs is changed. So we need to recurse in anyway\n(at least in the cache; if D1 is unchanged, we will not try to\nopendir() it, just get the exclude list from the cache and move on).\n-- \nDuy\n"},{"id":"239320","messageId":"53563CB2.5030603@gmail.com","threadId":"36429","inReplyTo":"1397713918-22829-1-git-send-email-pclouds@gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-04-22T09:56:02Z","receivedAt":"2014-04-22T09:56:02Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 17.04.2014 07:51, schrieb Nguyễn Thái Ngọc Duy:\n> This patch serves as a heads up about a feature I'm working on. I hope\n> that by posting it early, people could double check if I have made\n> some fundamental mistakes that completely ruin the idea. It's about\n> speeding up \"git status\" by caching untracked file info in the index\n> _if_ your file system supports it (more below).\n> \n> The whole WIP series is at\n> \n> https://github.com/pclouds/git/commits/untracked-cache\n> \n> I only post the real meat here. I'm aware of a few incomplete details\n> in this patch, but nothing fundamentally wrong. So far the numbers are\n> promising.  ls-files is updated to run fill_directory() twice in a\n> row and \"ls-files -o --directory --no-empty-directory --exclude-standard\"\n> (with gcc -O0) gives me:\n> \n>            first run  second (cached) run\n> gentoo-x86    500 ms             71.6  ms\n> wine          140 ms              9.72 ms\n> webkit        125 ms              6.88 ms\n\nIIRC name_hash.c::lazy_init_name_hash took ~100ms on my system, so hopefully you did a dummy 'cache_name_exists(\"anything\")' before starting the measurement of the first run?\n\n> linux-2.6     106 ms             16.2  ms\n> \n> Basically untracked time is cut to one tenth in the best case\n> scenario. The final numbers would be a bit higher because I haven't\n> stored or read the cache from index yet. Real commit message follows..\n> \n> \n> read_directory() plays a bit part in the slowness of \"git status\"\n> because it has to read every directory and check for excluded entries,\n> which is really expensive. This patch adds an option to cache the\n> results so that after the first slow read_directory(), the following\n> calls should be cheap and fast.\n> \n> The following inputs are sufficient to determine what files in a\n> directory are excluded:\n> \n>  - The list of files and directories of the direction in question\n>  - The $GIT_DIR/index\n>  - The content of $GIT_DIR/info/exclude\n>  - The content of core.excludesfile\n>  - The content (or the lack) of .gitignore of all parent directories\n>    from $GIT_WORK_TREE\n> \n\nThe dir_struct.flags also play a big role in evaluation of read_directory.\n\nE.g. it seems untracked files are not properly recorded if the cache is filled with '--ignored' option:\n\n> @@ -1360,15 +1603,18 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,\n>  \t\t\tbreak;\n>  \n>  \t\tcase path_untracked:\n> -\t\t\tif (!(dir->flags & DIR_SHOW_IGNORED))\n> -\t\t\t\tdir_add_name(dir, path.buf, path.len);\n> +\t\t\tif (dir->flags & DIR_SHOW_IGNORED)\n> +\t\t\t\tbreak;\n> +\t\t\tdir_add_name(dir, path.buf, path.len);\n> +\t\t\tif (cdir.fdir)\n> +\t\t\t\tadd_untracked(untracked, path.buf + baselen);\n>  \t\t\tbreak;\n\nSimilarly, the '--directory' option controls early returns from the directory scan (via read_directory_recursive's check_only argument), so you won't be able to get a full untracked files listing if the cache was recorded with '--directory'. Additionally, '--directory' aggregates the state at the topmost untracked directory, so that directory's cached state depends on all sub-directories as well...\n\nI wonder if it makes sense to separate cache recording logic from read_directory_recursive and friends, which are mainly concerned with flags processing.\n\n> If we can cheaply validate all those inputs for a certain directory,\n> we are sure that the current code will always produce the same\n> results, so we can cache and reuse those results.\n> \n> This is not a silver bullet approach. When you compile a C file, for\n> example, the old .o file is removed and a new one with the same name\n> created, effectively invalidating the containing directory's\n> cache. But at least with a large enough work tree, there could be many\n> directories you never touch. The cache could help there.\n> \n> The first input can be checked using directory mtime. In many\n> filesystems, directory mtime is updated when direct files/dirs are\n> added or removed (*). If you do not use such a file system, this\n> feature is not for you.\n> \n> The second one can be hooked from read-cache.c. Whenever a file (or a\n> submodule) is added or removed from a directory, we invalidate that\n> directory. This will be done in a later patch.\n> \n> The remaining inputs are easy, their SHA-1 could be used to verify\n> their contents. We do need to read .gitignore files and digest\n> them. But they are usually few and small, so the overhead should not\n> be much.\n> \n> At the implementation level, the whole directory structure is saved,\n> each directory corresponds to one struct untracked_dir.\n\nWith the usual options (e.g. standard 'git status'), untracked directories are mostly skipped, so the cache would mostly store tracked directories. Naming it 'struct untracked_dir' is a bit confusing, IMO.\n\n> Each directory\n> holds SHA-1 of the .gitignore underneath (or null if it does not\n> exist) and the list of untracked \"files\" and subdirs that need to\n> recurse into if all is well. Untracked subdirectories are saved in the\n> file queue and are the reason of quoting \"files\" in the previous\n> sentence.\n> \n> On the first run, no untracked_dir is valid, the default code path is\n> run. prep_exclude() is updated to record SHA-1 of .gitignore along the\n> way. read_directory_recursive() is updated to record untracked files.\n> \n> On subsequent runs, read_directory_recursive() reads stat info of the\n> directory in question and verifies if files/dirs have been added or\n> removed. With the help of prep_exclude() to verify .gitignore chain,\n> it may decide \"all is well\" and enable the fast path in\n> treat_path(). read_directory_recursive() is still called for\n> subdirectories even in fast path, because a directory mtime does not\n> cover all subdirs recursively.\n> \n> So if all is really well, read_directory() becomes a series of\n> open(\".gitignore\"), read(\".gitignore\"), close(), hash_sha1_file() and\n> stat(<dir>) _without_ heavyweight exclude filtering. There should be\n> no overhead if this feature is disabled.\n> \n\nWouldn't mtime of .gitignore files suffice here (so you don't need to open and parse them every time)?\n"},{"id":"239323","messageId":"CACsJy8AYyhZKBmL=z2H11Oemjw_YoUES0vYtB8s0HnMB+4uyVw@mail.gmail.com","threadId":"36429","inReplyTo":"53563CB2.5030603@gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-22T10:13:40Z","receivedAt":"2014-04-22T10:13:40Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 22, 2014 at 4:56 PM, Karsten Blees <karsten.blees@gmail.com> wrote:\n> Am 17.04.2014 07:51, schrieb Nguyễn Thái Ngọc Duy:\n>> This patch serves as a heads up about a feature I'm working on. I hope\n>> that by posting it early, people could double check if I have made\n>> some fundamental mistakes that completely ruin the idea. It's about\n>> speeding up \"git status\" by caching untracked file info in the index\n>> _if_ your file system supports it (more below).\n>>\n>> The whole WIP series is at\n>>\n>> https://github.com/pclouds/git/commits/untracked-cache\n>>\n>> I only post the real meat here. I'm aware of a few incomplete details\n>> in this patch, but nothing fundamentally wrong. So far the numbers are\n>> promising.  ls-files is updated to run fill_directory() twice in a\n>> row and \"ls-files -o --directory --no-empty-directory --exclude-standard\"\n>> (with gcc -O0) gives me:\n>>\n>>            first run  second (cached) run\n>> gentoo-x86    500 ms             71.6  ms\n>> wine          140 ms              9.72 ms\n>> webkit        125 ms              6.88 ms\n>\n> IIRC name_hash.c::lazy_init_name_hash took ~100ms on my system, so hopefully you did a dummy 'cache_name_exists(\"anything\")' before starting the measurement of the first run?\n\nNo I didn't. Thanks for pointing it out. I'll see if I can reduce its time.\n\n>> The following inputs are sufficient to determine what files in a\n>> directory are excluded:\n>>\n>>  - The list of files and directories of the direction in question\n>>  - The $GIT_DIR/index\n>>  - The content of $GIT_DIR/info/exclude\n>>  - The content of core.excludesfile\n>>  - The content (or the lack) of .gitignore of all parent directories\n>>    from $GIT_WORK_TREE\n>>\n>\n> The dir_struct.flags also play a big role in evaluation of read_directory.\n>\n> E.g. it seems untracked files are not properly recorded if the cache is filled with '--ignored' option:\n\nYeah. dir_struct.flags will be part of the input. I intend to optimize\n\"git status\" case only, so if it matches the recorded\ndir_struct.flags, the cache is used. Else the cache is ignored.\nCaching --ignored is not so interesting, because the list of ignored\nfiles could be huge, while untracked listing is usually small.\n\n>> @@ -1360,15 +1603,18 @@ static enum path_treatment read_directory_recursive(struct dir_struct *dir,\n>>                       break;\n>>\n>>               case path_untracked:\n>> -                     if (!(dir->flags & DIR_SHOW_IGNORED))\n>> -                             dir_add_name(dir, path.buf, path.len);\n>> +                     if (dir->flags & DIR_SHOW_IGNORED)\n>> +                             break;\n>> +                     dir_add_name(dir, path.buf, path.len);\n>> +                     if (cdir.fdir)\n>> +                             add_untracked(untracked, path.buf + baselen);\n>>                       break;\n>\n> Similarly, the '--directory' option controls early returns from the directory scan (via read_directory_recursive's check_only argument), so you won't be able to get a full untracked files listing if the cache was recorded with '--directory'. Additionally, '--directory' aggregates the state at the topmost untracked directory, so that directory's cached state depends on all sub-directories as well...\n\nI missed this. We could ignore check_only if caching is enabled, but\nthat does not sound really good. Let me think about it more..\n\n>\n> I wonder if it makes sense to separate cache recording logic from read_directory_recursive and friends, which are mainly concerned with flags processing.\n\nThe core code path is still shared though, or we would duplicate r_d_r\nentirely for caching recording, which sounds like a maintenance\nnightmare.\n\n>> At the implementation level, the whole directory structure is saved,\n>> each directory corresponds to one struct untracked_dir.\n>\n> With the usual options (e.g. standard 'git status'), untracked directories are mostly skipped, so the cache would mostly store tracked directories. Naming it 'struct untracked_dir' is a bit confusing, IMO.\n\nIt's actually just \"directories\". We may need to store both tracked\nand untracked directories. Maybe renaming it to cached_dir..\n\n>> So if all is really well, read_directory() becomes a series of\n>> open(\".gitignore\"), read(\".gitignore\"), close(), hash_sha1_file() and\n>> stat(<dir>) _without_ heavyweight exclude filtering. There should be\n>> no overhead if this feature is disabled.\n>>\n>\n> Wouldn't mtime of .gitignore files suffice here (so you don't need to open and parse them every time)?\n\nThat's a further optimization. With the current code it's simpler to\nopen .gitignore. Assume you have a path a/b/c. a/.gitignore's stat\ninfo is good, so you skip opening it. Then you find a/b/.gitignore is\nmodified and you need to recompute untracked files in a/b. To do that\nyou need a/.gitignore as well. Lazily opening a/.gitignore at this\nstage is possible, but trickier (you have to make sure the rules are\nin correct order because of negative patterns).\n\nAnyway, the number of .gitignore files is usually small. We can\nalready avoid opening non-existent .gitignore, which is proportional\nto the number of directories.\n-- \nDuy\n"},{"id":"239325","messageId":"CACsJy8AFDquHEajJQa_LWhtAMO-vHQbMCFuPV6UkGNZXTbANZw@mail.gmail.com","threadId":"36429","inReplyTo":"CACsJy8AYyhZKBmL=z2H11Oemjw_YoUES0vYtB8s0HnMB+4uyVw@mail.gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-22T10:35:13Z","receivedAt":"2014-04-22T10:35:13Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 22, 2014 at 5:13 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n>> IIRC name_hash.c::lazy_init_name_hash took ~100ms on my system, so hopefully you did a dummy 'cache_name_exists(\"anything\")' before starting the measurement of the first run?\n>\n> No I didn't. Thanks for pointing it out. I'll see if I can reduce its time.\n\nWell name-hash is only used when core.ignorecase is set. So it's\noptional. Maybe we could save it in a separate index extension, but we\nneed to verify that the reader uses the same hash function as the\nwriter.\n\n>> Similarly, the '--directory' option controls early returns from the directory scan (via read_directory_recursive's check_only argument), so you won't be able to get a full untracked files listing if the cache was recorded with '--directory'. Additionally, '--directory' aggregates the state at the topmost untracked directory, so that directory's cached state depends on all sub-directories as well...\n>\n> I missed this. We could ignore check_only if caching is enabled, but\n> that does not sound really good. Let me think about it more..\n\nWe could save \"check_only\" to the cache as well. This way we don't\nhave to disable the check_only trick completely.\n\nSo we process a directory with check_only set, find one untracked\nentry and stop short. We store check_only value and the status (\"found\nsomething\") in addition to dir mtime. Next time we check the dir's\nmtime. If it matches and is called with check_only set, we know there\nis at least one untracked entry, that's enough to stop r_d_r and\nreturn early. If dir mtime does not match, or r_d_r is called without\ncheck_only, we ignore the cached data and fall back to opendir.\n\nSounds good?\n-- \nDuy\n"},{"id":"239366","messageId":"5356BB5B.90903@gmail.com","threadId":"36429","inReplyTo":"CACsJy8AFDquHEajJQa_LWhtAMO-vHQbMCFuPV6UkGNZXTbANZw@mail.gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-04-22T18:56:27Z","receivedAt":"2014-04-22T18:56:27Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 22.04.2014 12:35, schrieb Duy Nguyen:\n> On Tue, Apr 22, 2014 at 5:13 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n>>> IIRC name_hash.c::lazy_init_name_hash took ~100ms on my system, so hopefully you did a dummy 'cache_name_exists(\"anything\")' before starting the measurement of the first run?\n>>\n>> No I didn't. Thanks for pointing it out. I'll see if I can reduce its time.\n> \n> Well name-hash is only used when core.ignorecase is set. So it's\n> optional.\n\nThis is only true for the case-insensitive directory hash. The file hash ('cache_file_exists') is always used to skip expensive excluded checks for tracked files. \n\n'cache_file_exists' basically treats faster lookups for higher setup costs, which makes perfect sense when scanning the entire work tree. However, if most of the directory info is cached and just a few directories need refresh (and core.ignorecase=false), binary search ('cache_name_pos') may be better. The difficulty is to decide when to choose one over the other :-)\n\n> Maybe we could save it in a separate index extension, but we\n> need to verify that the reader uses the same hash function as the\n> writer.\n> \n>>> Similarly, the '--directory' option controls early returns from the directory scan (via read_directory_recursive's check_only argument), so you won't be able to get a full untracked files listing if the cache was recorded with '--directory'. Additionally, '--directory' aggregates the state at the topmost untracked directory, so that directory's cached state depends on all sub-directories as well...\n>>\n>> I missed this. We could ignore check_only if caching is enabled, but\n>> that does not sound really good. Let me think about it more..\n> \n> We could save \"check_only\" to the cache as well. This way we don't\n> have to disable the check_only trick completely.\n> \n> So we process a directory with check_only set, find one untracked\n> entry and stop short. We store check_only value and the status (\"found\n> something\") in addition to dir mtime. Next time we check the dir's\n> mtime. If it matches and is called with check_only set, we know there\n> is at least one untracked entry, that's enough to stop r_d_r and\n> return early. If dir mtime does not match, or r_d_r is called without\n> check_only, we ignore the cached data and fall back to opendir.\n> \n> Sounds good?\n> \n\nWhat about untracked files in sub-directories? E.g. you have untracked dirs a/b with untracked file a/b/c, so normal 'git status' would list 'a/' as untracked.\nNow, 'rm a/b/c' would update mtime of b, but not of a, so you'd still list 'a/' as untracked. Same thing for 'echo \"c\" >a/b/.gitignore'.\n\nYour solution could work if you additionally cache the directories that had to be scanned to find that first untracked file (but you probably had that in mind anyway).\n\nIf the cache is only used for certain dir_struct.flags combinations, you can probably get around saving the check_only flag (which can only ever be true if both DIR_SHOW_OTHER_DIRECTORIES and DIR_HIDE_EMPTY_DIRECTORIES are set (which is the default for 'git status')).\n"},{"id":"239405","messageId":"CACsJy8B1_L+hOSZ86W0h+3xyh=fvgcaMqxrSndMB-BY3Ks2Xug@mail.gmail.com","threadId":"36429","inReplyTo":"5356BB5B.90903@gmail.com","subject":"Re: [RFC] Speed up \"git status\" by caching untracked file info","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-23T00:52:46Z","receivedAt":"2014-04-23T00:52:46Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Apr 23, 2014 at 1:56 AM, Karsten Blees <karsten.blees@gmail.com> wrote:\n> Am 22.04.2014 12:35, schrieb Duy Nguyen:\n>> On Tue, Apr 22, 2014 at 5:13 PM, Duy Nguyen <pclouds@gmail.com> wrote:\n>>>> IIRC name_hash.c::lazy_init_name_hash took ~100ms on my system, so hopefully you did a dummy 'cache_name_exists(\"anything\")' before starting the measurement of the first run?\n>>>\n>>> No I didn't. Thanks for pointing it out. I'll see if I can reduce its time.\n>>\n>> Well name-hash is only used when core.ignorecase is set. So it's\n>> optional.\n>\n> This is only true for the case-insensitive directory hash. The file hash ('cache_file_exists') is always used to skip expensive excluded checks for tracked files.\n>\n> 'cache_file_exists' basically treats faster lookups for higher setup costs, which makes perfect sense when scanning the entire work tree. However, if most of the directory info is cached and just a few directories need refresh (and core.ignorecase=false), binary search ('cache_name_pos') may be better. The difficulty is to decide when to choose one over the other :-)\n\nRight. The problem is even if untracked cache is used, we don't know\nin advance how cache_file_exists calls we need to make. If .gitignore\nchanges, we could see how many directories are invalidated recursively\nand that could be an indicator for favoring cache_file_exists over\ncache_name_pos. It's harder when dir mtime changes, I suppose we could\nbe optimistic and stick to cache_name_pos until the number of calls\ngets over a limit and turn to cache_file_exists. May backfire though..\n\n>\n>> Maybe we could save it in a separate index extension, but we\n>> need to verify that the reader uses the same hash function as the\n>> writer.\n>>\n>>>> Similarly, the '--directory' option controls early returns from the directory scan (via read_directory_recursive's check_only argument), so you won't be able to get a full untracked files listing if the cache was recorded with '--directory'. Additionally, '--directory' aggregates the state at the topmost untracked directory, so that directory's cached state depends on all sub-directories as well...\n>>>\n>>> I missed this. We could ignore check_only if caching is enabled, but\n>>> that does not sound really good. Let me think about it more..\n>>\n>> We could save \"check_only\" to the cache as well. This way we don't\n>> have to disable the check_only trick completely.\n>>\n>> So we process a directory with check_only set, find one untracked\n>> entry and stop short. We store check_only value and the status (\"found\n>> something\") in addition to dir mtime. Next time we check the dir's\n>> mtime. If it matches and is called with check_only set, we know there\n>> is at least one untracked entry, that's enough to stop r_d_r and\n>> return early. If dir mtime does not match, or r_d_r is called without\n>> check_only, we ignore the cached data and fall back to opendir.\n>>\n>> Sounds good?\n>>\n>\n> What about untracked files in sub-directories? E.g. you have untracked dirs a/b with untracked file a/b/c, so normal 'git status' would list 'a/' as untracked.\n> Now, 'rm a/b/c' would update mtime of b, but not of a, so you'd still list 'a/' as untracked. Same thing for 'echo \"c\" >a/b/.gitignore'.\n>\n> Your solution could work if you additionally cache the directories that had to be scanned to find that first untracked file (but you probably had that in mind anyway).\n\nBasically all directories that are touched by r_d_r() will be cached.\n\n> If the cache is only used for certain dir_struct.flags combinations, you can probably get around saving the check_only flag (which can only ever be true if both DIR_SHOW_OTHER_DIRECTORIES and DIR_HIDE_EMPTY_DIRECTORIES are set (which is the default for 'git status')).\n-- \nDuy\n"}]}