[poppler] KMP for search

[Johannes Buchner]

Hi

On Tue, 15 Jun 2010 19:05:25 +0100
Albert Astals Cid <aacid at kde.org> wrote:

> > I implemented the KMP search algorithm in [1] but I feel it doesn't
> > get attention. Please apply [2] and test it.
> 
> You sent a mail yesterday and already complain you are being ignored?

No, I added the patch the day before, and since only 3 adresses are
notified about it, I thought it would be worth mentioning on the
mailing list aswell.

> > [1] https://bugs.freedesktop.org/show_bug.cgi?id=8821
> > [2] https://bugs.freedesktop.org/attachment.cgi?id=36255
> > 
> > To be honest, the gain is small; 
> 
> If the gain is small i'd prefer to stay with our tested code than to
> switch to something totally new.

I understand where you're coming from; I've seen a improvement of factor
3 for certain cases, and I've never seen a lower speed compared to the
naive implementation. It shows that the factors of O(n*m) are comparable
to the factors of the new O(n). So it has a gain. 
I tested the KMP code with several instances before integrating it into
poppler, and afterwards using the glib-demo program. The code is not
"totally new" in the sense that KMP is old, and I kept to
implementations I found on the web. The change [1] is small (~10
lines changed plus two new functions), although the additional
indentation level makes it look bigger.
https://bugs.freedesktop.org/review?bug=8821&attachment=36292

So, yes, I think it should go in.

> > I find it odd that the search
> > function is page-based and runs per block (sorry, I'm new to
> > poppler). It strikes me that no wrapped words can ever be found.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/poppler/attachments/20100616/0ec58f4d/attachment.pgp>