From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms11 with LMTPS id SFROGrbU1F4lfQAA0tVLHw (envelope-from ) for ; Mon, 01 Jun 2020 10:13:10 +0000 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id ME4+FrbU1F6xPAAAB5/wlQ (envelope-from ) for ; Mon, 01 Jun 2020 10:13:10 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 03F7B9402D1 for ; Mon, 1 Jun 2020 10:13:09 +0000 (UTC) Received: from localhost ([::1]:45816 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jfhRM-00054f-P8 for larch@yhetil.org; Mon, 01 Jun 2020 06:13:08 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:35754) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jfhRG-00054W-Pf for guix-patches@gnu.org; Mon, 01 Jun 2020 06:13:02 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:51258) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1jfhRG-0006kH-Go for guix-patches@gnu.org; Mon, 01 Jun 2020 06:13:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1jfhRG-0005sM-Bq for guix-patches@gnu.org; Mon, 01 Jun 2020 06:13:02 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#39258] KMP string search algorithm? References: In-Reply-To: Resent-From: zimoun Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Mon, 01 Jun 2020 10:13: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: Arun Isaac , 39258@debbugs.gnu.org, Ludovic =?UTF-8?Q?Court=C3=A8s?= Received: via spool by 39258-submit@debbugs.gnu.org id=B39258.159100633022525 (code B ref 39258); Mon, 01 Jun 2020 10:13:02 +0000 Received: (at 39258) by debbugs.gnu.org; 1 Jun 2020 10:12:10 +0000 Received: from localhost ([127.0.0.1]:34570 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1jfhQQ-0005rF-IW for submit@debbugs.gnu.org; Mon, 01 Jun 2020 06:12:10 -0400 Received: from mail-qk1-f172.google.com ([209.85.222.172]:46378) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1jfhQP-0005r2-5T for 39258@debbugs.gnu.org; Mon, 01 Jun 2020 06:12:09 -0400 Received: by mail-qk1-f172.google.com with SMTP id c12so8418191qkk.13 for <39258@debbugs.gnu.org>; Mon, 01 Jun 2020 03:12:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=ohMequnGklGeHnzbOaO2DgtPJJxLJ/i5TQ861Q5o4rw=; b=sYZC8hSuoA/IQj1T2gj6WDf2xFBImPabh9+WSiVJDtBWdce1so2eidqsnIuqBKJLkH qrgCLtn2NS30j8w+PnVipnTXJoNaBNPM/MWn2fOzLhQpbH0X9WRbArfeMFoPv740KhGc SaKMbxNvG5llytHf6IlGqmBTPlm27MB9vdYyWzH23rpRkKi8jZXcRkOMSj7O13JE7TNZ V3LfzbkkWqFzZocfzXtajL1+2d0NGwTCqfTHMASQpnd8pPHRe/WZTaEPQi3zImwmc9i3 /syC5CkZAKX3TO/u5bptEuyhX9NstoDxdzBAjiXYMMqcwWo5S1jKduqb0cm/5I1OYhpK llgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=ohMequnGklGeHnzbOaO2DgtPJJxLJ/i5TQ861Q5o4rw=; b=DIDQkEHtxBo2ShTd0ti0OMfs7wsd9FjCt00H/X4EizEA2yWqgvhcyr/nvYqO0S6gPV Lb3ds2Tk5E+CcO/rvMt45MJoqspXR6XJpY8S762kRPgCYT4cKOlJ5dJIsMgbFUN/Ehg3 Gfu7ye3KmEKtabSesaMSArEmIxM7TX3rzAHou+Mm5oq/9sdMzWOo5P91dpY8PVm6SQc9 Me6dTf5+MwEOUFMcd+joSDaKlH0NJD75gA+MAntsoIVX3k3B9znNR4wH1u+UMWBcx4bI uc5ALgi6oPnmVJFy1CVIbsdnddeFkjLEmDCev7JA6XXUA5tCQkUawgH/u+4Wlg4h0TRp 93hQ== X-Gm-Message-State: AOAM530GHEOZCXOK78D8MqXiNgJ+H3sd0goL6Kff1OtkqcbswYTnLrLV ee267dN0zxC9hkGx0KdScp6ydvWBABxEpT0JuA8= X-Google-Smtp-Source: ABdhPJzhZmhhKZY/wfP4TrxB8xe9aT0UER/7zRJ7FPXsUKBGtdD3C7S3za1n4vLKogKD7L1kADZczVfiBxMrxJGGmak= X-Received: by 2002:a05:620a:148a:: with SMTP id w10mr17287713qkj.201.1591006323659; Mon, 01 Jun 2020 03:12:03 -0700 (PDT) MIME-Version: 1.0 From: zimoun Date: Mon, 1 Jun 2020 12:11:52 +0200 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-Spam-Score: -1.0 (-) X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Scanner: scn0 Authentication-Results: aspmx1.migadu.com; dkim=fail (rsa verify failed) header.d=gmail.com header.s=20161025 header.b=sYZC8hSu; dmarc=fail reason="SPF not aligned (relaxed)" header.from=gmail.com (policy=none); spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Spam-Score: 1.09 X-TUID: OcV9//KuDe10 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. :-)