From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: miha--- via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#51293: 29.0.50; [PATCH] Avoid excessive specbinding in all-completions Date: Tue, 19 Oct 2021 23:58:17 +0200 Message-ID: <871r4goex2.fsf@miha-pc> Reply-To: miha@kamnitnik.top Mime-Version: 1.0 Content-Type: multipart/signed; boundary="==-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38846"; mail-complaints-to="usenet@ciao.gmane.io" To: 51293@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Tue Oct 19 23:55:21 2021 Return-path: Envelope-to: geb-bug-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 1mcx4p-0009rx-A2 for geb-bug-gnu-emacs@m.gmane-mx.org; Tue, 19 Oct 2021 23:55:19 +0200 Original-Received: from localhost ([::1]:50808 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mcx4n-0002tP-Fg for geb-bug-gnu-emacs@m.gmane-mx.org; Tue, 19 Oct 2021 17:55:17 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:55478) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mcx4Z-0002tE-OV for bug-gnu-emacs@gnu.org; Tue, 19 Oct 2021 17:55:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:40630) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mcx4Y-0003PB-0R for bug-gnu-emacs@gnu.org; Tue, 19 Oct 2021 17:55:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mcx4X-0005fb-VJ for bug-gnu-emacs@gnu.org; Tue, 19 Oct 2021 17:55:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: miha@kamnitnik.top Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 19 Oct 2021 21:55:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 51293 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.163468048121762 (code B ref -1); Tue, 19 Oct 2021 21:55:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 19 Oct 2021 21:54:41 +0000 Original-Received: from localhost ([127.0.0.1]:52176 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mcx4C-0005ev-Lu for submit@debbugs.gnu.org; Tue, 19 Oct 2021 17:54:41 -0400 Original-Received: from lists.gnu.org ([209.51.188.17]:54210) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mcx4B-0005eo-8o for submit@debbugs.gnu.org; Tue, 19 Oct 2021 17:54:39 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:55414) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mcx47-0002r4-9t for bug-gnu-emacs@gnu.org; Tue, 19 Oct 2021 17:54:39 -0400 Original-Received: from kamnitnik.top ([2001:19f0:5001:bf2:5400:2ff:fee0:2626]:57826) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mcx44-0003Al-5O for bug-gnu-emacs@gnu.org; Tue, 19 Oct 2021 17:54:34 -0400 Original-Received: from localhost (BSN-77-156-43.static.siol.net [193.77.156.43]) by kamnitnik.top (Postfix) with ESMTPSA id AD9F09CFB0 for ; Tue, 19 Oct 2021 21:54:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kamnitnik.top; s=mail; t=1634680468; bh=qq5iYf10Zk7g1ODcUBidV+IjxIUPBOzAnGLlLZ4x6sU=; h=From:To:Subject:Date:From; b=JrWfvpQo1ewiHkpP5Tz0Lu9ZVt1gwbKwu3MMff0d7YcCVWEO51tYFua9g1tsR8cLy xabuoxKw3REWhwh+NaPVFngASQPpsuLnmxg+7tLy/4YDT7coQfvmldzjkAOKCNmTeF A0tvyh0jkRWRbqKclSk/oLKP7AXOuIqPdqYh53B1JHNHE64P3Ap30VzAL6LsQbTDSF 60HOFJvNSiiNvjPh42LJu21pW6m9ktjZ4vIkj8E0yxFF8cFsrjjKOdkmtBxMSg7aDu zabGlUH53dYX5Yg2ckAXNgd+a26CMfHpTPLEiTLbSGBjVfG8eI6YFWpCfc0cRQ83pf 8iNngcOwUzC+Q== Received-SPF: pass client-ip=2001:19f0:5001:bf2:5400:2ff:fee0:2626; envelope-from=miha@kamnitnik.top; helo=kamnitnik.top X-Spam_score_int: 8 X-Spam_score: 0.8 X-Spam_bar: / X-Spam_report: (0.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FROM_SUSPICIOUS_NTLD=0.499, FROM_SUSPICIOUS_NTLD_FP=1.997, PDS_OTHER_BAD_TLD=0.452, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:217609 Archived-At: --==-=-= Content-Type: multipart/mixed; boundary="=-=-=" --=-=-= Content-Type: text/plain If 'all-completions' is called under certain conditions, case-fold-search is specbound and unbound for each matching candidate. Because this variable is DEFVAR_PER_BUFFER, specbinding it is slow (scales with number of buffers). This patch eliminates specbinding from the three core completion functions. Benchmark: (dotimes (i 300) (get-buffer-create (format " *test-buffer-%s*" i))) (let ((completion-regexp-list '("\\`.*?"))) (benchmark-run-compiled 50 (all-completions "" obarray #'boundp))) 9.9 seconds without patch, 0.83 seconds with patch applied. Note that for the performance issue to be observed, we must have a lot of live buffers, completion-regexp-list must be non-nil and a predicate must be passed to all-completions. The last two conditions are satisfied if we press M-x TAB. --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0001-Avoid-excessive-specbinding-in-all-completions.patch Content-Transfer-Encoding: quoted-printable From=20e74c44270965c725d4e6e27b2b1bebed1f5308a2 Mon Sep 17 00:00:00 2001 From: =3D?UTF-8?q?Miha=3D20Rihtar=3DC5=3DA1i=3DC4=3D8D?=3D Date: Tue, 19 Oct 2021 18:41:13 +0200 Subject: [PATCH] Avoid excessive specbinding in all-completions * src/minibuf.c (match_regexps): (Ftry_completion): (Fall_completions): (Ftest_completion): Use fast_string_match_internal to match against regexps in completion-regexp-list without having to bind case-fold-search. =2D-- src/minibuf.c | 105 +++++++++++++++----------------------------------- 1 file changed, 32 insertions(+), 73 deletions(-) diff --git a/src/minibuf.c b/src/minibuf.c index 0dc340e967..6c0cd358c5 100644 =2D-- a/src/minibuf.c +++ b/src/minibuf.c @@ -1545,6 +1545,27 @@ minibuf_conform_representation (Lisp_Object string, = Lisp_Object basis) return Fstring_make_multibyte (string); } =20 +static bool +match_regexps (Lisp_Object string, Lisp_Object regexps, + bool ignore_case) +{ + ptrdiff_t val; + for (; CONSP (regexps); regexps =3D XCDR (regexps)) + { + CHECK_STRING (XCAR (regexps)); + + val =3D fast_string_match_internal + (XCAR (regexps), string, + (ignore_case ? BVAR (current_buffer, case_canon_table) : Qnil)); + + if (val =3D=3D -2) + error ("Stack overflow in regexp matcher"); + if (val < 0) + return false; + } + return true; +} + DEFUN ("try-completion", Ftry_completion, Stry_completion, 2, 3, 0, doc: /* Return common substring of all completions of STRING in COL= LECTION. Test each possible completion specified by COLLECTION @@ -1578,6 +1599,7 @@ DEFUN ("try-completion", Ftry_completion, Stry_comple= tion, 2, 3, 0, is used to further constrain the set of candidates. */) (Lisp_Object string, Lisp_Object collection, Lisp_Object predicate) { + Lisp_Object bestmatch, tail, elt, eltstring; /* Size in bytes of BESTMATCH. */ ptrdiff_t bestmatchsize =3D 0; @@ -1591,7 +1613,6 @@ DEFUN ("try-completion", Ftry_completion, Stry_comple= tion, 2, 3, 0, ? list_table : function_table)); ptrdiff_t idx =3D 0, obsize =3D 0; int matchcount =3D 0; =2D ptrdiff_t bindcount =3D -1; Lisp_Object bucket, zero, end, tem; =20 CHECK_STRING (string); @@ -1670,27 +1691,10 @@ DEFUN ("try-completion", Ftry_completion, Stry_comp= letion, 2, 3, 0, completion_ignore_case ? Qt : Qnil), EQ (Qt, tem))) { =2D /* Yes. */ =2D Lisp_Object regexps; =2D /* Ignore this element if it fails to match all the regexps. */ =2D { =2D for (regexps =3D Vcompletion_regexp_list; CONSP (regexps); =2D regexps =3D XCDR (regexps)) =2D { =2D if (bindcount < 0) =2D { =2D bindcount =3D SPECPDL_INDEX (); =2D specbind (Qcase_fold_search, =2D completion_ignore_case ? Qt : Qnil); =2D } =2D tem =3D Fstring_match (XCAR (regexps), eltstring, zero, Qnil); =2D if (NILP (tem)) =2D break; =2D } =2D if (CONSP (regexps)) =2D continue; =2D } + if (!match_regexps (eltstring, Vcompletion_regexp_list, + completion_ignore_case)) + continue; =20 /* Ignore this element if there is a predicate and the predicate doesn't like it. */ @@ -1701,11 +1705,6 @@ DEFUN ("try-completion", Ftry_completion, Stry_compl= etion, 2, 3, 0, tem =3D Fcommandp (elt, Qnil); else { =2D if (bindcount >=3D 0) =2D { =2D unbind_to (bindcount, Qnil); =2D bindcount =3D -1; =2D } tem =3D (type =3D=3D hash_table ? call2 (predicate, elt, HASH_VALUE (XHASH_TABLE (collection), @@ -1787,9 +1786,6 @@ DEFUN ("try-completion", Ftry_completion, Stry_comple= tion, 2, 3, 0, } } =20 =2D if (bindcount >=3D 0) =2D unbind_to (bindcount, Qnil); =2D if (NILP (bestmatch)) return Qnil; /* No completions found. */ /* If we are ignoring case, and there is no exact match, @@ -1849,7 +1845,6 @@ DEFUN ("all-completions", Fall_completions, Sall_comp= letions, 2, 4, 0, : VECTORP (collection) ? 2 : NILP (collection) || (CONSP (collection) && !FUNCTIONP (collection)); ptrdiff_t idx =3D 0, obsize =3D 0; =2D ptrdiff_t bindcount =3D -1; Lisp_Object bucket, tem, zero; =20 CHECK_STRING (string); @@ -1934,27 +1929,10 @@ DEFUN ("all-completions", Fall_completions, Sall_co= mpletions, 2, 4, 0, completion_ignore_case ? Qt : Qnil), EQ (Qt, tem))) { =2D /* Yes. */ =2D Lisp_Object regexps; =2D /* Ignore this element if it fails to match all the regexps. */ =2D { =2D for (regexps =3D Vcompletion_regexp_list; CONSP (regexps); =2D regexps =3D XCDR (regexps)) =2D { =2D if (bindcount < 0) =2D { =2D bindcount =3D SPECPDL_INDEX (); =2D specbind (Qcase_fold_search, =2D completion_ignore_case ? Qt : Qnil); =2D } =2D tem =3D Fstring_match (XCAR (regexps), eltstring, zero, Qnil); =2D if (NILP (tem)) =2D break; =2D } =2D if (CONSP (regexps)) =2D continue; =2D } + if (!match_regexps (eltstring, Vcompletion_regexp_list, + completion_ignore_case)) + continue; =20 /* Ignore this element if there is a predicate and the predicate doesn't like it. */ @@ -1965,11 +1943,6 @@ DEFUN ("all-completions", Fall_completions, Sall_com= pletions, 2, 4, 0, tem =3D Fcommandp (elt, Qnil); else { =2D if (bindcount >=3D 0) =2D { =2D unbind_to (bindcount, Qnil); =2D bindcount =3D -1; =2D } tem =3D type =3D=3D 3 ? call2 (predicate, elt, HASH_VALUE (XHASH_TABLE (collection), idx - 1)) @@ -1982,9 +1955,6 @@ DEFUN ("all-completions", Fall_completions, Sall_comp= letions, 2, 4, 0, } } =20 =2D if (bindcount >=3D 0) =2D unbind_to (bindcount, Qnil); =2D return Fnreverse (allmatches); } @@ -2068,7 +2038,7 @@ DEFUN ("test-completion", Ftest_completion, Stest_com= pletion, 2, 3, 0, the values STRING, PREDICATE and `lambda'. */) (Lisp_Object string, Lisp_Object collection, Lisp_Object predicate) { =2D Lisp_Object regexps, tail, tem =3D Qnil; + Lisp_Object tail, tem =3D Qnil; ptrdiff_t i =3D 0; =20 CHECK_STRING (string); @@ -2154,20 +2124,9 @@ DEFUN ("test-completion", Ftest_completion, Stest_co= mpletion, 2, 3, 0, return call3 (collection, string, predicate, Qlambda); =20 /* Reject this element if it fails to match all the regexps. */ =2D if (CONSP (Vcompletion_regexp_list)) =2D { =2D ptrdiff_t count =3D SPECPDL_INDEX (); =2D specbind (Qcase_fold_search, completion_ignore_case ? Qt : Qnil); =2D for (regexps =3D Vcompletion_regexp_list; CONSP (regexps); =2D regexps =3D XCDR (regexps)) =2D { =2D /* We can test against STRING, because if we got here, then =2D the element is equivalent to it. */ =2D if (NILP (Fstring_match (XCAR (regexps), string, Qnil, Qnil))) =2D return unbind_to (count, Qnil); =2D } =2D unbind_to (count, Qnil); =2D } + if (!match_regexps (string, Vcompletion_regexp_list, + completion_ignore_case)) + return Qnil; =20 /* Finally, check the predicate. */ if (!NILP (predicate)) =2D-=20 2.33.0 --=-=-=-- --==-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQJHBAEBCAAxFiEEmxVnesoT5rQXvVXnswkaGpIVmT8FAmFvP3kTHG1paGFAa2Ft bml0bmlrLnRvcAAKCRCzCRoakhWZP323EACisIn6GHCBQ089F7nEyUm0in3gEjC0 kZkK2G5vvqme+E0jrfI1MqrabT91VTX9u17jKDeX6oXkbMU8VSkHsfmKiTVh1HXi 2/lbyCaPCoq5cLKoRbk/eFhsXBHpu1x2qVrbQSCFRADGjvGWt76bb2L2sPPXHQID LqjywZry4wiJQ3nf2ia5kTaSBtsAcHZVzwBC+wrIFeP0Pp7aH3+huCmi3SATq61W TFuiUfEhPYsyJn+gENCbiMamWmCK6tHcp4um9rllROLWOjUPQLjf2aCM9F4+WOpj uuE2NIGrsVjPKitMIUsBp/sJPHmyYts5H0FCJI2cBNSSPTrj+akoenerEZbXhbCu JT8Ee6iVKmTJrY16UrKE2Sy4uIT+ceYr/tEULKqQ97QjxkJlGYmRQvbo0bmNORff SzsukVPPgU48opshrK+hPTTTqsJXlo8QIMs9VZRxrWM1EfKi08ZE9Ebj2z+mHqVV MJ+P/aUs9gd13TpfMB/x3jco9yjfXvH1K2UBGpl9WwFg1sApDtErYFWNEYcAjubE Tjy1MOe2ZQnGxiPN/Wzcj6fGJkIcd32BzUXBXjW0WZCF0jZVa8ZOiQzo+IQg1M0A CFdGFvocQMPXEUhlru6K3gkrQtC8IWcMhXAmbX/66AIv1UK0/4KhhGbIT5VHwYM1 0RNuT5DgstcBsw== =VFyS -----END PGP SIGNATURE----- --==-=-=--