GNU bug report logs - #73766
30.0.91; (documentation 'pcase) can take several seconds

Previous Next

Full log

Message #11 received at 73766 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 73766 <at> debbugs.gnu.org, Yikai Zhao <yikai <at> z1k.dev>,
 João Távora <joaotavora <at> gmail.com>
Subject: Re: bug#73766: 30.0.91; (documentation 'pcase) can take several
 seconds
Date: Sat, 12 Oct 2024 12:39:38 -0400

[Message part 1 (text/plain, inline)]

>> Apparently, it would iterate over all defined pcase macros (N), and for
>> each of those, `help-fns-short-filename` would iterate over all items in
>> `load-path` (M). Total time complexity is N*M.
> Adding Stefan and João, in case they have some comments or
> suggestions.

How 'bout a patch like the one below?


        Stefan

[shortenfile.patch (text/x-diff, inline)]

diff --git a/lisp/help-fns.el b/lisp/help-fns.el
index 3f64b2e126f..3e0973c25ee 100644
--- a/lisp/help-fns.el
+++ b/lisp/help-fns.el
@@ -1090,17 +1090,38 @@ help-fns--mention-shortdoc-groups
         (fill-region-as-paragraph (point-min) (point-max))
         (goto-char (point-max))))))
 
+(require 'radix-tree)
+
+(defconst help-fns--radix-trees
+  (make-hash-table :weakness 'key :test #'equal))
+
+(defun help-fns--radix-tree (dirs)
+  (with-memoization (gethash dirs help-fns--radix-trees)
+    (let ((rt radix-tree-empty))
+      (dolist (d dirs)
+        (let ((d (abbreviate-file-name
+                  (file-name-as-directory (expand-file-name d)))))
+          (setq rt (radix-tree-insert rt d t))))
+      rt)))
+
 (defun help-fns-short-filename (filename)
-  (let* ((abbrev (abbreviate-file-name filename))
-         (short abbrev))
-    (dolist (dir load-path)
-      (let ((rel (file-relative-name filename dir)))
-        (if (< (length rel) (length short))
-            (setq short rel)))
-      (let ((rel (file-relative-name abbrev dir)))
-        (if (< (length rel) (length short))
-            (setq short rel))))
-    short))
+  (let* ((short (abbreviate-file-name (expand-file-name filename)))
+         (dir (file-name-directory short))
+         (nondir (file-name-nondirectory short))
+         (rt (help-fns--radix-tree load-path))
+         (prefixes (radix-tree-prefixes rt dir)))
+    (if (not prefixes)
+        ;; The file is not inside the `load-path'.
+        ;; FIXME: We used to try and shorten it with "../".
+        ;; (dolist (dir load-path)
+        ;;   (let ((rel (file-relative-name filename dir)))
+        ;;     (if (< (length rel) (length short))
+        ;;         (setq short rel)))
+        ;;   (let ((rel (file-relative-name abbrev dir)))
+        ;;     (if (< (length rel) (length short))
+        ;;         (setq short rel))))
+        short
+      (file-relative-name short (caar prefixes)))))
 
 (defun help-fns--analyze-function (function)
   ;; FIXME: Document/explain the differences between FUNCTION,

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.