From debbugs-submit-bounces@debbugs.gnu.org Sun May 31 20:00:40 2020 Received: (at 39258) by debbugs.gnu.org; 1 Jun 2020 00:00:40 +0000 Received: from localhost ([127.0.0.1]:34100 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1jfXse-0003ZH-6k for submit@debbugs.gnu.org; Sun, 31 May 2020 20:00:40 -0400 Received: from mugam.systemreboot.net ([139.59.75.54]:37192) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1jfXsb-0003Yl-57 for 39258@debbugs.gnu.org; Sun, 31 May 2020 20:00:38 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=systemreboot.net; s=default; h=Content-Transfer-Encoding:MIME-Version: Message-Id:Date:Subject:Cc:To:From:Sender:Reply-To:Content-Type:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=2jTYtU4y5MC0/bYrF3fsZzG9NRjCcmUfkno2BNH95o0=; b=ZU0i6PzLrAeER8sMT+UCURsQZo SFgC3aR6rlb2qMkWVnBSqIfWboZiwyrDwJoWECL1ajwZ1pX+tkqyT9USzhlw9iD5dGqrvTrykILds k5S9KDboT3tVUR8XGb31Lh84EggCag0uAXT/WjP1Z43JmuzlcrCWcr5av0V/caVi8DPQ=; Received: from [192.168.2.1] (helo=steel.lan) by systemreboot.net with esmtpsa (TLS1.3) tls TLS_AES_256_GCM_SHA384 (Exim 4.93) (envelope-from ) id 1jfXsW-000Zk2-EI; Mon, 01 Jun 2020 05:30:32 +0530 From: Arun Isaac To: 39258@debbugs.gnu.org Subject: [PATCH 0/4] Optimize guix search Date: Mon, 1 Jun 2020 05:30:26 +0530 Message-Id: <20200601000030.7443-1-arunisaac@systemreboot.net> X-Mailer: git-send-email 2.26.2 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 39258 Cc: Arun Isaac , ludo@gnu.org, zimon.toutoune@gmail.com X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) 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