GNU bug report logs - #39258
Faster guix search using an sqlite cache

Previous Next

Full log

Message #319 received at 39258 <at> debbugs.gnu.org (full text, mbox):

From: Leo Famulari <leo <at> famulari.name>
To: zimoun <zimon.toutoune <at> gmail.com>
Cc: Arun Isaac <arunisaac <at> systemreboot.net>,
 Ludovic Courtès <ludo <at> gnu.org>, 39258 <at> debbugs.gnu.org
Subject: Re: [bug#39258] KMP string search algorithm?
Date: Mon, 1 Jun 2020 18:24:14 -0400

On Mon, Jun 01, 2020 at 12:11:52PM +0200, zimoun wrote:
> Dear,
> 
> > > Often our search strings are only literal strings. So, we can save some time
> > > by using string-contains instead of invoking the regexp engine. Patch 2 does
> > > this. In addition, guile's string-contains uses a naive O(n^2) string search
> > > algorithm. We should perhaps use the O(n) Knuth-Morris-Pratt algorithm[1]. In
> > > fact, a comment on line 2006 of libguile/srfi-13.c in the guile source code
> > > mentions this. If implemented, the KMP algorithm could speed up guix search
> > > further.
> > >
> > > [1]: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
> 
> It could improve.
> Well, I will try to do some back-to-envelop computations because I am
> not convinced that the mean value of 'n' (length of description,
> isn't) is large enough to really see an improvement for the end-user;
> the visible bottleneck is I/O.
> 
> All the best,
> simon
> 
> ps;
> To be honest, I thought this kind of algorithm was the default. :-)

I also recommend taking a look at the Boyer Moore string search
implementation in (guix build grafts).

It would be great to generalize it and make it accessible to other parts
of Guix.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.