From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Marcin Borkowski Newsgroups: gmane.emacs.help Subject: Re: Performance of `re-search-backward' vs `re-search-forward' Date: Tue, 13 Apr 2021 08:07:44 +0200 Message-ID: <87zgy2af9r.fsf@mbork.pl> References: <87czv0awpq.fsf@mbork.pl> <8735vvb8c5.fsf@mbork.pl> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="15786"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: mu4e 1.1.0; emacs 28.0.50 Cc: help-gnu-emacs@gnu.org To: Stefan Monnier Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Tue Apr 13 08:08:29 2021 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lWCDt-0003xe-HD for geh-help-gnu-emacs@m.gmane-mx.org; Tue, 13 Apr 2021 08:08:29 +0200 Original-Received: from localhost ([::1]:58618 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lWCDs-0006Fe-F3 for geh-help-gnu-emacs@m.gmane-mx.org; Tue, 13 Apr 2021 02:08:28 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48360) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lWCDZ-0006FX-JA for help-gnu-emacs@gnu.org; Tue, 13 Apr 2021 02:08:09 -0400 Original-Received: from mail.mojserwer.eu ([195.110.48.8]:54738) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lWCDX-0007zf-A8 for help-gnu-emacs@gnu.org; Tue, 13 Apr 2021 02:08:09 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by mail.mojserwer.eu (Postfix) with ESMTP id 3A75FE6DA4; Tue, 13 Apr 2021 08:07:54 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at mail.mojserwer.eu Original-Received: from mail.mojserwer.eu ([127.0.0.1]) by localhost (mail.mojserwer.eu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9bAAzkAlqblY; Tue, 13 Apr 2021 08:07:49 +0200 (CEST) Original-Received: from localhost (178235147192.dynamic-3-poz-k-0-1-0.vectranet.pl [178.235.147.192]) by mail.mojserwer.eu (Postfix) with ESMTPSA id 33661E6226; Tue, 13 Apr 2021 08:07:49 +0200 (CEST) In-reply-to: Received-SPF: pass client-ip=195.110.48.8; envelope-from=mbork@mbork.pl; helo=mail.mojserwer.eu X-Spam_score_int: -25 X-Spam_score: -2.6 X-Spam_bar: -- X-Spam_report: (-2.6 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "help-gnu-emacs" Xref: news.gmane.io gmane.emacs.help:128979 Archived-At: On 2021-04-12, at 22:59, Stefan Monnier wrote: >>>> I seem to (very vaguely) remember reading that `re-search-backward' is >>>> significantly slower than `re-search-forward'. However, I can't find >>>> anything about it in the docstring (nor in the Elisp reference) now. Am >>>> I even correct? >>> I haven't looked at the code recently so my memory might be off, but >>> I can't think of any reason why it should be noticeably slower, no. >> So both basically move character by character and check if the regex >> matches there (more or less)? > > Yes, they're more or less loops that move char-by-char and call > `looking-at` each time. The `looking-at` is always doing a "forward > match" even if the outer loop is search backward, which is why the > performance difference should be negligible even if there might be > a difference in the performance of the outer loop. > > >>> Maybe you're confusing it with `looking-back` which is much slower than >>> `looking-at`? >> Yes, that was it! Thanks! > > Right: `looking-back` is actually doing a `re-search-backward` so it has > an outer loop which calls `looking-at` each time, hence it's O(n) times > slower than `looking-at`. Thanks for the explanation! -- Marcin Borkowski http://mbork.pl