To: "David Rowley" <dgrowley@gmail.com>
cc: "'Heikki Linnakangas'" <heikki.linnakangas@enterprisedb.com>,
	"'Peter Eisentraut'" <peter_e@gmx.net>, pgsql-hackers@postgresql.org
Subject: Re: [PATCHES] TODO item: Implement Boyer-Moore searching (First time
	hacker)
In-reply-to: <2B14F8402C8E4A3C9E240E3DAF31BA25@amd64> 
References: <2B14F8402C8E4A3C9E240E3DAF31BA25@amd64>
Comments: In-reply-to "David Rowley" <dgrowley@gmail.com>
	message dated "Sun, 07 Sep 2008 03:03:57 +0100"
Date: Sun, 07 Sep 2008 00:26:47 -0400
Message-ID: <6183.1220761607@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

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

			regards, tom lane