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

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

[Richard M Stallman]

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)
    "completion--file-name-table" (0x7fbe26c4)
    "complete-with-action" (0x7fbe29a4)
    0x87978c PVEC_COMPILED
    "byte-code" (0x7fbe2f14)
    "completion--some" (0x7fbe33b4)
    0x8797dc PVEC_COMPILED
    "apply" (0x7fbe3710)
    "read-file-name-internal" (0x7fbe38f4)
    "try-completion" (0x7fbe3a74)
    "completion-pcm--find-all-completions" (0x7fbe3f2c)
    "completion-pcm-try-completion" (0x7fbe4214)
    0x879d04 PVEC_COMPILED
    "byte-code" (0x7fbe4784)
    "completion--some" (0x7fbe4c24)
    "completion-try-completion" (0x7fbe4f04)
    "completion--do-completion" (0x7fbe51f4)
    "minibuffer-complete" (0x7fbe550c)
    "call-interactively" (0x7fbe5764)
    "completing-read" (0x7fbe5ebc)
    "read-file-name" (0x7fbe61ac)
    "find-file-read-args" (0x7fbe648c)
    "byte-code" (0x7fbe671c)
    "call-interactively" (0x7fbe69c4)

I think that is because of the partial completion feature
that is now enabled by default and was not before.

I don't notice (or mind) the feature itself.  But the delay
is a real pain whenever I make a typo in these names.
I think the feature should be disabled by default
if it can't be made fast enough to run in half a second.

This is on the Lemote Yeelong mini-laptop.



In GNU Emacs 23.0.90.4 (mipsel-unknown-linux-gnu, GTK+ Version 2.12.11)
 of 2009-02-23 on lemote-yeeloong
configured using `configure  'CFLAGS=-O0 -g -Wno-pointer-sign' 'mipsel-unknown-linux-gnu' 'build_alias=mipsel-unknown-linux-gnu' 'host_alias=mipsel-unknown-linux-gnu' 'target_alias=mipsel-unknown-linux-gnu''

Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: nil
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: nil
  value of $LANG: en_US.UTF-8
  value of $XMODIFIERS: nil
  locale-coding-system: utf-8-unix
  default-enable-multibyte-characters: t

Major mode: Emacs-Lisp

Minor modes in effect:
  gpm-mouse-mode: t
  tooltip-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  global-auto-composition-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t
  abbrev-mode: t

Recent input:
C-x b RET C-z o x m a i l / f o o x TAB C-z C-g o x 
a i DEL DEL m a i l / f o o x TAB C-g C-z C-x C-g ESC 
x C-g C-h f r e o DEL p o r t - f i l e - ESC DEL ESC 
DEL r e a d - f i e - DEL DEL l e - n a m e - i n t 
e r n a l RET C-x o TAB RET C-x 1 ESC x r e p o r t 
SPC e m a s DEL c s SPC b u g RET

Recent messages:
Loading paren...done
Note: file is write protected [2 times]
Counting messages...done
(No new mail has arrived)
0 new messages read
For information about GNU Emacs and the GNU system, type C-h C-a.
Quit [3 times]
Type C-x 4 C-o RET to restore the other window.
mouse-2, RET: find function's definition
Loading vc-cvs...done

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

[Stefan Monnier]

> 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)
>     "completion--file-name-table" (0x7fbe26c4)
>     "complete-with-action" (0x7fbe29a4)
>     0x87978c PVEC_COMPILED
>     "byte-code" (0x7fbe2f14)
>     "completion--some" (0x7fbe33b4)
>     0x8797dc PVEC_COMPILED
>     "apply" (0x7fbe3710)
>     "read-file-name-internal" (0x7fbe38f4)
>     "try-completion" (0x7fbe3a74)
>     "completion-pcm--find-all-completions" (0x7fbe3f2c)
>     "completion-pcm-try-completion" (0x7fbe4214)
>     0x879d04 PVEC_COMPILED
>     "byte-code" (0x7fbe4784)
>     "completion--some" (0x7fbe4c24)
>     "completion-try-completion" (0x7fbe4f04)
>     "completion--do-completion" (0x7fbe51f4)
>     "minibuffer-complete" (0x7fbe550c)
>     "call-interactively" (0x7fbe5764)
>     "completing-read" (0x7fbe5ebc)
>     "read-file-name" (0x7fbe61ac)
>     "find-file-read-args" (0x7fbe648c)
>     "byte-code" (0x7fbe671c)
>     "call-interactively" (0x7fbe69c4)

> I think that is because of the partial completion feature
> that is now enabled by default and was not before.

It may be, indeed.  But there's no good reason why it should be much
slower in such a circumstance.  A factor of 2 slowdown should be
expected, but not much more than that since the "xmail/foox" pattern
doesn't offer much opportunity for partial completion.
So it sounds more like an implementation inefficiency somewhere.


        Stefan

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

[Richard M Stallman]

    It may be, indeed.  But there's no good reason why it should be much
    slower in such a circumstance.  A factor of 2 slowdown should be
    expected, but not much more than that since the "xmail/foox" pattern
    doesn't offer much opportunity for partial completion.
    So it sounds more like an implementation inefficiency somewhere.

If you can speed it up, that would be a fine solution to this bug
report.  But otherwise I think the feature should be disabled.

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

[Stefan Monnier]

> 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?


        Stefan


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)
 	    {
 #ifndef TRIVIAL_DIRECTORY_ENTRY
@@ -683,6 +693,14 @@
       else
 	{
 	  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

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

[Stefan Monnier]

> 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)

Indeed, the new partial-completion code triggers an inefficiency in
file-name-completion.  I've installed a patch which should significantly
reduce the problem (at least in my test case, tho I had to use
a directory with 100K files to reproduce a problem that seems similar to
yours).


        Stefan

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

[Richard M Stallman]

    Indeed, the new partial-completion code triggers an inefficiency in
    file-name-completion.  I've installed a patch which should significantly
    reduce the problem (at least in my test case, tho I had to use
    a directory with 100K files to reproduce a problem that seems similar to
    yours).

I think you fixed it.  The cases that were slow before are fast now.
Thanks.

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

[Richard M Stallman]

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

The problem in my real cases is fixed given the sources as of
yesterday.  It looks like you've identified fixes to other big
slowdowns that arise in yet larger test cases.  I don't need them,
but now that you've written them, you may as well install them
unless they will cause trouble for someone.

    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/").

I have a feeling that (file-name-completion "" "xmail/") ought to
first check (file-directory-p "xmail/") and return t if that does.  In
other words, if the buffer contains a valid directory name, completion
should treat that as fixed.  It should only try to do completion on
previous file name components when they don't match existing names.

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

[Stefan Monnier]

>     Can you try the patch below to confirm it fixes your problem?
> The problem in my real cases is fixed given the sources as of
> yesterday.  It looks like you've identified fixes to other big
> slowdowns that arise in yet larger test cases.  I don't need them,
> but now that you've written them, you may as well install them
> unless they will cause trouble for someone.

Sorry about the email confusion: I wrote and sent the second email
first, but it got stuck on its machine and only got delivered much
later, at which point I had written the second email and installed the
fix already.

>     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/").

> I have a feeling that (file-name-completion "" "xmail/") ought to
> first check (file-directory-p "xmail/") and return t if that does.

No: if all files in xmail/ start with "aba", then the above should
return "aba".


        Stefan

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

[Richard M Stallman]

    > I have a feeling that (file-name-completion "" "xmail/") ought to
    > first check (file-directory-p "xmail/") and return t if that does.

    No: if all files in xmail/ start with "aba", then the above should
    return "aba".

I am not convinced it should do that.  Maybe
(file-name-completion "xmail" "") should do that,
but I tend to think that (file-name-completion "" "xmail/"), with the
empty string as file name, should not complete anything.

There is a semantic confusion going on here.
The question that (try-completion "xmail/" table) answers
is not the question that its caller wants to ask.

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

[Stefan Monnier]

>     No: if all files in xmail/ start with "aba", then the above should
>     return "aba".

> I am not convinced it should do that.

If I type "C-x C-f foo/ TAB", I want it to complete to "foo/bar" if bar
is the only member of that directory (ignoring ., .., CVS/ and other
such things, of course).

What you're suggesting is a significant change to the semantics of
file-name-completion.


        Stefan