From: David Rowley <dgrowley@gmail.com>
To: 'Tom Lane' <tgl@sss.pgh.pa.us>
To: 'Heikki Linnakangas' <heikki.linnakangas@enterprisedb.com>
Cc: 'Peter Eisentraut' <peter_e@gmx.net>
Cc: pgsql-patches@postgresql.org
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Date: Fri, 5 Sep 2008 21:13:58 +0100
Message-ID: <C848A7ECB1E346388B9BD7F7966C0DDC@amd64> (raw)
In-Reply-To: <11787.1220580297@sss.pgh.pa.us>
Heikki Linnakangas wrote:
> The skip table really should be constructed only once in
> text_position_start and stored in TextPositionState. That would make a
> big difference to the performance of those functions that call
> text_position_next repeatedly: replace_text, split_text and text_to_array.
I Wrote:
> Of course you are right. That will help for replace and the like. I'll
> update the patch tonight.
I've made and attached the changes Heikki recommended.
Also updated benchmark spreadsheet. Here ->
http://www.unixbeast.com/~fat/8.3_test_v1.2.xls
Previously there was an error with "Test 6", the test that benchmarked
replace(). I kept this one so not to affect the summary result in the new
sheet. I then added the sheet "Replace Test" to show more accurate results.
I had failed to notice that the optimizer was helping me out more than I
wanted it to.
My tested replace() script runs in 91% of the time than the 8.3 version.
I've not tested with the CVS head.
Now that the skip table is a member of TextPositionState, I was not quite
sure if I should #define a size for it. It would certainly look neater, only
the code that defines the skip table size in text_position_start assumes 256
elements.
Any thoughts on this?
David.
Attachments:boyer-moore-strpos_v1.2.patch (application/octet-stream, 9.0K) download
*** varlena.c 2008-08-31 20:31:56.000000000 +0100
--- varlena.c 2008-09-05 19:41:04.000000000 +0100
***************
*** 40,45 ****
--- 40,48 ----
pg_wchar *wstr2; /* note: these are palloc'd */
int len1; /* string lengths in logical characters */
int len2;
+ int skiptable[256]; /* For boyer-moore searching */+ int skiptablesize; /* How much of the skiptable do we utilize */+
} TextPositionState;
#define DatumGetUnknownP(X) ((unknown *) PG_DETOAST_DATUM(X))
***************
*** 804,816 ****
* called multiple times with increasing values of start_pos, which is
* the 1-based character position to start the search from. The "state"
* variable is normally just a local variable in the caller.
*/
-
static void
text_position_setup(text *t1, text *t2, TextPositionState *state)
{
int len1 = VARSIZE_ANY_EXHDR(t1);
int len2 = VARSIZE_ANY_EXHDR(t2);
if (pg_database_encoding_max_length() == 1)
{
--- 807,821 ----
* called multiple times with increasing values of start_pos, which is
* the 1-based character position to start the search from. The "state"
* variable is normally just a local variable in the caller.
+ *+ * David Rowley: 2008-09-04 -- Updated for Boyer-Moore searching
*/
static void
text_position_setup(text *t1, text *t2, TextPositionState *state)
{
int len1 = VARSIZE_ANY_EXHDR(t1);
int len2 = VARSIZE_ANY_EXHDR(t2);
+ int ai;
if (pg_database_encoding_max_length() == 1)
{
***************
*** 820,825 ****
--- 825,880 ----
state->str2 = VARDATA_ANY(t2);
state->len1 = len1;
state->len2 = len2;
+ + /* Here we must determine how much of the skip table we should use.+ * With haystack lengths of only a few characters we don't really want+ * to have to initalize the full 256 elements of the table. Such an+ * initialization would take too long in comparison to the rest of the+ * search time.+ * To get around this problem when searching for smaller strings we only+ * use part of the skiptable, the larger the search (or at least the longer+ * we estimate that it will take) the more we use of the skip table.+ *+ * After quite a few benchmarks a rule of thumb seems to show that the+ * best skip table size is around 10 times less than the length of the+ * haystack. Of course this is not an exact science. The needle length+ * counts and also the mix of characters in both the needle and the haystack.+ * It might look like a good idea to make the skip table around the same size+ * as the needle, however that likely means more collisions or possibly no + * empty positions in the table. That would mean we'd never be able to+ * skip the length of the needle.+ * + * The following code calculates the skip table's size. Notice that for small + * searches we're bearly using any of the skiptable. + *+ */+ + if (state->len2 < 16)+ state->skiptablesize = 3;+ else if (state->len2 < 64)+ state->skiptablesize = 7;+ else if (state->len2 < 128)+ state->skiptablesize = 15;+ else if (state->len2 < 512)+ state->skiptablesize = 31;+ else if (state->len2 < 2048)+ state->skiptablesize = 63;+ else if (state->len2 < 4096)+ state->skiptablesize = 127;+ else+ state->skiptablesize = 255;+ + /* Initalize the skip table. We set all elements to the needle length */+ for (ai = 0; ai <= state->skiptablesize; ai++)+ state->skiptable[ai] = state->len2;+ + /* Here we process the needle marking the last occurence+ * of each character (ignoring the very last character)+ */+ for (ai = 0; ai < state->len2 - 1; ai++)+ state->skiptable[(unsigned char) state->str2[ai] & state->skiptablesize] = state->len2 - ai - 1;+ +
}
else
{
***************
*** 837,903 ****
state->wstr2 = p2;
state->len1 = len1;
state->len2 = len2;
}
}
! static int
text_position_next(int start_pos, TextPositionState *state)
{
! int pos = 0,
! p,
! px;
Assert(start_pos > 0); /* else caller error */
- if (state->len2 <= 0)- return start_pos; /* result for empty pattern */
! if (!state->use_wchar)
! {
! /* simple case - single byte encoding */
! char *p1 = state->str1;
! char *p2 = state->str2;
- /* no use in searching str past point where search_str will fit */- px = (state->len1 - state->len2);
! p1 += start_pos - 1;
- for (p = start_pos - 1; p <= px; p++)- {- if ((*p1 == *p2) && (strncmp(p1, p2, state->len2) == 0))- {- pos = p + 1;- break;- }- p1++;- }- }- else- {- /* not as simple - multibyte encoding */- pg_wchar *p1 = state->wstr1;- pg_wchar *p2 = state->wstr2;
! /* no use in searching str past point where search_str will fit */
! px = (state->len1 - state->len2);
- p1 += start_pos - 1;
! for (p = start_pos - 1; p <= px; p++)
! {
! if ((*p1 == *p2) && (pg_wchar_strncmp(p1, p2, state->len2) == 0))
! {
! pos = p + 1;
! break;
! }
! p1++;
! }
! }
! return pos;
}
static void
text_position_cleanup(TextPositionState *state)
{
--- 892,1043 ----
state->wstr2 = p2;
state->len1 = len1;
state->len2 = len2;
+ + + if (state->len2 < 16)+ state->skiptablesize = 3;+ else if (state->len2 < 64)+ state->skiptablesize = 7;+ else if (state->len2 < 128)+ state->skiptablesize = 15;+ else if (state->len2 < 512)+ state->skiptablesize = 31;+ else if (state->len2 < 2048)+ state->skiptablesize = 63;+ else if (state->len2 < 4096)+ state->skiptablesize = 127;+ else+ state->skiptablesize = 255;+ + /* Initalize the skip table. We set all elements to the needle length */+ for (ai = 0; ai <= state->skiptablesize; ai++)+ state->skiptable[ai] = state->len2;+ + /* Here we process the needle marking the last occurence+ * of each character (ignoring the very last character)+ */+ for (ai = 0; ai < state->len2 - 1; ai++)+ state->skiptable[state->wstr2[ai] & state->skiptablesize] = state->len2 - ai - 1;+
}
}
! /* text_position_next
! * David Rowley 2008-09-05
! * Uses Boyer-Moore searching
! */
! int
text_position_next(int start_pos, TextPositionState *state)
{
! /*
! * state->len2 = needle length in chars
! * state->len1 = haystack length in chars
! */
Assert(start_pos > 0); /* else caller error */
! if (state->len2 <= 0)
! return start_pos; /* Empty needle, found it! */
! /* Changed for zero based arrays */
! start_pos--;
! /* Eliminate the impossible first, the needle is
! * too big for the haystack.
! */
! if (state->len1 + start_pos < state->len2)
! return 0;
! if (!state->use_wchar)
! {
! char *nptr;
! char *hptr;
! char *p;
! char *needle = state->str2;
! char *haystack = state->str1;
!
!
! /* Start at startpos plus the length of the needle */
! hptr = &haystack[state->len2 - 1 + start_pos];
!
! while (hptr < &haystack[state->len1])
! {
! nptr = &needle[state->len2 - 1]; /* Point to the end of the needle */
! p = hptr;
!
! while (*nptr == *p)
! {
! /* Do we have it? Return 1 based array pos */
! if (nptr-- == needle)
! return p - haystack + 1;
!
! p--;
! }
!
! /* Ask the skiptable where to look next. If it
! * finds a match then we align the two ~matching~
! * characters and start another search there.
! * Else we skip a whole needle length.
! * Of course the ~matching~ characters only have the
! * same hash value, the character value may be different.
! */
!
! hptr += state->skiptable[(unsigned char) *hptr & state->skiptablesize];
! }
!
! return 0; /* Not found */
!
! }
!
! else
! {
! /* The multibyte char version. This works exactly the same way.
! */
! pg_wchar *nptr;
! pg_wchar *hptr;
! pg_wchar *p;
! pg_wchar *needle = state->wstr2;
! pg_wchar *haystack = state->wstr1;
!
!
! /* Start at start_pos plus the length of the needle */
! hptr = &haystack[state->len2 - 1 + start_pos];
!
! while (hptr < &haystack[state->len1])
! {
! nptr = &needle[state->len2 - 1]; /* Point to the end of the needle */
! p = hptr;
!
! while (*nptr == *p)
! {
! /* Do we have it? Return 1 based array pos */
! if (nptr-- == needle)
! return p - haystack + 1;
!
! p--;
! }
!
! /* Ask the skiptable where to look next. If it
! * finds a match then we align the two ~matching~
! * characters and start another search there.
! * Else we skip a whole needle length.
! * Of course the ~matching~ characters only have the
! * same hash value, the character value may be different.
! */
!
! hptr += state->skiptable[*hptr & state->skiptablesize];
! }
! return 0; /* Not found */
! }
}
+ +
static void
text_position_cleanup(TextPositionState *state)
{
=
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: dgrowley@gmail.com, tgl@sss.pgh.pa.us, heikki.linnakangas@enterprisedb.com, peter_e@gmx.net
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
In-Reply-To: <C848A7ECB1E346388B9BD7F7966C0DDC@amd64>
* 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