Received: from localhost (unknown [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 5725464FE0F for ; Tue, 2 Sep 2008 20:19:29 -0300 (ADT) Received: from postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 52584-03 for ; Tue, 2 Sep 2008 20:19:21 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from ug-out-1314.google.com (ug-out-1314.google.com [66.249.92.174]) by postgresql.org (Postfix) with ESMTP id 5775A64FCEA for ; Tue, 2 Sep 2008 20:19:25 -0300 (ADT) Received: by ug-out-1314.google.com with SMTP id 29so1876378ugo.7 for ; Tue, 02 Sep 2008 16:19:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:to:subject:date :message-id:mime-version:content-type:x-priority:x-msmail-priority :x-mailer:in-reply-to:thread-index:x-mimeole:importance; bh=F9pU9z2fLzgOdQgAMtXH+UQsT+HFc3f+s5in9PIXXKI=; b=hdWQhbpOU20U4v28BI5Cd9LaM+aKeJjpsGuOMAN2KyxtASgLq/Tf/poiXR8JTCK6YD NsNeqaTWZIrjzttLZLRljRiu5ymxj4gVTpyoKUQNCtH3bzs1sfso2EKakz2xygH1zIZe kEsLmL8RxyrsJwN59IC4XoClrPKVrvG3jtZDY= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:subject:date:message-id:mime-version:content-type :x-priority:x-msmail-priority:x-mailer:in-reply-to:thread-index :x-mimeole:importance; b=ZvGiQJJYLHBwDh9z2KMK6Nf0UnNpjKchQDU/5Z0ecX3+Q4SmoKhf+ZK/m0Fd1N7mqF 2KWdYYRKJYrYN8cVXvySKUegekTLGRf7ABEsx/9+bNFnq6rw43NkPoTZc5/VGPQZYN8o LBtXQWnoe5/IBD1vpR99IatmEIKSUohnPnVIo= Received: by 10.67.10.8 with SMTP id n8mr4507537ugi.23.1220397563286; Tue, 02 Sep 2008 16:19:23 -0700 (PDT) Received: from amd64 ( [83.104.138.235]) by mx.google.com with ESMTPS id 36sm5539156ugb.26.2008.09.02.16.19.21 (version=TLSv1/SSLv3 cipher=RC4-MD5); Tue, 02 Sep 2008 16:19:22 -0700 (PDT) From: "David Rowley" To: "'Peter Eisentraut'" , Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) Date: Wed, 3 Sep 2008 00:19:26 +0100 Message-ID: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_0035_01C90D5A.BE44FDE0" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.6838 In-Reply-To: <48BD2AA9.7070509@gmx.net> Thread-Index: AckM8sQycFhXLEnDRkW5vOjBKk8/kgAW8O8g X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5579 Importance: Normal X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.819 tagged_above=0 required=5 tests=MIME_QP_LONG_LINE=1.819 X-Spam-Level: * X-Archive-Number: 200809/29 X-Sequence-Number: 7044 This is a multi-part message in MIME format. ------=_NextPart_000_0035_01C90D5A.BE44FDE0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable I wrote:=20 > I look forward to receiving feedback on this. Peter Eisentraut wrote: > Please send a patch in diff -c format. And don't put a single patch=20 > file in a tar file. Thanks for the pointer. I'm quite new to this. I've done some more revisions to the patch. This has mostly just = involved tuning the skip table size based on the size of the search. This has basically involved lots of benchmarks with different strings and = calculating the best size of table to use. The reason for this is to maintain fast searches for smaller strings. The overhead of initialising a 256 element array would probably out weigh the cost of the search if this were not = done. The size of the skip table increases with longer strings, or rather the = size that is utilised. Performance: For smaller searches performance of the patch and existing version are = very similar. The patched version starts to out perform the existing version = when the needle and haystack become larger. The patch wins hands down with searches that leads the existing function = in to dead ends, for example: SELECT STRPOS('A AA AAA AAAA AAAAA AAAAAA AAAAAAA','AAAAAAA'); When searching for very small strings, say just a single character in a sentence the existing function marginally beats the patched version. Outside of Postgres I've done benchmarks where I've searched for every combination of the search string in the search string. Like: test | t | test | te | test | tes | test | test | test | e | test | es | test | est | test | s | test | st | test | t | I felt this was fair for both versions. The patched version beat the unpatched version. The test I carried out was a string of 934 = characters. I can upload more benchmarks if required. I'm quite happy with the patch now so I'm going to submit it (in diff -c format this time :) David. ------=_NextPart_000_0035_01C90D5A.BE44FDE0 Content-Type: application/octet-stream; name="boyer-moore_strpos_v1.1.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="boyer-moore_strpos_v1.1.patch" *** varlena.c 2008-09-02 23:45:48.000000000 +0100=0A= --- varlena.c 2008-09-02 23:38:15.000000000 +0100=0A= ***************=0A= *** 840,901 ****=0A= }=0A= }=0A= =0A= ! static int=0A= text_position_next(int start_pos, TextPositionState *state)=0A= {=0A= ! int pos =3D 0,=0A= ! p,=0A= ! px;=0A= =0A= Assert(start_pos > 0); /* else caller error */=0A= =0A= ! if (state->len2 <=3D 0)=0A= ! return start_pos; /* result for empty pattern */=0A= =0A= - if (!state->use_wchar)=0A= - {=0A= - /* simple case - single byte encoding */=0A= - char *p1 =3D state->str1;=0A= - char *p2 =3D state->str2;=0A= =0A= ! /* no use in searching str past point where search_str will fit */=0A= ! px =3D (state->len1 - state->len2);=0A= =0A= - p1 +=3D start_pos - 1;=0A= =0A= ! for (p =3D start_pos - 1; p <=3D px; p++)=0A= ! {=0A= ! if ((*p1 =3D=3D *p2) && (strncmp(p1, p2, state->len2) =3D=3D 0))=0A= ! {=0A= ! pos =3D p + 1;=0A= ! break;=0A= ! }=0A= ! p1++;=0A= ! }=0A= ! }=0A= ! else=0A= ! {=0A= ! /* not as simple - multibyte encoding */=0A= ! pg_wchar *p1 =3D state->wstr1;=0A= ! pg_wchar *p2 =3D state->wstr2;=0A= =0A= - /* no use in searching str past point where search_str will fit */=0A= - px =3D (state->len1 - state->len2);=0A= =0A= ! p1 +=3D start_pos - 1;=0A= =0A= ! for (p =3D start_pos - 1; p <=3D px; p++)=0A= ! {=0A= ! if ((*p1 =3D=3D *p2) && (pg_wchar_strncmp(p1, p2, state->len2) = =3D=3D 0))=0A= ! {=0A= ! pos =3D p + 1;=0A= ! break;=0A= ! }=0A= ! p1++;=0A= ! }=0A= ! }=0A= =0A= ! return pos;=0A= }=0A= =0A= static void=0A= --- 840,1027 ----=0A= }=0A= }=0A= =0A= ! /* text_position_next=0A= ! * David Rowley 2008-09-01=0A= ! * Uses Boyer-Moore searching=0A= ! */=0A= ! int=0A= text_position_next(int start_pos, TextPositionState *state)=0A= {=0A= ! =0A= ! int skiptable[256];=0A= ! int ai;=0A= ! int hashsize;=0A= ! =0A= ! /*=0A= ! * state->len2 =3D needle length in chars =0A= ! * state->len1 =3D haystack length in chars =0A= ! */=0A= =0A= Assert(start_pos > 0); /* else caller error */=0A= =0A= ! if (state->len2 <=3D 0)=0A= ! return start_pos; /* Empty needle, found it! */=0A= =0A= =0A= ! /* Changed for zero based arrays */=0A= ! start_pos--;=0A= =0A= =0A= ! /* Eliminate the impossible first, the needle is=0A= ! * too big for the haystack.=0A= ! */=0A= ! if (state->len1 + start_pos < state->len2)=0A= ! return 0;=0A= ! =0A= ! /* Here we must determine how much of the skip table we should use.=0A= ! * With haystack lengths of only a few characters we don't really = want=0A= ! * to have to initalize the full 256 elements of the table. Such an=0A= ! * initialization would take too long in comparison to the rest of = the=0A= ! * search time.=0A= ! * To get around this problem when searching for smaller strings we = only=0A= ! * use part of the skiptable, the larger the search (or at least the = longer=0A= ! * we estimate that it will take) the more we use of the skip table.=0A= ! *=0A= ! * After quite a few benchmarks a rule of thumb seems to show that = the=0A= ! * best skip table size is around 10 times less than the length of = the=0A= ! * haystack. Of course this is not an exact science. The needle = length=0A= ! * counts and also the mix of characters in both the needle and the = haystack.=0A= ! * It might look like a good idea to make the skip table around the = same size=0A= ! * as the needle, however that likely means more collisions or = possibly no =0A= ! * empty positions in the table. That would mean we'd never be able = to=0A= ! * skip the length of the needle.=0A= ! * =0A= ! * We skiptable[ & hashsize] to tell us how many = characters=0A= ! * we should skip ahead in the haystack when we don't find a match.=0A= ! * It does not matter that it's a lossy hash check as we're = re-checking the=0A= ! * actual character value again once the loop reiterates.=0A= ! *=0A= ! * The above method works both for char and pg_wchar. Perhaps with = UTF8=0A= ! * the character mix will be greater.=0A= ! *=0A= ! * The following code calculates the hashsize. Notice that for small =0A= ! * searches we're bearly using any of the skiptable. We also allocate=0A= ! * the hash size to smaller searches first to allow them to get on =0A= ! * searching...=0A= ! *=0A= ! */=0A= ! =0A= ! if ((state->len2 - start_pos) < 16)=0A= ! hashsize =3D 3;=0A= ! else if ((state->len2 - start_pos) < 64)=0A= ! hashsize =3D 7;=0A= ! else if ((state->len2 - start_pos) < 128)=0A= ! hashsize =3D 15;=0A= ! else if ((state->len2 - start_pos) < 512)=0A= ! hashsize =3D 31;=0A= ! else if ((state->len2 - start_pos) < 2048)=0A= ! hashsize =3D 63;=0A= ! else if ((state->len2 - start_pos) < 4096)=0A= ! hashsize =3D 127;=0A= ! else=0A= ! hashsize =3D 255;=0A= ! =0A= ! =0A= ! /* Initalize the skip table. We set all elements to the needle = length */=0A= ! for (ai =3D 0; ai <=3D hashsize; ai++)=0A= ! skiptable[ai] =3D state->len2;=0A= =0A= =0A= ! if (!state->use_wchar)=0A= ! {=0A= ! char *nptr;=0A= ! char *hptr;=0A= ! char *p;=0A= ! char *needle =3D state->str2;=0A= ! char *haystack =3D state->str1;=0A= ! =0A= ! /* Here we process the needle marking the last occurence=0A= ! * of each character (ignoring the very last character)=0A= ! */=0A= ! for (ai =3D 0; ai < state->len2 - 1; ai++)=0A= ! skiptable[(unsigned char) needle[ai] & hashsize] =3D state->len2 = - ai - 1;=0A= ! =0A= ! =0A= ! /* Start at startpos plus the length of the needle */=0A= ! hptr =3D &haystack[state->len2 - 1 + start_pos];=0A= ! =0A= ! while (hptr < &haystack[state->len1]) =0A= ! {=0A= ! nptr =3D &needle[state->len2 - 1]; /* Point to the end of the = needle */=0A= ! p =3D hptr;=0A= ! =0A= ! while (*nptr =3D=3D *p) =0A= ! {=0A= ! /* Do we have it? Return 1 based array pos */=0A= ! if (nptr-- =3D=3D needle) =0A= ! return p - haystack + 1; =0A= ! =0A= ! p--;=0A= ! }=0A= ! =0A= ! /* Ask the skiptable where to look next. If it=0A= ! * finds a match then we align the two ~matching~=0A= ! * characters and start another search there.=0A= ! * Else we skip a whole needle length.=0A= ! * Of course the ~matching~ characters only have the=0A= ! * same hash value, the character value may be different.=0A= ! */=0A= ! =0A= ! hptr +=3D skiptable[(unsigned char) *hptr & hashsize];=0A= ! }=0A= ! =0A= ! return 0; /* Not found */=0A= ! =0A= ! } =0A= ! =0A= ! else=0A= ! { =0A= ! /* The multibyte char version. This works exactly the same way.=0A= ! */=0A= ! pg_wchar *nptr;=0A= ! pg_wchar *hptr;=0A= ! pg_wchar *p;=0A= ! pg_wchar *needle =3D state->wstr2;=0A= ! pg_wchar *haystack =3D state->wstr1;=0A= ! =0A= ! /* Here we process the needle marking the last occurence=0A= ! * of each character (ignoring the very last character)=0A= ! */=0A= ! for (ai =3D 0; ai < state->len2 - 1; ai++)=0A= ! skiptable[needle[ai] & hashsize] =3D state->len2 - ai - 1;=0A= ! =0A= ! =0A= ! /* Start at start_pos plus the length of the needle */=0A= ! hptr =3D &haystack[state->len2 - 1 + start_pos];=0A= ! =0A= ! while (hptr < &haystack[state->len1]) =0A= ! {=0A= ! nptr =3D &needle[state->len2 - 1]; /* Point to the end of the = needle */=0A= ! p =3D hptr;=0A= ! =0A= ! while (*nptr =3D=3D *p) =0A= ! {=0A= ! =0A= ! /* Do we have it? Return 1 based array pos */=0A= ! if (nptr-- =3D=3D needle) =0A= ! return p - haystack + 1; =0A= ! =0A= ! p--;=0A= ! }=0A= ! =0A= ! /* Ask the skiptable where to look next. If it=0A= ! * finds a match then we align the two ~matching~=0A= ! * characters and start another search there.=0A= ! * Else we skip a whole needle length.=0A= ! * Of course the ~matching~ characters only have the=0A= ! * same hash value, the character value may be different.=0A= ! */=0A= =0A= ! hptr +=3D skiptable[*hptr & hashsize];=0A= ! }=0A= =0A= ! return 0; /* Not found */=0A= ! }=0A= }=0A= =0A= static void=0A= ------=_NextPart_000_0035_01C90D5A.BE44FDE0--