All of lore.kernel.org
 help / color / mirror / Atom feed
From: Paolo Bonzini <bonzini@gnu.org>
To: Fredrik Kuivinen <frekui@gmail.com>
Cc: git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH 5/5] Use kwset in grep
Date: Sat, 13 Feb 2010 18:38:12 +0100	[thread overview]
Message-ID: <4B76E384.2070602@gnu.org> (raw)
In-Reply-To: <20100213142110.GF9543@fredrik-laptop>

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...

Paolo

  parent reply	other threads:[~2010-02-13 17:38 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <20100213141558.22851.13660.stgit@fredrik-laptop>
2010-02-13 14:20 ` [PATCH 1/5] Add obstack.[ch] from EGLIBC 2.10 Fredrik Kuivinen
2010-02-13 14:20 ` [PATCH 2/5] Add string search routines from GNU grep Fredrik Kuivinen
2010-02-13 15:49   ` Dmitry Potapov
2010-02-13 15:56   ` Paolo Bonzini
2010-02-14 16:52     ` Fredrik Kuivinen
2010-02-13 14:20 ` [PATCH 3/5] Adapt the kwset code to Git Fredrik Kuivinen
2010-02-13 14:21 ` [PATCH 4/5] Use kwset in pickaxe Fredrik Kuivinen
2010-02-13 14:21 ` [PATCH 5/5] Use kwset in grep Fredrik Kuivinen
2010-02-13 15:58   ` Paolo Bonzini
2010-02-13 17:38   ` Paolo Bonzini [this message]
2010-02-14 16:51     ` Fredrik Kuivinen

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=4B76E384.2070602@gnu.org \
    --to=bonzini@gnu.org \
    --cc=frekui@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.