[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bug#2445: 23.0.90; file name completion GCs a lot

From: Stefan Monnier
Subject: bug#2445: 23.0.90; file name completion GCs a lot
Date: Tue, 17 Mar 2009 14:03:38 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.90 (gnu/linux)

> When I type C-x C-f xmail/foox TAB, where xmail contains 800 files
> and none of them starts with foox, it takes a few seconds (including
> 3 GCs) before telling me it can't be found.
> Here's output from xbacktrace:

>     "file-name-completion" (0x7fbe23e4)

I finally managed to reproduce it (completion was still immediate with
800 files, but with 50000 it did take about 4s, whereas Emacs-22 is
still pretty much instantaneous).

The problem is that when the new partial completion code fails to find
any completion, it needs to figure out "is there *any* completion in
xmail/?" in order to figure out whether it should instead first try to
complete "xmail".

In the case of file completion, a simple (file-directory-p "xmail/")
would give us the necessary answer, but the code is generic and the
only/best way to get this information from a completion tables is to
call (try-completion "xmail/" table), which calls (file-name-completion
"" "xmail/").

Now `file-name-completion' has several inefficiencies.  In the current
case, what kills us is that for every entry that matches (i.e. in our
case: every entry since we're matching "") we compare it to every
pattern in completion-ignored-extensions, and this comparison ends up
encoding each element of completion-ignored-extensions each time.  So if
we have 52 entries in completion-ignored-extensions (the default in
Emacs-22) and we do (file-name-completion "" "xmail/") where xmail
contains 800 entries, we end up encoding 40K strings, where each
encoding will allocate at least one string (each strings takes up
a "struct Lisp_String" object (4 pointers) plus a a "struct sdata" which
contains another pointer (back to the "struct Lisp_String") plus the
actual string's bytes, so a minimum of 24B on 32bit systems and 48B on
64bit systems.  I.e. a minimum of 1MB of allocation, 2MB on 64bit
systems.  That might explain some of the GCs (tho maybe not all 3).

The code should be changed so as to eliminate those repeated encodings,
e.g. by comparing decoded strings rather than encoded strings
(i.e. move the DECODE_FILE call earlier).

Rather than make such a change (which seems a bit more delicate than I'd
like right now), I've added two simple optimizations to shortcircuit
some of the code in some "common" cases.  In my tests, this
significantly speeds up the problematic operation.

More specifically, in a directory with 230K entries, Emacs-22 takes
about 1s to say [no match] (on my test machine) whereas Emacs-23 with my
patch takes about 3s, which is the expected slowdown now that
completion-styles contains 3 entries.

Can you try the patch below to confirm it fixes your problem?


Index: lisp/minibuffer.el
RCS file: /sources/emacs/emacs/lisp/minibuffer.el,v
retrieving revision 1.75
diff -u -r1.75 minibuffer.el
--- lisp/minibuffer.el  17 Mar 2009 04:39:09 -0000      1.75
+++ lisp/minibuffer.el  17 Mar 2009 17:58:52 -0000
@@ -1485,7 +1485,13 @@
                   (error (unless firsterror (setq firsterror err)) nil))))
       (when (and (null all)
                  (> (car bounds) 0)
-                 (null (ignore-errors (try-completion prefix table pred))))
+                 (null (ignore-errors
+                         ;; `try-completion' sometimes has to work very hard to
+                         ;; properly ignore case, and at the same time choose
+                         ;; the best case among various matches, so we set
+                         ;; completion-ignore-case to avoid this needless work.
+                         (let ((completion-ignore-case nil))
+                           (try-completion prefix table pred)))))
         ;; The prefix has no completions at all, so we should try and fix
         ;; that first.
         (let ((substring (substring prefix 0 -1)))
Index: src/dired.c
RCS file: /sources/emacs/emacs/src/dired.c,v
retrieving revision 1.158
diff -u -r1.158 dired.c
--- src/dired.c 8 Jan 2009 03:15:31 -0000       1.158
+++ src/dired.c 17 Mar 2009 17:58:52 -0000
@@ -537,6 +537,16 @@
       if (!all_flag)
          int skip;
+         /* If this entry matches the current bestmatch, the only
+            thing it can do is increase matchcount, so don't bother
+            investigating it any further.  */
+         if (!completion_ignore_case
+             && matchcount > 1
+             && len >= bestmatchsize
+             && 0 >= scmp (dp->d_name, SDATA (bestmatch), bestmatchsize))
+           continue;
          if (directoryp)
@@ -683,6 +693,14 @@
          Lisp_Object zero = make_number (0);
+         /* If the best completion so far is the empty string,
+            there's no need to look any further.  */
+         if (bestmatchsize == 0
+             /* The return value depends on whether it's the sole match.  */
+             && matchcount > 1)
+           break;
          /* FIXME: This is a copy of the code in Ftry_completion.  */
          int compare = min (bestmatchsize, SCHARS (name));
          Lisp_Object tem

reply via email to

[Prev in Thread] Current Thread [Next in Thread]