Skip site navigation (1) Skip section navigation (2)

Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)

From: "David Rowley" <dgrowley(at)gmail(dot)com>
To: "'Tom Lane'" <tgl(at)sss(dot)pgh(dot)pa(dot)us>,"'Heikki Linnakangas'" <heikki(dot)linnakangas(at)enterprisedb(dot)com>
Cc: "'Peter Eisentraut'" <peter_e(at)gmx(dot)net>,<pgsql-patches(at)postgresql(dot)org>
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Date: 2008-09-05 20:13:58
Message-ID: C848A7ECB1E346388B9BD7F7966C0DDC@amd64 (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-patches
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.

Attachment: boyer-moore-strpos_v1.2.patch
Description: application/octet-stream (9.0 KB)

In response to

Responses

pgsql-hackers by date

Next:From: Alvaro HerreraDate: 2008-09-05 20:15:04
Subject: Re: [PATCHES] libpq events patch (with sgml docs)
Previous:From: Andrew ChernowDate: 2008-09-05 20:08:07
Subject: Re: [PATCHES] libpq events patch (with sgml docs)

pgsql-patches by date

Next:From: Alvaro HerreraDate: 2008-09-05 20:15:04
Subject: Re: [PATCHES] libpq events patch (with sgml docs)
Previous:From: Andrew ChernowDate: 2008-09-05 20:08:07
Subject: Re: [PATCHES] libpq events patch (with sgml docs)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group