etags completion table (was: bug#20629: 25.0.50; Regression: TAGS broken, can't find anything in C++ files)

etags completion table (was: bug#20629: 25.0.50; Regression: TAGS broken, can't find anything in C++ files)

[Stefan Monnier]

>> Oh, then it's a non-starter (unless the search can be sped up).
> I've posted the numbers along with the two versions of the patch:
> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=20629#101
> http://debbugs.gnu.org/cgi/bugreport.cgi?bug=20629#107

Hmm... I missed those, sorry.

I see the first patch says that it takes 1.34s to build the obarray and
0.78s to build an equivalent list of strings, so we could change the
code so as to keep the completion table as a pre-built list of strings
instead of a pre-built obarray.  It will also save us a bit of memory.

As for doing the search each time, the possible gain on the first
completion (0.3s instead of 0.78s) doesn't make up for the loss of going
from 0.02s to 0.3s on subsequent completions.

So that seems like a non-starter, unless we can speed it up
significantly.  It shouldn't be too hard to keep the worst case at
0.76s, but lowering the 0.3s seems harder.  Obviously we could get rid
of the "looking-at" within the loop (fold it into the preceding
re-search-forward), but it seems unlikely that this would gain us much
when there are few matches.


        Stefan

Re: etags completion table

[Dmitry Gutov]

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

On 05/30/2015 12:41 AM, Stefan Monnier wrote:

> I see the first patch says that it takes 1.34s to build the obarray and
> 0.78s to build an equivalent list of strings, so we could change the
> code so as to keep the completion table as a pre-built list of strings
> instead of a pre-built obarray.  It will also save us a bit of memory.

Maybe. The difference isn't much, though, and it's a one-time thing.

> As for doing the search each time, the possible gain on the first
> completion (0.3s instead of 0.78s)

The possible gain is from 1.34s down to 0.78s. I haven't managed to 
bring the time to generate all completions for "" down any further.

> doesn't make up for the loss of going
> from 0.02s to 0.3s on subsequent completions.

I think you mean 0.02 to 0.2.

> So that seems like a non-starter, unless we can speed it up
> significantly.  It shouldn't be too hard to keep the worst case at
> 0.76s, but lowering the 0.3s seems harder.

Lowering 0.2 is not too hard if the prefix is at least 2-3 characters 
long: you drop [\n \t()=,;\177] from the first regexp and simply search 
for the string. This way, the search for completions for "test" takes 
only 0.05s (with 37 matches). Of course, that doesn't work at all for an 
empty prefix.

Seems like support for lookbehind in the regexp engine would help unify 
these cases.

However, the worst case is going to come up a lot. After all, that's 
what you trigger with `C-u M-. TAB'.

> Obviously we could get rid
> of the "looking-at" within the loop (fold it into the preceding
> re-search-forward), but it seems unlikely that this would gain us much
> when there are few matches.

Indeed. It brings us to 0.78 in the worst case and 0.26 in the best case 
(I'm blaming the regexp engine), with no easy opportunity for a speed-up 
when matching a longer string. Patch attached.

[-- Attachment #2: etags-completion.diff --]
[-- Type: text/x-patch, Size: 4561 bytes --]

diff --git a/lisp/progmodes/etags.el b/lisp/progmodes/etags.el
index 9ff164e..98bbabd 100644
--- a/lisp/progmodes/etags.el
+++ b/lisp/progmodes/etags.el
@@ -753,31 +753,18 @@ Assumes the tags table is the current buffer."
       (setq tags-included-tables (funcall tags-included-tables-function))))
 \f
 (defun tags-completion-table ()
-  "Build `tags-completion-table' on demand.
+  "Return tags completion table.
 The tags included in the completion table are those in the current
 tags table and its (recursively) included tags tables."
-  (or tags-completion-table
-      ;; No cached value for this buffer.
-      (condition-case ()
-	  (let (current-table combined-table)
-	    (message "Making tags completion table for %s..." buffer-file-name)
-	    (save-excursion
-	      ;; Iterate over the current list of tags tables.
-	      (while (visit-tags-table-buffer (and combined-table t))
-		;; Find possible completions in this table.
-		(setq current-table (funcall tags-completion-table-function))
-		;; Merge this buffer's completions into the combined table.
-		(if combined-table
-		    (mapatoms
-		     (lambda (sym) (intern (symbol-name sym) combined-table))
-		     current-table)
-		  (setq combined-table current-table))))
-	    (message "Making tags completion table for %s...done"
-		     buffer-file-name)
-	    ;; Cache the result in a buffer-local variable.
-	    (setq tags-completion-table combined-table))
-	(quit (message "Tags completion table construction aborted.")
-	      (setq tags-completion-table nil)))))
+  (completion-table-with-cache
+   (lambda (string)
+     (let (cont tables)
+       (save-excursion
+         ;; Iterate over the current list of tags tables.
+         (while (visit-tags-table-buffer (or cont (progn (setq cont t)  nil)))
+           ;; Find possible completions in this table.
+           (push (funcall tags-completion-table-function string) tables)))
+       (nreverse (apply #'nconc tables))))))
 
 ;;;###autoload
 (defun tags-lazy-completion-table ()
@@ -1218,7 +1205,7 @@ buffer-local values of tags table format variables."
        (mapc (lambda (elt) (set (make-local-variable (car elt)) (cdr elt)))
 	     '((file-of-tag-function . etags-file-of-tag)
 	       (tags-table-files-function . etags-tags-table-files)
-	       (tags-completion-table-function . etags-tags-completion-table)
+	       (tags-completion-table-function . etags-tags-completions)
 	       (snarf-tag-function . etags-snarf-tag)
 	       (goto-tag-location-function . etags-goto-tag-location)
 	       (find-tag-regexp-search-function . re-search-forward)
@@ -1254,35 +1241,20 @@ buffer-local values of tags table format variables."
 	  str
 	(expand-file-name str (file-truename default-directory))))))
 
-
-(defun etags-tags-completion-table () ; Doc string?
-  (let ((table (make-vector 511 0))
-	(progress-reporter
-	 (make-progress-reporter
-	  (format "Making tags completion table for %s..." buffer-file-name)
-	  (point-min) (point-max))))
+(defun etags-tags-completions (string) ; Doc string?
+  (let* (table
+         (qs (regexp-quote string))
+         (re (format (concat "[\n \t()=,;]\\(%s[^\177 \t()=,;]*\\)\177[0-9]"
+                             "\\|"
+                             "\177\\(%s[^\001]*\\)\001")
+                     qs qs)))
     (save-excursion
       (goto-char (point-min))
-      ;; This monster regexp matches an etags tag line.
-      ;;   \1 is the string to match;
-      ;;   \2 is not interesting;
-      ;;   \3 is the guessed tag name; XXX guess should be better eg DEFUN
-      ;;   \4 is not interesting;
-      ;;   \5 is the explicitly-specified tag name.
-      ;;   \6 is the line to start searching at;
-      ;;   \7 is the char to start searching at.
-      (while (re-search-forward
-	      "^\\(\\([^\177]+[^-a-zA-Z0-9_+*$:\177]+\\)?\
-\\([-a-zA-Z0-9_+*$?:]+\\)[^-a-zA-Z0-9_+*$?:\177]*\\)\177\
-\\(\\([^\n\001]+\\)\001\\)?\\([0-9]+\\)?,\\([0-9]+\\)?\n"
-	      nil t)
-	(intern	(prog1 (if (match-beginning 5)
-			   ;; There is an explicit tag name.
-			   (buffer-substring (match-beginning 5) (match-end 5))
-			 ;; No explicit tag name.  Best guess.
-			 (buffer-substring (match-beginning 3) (match-end 3)))
-		  (progress-reporter-update progress-reporter (point)))
-		table)))
+      (while (re-search-forward re nil t)
+        (push (if (match-beginning 1)
+                  (match-string-no-properties 1)
+                (match-string-no-properties 2))
+              table)))
     table))
 
 (defun etags-snarf-tag (&optional use-explicit) ; Doc string?

Re: etags completion table

[Stefan Monnier]

>> I see the first patch says that it takes 1.34s to build the obarray and
>> 0.78s to build an equivalent list of strings, so we could change the
>> code so as to keep the completion table as a pre-built list of strings
>> instead of a pre-built obarray.  It will also save us a bit of memory.
> Maybe. The difference isn't much, though, and it's a one-time thing.

Agreed.  But the current use of an obarray is just wrong: it makes the
code use more CPU and memory resources for no benefit.


        Stefan

Re: etags completion table

[Dmitry Gutov]

On 05/30/2015 07:00 AM, Stefan Monnier wrote:

> Agreed.  But the current use of an obarray is just wrong: it makes the
> code use more CPU and memory resources for no benefit.

Ok, pushed that change.

Are there any good uses of an obarray, aside from being employed in the 
Emacs Lisp runtime?

Re: etags completion table

[Stefan Monnier]

> Are there any good uses of an obarray, aside from being employed in the
> Emacs Lisp runtime?

Not sure, to tell you the truth.  Most typical uses nowadays are better
served by hash-tables, but there might still be cases where
it's worthwhile.


        Stefan