Re: [PATCH] grep: do not do external grep on skip-worktree entries

Jeff King [off-list ref] writes:

I have to wonder, though...did anybody ever actually profile our
internal grep to find out _why_ it was so much slower than GNU grep?

I vaguely recall that somebody fairly competent mentioned that modern grep
implementations are based on DFA engines, but I offhand don't remember if
the discussion had concrete numbers.

Could we simply ship a better grep engine and obsolete external grep?

Yes, that is a very constructive longer term solution.

On Sun, Jan 03, 2010 at 11:08:46PM -0800, Junio C Hamano wrote:

quoted

I have to wonder, though...did anybody ever actually profile our
internal grep to find out _why_ it was so much slower than GNU grep?

I vaguely recall that somebody fairly competent mentioned that modern grep
implementations are based on DFA engines, but I offhand don't remember if
the discussion had concrete numbers.

Probably this:

  http://article.gmane.org/gmane.comp.version-control.git/41685

Also of interest is:

  http://article.gmane.org/gmane.comp.version-control.git/50174

The pcre analysis there came from just using the "pcreposix" header, I
think. From my limited research, modern pcre may have some tuning
options (including a DFA engine!) that could do a lot better.

-Peff

On Mon, Jan 04, 2010 at 02:26:59AM -0500, Jeff King wrote:

The pcre analysis there came from just using the "pcreposix" header, I
think. From my limited research, modern pcre may have some tuning
options (including a DFA engine!) that could do a lot better.

Hmm. I was able to get some improvements by using pcre_dfa_exec, but
still not as good as external grep. For "git grep 'foo.*bar'" in the
linux-2.6 repo, I got:

  external grep: 0.76s
  pcre_dfa_exec: 1.85s
      pcre_exec: 3.21s
          glibc: 4.00s

However, gprof reports that for the pcre dfa case, we spend more time in
grep.c:end_of_line than we do actually running the regex. So clearly
there are some other micro-optimizations in GNU grep that are making a
difference, too.

By the way, you can see the abysmal performance of our internal code by
doing a "git grep foo". It uses the "fixed" internal engine and weighs
in at 3.24s on the same machine, _slower_ than pcre doing an actual
regex.

-Peff

On Mon, 4 Jan 2010, Jeff King wrote:

However, gprof reports that for the pcre dfa case, we spend more time in
grep.c:end_of_line than we do actually running the regex. So clearly
there are some other micro-optimizations in GNU grep that are making a
difference, too.

Don't use gprof. You're _much_ better off using the newish Linux 'perf' 
tool. It's quite competent, and doesn't need the code to be compiled with 
-pg (which totally changes all performance characteristics).

Do something like this:

	perf record git grep qwerty

followed by

	perf report
	perf annotate grep_buffer_1

(that "perf report" gives a per-symbol overview, the "perf annotate" gives 
a disassembly with source annotations and per-instruction costs). It works 
with inlining too, so you get things like this:

	...
         :      static char *end_of_line(char *cp, unsigned long *left)
         :      {
         :              unsigned long l = *left;
         :              while (l && *cp != '\n') {
   24.76 :        476a50:       80 3b 0a                cmpb   $0xa,(%rbx)
   10.46 :        476a53:       0f 84 e7 00 00 00       je     476b40 <grep_buffer_1+0x1b0>
         :                      l--;
         :                      cp++;
   21.19 :        476a59:       48 83 c3 01             add    $0x1,%rbx
         :      }
         :
         :      static char *end_of_line(char *cp, unsigned long *left)
         :      {
         :              unsigned long l = *left;
         :              while (l && *cp != '\n') {
    0.94 :        476a5d:       49 83 ed 01             sub    $0x1,%r13
    4.85 :        476a61:       75 ed                   jne    476a50 <grep_buffer_1+0xc0>
         :
	...

and yes, it's all the per-line crap.

The perf tools are included with modern kernels in tools/perf (which also 
has a Documentation subdirectory). I can pretty much guarantee that once 
you start using it, you'll never use gprof or oprofile again.

		Linus