[poppler] KMP for search
Albert Astals Cid
aacid at kde.org
Wed Jun 16 16:00:38 PDT 2010
A Dimecres, 16 de juny de 2010, Johannes Buchner va escriure:
> On Tue, 15 Jun 2010 19:05:25 +0100
> Albert Astals Cid <aacid at kde.org> wrote:
> > > I implemented the KMP search algorithm in  but I feel it doesn't
> > > get attention. Please apply  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.
> > >  https://bugs.freedesktop.org/show_bug.cgi?id=8821
> > >  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  is small (~10
> lines changed plus two new functions), although the additional
> indentation level makes it look bigger.
> 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 ;-)
> > > 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.
More information about the poppler