git grep performance regression

Hi,

I have noticed a performance regression in git grep between v1.8.1 and v1.8.1.1:

On the kernel tree: For git 1.8.1: $ time git grep foodsgsg

real 0m0.158s user 0m0.290s sys 0m0.207s

For git 1.8.1.1: $ time /tmp/g/bin/git grep foodsgsg

real 0m0.501s user 0m0.707s sys 0m0.493s

A bisect seems to indicate that it was introduced by 94bc67:
commit 94bc671a1f2e8610de475c2494d2763355a99f65
Author: Jean-Noël AVILA <avila.jn@gmail.com>
Date:   Sat Dec 8 21:04:39 2012 +0100

    Add directory pattern matching to attributes
    
    The manpage of gitattributes says: "The rules how the pattern
    matches paths are the same as in .gitignore files" and the gitignore
    pattern matching has a pattern ending with / for directory matching.
    
    This rule is specifically relevant for the 'export-ignore' rule used
    for git archive.
    
    Signed-off-by: Jean-Noel Avila <jn.avila@free.fr>
    Signed-off-by: Junio C Hamano <gitster@pobox.com>

Regards

On Tue, Jan 15, 2013 at 5:38 AM, Ross Lagerwall <rosslagerwall@gmail.com> wrote:

Interesting. I see the regression on linux-2.6 too (0.6s real vs 0.9s).

Not the real contributor to the regression, but it should be noted that glibc's strrchr does not employ a typical loop. Instead it advances with strchr with a note that strchr is much faster. It looks like strchr compares a word at a time instead of a byte. We might want to do the same.

I don't have time to look into details now, but by enabling DEBUG_ATTR, it looks like this commit makes it push and pop patterns a lot more than without the commit.

On Tue, Jan 15, 2013 at 9:46 AM, Duy Nguyen <pclouds@gmail.com> wrote:

I think the culprit is at this chunk:

 static void prepare_attr_stack(const char *path)
 {
        struct attr_stack *elem, *info;
        int dirlen, len;
        const char *cp;

-       cp = strrchr(path, '/');
-       if (!cp)
-               dirlen = 0;
-       else
-               dirlen = cp - path;
+       dirlen = find_basename(path) - path;

dirlen is not expected to include the trailing slash, but find_basename() does that. It messes up with the path filters for push/pop in the next code. This brings grep performance closely back to before for me. Ross, can you check (patch could be whitespace damaged by gmail)?

-- 8< --

On Tue, Jan 15, 2013 at 11:38:32AM +0700, Duy Nguyen wrote:

Yes, that did seem to bring back the performance to the old level.

I noticed that before the patch, the strace output was something like this: open("tools/vm/.gitattributes", O_RDONLY) = -1 ENOENT open("tools/vm//.gitattributes", O_RDONLY) = -1 ENOENT open("tools/vm//.gitattributes", O_RDONLY) = -1 ENOENT open("tools/vm//.gitattributes", O_RDONLY) = -1 ENOENT open("usr/.gitattributes", O_RDONLY) = -1 ENOENT open("usr//.gitattributes", O_RDONLY) = -1 ENOENT open("usr//.gitattributes", O_RDONLY) = -1 ENOENT open("usr//.gitattributes", O_RDONLY) = -1 ENOENT open("usr//.gitattributes", O_RDONLY) = -1 ENOENT open("usr//.gitattributes", O_RDONLY) = -1 ENOENT

(and yes, the whitespace was damaged by Gmail!)

Regards

Ross Lagerwall <rosslagerwall@gmail.com> writes:

Hmph, that looks really bad, especially given that in the normal codepath like "git grep", we would never care about directories (the attributes are normally applied to real paths with contents, and the use by archive is an anomaly) and the implementation should be done in a way not to impose such excess and useless overhead.

We may end up reverting that patch for the time being X-<.

Jean-Noël, ideas?