bug#44529: [PATCH] Convert apropos-internal from C to Lisp

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Kangas]

[-- Attachment #1: Type: text/plain, Size: 704 bytes --]

Severity: wishlist

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I discovered that apropos-internal is defined in keymap.c for a reason
> that escapes me (it really should be moved to apropos.el).

Yes.  So I was actually going to propose the attached patch.  In my
testing, it is as fast as the C version (especially when byte-compiled),
which would match my intuition from reading the code.

(benchmark-run 10
  (apropos-command "test"))
=> (0.12032415399999999 2 0.014772391999999995) ; C
=> (0.13513192100000002 2 0.017216643000000004) ; Lisp

(benchmark-run 10
  (apropos "x"))
=> (3.846117816 131 1.092690677) ; C
=> (4.218219444 145 1.2153865740000003) ; Lisp

Any comments or objections?

[-- Attachment #2: 0001-Convert-apropos-internal-from-C-to-Lisp.patch --]
[-- Type: text/x-diff, Size: 6052 bytes --]

From 1324812b40315f022991b9f92fae896b343ae6d4 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <stefan@marxist.se>
Date: Sun, 8 Nov 2020 21:04:44 +0100
Subject: [PATCH] Convert apropos-internal from C to Lisp

This runs insignificantly faster in C, and is already fast enough on
reasonably modern hardware.  We might as well lift it to Lisp.
This benchmark can be used to verify:

  (benchmark-run 10 (apropos-command "test"))
  => (0.12032415399999999 2 0.014772391999999995) ; C
  => (0.13513192100000002 2 0.017216643000000004) ; Lisp

* lisp/apropos.el (apropos-internal): New defun, converted from C.
* src/keymap.c (Fapropos_internal): Remove defun.
(apropos_accum): Remove function.
(apropos_predicate, apropos_accumulate): Remove variables.
(syms_of_keymap): Remove defsubr for Fapropos_internal, and
definitions of the above variables.
* test/src/keymap-tests.el (keymap-apropos-internal)
(keymap-apropos-internal/predicate): Move tests from here...
* test/lisp/apropos-tests.el (apropos-apropos-internal)
(apropos-apropos-internal/predicate): ...to here.
---
 lisp/apropos.el            | 14 ++++++++++++++
 src/keymap.c               | 39 --------------------------------------
 test/lisp/apropos-tests.el | 10 ++++++++++
 test/src/keymap-tests.el   | 10 ----------
 4 files changed, 24 insertions(+), 49 deletions(-)

diff --git a/lisp/apropos.el b/lisp/apropos.el
index 9debdfb19c..89957f19fe 100644
--- a/lisp/apropos.el
+++ b/lisp/apropos.el
@@ -496,6 +496,20 @@ apropos-multi-type
   "If non-nil, this apropos query concerns multiple types.
 This is used to decide whether to print the result's type or not.")
 
+;;;###autoload
+(defun apropos-internal (regexp &optional predicate)
+  "Show all symbols whose names contain match for REGEXP.
+If optional 2nd arg PREDICATE is non-nil, (funcall PREDICATE SYMBOL) is done
+for each symbol and a symbol is mentioned only if that returns non-nil.
+Return list of symbols found."
+  (let (found)
+    (mapatoms (lambda (symbol)
+                (when (and (string-match regexp (symbol-name symbol))
+                           (or (not predicate)
+                               (funcall predicate symbol)))
+                  (push symbol found))))
+    (sort found #'string-lessp)))
+
 ;;;###autoload
 (defun apropos-user-option (pattern &optional do-all)
   "Show user options that match PATTERN.
diff --git a/src/keymap.c b/src/keymap.c
index e5b4781076..7dc4bd3f8e 100644
--- a/src/keymap.c
+++ b/src/keymap.c
@@ -3223,49 +3223,11 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
     }
 }
 \f
-/* Apropos - finding all symbols whose names match a regexp.		*/
-static Lisp_Object apropos_predicate;
-static Lisp_Object apropos_accumulate;
-
-static void
-apropos_accum (Lisp_Object symbol, Lisp_Object string)
-{
-  register Lisp_Object tem;
-
-  tem = Fstring_match (string, Fsymbol_name (symbol), Qnil);
-  if (!NILP (tem) && !NILP (apropos_predicate))
-    tem = call1 (apropos_predicate, symbol);
-  if (!NILP (tem))
-    apropos_accumulate = Fcons (symbol, apropos_accumulate);
-}
-
-DEFUN ("apropos-internal", Fapropos_internal, Sapropos_internal, 1, 2, 0,
-       doc: /* Show all symbols whose names contain match for REGEXP.
-If optional 2nd arg PREDICATE is non-nil, (funcall PREDICATE SYMBOL) is done
-for each symbol and a symbol is mentioned only if that returns non-nil.
-Return list of symbols found.  */)
-  (Lisp_Object regexp, Lisp_Object predicate)
-{
-  Lisp_Object tem;
-  CHECK_STRING (regexp);
-  apropos_predicate = predicate;
-  apropos_accumulate = Qnil;
-  map_obarray (Vobarray, apropos_accum, regexp);
-  tem = Fsort (apropos_accumulate, Qstring_lessp);
-  apropos_accumulate = Qnil;
-  apropos_predicate = Qnil;
-  return tem;
-}
-\f
 void
 syms_of_keymap (void)
 {
   DEFSYM (Qkeymap, "keymap");
   DEFSYM (Qdescribe_map_tree, "describe-map-tree");
-  staticpro (&apropos_predicate);
-  staticpro (&apropos_accumulate);
-  apropos_predicate = Qnil;
-  apropos_accumulate = Qnil;
 
   DEFSYM (Qkeymap_canonicalize, "keymap-canonicalize");
 
@@ -3409,7 +3371,6 @@ syms_of_keymap (void)
   defsubr (&Stext_char_description);
   defsubr (&Swhere_is_internal);
   defsubr (&Sdescribe_buffer_bindings);
-  defsubr (&Sapropos_internal);
 }
 
 void
diff --git a/test/lisp/apropos-tests.el b/test/lisp/apropos-tests.el
index 4c5522d14c..7386dd03ff 100644
--- a/test/lisp/apropos-tests.el
+++ b/test/lisp/apropos-tests.el
@@ -29,6 +29,16 @@
 (require 'apropos)
 (require 'ert)
 
+(ert-deftest apropos-apropos-internal ()
+  (should (equal (apropos-internal "^next-line$") '(next-line)))
+  (should (>= (length (apropos-internal "^help")) 100))
+  (should-not (apropos-internal "^test-a-missing-symbol-foo-bar-zot$")))
+
+(ert-deftest apropos-apropos-internal/predicate ()
+  (should (equal (apropos-internal "^next-line$" #'commandp) '(next-line)))
+  (should (>= (length (apropos-internal "^help" #'commandp)) 15))
+  (should-not (apropos-internal "^next-line$" #'keymapp)))
+
 (ert-deftest apropos-tests-words-to-regexp-1 ()
   (let ((re (apropos-words-to-regexp '("foo" "bar") "baz")))
     (should (string-match-p re "foobazbar"))
diff --git a/test/src/keymap-tests.el b/test/src/keymap-tests.el
index e3dd8420d7..6de98547d2 100644
--- a/test/src/keymap-tests.el
+++ b/test/src/keymap-tests.el
@@ -170,16 +170,6 @@ keymap-where-is-internal/preferred-modifier-is-a-string
             (where-is-internal 'execute-extended-command global-map t))
           [#x8000078])))
 
-(ert-deftest keymap-apropos-internal ()
-  (should (equal (apropos-internal "^next-line$") '(next-line)))
-  (should (>= (length (apropos-internal "^help")) 100))
-  (should-not (apropos-internal "^test-a-missing-symbol-foo-bar-zut$")))
-
-(ert-deftest keymap-apropos-internal/predicate ()
-  (should (equal (apropos-internal "^next-line$" #'commandp) '(next-line)))
-  (should (>= (length (apropos-internal "^help" #'commandp)) 15))
-  (should-not (apropos-internal "^next-line$" #'keymapp)))
-
 (provide 'keymap-tests)
 
 ;;; keymap-tests.el ends here
-- 
2.28.0

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Monnier]

> Any comments or objections?

LGTM,


        Stefan

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Mon, 9 Nov 2020 02:38:59 -0800
> Cc: monnier@iro.umontreal.ca
> 
> > I discovered that apropos-internal is defined in keymap.c for a reason
> > that escapes me (it really should be moved to apropos.el).
> 
> Yes.  So I was actually going to propose the attached patch.  In my
> testing, it is as fast as the C version (especially when byte-compiled),
> which would match my intuition from reading the code.
> 
> (benchmark-run 10
>   (apropos-command "test"))
> => (0.12032415399999999 2 0.014772391999999995) ; C
> => (0.13513192100000002 2 0.017216643000000004) ; Lisp
> 
> (benchmark-run 10
>   (apropos "x"))
> => (3.846117816 131 1.092690677) ; C
> => (4.218219444 145 1.2153865740000003) ; Lisp

20% slowdown is not negligible, at least not in principle.  Let's wait
for more people to voice their opinions on this aspect.

> Any comments or objections?

A bother: apropos.el is not preloaded, so please double-check that
none of the preloaded files call apropos-internal, otherwise that
would mean we need to preload apropos.el, which I think is
undesirable.

Thanks.

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Kangas]

Eli Zaretskii <eliz@gnu.org> writes:

>> (benchmark-run 10
>>   (apropos "x"))
>> => (3.846117816 131 1.092690677) ; C
>> => (4.218219444 145 1.2153865740000003) ; Lisp
>
> 20% slowdown is not negligible, at least not in principle.  Let's wait
> for more people to voice their opinions on this aspect.

Unless I'm missing something, the slowdown should be around 10%.

(FWIW, the figure of 0.38 or 0.42 seconds is for the more unlikely
string with one character.  In the more realistic scenario with a
slightly longer string, we see a difference between 0.012 and 0.013
seconds.)

> A bother: apropos.el is not preloaded, so please double-check that
> none of the preloaded files call apropos-internal, otherwise that
> would mean we need to preload apropos.el, which I think is
> undesirable.

I only see one call in a preloaded file:

./lisp/progmodes/elisp-mode.el:873: (dolist (sym (apropos-internal regexp))

(This is from a `cl-defmethod' for `xref-backend-apropos'.)

Does this mean we have to preload apropos.el?  I don't understand how,
so I'm probably missing something.

Thanks for commenting.

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Mon, 9 Nov 2020 12:44:26 -0800
> Cc: 44529@debbugs.gnu.org, monnier@iro.umontreal.ca
> 
> > A bother: apropos.el is not preloaded, so please double-check that
> > none of the preloaded files call apropos-internal, otherwise that
> > would mean we need to preload apropos.el, which I think is
> > undesirable.
> 
> I only see one call in a preloaded file:
> 
> ./lisp/progmodes/elisp-mode.el:873: (dolist (sym (apropos-internal regexp))
> 
> (This is from a `cl-defmethod' for `xref-backend-apropos'.)
> 
> Does this mean we have to preload apropos.el?

Or move this Lisp implementation to another file, which is already
preloaded.

> I don't understand how, so I'm probably missing something.

Because if we don't, every Emacs session will load it right at the
start.

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Monnier]

> Because if we don't, every Emacs session will load it right at the
> start.

I don't see that: elisp-mode.el calls `apropos-internal` only from
`xref-backend-apropos`, which AFAICT is not used "right at the
start" but only after loading `xref.el` which is itself not preloaded.


        Stefan

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Stefan Kangas <stefan@marxist.se>,  44529@debbugs.gnu.org
> Date: Tue, 10 Nov 2020 08:14:01 -0500
> 
> > Because if we don't, every Emacs session will load it right at the
> > start.
> 
> I don't see that: elisp-mode.el calls `apropos-internal` only from
> `xref-backend-apropos`, which AFAICT is not used "right at the
> start" but only after loading `xref.el` which is itself not preloaded.

I don't want to rely on such shaky assumptions: the code in
elisp-mode.el can change any moment.

apropos-internal was always available in Emacs, so let's leave it
always available by putting it in subr.el or somesuch.

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Monnier]

>> I don't see that: elisp-mode.el calls `apropos-internal` only from
>> `xref-backend-apropos`, which AFAICT is not used "right at the
>> start" but only after loading `xref.el` which is itself not preloaded.
>
> I don't want to rely on such shaky assumptions: the code in
> elisp-mode.el can change any moment.
>
> apropos-internal was always available in Emacs, so let's leave it
> always available by putting it in subr.el or somesuch.

If we autoload it, it will work just as well without having to move it
outside of its most natural habitat.


        Stefan

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: stefan@marxist.se,  44529@debbugs.gnu.org
> Date: Tue, 10 Nov 2020 14:50:02 -0500
> 
> > apropos-internal was always available in Emacs, so let's leave it
> > always available by putting it in subr.el or somesuch.
> 
> If we autoload it, it will work just as well without having to move it
> outside of its most natural habitat.

I don't want it to become autoloaded, it could break something.  Why
risk that?

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Kangas]

[-- Attachment #1: Type: text/plain, Size: 301 bytes --]

Eli Zaretskii <eliz@gnu.org> writes:

>> If we autoload it, it will work just as well without having to move it
>> outside of its most natural habitat.
>
> I don't want it to become autoloaded, it could break something.  Why
> risk that?

The attached patch moves it to subr.el instead, as requested.

[-- Attachment #2: 0001-Convert-apropos-internal-from-C-to-Lisp.patch --]
[-- Type: text/x-diff, Size: 5784 bytes --]

From 07ab0d3dcd51be36fcee24b8b7fbe66040ee3d62 Mon Sep 17 00:00:00 2001
From: Stefan Kangas <stefan@marxist.se>
Date: Sun, 8 Nov 2020 21:04:44 +0100
Subject: [PATCH] Convert apropos-internal from C to Lisp

This runs insignificantly faster in C, and is already fast enough on
reasonably modern hardware.  We might as well lift it to Lisp.
This benchmark can be used to verify:

  (benchmark-run 10 (apropos-command "test"))
  => (0.12032415399999999 2 0.014772391999999995) ; C
  => (0.13513192100000002 2 0.017216643000000004) ; Lisp

* lisp/subr.el (apropos-internal): New defun, converted from C.
* src/keymap.c (Fapropos_internal): Remove defun.
(apropos_accum): Remove function.
(apropos_predicate, apropos_accumulate): Remove variables.
(syms_of_keymap): Remove defsubr for Fapropos_internal, and
definitions of the above variables.
* test/src/keymap-tests.el (keymap-apropos-internal)
(keymap-apropos-internal/predicate): Move tests from here...
* test/lisp/subr-tests.el (apropos-apropos-internal)
(apropos-apropos-internal/predicate): ...to here.
---
 lisp/subr.el             | 16 ++++++++++++++++
 src/keymap.c             | 39 ---------------------------------------
 test/lisp/subr-tests.el  | 13 +++++++++++++
 test/src/keymap-tests.el | 10 ----------
 4 files changed, 29 insertions(+), 49 deletions(-)

diff --git a/lisp/subr.el b/lisp/subr.el
index 6e9f66fe97..de0c49f756 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -5786,6 +5786,22 @@ with-mutex
 	   (progn ,@body)
 	 (mutex-unlock ,sym)))))
 
+\f
+;;; Apropos.
+
+(defun apropos-internal (regexp &optional predicate)
+  "Show all symbols whose names contain match for REGEXP.
+If optional 2nd arg PREDICATE is non-nil, (funcall PREDICATE SYMBOL) is done
+for each symbol and a symbol is mentioned only if that returns non-nil.
+Return list of symbols found."
+  (let (found)
+    (mapatoms (lambda (symbol)
+                (when (and (string-match regexp (symbol-name symbol))
+                           (or (not predicate)
+                               (funcall predicate symbol)))
+                  (push symbol found))))
+    (sort found #'string-lessp)))
+
 \f
 ;;; Misc.
 
diff --git a/src/keymap.c b/src/keymap.c
index 181dcdad3a..c75460f9c3 100644
--- a/src/keymap.c
+++ b/src/keymap.c
@@ -3223,49 +3223,11 @@ describe_vector (Lisp_Object vector, Lisp_Object prefix, Lisp_Object args,
     }
 }
 \f
-/* Apropos - finding all symbols whose names match a regexp.		*/
-static Lisp_Object apropos_predicate;
-static Lisp_Object apropos_accumulate;
-
-static void
-apropos_accum (Lisp_Object symbol, Lisp_Object string)
-{
-  register Lisp_Object tem;
-
-  tem = Fstring_match (string, Fsymbol_name (symbol), Qnil);
-  if (!NILP (tem) && !NILP (apropos_predicate))
-    tem = call1 (apropos_predicate, symbol);
-  if (!NILP (tem))
-    apropos_accumulate = Fcons (symbol, apropos_accumulate);
-}
-
-DEFUN ("apropos-internal", Fapropos_internal, Sapropos_internal, 1, 2, 0,
-       doc: /* Show all symbols whose names contain match for REGEXP.
-If optional 2nd arg PREDICATE is non-nil, (funcall PREDICATE SYMBOL) is done
-for each symbol and a symbol is mentioned only if that returns non-nil.
-Return list of symbols found.  */)
-  (Lisp_Object regexp, Lisp_Object predicate)
-{
-  Lisp_Object tem;
-  CHECK_STRING (regexp);
-  apropos_predicate = predicate;
-  apropos_accumulate = Qnil;
-  map_obarray (Vobarray, apropos_accum, regexp);
-  tem = Fsort (apropos_accumulate, Qstring_lessp);
-  apropos_accumulate = Qnil;
-  apropos_predicate = Qnil;
-  return tem;
-}
-\f
 void
 syms_of_keymap (void)
 {
   DEFSYM (Qkeymap, "keymap");
   DEFSYM (Qdescribe_map_tree, "describe-map-tree");
-  staticpro (&apropos_predicate);
-  staticpro (&apropos_accumulate);
-  apropos_predicate = Qnil;
-  apropos_accumulate = Qnil;
 
   DEFSYM (Qkeymap_canonicalize, "keymap-canonicalize");
 
@@ -3409,7 +3371,6 @@ syms_of_keymap (void)
   defsubr (&Stext_char_description);
   defsubr (&Swhere_is_internal);
   defsubr (&Sdescribe_buffer_bindings);
-  defsubr (&Sapropos_internal);
 }
 
 void
diff --git a/test/lisp/subr-tests.el b/test/lisp/subr-tests.el
index 035c064d75..0f883ef6a7 100644
--- a/test/lisp/subr-tests.el
+++ b/test/lisp/subr-tests.el
@@ -484,5 +484,18 @@ string-replace
 
   (should-error (string-replace "" "x" "abc")))
 
+\f
+;;; Apropos.
+
+(ert-deftest apropos-apropos-internal ()
+  (should (equal (apropos-internal "^next-line$") '(next-line)))
+  (should (>= (length (apropos-internal "^help")) 100))
+  (should-not (apropos-internal "^test-a-missing-symbol-foo-bar-zot$")))
+
+(ert-deftest apropos-apropos-internal/predicate ()
+  (should (equal (apropos-internal "^next-line$" #'commandp) '(next-line)))
+  (should (>= (length (apropos-internal "^help" #'commandp)) 15))
+  (should-not (apropos-internal "^next-line$" #'keymapp)))
+
 (provide 'subr-tests)
 ;;; subr-tests.el ends here
diff --git a/test/src/keymap-tests.el b/test/src/keymap-tests.el
index 610234c5a1..900ade7f48 100644
--- a/test/src/keymap-tests.el
+++ b/test/src/keymap-tests.el
@@ -200,16 +200,6 @@ keymap-where-is-internal/preferred-modifier-is-a-string
             (where-is-internal 'execute-extended-command global-map t))
           [#x8000078])))
 
-(ert-deftest keymap-apropos-internal ()
-  (should (equal (apropos-internal "^next-line$") '(next-line)))
-  (should (>= (length (apropos-internal "^help")) 100))
-  (should-not (apropos-internal "^test-a-missing-symbol-foo-bar-zut$")))
-
-(ert-deftest keymap-apropos-internal/predicate ()
-  (should (equal (apropos-internal "^next-line$" #'commandp) '(next-line)))
-  (should (>= (length (apropos-internal "^help" #'commandp)) 15))
-  (should-not (apropos-internal "^next-line$" #'keymapp)))
-
 (provide 'keymap-tests)
 
 ;;; keymap-tests.el ends here
-- 
2.29.2

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Sun, 15 Nov 2020 17:07:14 -0800
> Cc: 44529@debbugs.gnu.org
> 
> The attached patch moves it to subr.el instead, as requested.

Thanks.

> This runs insignificantly faster in C, and is already fast enough on
> reasonably modern hardware.  We might as well lift it to Lisp.
> This benchmark can be used to verify:
> 
>   (benchmark-run 10 (apropos-command "test"))
>   => (0.12032415399999999 2 0.014772391999999995) ; C
>   => (0.13513192100000002 2 0.017216643000000004) ; Lisp

Btw, did you try with less trivial strings?  E.g., what happens if you
replace "test" with "set" or "file"?

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Kangas]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Stefan Kangas <stefan@marxist.se>
>> Date: Sun, 15 Nov 2020 17:07:14 -0800
>> Cc: 44529@debbugs.gnu.org
>>
>> The attached patch moves it to subr.el instead, as requested.
>
> Thanks.
>
>> This runs insignificantly faster in C, and is already fast enough on
>> reasonably modern hardware.  We might as well lift it to Lisp.
>> This benchmark can be used to verify:
>>
>>   (benchmark-run 10 (apropos-command "test"))
>>   => (0.12032415399999999 2 0.014772391999999995) ; C
>>   => (0.13513192100000002 2 0.017216643000000004) ; Lisp
>
> Btw, did you try with less trivial strings?  E.g., what happens if you
> replace "test" with "set" or "file"?

(Sorry for the late reply.)

I see results consistent with the previously reported 10 % difference,
or even slightly better than that:

(benchmark-run 10 (apropos-command "file"))
=> (0.6285004230000001 26 0.176056903)  ; C
=> (0.667433809 26 0.19296271500000006) ; Lisp

(/ 0.667433809 0.6285004230000001) => 1.0619

(benchmark-run 10 (apropos-command "set"))
=> (0.463329467 19 0.12921543499999996) ; C
=> (0.486383881 19 0.13347332099999998) ; Lisp

(/ 0.486383881 0.463329467) => 1.0497

bug#44529: [PATCH] Convert apropos-internal from C to Lisp

[Stefan Kangas]

tags 44529 fixed
close 44529 28.1
thanks

Eli Zaretskii <eliz@gnu.org> writes:

>> The attached patch moves it to subr.el instead, as requested.
>
> Thanks.

No further comments within a month; pushed to master as commit
49ae715966.