From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS22989 209.51.188.0/24 X-Spam-Status: No, score=-3.9 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 87E5620248 for ; Sat, 23 Mar 2019 04:08:37 +0000 (UTC) Received: from localhost ([127.0.0.1]:38340 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h7XxT-0005QK-84 for normalperson@yhbt.net; Sat, 23 Mar 2019 00:08:35 -0400 Received: from eggs.gnu.org ([209.51.188.92]:42918) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h7WsB-0007uh-6J for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:59:04 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1h7Ws9-0004Ke-Cl for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:59:03 -0400 Received: from mail-yw1-xc43.google.com ([2607:f8b0:4864:20::c43]:39371) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1h7Ws9-0004HJ-1o for bug-gnulib@gnu.org; Fri, 22 Mar 2019 22:59:01 -0400 Received: by mail-yw1-xc43.google.com with SMTP id z191so3308770ywa.6 for ; Fri, 22 Mar 2019 19:59:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=p+CUNJp5YF2WRU+tpa1AnfOrHlZehLbVI5nKD3iSTeY=; b=LDUoGsupS6fcci47wFhwGXChn0EyImvgbSIK8lCJKjgUKbru8KA9LCxpV5AfscgciP NQx5NH0npqTC1UsJWvCm1FFkKUOx3nWm2OhuXWjZdGmS7M7g9frVikRYEpRH2R6yis0H TuA6snh3A6wjJ7ZrONngYE2umUG5hP15VFj2aehpZTNOOCm/bo/HRTjbrbi/7H7nuYjA vrkci03XNpg89IH2TRbYrDTmDy+ACFBG83errX6YtGEAjl+Fx3zLU+hnNZlpO86NDNbo /H3m+QDYgigasDLxbnD1o4dQvJHV6J2HaaiPuLlQvBlA9JP2CjV80+apMswRyFRSt7/E DUSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=p+CUNJp5YF2WRU+tpa1AnfOrHlZehLbVI5nKD3iSTeY=; b=TKYLE6P+FTPa6Knf2QcKVw+8FLCFgI8MtbpWyBRAnzcMmYjndvj7D/4og5LzsE7Yen 2qtf/rpaWAMIeun9vRgVRGRVMTnicvsqPkuvGvgyT4giP/w8LaxcP5dirXJM1FUdqtaX mOL2Mi8JMU2vJhW78U8/ooHAfRbbXmkcJ2PhjRVPNbBbuRvTilAql75VEFE/jgI89xmX 9vKW/YCQPqbt0QSlVERvwe6E7+7KbPWYtEgaBRN4vn0pNuaJ621FZsxJcHkbG0Zfo8b8 87e7FegtYOx5LXBJxyNXRCboOTZdhg4HM968u2x7WQpW1woQQ7+lhhLTEkS6FxqB36QC f+cw== X-Gm-Message-State: APjAAAW285tdFec62NUeV2/cjrdo2owftaLXvcFqRO2CXZJP7RG+6Det jHs0xdGz3HFnTfBTAHvFxQpeZEffSENcqZcRVG8= X-Google-Smtp-Source: APXvYqwsSTwoUyQFdgclPnmGMQrC3Ctj+TCbMK5DOfYHF1nKfF+NzmJyy78MPecaRGdc6pS1Wo16koJtW7DHVoXG5V0= X-Received: by 2002:a25:b31b:: with SMTP id l27mr11643745ybj.67.1553309940360; Fri, 22 Mar 2019 19:59:00 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a25:3794:0:0:0:0:0 with HTTP; Fri, 22 Mar 2019 19:59:00 -0700 (PDT) In-Reply-To: References: <20190323080618.E6EB.27F6AC2D@kcn.ne.jp> <20190323114902.E6F6.27F6AC2D@kcn.ne.jp> From: Budi Date: Sat, 23 Mar 2019 09:59:00 +0700 Message-ID: Subject: Re: bug#34951: [PATCH] grep: a kwset matcher not work in a grep matcher To: Norihiro Tanaka Content-Type: text/plain; charset="UTF-8" X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::c43 X-Mailman-Approved-At: Sat, 23 Mar 2019 00:08:29 -0400 X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: 34951@debbugs.gnu.org, bug-gnulib@gnu.org Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" How make grep walking through FS by scanning breadth first instead of On 3/23/19, Budi wrote: > How make grep walinh through FS by scanning breadth first instead of > the usual depth > > On 3/23/19, Norihiro Tanaka wrote: >> On Sat, 23 Mar 2019 08:06:35 +0900 >> Norihiro Tanaka wrote: >> >>> A kwset matcher is not built in a grep matcher after token re-order is >>> introduced in commit 5c7a0371823876cca7a1347fa09ca26bbbff0c98 in dfa. >>> It caused performance degradation in some typical cases. This bug is >>> introduced in grep-3.2. >>> >>> DFAMUST() does not work if tokens which are parsed in dfa matcher are >>> re-ordered. Therefore, change as it is called after parse and before >>> tokens re-order. >>> >>> BTW, this change does not affect programs that do not use DFAMUST(), >>> such as sed or gawk. >>> >>> $ yes $(printf '%040d' 0) | head -10000000 >inp >>> $ grep-2.2/src/grep 01.2 inp >>> real 1.61 >>> user 1.53 >>> sys 0.07 >>> $ grep-2.3/src/grep 01.2 inp >>> real 1.57 >>> user 1.48 >>> sys 0.08 >>> $ grep-2.4/src/grep 01.2 inp >>> real 1.50 >>> user 1.44 >>> sys 0.05 >>> $ grep-2.4.1/src/grep 01.2 inp >>> real 1.53 >>> user 1.48 >>> sys 0.05 >>> $ grep-2.4.2/src/grep 01.2 inp >>> real 1.52 >>> user 1.47 >>> sys 0.04 >>> $ grep-2.5.4/src/grep 01.2 inp >>> real 1.53 >>> user 1.47 >>> sys 0.05 >>> $ grep-2.6/src/grep 01.2 inp >>> real 1.51 >>> user 1.47 >>> sys 0.04 >>> $ grep-2.6.1/src/grep 01.2 inp >>> real 1.50 >>> user 1.44 >>> sys 0.05 >>> $ grep-2.6.2/src/grep 01.2 inp >>> real 1.52 >>> user 1.46 >>> sys 0.05 >>> $ grep-2.6.3/src/grep 01.2 inp >>> real 1.52 >>> user 1.47 >>> sys 0.05 >>> $ grep-2.7/src/grep 01.2 inp >>> real 1.53 >>> user 1.49 >>> sys 0.04 >>> $ grep-2.8/src/grep 01.2 inp >>> real 1.52 >>> user 1.46 >>> sys 0.05 >>> $ grep-2.9/src/grep 01.2 inp >>> real 1.54 >>> user 1.50 >>> sys 0.04 >>> $ grep-2.10/src/grep 01.2 inp >>> real 1.51 >>> user 1.46 >>> sys 0.05 >>> $ grep-2.11/src/grep 01.2 inp >>> real 1.53 >>> user 1.48 >>> sys 0.05 >>> $ grep-2.12/src/grep 01.2 inp >>> real 1.51 >>> user 1.47 >>> sys 0.03 >>> $ grep-2.13/src/grep 01.2 inp >>> real 1.52 >>> user 1.47 >>> sys 0.03 >>> $ grep-2.14/src/grep 01.2 inp >>> real 1.52 >>> user 1.47 >>> sys 0.04 >>> $ grep-2.15/src/grep 01.2 inp >>> real 1.55 >>> user 1.49 >>> sys 0.05 >>> $ grep-2.16/src/grep 01.2 inp >>> real 1.53 >>> user 1.48 >>> sys 0.04 >>> $ grep-2.17/src/grep 01.2 inp >>> real 1.53 >>> user 1.48 >>> sys 0.05 >>> $ grep-2.18/src/grep 01.2 inp >>> real 1.51 >>> user 1.44 >>> sys 0.06 >>> $ grep-2.19/src/grep 01.2 inp >>> real 0.06 >>> user 0.02 >>> sys 0.04 >>> $ grep-2.20/src/grep 01.2 inp >>> real 0.07 >>> user 0.01 >>> sys 0.05 >>> $ grep-2.21/src/grep 01.2 inp >>> real 0.06 >>> user 0.02 >>> sys 0.04 >>> $ grep-2.22/src/grep 01.2 inp >>> real 0.06 >>> user 0.01 >>> sys 0.05 >>> $ grep-2.23/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.05 >>> $ grep-2.24/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.04 >>> $ grep-2.25/src/grep 01.2 inp >>> real 0.09 >>> user 0.05 >>> sys 0.04 >>> $ grep-2.26/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.05 >>> $ grep-2.27/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.04 >>> $ grep-2.28/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.04 >>> $ grep-3.0/src/grep 01.2 inp >>> real 0.09 >>> user 0.04 >>> sys 0.04 >>> $ grep-3.1/src/grep 01.2 inp >>> real 0.11 >>> user 0.05 >>> sys 0.06 >>> $ grep-3.2/src/grep 01.2 inp >>> real 0.37 >>> user 0.32 >>> sys 0.04 >>> $ grep-3.3/src/grep 01.2 inp >>> real 0.29 >>> user 0.25 >>> sys 0.04 >>> >>> Thanks, >>> Norihiro >> >> Missing a patch for dfa. Re-send correct patch file. >> >