Re: [PATCH 5/5] Use kwset in grep

From: Paolo Bonzini <bonzini@gnu.org>
Date: Feb 13, 2010, 17:38 UTC
Message-ID: <4B76E384.2070602@gnu.org>
In-Reply-To: <20100213142110.GF9543@fredrik-laptop>

On 02/13/2010 03:21 PM, Fredrik Kuivinen wrote:

Show 22 quoted lines

> Best of five runs in the linux repository:
>
> before:
>
> $ time git grep qwerty
> drivers/char/keyboard.c:        "qwertyuiop[]\r\000as"                          /* 0x10 - 0x1f */
>
> real	0m1.065s
> user	0m1.400s
> sys	0m0.536s
>
>
> after:
>
> $ time git grep qwerty
> drivers/char/keyboard.c:        "qwertyuiop[]\r\000as"                          /* 0x10 - 0x1f */
>
> real	0m0.621s
> user	0m0.560s
> sys	0m0.564s
>
> So we gain about 40% by using the kwset code.

Hmm, on a more accurate review for

     git grep -e foo -e bar

you're creating two kwsets, so a Boyer-Moore search be much simpler---the performance would be the same since that's what kwset degrades to for a single string, but you'd probably save around 600 lines of code...

Paolo