From: "René Scharfe" <rene.scharfe@lsrfire.ath.cx>
To: Junio C Hamano <gitster@pobox.com>
Cc: git@vger.kernel.org
Subject: Re: [PATCH 3/4] diffcore-pickaxe: further refactor count_match()
Date: Sat, 28 Feb 2009 19:15:46 +0100 [thread overview]
Message-ID: <49A97F52.4080405@lsrfire.ath.cx> (raw)
In-Reply-To: <7vmyc6foj3.fsf@gitster.siamese.dyndns.org>
Junio C Hamano schrieb:
> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
>
>> I get this (Ubuntu 8.10 x64, Fedora 10 x64 using the same Linux repo,
>> Windows Vista x64 using a different Linux repo with the same HEAD on
>> NTFS and msysgit, numbers are the elapsed time in seconds, best of five
>> runs):
>>
>> Ubuntu Fedora Windows
>> v1.6.2-rc2 8.14 8.16 9.236
>> v1.6.2-rc2+[1-4] 2.43 2.45 2.995
>> v1.6.2-rc2+[1-4]+memmem 1.31 1.25 2.917
>> v1.6.2-rc2+[1-3]+memmem 1.51 1.16 8.455
>>
>> Ubuntu has glibc 2.8, while Fedora 10 has glibc 2.9, with a new and more
>> efficient memmem() implementation. On Windows, we use our own naive
>> memmem() implementation.
>
> Yeah, what does glibc use these days? Some variant of Boyer-Moore?
No, the algorithm is called Two Way, which, unlike Boyer-Moore, only
needs constant space. The implementation seems to originate from this bug:
http://sourceware.org/bugzilla/show_bug.cgi?id=5514
And the algorithm is documented here:
http://www-igm.univ-mlv.fr/~lecroq/string/node26.html
René
next prev parent reply other threads:[~2009-02-28 18:17 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-02-26 6:52 [PATCH 0/4] Pickaxe search clean-up and optimization Junio C Hamano
2009-02-26 6:52 ` [PATCH 1/4] diffcore-pickaxe: refactor diffcore_pickaxe() Junio C Hamano
2009-02-27 23:58 ` René Scharfe
2009-02-26 6:52 ` [PATCH 2/4] diffcore-pickaxe: micro-optimize has_match() function Junio C Hamano
2009-02-26 6:52 ` [PATCH 3/4] diffcore-pickaxe: further refactor count_match() Junio C Hamano
2009-02-26 7:23 ` Kjetil Barvik
2009-02-28 1:13 ` René Scharfe
2009-02-28 1:25 ` Junio C Hamano
2009-02-28 6:08 ` Junio C Hamano
2009-02-28 13:10 ` René Scharfe
2009-02-28 17:40 ` Junio C Hamano
2009-02-28 18:15 ` René Scharfe [this message]
2009-02-28 19:16 ` [PATCH] import memmem() with linear complexity from Gnulib René Scharfe
2009-02-28 22:44 ` Mike Hommey
2009-03-01 3:41 ` Jeff King
2009-03-01 11:15 ` René Scharfe
2009-03-01 18:55 ` René Scharfe
2009-03-01 7:31 ` [PATCH 3/4] diffcore-pickaxe: further refactor count_match() Junio C Hamano
2009-03-01 10:53 ` René Scharfe
2009-02-26 6:52 ` [PATCH 4/4] diffcore-pickaxe: optimize by trimming common initial and trailing parts Junio C Hamano
2009-02-26 9:05 ` Junio C Hamano
2009-03-02 23:00 ` [PATCH 1/2] diffcore-pickaxe: use memmem() René Scharfe
2009-03-02 23:19 ` [PATCH 2/2] optimize compat/ memmem() René Scharfe
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=49A97F52.4080405@lsrfire.ath.cx \
--to=rene.scharfe@lsrfire.ath.cx \
--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.