From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <dgrowley@gmail.com>
Cc: 'Heikki Linnakangas' <heikki.linnakangas@enterprisedb.com>
Cc: '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, 07 Sep 2008 00:26:47 -0400
Message-ID: <6183.1220761607@sss.pgh.pa.us> (raw)
In-Reply-To: <2B14F8402C8E4A3C9E240E3DAF31BA25@amd64>
References: <2B14F8402C8E4A3C9E240E3DAF31BA25@amd64>
"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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-patches@postgresql.org
Cc: tgl@sss.pgh.pa.us, dgrowley@gmail.com, heikki.linnakangas@enterprisedb.com, peter_e@gmx.net, pgsql-hackers@postgresql.org
Subject: Re: [PATCHES] TODO item: Implement Boyer-Moore searching (First time hacker)
In-Reply-To: <6183.1220761607@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox