From: Fredrik Kuivinen <frekui@gmail.com>
Date: Sun, 14 Feb 2010 16:51:19 GMT
Subject: Re: [PATCH 5/5] Use kwset in grep
Message-ID: <4c8ef71002140851hff65a2bj7cc31c634ce5bab3@mail.gmail.com>
In-Reply-To: <4B76E384.2070602@gnu.org>

On Sat, Feb 13, 2010 at 18:38, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 02/13/2010 03:21 PM, Fredrik Kuivinen wrote:
>>
>> 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...

Another approach is to just create a single kwset for this case as
well. I will try that in the next iteration.

- Fredrik