* bug#2445: 23.0.90; file name completion GCs a lot @ 2009-02-23 15:02 Richard M Stallman 2009-02-25 16:35 ` Stefan Monnier ` (2 more replies) 0 siblings, 3 replies; 10+ messages in thread From: Richard M Stallman @ 2009-02-23 15:02 UTC (permalink / raw) To: emacs-pretest-bug 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-02-23 15:02 bug#2445: 23.0.90; file name completion GCs a lot Richard M Stallman @ 2009-02-25 16:35 ` Stefan Monnier 2009-02-26 19:25 ` Richard M Stallman 2009-03-17 18:03 ` Stefan Monnier 2009-03-18 13:40 ` Stefan Monnier 2 siblings, 1 reply; 10+ messages in thread From: Stefan Monnier @ 2009-02-25 16:35 UTC (permalink / raw) To: rms; +Cc: emacs-pretest-bug, 2445 > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-02-25 16:35 ` Stefan Monnier @ 2009-02-26 19:25 ` Richard M Stallman 0 siblings, 0 replies; 10+ messages in thread From: Richard M Stallman @ 2009-02-26 19:25 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-pretest-bug, 2445 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-02-23 15:02 bug#2445: 23.0.90; file name completion GCs a lot Richard M Stallman 2009-02-25 16:35 ` Stefan Monnier @ 2009-03-17 18:03 ` Stefan Monnier 2009-03-19 19:37 ` Richard M Stallman 2009-03-18 13:40 ` Stefan Monnier 2 siblings, 1 reply; 10+ messages in thread From: Stefan Monnier @ 2009-03-17 18:03 UTC (permalink / raw) To: rms; +Cc: emacs-pretest-bug, 2445 > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-03-17 18:03 ` Stefan Monnier @ 2009-03-19 19:37 ` Richard M Stallman 2009-03-19 20:43 ` Stefan Monnier 0 siblings, 1 reply; 10+ messages in thread From: Richard M Stallman @ 2009-03-19 19:37 UTC (permalink / raw) To: Stefan Monnier, 2445; +Cc: emacs-pretest-bug, 2445 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-03-19 19:37 ` Richard M Stallman @ 2009-03-19 20:43 ` Stefan Monnier 2009-03-20 22:52 ` Richard M Stallman 0 siblings, 1 reply; 10+ messages in thread From: Stefan Monnier @ 2009-03-19 20:43 UTC (permalink / raw) To: rms; +Cc: emacs-pretest-bug, 2445 > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-03-19 20:43 ` Stefan Monnier @ 2009-03-20 22:52 ` Richard M Stallman 2009-03-21 1:41 ` Stefan Monnier 0 siblings, 1 reply; 10+ messages in thread From: Richard M Stallman @ 2009-03-20 22:52 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-pretest-bug, 2445 > 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-03-20 22:52 ` Richard M Stallman @ 2009-03-21 1:41 ` Stefan Monnier 0 siblings, 0 replies; 10+ messages in thread From: Stefan Monnier @ 2009-03-21 1:41 UTC (permalink / raw) To: rms; +Cc: emacs-pretest-bug, 2445 > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-02-23 15:02 bug#2445: 23.0.90; file name completion GCs a lot Richard M Stallman 2009-02-25 16:35 ` Stefan Monnier 2009-03-17 18:03 ` Stefan Monnier @ 2009-03-18 13:40 ` Stefan Monnier 2009-03-18 22:18 ` Richard M Stallman 2 siblings, 1 reply; 10+ messages in thread From: Stefan Monnier @ 2009-03-18 13:40 UTC (permalink / raw) To: rms; +Cc: emacs-pretest-bug, 2445 > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#2445: 23.0.90; file name completion GCs a lot 2009-03-18 13:40 ` Stefan Monnier @ 2009-03-18 22:18 ` Richard M Stallman 0 siblings, 0 replies; 10+ messages in thread From: Richard M Stallman @ 2009-03-18 22:18 UTC (permalink / raw) To: Stefan Monnier; +Cc: emacs-pretest-bug, 2445 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. ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2009-03-21 1:41 UTC | newest] Thread overview: 10+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2009-02-23 15:02 bug#2445: 23.0.90; file name completion GCs a lot Richard M Stallman 2009-02-25 16:35 ` Stefan Monnier 2009-02-26 19:25 ` Richard M Stallman 2009-03-17 18:03 ` Stefan Monnier 2009-03-19 19:37 ` Richard M Stallman 2009-03-19 20:43 ` Stefan Monnier 2009-03-20 22:52 ` Richard M Stallman 2009-03-21 1:41 ` Stefan Monnier 2009-03-18 13:40 ` Stefan Monnier 2009-03-18 22:18 ` Richard M Stallman
Code repositories for project(s) associated with this public inbox https://git.savannah.gnu.org/cgit/emacs.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).