From patchwork Mon Jun 1 00:00:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arun Isaac X-Patchwork-Id: 22484 Return-Path: X-Original-To: patchwork@mira.cbaines.net Delivered-To: patchwork@mira.cbaines.net Received: by mira.cbaines.net (Postfix, from userid 113) id AFE8827BBE3; Mon, 1 Jun 2020 01:01:16 +0100 (BST) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on mira.cbaines.net X-Spam-Level: X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,T_DKIM_INVALID, URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mira.cbaines.net (Postfix) with ESMTP id 3470827BBE1 for ; Mon, 1 Jun 2020 01:01:16 +0100 (BST) Received: from localhost ([::1]:37148 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jfXtD-0002lG-Hr for patchwork@mira.cbaines.net; Sun, 31 May 2020 20:01:15 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:38224) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jfXt0-0002je-Jm for guix-patches@gnu.org; Sun, 31 May 2020 20:01:02 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:50795) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1jfXt0-0005zG-74 for guix-patches@gnu.org; Sun, 31 May 2020 20:01:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1jfXt0-0003aR-5G for guix-patches@gnu.org; Sun, 31 May 2020 20:01:02 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#39258] [PATCH 0/4] Optimize guix search References: In-Reply-To: Resent-From: Arun Isaac Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Mon, 01 Jun 2020 00:01:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 39258 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: To: 39258@debbugs.gnu.org Cc: Arun Isaac , ludo@gnu.org, zimon.toutoune@gmail.com Received: via spool by 39258-submit@debbugs.gnu.org id=B39258.159096964013725 (code B ref 39258); Mon, 01 Jun 2020 00:01:02 +0000 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 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 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+patchwork=mira.cbaines.net@gnu.org Sender: "Guix-patches" X-getmail-retrieved-from-mailbox: Patches 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(-)