[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug#39258] [PATCH 0/4] Optimize guix search
From: |
Arun Isaac |
Subject: |
[bug#39258] [PATCH 0/4] Optimize guix search |
Date: |
Mon, 1 Jun 2020 05:30:26 +0530 |
Hi,
Sorry for the long delay in replying to this thread.
I think Ludo is right in that we can improve guix search performance with only
simple code improvements rather than including xapian or improving our
existing cache. Here are a few patches on those lines.
In `relevance`, we set our score to 0 if any of the regexps don't match. Then,
we might as well not match the remaining regexps. Patch 1 does this early cut
off optimization.
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
Patch 3 and 4 are minor improvements.
Here's a rough performance comparison.
--8<---------------cut here---------------start------------->8---
time ./pre-inst-env guix search game
real 0m2.261s
user 0m2.351s
sys 0m0.104s
--8<---------------cut here---------------end--------------->8---
--8<---------------cut here---------------start------------->8---
time guix search game
real 0m2.661s
user 0m2.843s
sys 0m0.080s
--8<---------------cut here---------------end--------------->8---
--8<---------------cut here---------------start------------->8---
time ./pre-inst-env guix search strategy game
real 0m1.613s
user 0m1.635s
sys 0m0.096s
--8<---------------cut here---------------end--------------->8---
--8<---------------cut here---------------start------------->8---
time guix search strategy game
real 0m2.520s
user 0m2.583s
sys 0m0.112s
--8<---------------cut here---------------end--------------->8---
Arun Isaac (4):
ui: Cut off search early if any regexp does not match.
ui: Use string matching with literal search strings.
ui: Do not translate package synopsis a second time.
ui: Use package-description-string.
guix/scripts/package.scm | 12 +++++--
guix/ui.scm | 68 ++++++++++++++++++++++++----------------
2 files changed, 50 insertions(+), 30 deletions(-)
--
2.26.2
- [bug#39258] [PATCH 0/4] Optimize guix search,
Arun Isaac <=
- [bug#39258] [PATCH 1/4] ui: Cut off search early if any regexp does not match., Arun Isaac, 2020/05/31
- [bug#39258] [PATCH 4/4] ui: Use package-description-string., Arun Isaac, 2020/05/31
- [bug#39258] [PATCH 3/4] ui: Do not translate package synopsis a second time., Arun Isaac, 2020/05/31
- [bug#39258] [PATCH 2/4] ui: Use string matching with literal search strings., Arun Isaac, 2020/05/31
- [bug#39258] [PATCH v5 0/4] Optimize guix search, zimoun, 2020/05/31