[poppler] KMP for search

[Albert Astals Cid]

A Dimecres, 16 de juny de 2010, Johannes Buchner va escriure:
> 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, 

One of them being a mailing list (not this one, a different one) ;-)

> I thought it would be worth mentioning on the
> mailing list aswell.

Ok, no problemo.

> 
> > > [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.

Carlos do you feel like reviewing it? After all Okular is not using poppler 
search code so i think you have more at stake if that patch introduces a 
regression than me ;-)

Albert

> 
> > > 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.