DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=from:to:cc:subject:date:message-id:mime-version:content-type
	:content-transfer-encoding:x-priority:x-msmail-priority:x-mailer
	:in-reply-to:x-mimeole:thread-index:importance;
	b=rU1csrIJpP7Cc6G8a91d60sDhPUS3f5rgBuCXjrgTbiYV44gJTklhSBFmTG7GQaa7a
	TtB8l3dEnHYJKtKv1zKJXNHMnKMXTSC/M9EcWPPamM2nHlqfdNoh6KdPR8n4ia5l3hNi
	3LCjeH8PLNG352ih2r+L94IZ6XrFdv1KMKAQ0=
From: "David Rowley" <dgrowley@gmail.com>
To: "'Tom Lane'" <tgl@sss.pgh.pa.us>,
	"'Heikki Linnakangas'" <heikki.linnakangas@enterprisedb.com>,
	"'Peter Eisentraut'" <peter_e@gmx.net>
Cc: <pgsql-hackers@postgresql.org>
Subject: Re: [PATCHES] TODO item: Implement Boyer-Moore searching (First time
	hacker)
Date: Sun, 7 Sep 2008 12:04:35 +0100
Message-ID: <E737D69A2FDE4F79832CDAF8FC6C1DEC@amd64>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="US-ASCII"
Content-Transfer-Encoding: 7bit
In-Reply-To: <6183.1220761607@sss.pgh.pa.us>
Thread-Index: AckQofJwzMQA26Q5ThOEBdVCZtdd0wANZp0g
Importance: Normal

Tom Lane Wrote:
> "David Rowley" <dgrowley@gmail.com> writes:
> > I've made the discussed changes. Also updated the benchmark results.
> > http://www.unixbeast.com/~fat/8.3_test_v1.3.xls

> Applied with revisions; mostly cosmetic except for one point.  I
> realized after studying the code a bit more that B-M cannot possibly win
> for a single-character pattern (needle), since the skip distance must
> always be 1 in that case.  The fact that it seemed to keep up at that
> length has to be because the original coding included a strncmp call
> inside the innermost loop, which likely prevents the compiler from
> optimizing that loop really tightly.  But the strncmp wasn't doing
> anything anyway for the case of pattern length = 1. So what I committed
> special-cases pattern length 1 to be a naive search with a *very* tight
> inner loop.  I think it's worth troubling over this case because a
> common usage is split_to_array and suchlike with single-character
> delimiters.

I had thought about this, but failed to think about string_to_array.
Probably worth the extra code for that.

Well simple enough patch. I've learned quite a bit about the postgresql
source even just for working in varlena.c. I've got a very long way to go
though.

Thanks for all the reviews and suggestions.

David.