do_compare_entry: use already-computed path

In traverse_trees, we generate the complete traverse path for a
traverse_info.  Later, in do_compare_entry, we used to go do a bunch
of work to compare the traverse_info to a cache_entry's name without
computing that path.  But since we already have that path, we don't
need to do all that work.  Instead, we can just put the generated
path into the traverse_info, and do the comparison more directly.

We copy the path because prune_traversal might mutate `base`. This
doesn't happen in any codepaths where do_compare_entry is called,
but it's better to be safe.

This makes git checkout much faster -- about 25% on Twitter's
monorepo.  Deeper directory trees are likely to benefit more than
shallower ones.

Signed-off-by: David Turner <dturner@twopensource.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/tree-walk.c b/tree-walk.c
index 6dccd2d5dd78e0ee71c1ebc771a99010a56db157..cd4bb2c38bdf40f497ece781ce3a9e61de6b4399 100644 (file)
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -320,6 +320,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
        struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
        struct strbuf base = STRBUF_INIT;
        int interesting = 1;
        struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
        struct strbuf base = STRBUF_INIT;
        int interesting = 1;

+       char *traverse_path;

 
        for (i = 0; i < n; i++)
                tx[i].d = t[i];
 
        for (i = 0; i < n; i++)
                tx[i].d = t[i];


@@ -329,7 +330,11 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
                make_traverse_path(base.buf, info->prev, &info->name);
                base.buf[info->pathlen-1] = '/';
                strbuf_setlen(&base, info->pathlen);
                make_traverse_path(base.buf, info->prev, &info->name);
                base.buf[info->pathlen-1] = '/';
                strbuf_setlen(&base, info->pathlen);

+               traverse_path = xstrndup(base.buf, info->pathlen);
+       } else {
+               traverse_path = xstrndup(info->name.path, info->pathlen);

        }
        }

+       info->traverse_path = traverse_path;

        for (;;) {
                int trees_used;
                unsigned long mask, dirmask;
        for (;;) {
                int trees_used;
                unsigned long mask, dirmask;


@@ -411,6 +416,8 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
        for (i = 0; i < n; i++)
                free_extended_entry(tx + i);
        free(tx);
        for (i = 0; i < n; i++)
                free_extended_entry(tx + i);
        free(tx);

+       free(traverse_path);
+       info->traverse_path = NULL;

        strbuf_release(&base);
        return error;
 }
        strbuf_release(&base);
        return error;
 }

diff --git a/tree-walk.h b/tree-walk.h
index 3b2f7bf17d37de5b475c415b41c6abb4281d5469..174eb617dfb9d6a85bcf1e309227c8b724089765 100644 (file)
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -59,6 +59,7 @@ enum follow_symlinks_result {
 enum follow_symlinks_result get_tree_entry_follow_symlinks(unsigned char *tree_sha1, const char *name, unsigned char *result, struct strbuf *result_path, unsigned *mode);
 
 struct traverse_info {
 enum follow_symlinks_result get_tree_entry_follow_symlinks(unsigned char *tree_sha1, const char *name, unsigned char *result, struct strbuf *result_path, unsigned *mode);
 
 struct traverse_info {

+       const char *traverse_path;

        struct traverse_info *prev;
        struct name_entry name;
        int pathlen;
        struct traverse_info *prev;
        struct name_entry name;
        int pathlen;

diff --git a/unpack-trees.c b/unpack-trees.c
index 8e2032f4e592910d6f3336f95019647992113877..5f541c28c6aadda347c85018a6591ac6b2622820 100644 (file)
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -498,13 +498,14 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
  * itself - the caller needs to do the final check for the cache
  * entry having more data at the end!
  */
  * itself - the caller needs to do the final check for the cache
  * entry having more data at the end!
  */

-static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
+static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)

 {
        int len, pathlen, ce_len;
        const char *ce_name;
 
        if (info->prev) {
 {
        int len, pathlen, ce_len;
        const char *ce_name;
 
        if (info->prev) {

-               int cmp = do_compare_entry(ce, info->prev, &info->name);
+               int cmp = do_compare_entry_piecewise(ce, info->prev,
+                                                    &info->name);

                if (cmp)
                        return cmp;
        }
                if (cmp)
                        return cmp;
        }


@@ -522,6 +523,39 @@ static int do_compare_entry(const struct cache_entry *ce, const struct traverse_
        return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
 }
 
        return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
 }
 

+static int do_compare_entry(const struct cache_entry *ce,
+                           const struct traverse_info *info,
+                           const struct name_entry *n)
+{
+       int len, pathlen, ce_len;
+       const char *ce_name;
+       int cmp;
+
+       /*
+        * If we have not precomputed the traverse path, it is quicker
+        * to avoid doing so.  But if we have precomputed it,
+        * it is quicker to use the precomputed version.
+        */
+       if (!info->traverse_path)
+               return do_compare_entry_piecewise(ce, info, n);
+
+       cmp = strncmp(ce->name, info->traverse_path, info->pathlen);
+       if (cmp)
+               return cmp;
+
+       pathlen = info->pathlen;
+       ce_len = ce_namelen(ce);
+
+       if (ce_len < pathlen)
+               return -1;
+
+       ce_len -= pathlen;
+       ce_name = ce->name + pathlen;
+
+       len = tree_entry_len(n);
+       return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
+}
+

 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
 {
        int cmp = do_compare_entry(ce, info, n);
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
 {
        int cmp = do_compare_entry(ce, info, n);