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

Previous Next

Full log

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

From: zimoun <zimon.toutoune <at> gmail.com>
To: Arun Isaac <arunisaac <at> systemreboot.net>, 39258 <at> debbugs.gnu.org, 
 Ludovic Courtès <ludo <at> gnu.org>
Subject: KMP string search algorithm?
Date: Mon, 1 Jun 2020 12:11:52 +0200

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

Previous Next

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