From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.bugs,gmane.emacs.pretest.bugs Subject: bug#2445: 23.0.90; file name completion GCs a lot Date: Tue, 17 Mar 2009 14:03:38 -0400 Message-ID: References: Reply-To: Stefan Monnier , 2445@emacsbugs.donarmstrong.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1237434245 10626 80.91.229.12 (19 Mar 2009 03:44:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 19 Mar 2009 03:44:05 +0000 (UTC) Cc: emacs-pretest-bug@gnu.org, 2445@emacsbugs.donarmstrong.com To: rms@gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Mar 19 04:45:21 2009 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1Lk9C4-00037q-3k for geb-bug-gnu-emacs@m.gmane.org; Thu, 19 Mar 2009 04:45:21 +0100 Original-Received: from localhost ([127.0.0.1]:35364 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Lk9Ah-00048Y-OA for geb-bug-gnu-emacs@m.gmane.org; Wed, 18 Mar 2009 23:43:55 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Lk9Ad-00048T-JM for bug-gnu-emacs@gnu.org; Wed, 18 Mar 2009 23:43:51 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Lk9AY-00045X-Du for bug-gnu-emacs@gnu.org; Wed, 18 Mar 2009 23:43:51 -0400 Original-Received: from [199.232.76.173] (port=50950 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Lk9AY-00045N-At for bug-gnu-emacs@gnu.org; Wed, 18 Mar 2009 23:43:46 -0400 Original-Received: from rzlab.ucr.edu ([138.23.92.77]:57900) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1Lk9AX-0007HU-I9 for bug-gnu-emacs@gnu.org; Wed, 18 Mar 2009 23:43:45 -0400 Original-Received: from rzlab.ucr.edu (rzlab.ucr.edu [127.0.0.1]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n2J3hh8f020030; Wed, 18 Mar 2009 20:43:43 -0700 Original-Received: (from debbugs@localhost) by rzlab.ucr.edu (8.13.8/8.13.8/Submit) id n2J3P5ri015035; Wed, 18 Mar 2009 20:25:05 -0700 X-Loop: owner@emacsbugs.donarmstrong.com Resent-From: Stefan Monnier Resent-To: bug-submit-list@donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Thu, 19 Mar 2009 03:25:05 +0000 Resent-Message-ID: Resent-Sender: owner@emacsbugs.donarmstrong.com X-Emacs-PR-Message: followup 2445 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Original-Received: via spool by submit@emacsbugs.donarmstrong.com id=B.123743291414758 (code B ref -1); Thu, 19 Mar 2009 03:25:05 +0000 Original-Received: (at submit) by emacsbugs.donarmstrong.com; 19 Mar 2009 03:21:54 +0000 X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. Original-Received: from fencepost.gnu.org (fencepost.gnu.org [140.186.70.10]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n2J3Lo1H014750 for ; Wed, 18 Mar 2009 20:21:52 -0700 Original-Received: from mx10.gnu.org ([199.232.76.166]:35420) by fencepost.gnu.org with esmtp (Exim 4.67) (envelope-from ) id 1Lk8pJ-0000Nv-Tn for emacs-pretest-bug@gnu.org; Wed, 18 Mar 2009 23:21:50 -0400 Original-Received: from Debian-exim by monty-python.gnu.org with spam-scanned (Exim 4.60) (envelope-from ) id 1Lk8pI-0004rc-PU for emacs-pretest-bug@gnu.org; Wed, 18 Mar 2009 23:21:49 -0400 Original-Received: from ironport2-out.pppoe.ca ([206.248.154.182]:38426 helo=ironport2-out.teksavvy.com) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1Lk8pI-0004rY-D5; Wed, 18 Mar 2009 23:21:48 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgwFAK5XwUlFxIZP/2dsb2JhbACBT9F2g34GhF8 X-IronPort-AV: E=Sophos;i="4.38,386,1233550800"; d="scan'208";a="35386098" Original-Received: from 69-196-134-79.dsl.teksavvy.com (HELO ceviche.home) ([69.196.134.79]) by ironport2-out.teksavvy.com with ESMTP; 18 Mar 2009 23:21:47 -0400 Original-Received: by ceviche.home (Postfix, from userid 20848) id E2D03B40E2; Tue, 17 Mar 2009 14:03:38 -0400 (EDT) In-Reply-To: (Richard M. Stallman's message of "Mon, 23 Feb 2009 10:02:46 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.90 (gnu/linux) X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Resent-Date: Wed, 18 Mar 2009 23:43:51 -0400 X-BeenThere: bug-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:26474 gmane.emacs.pretest.bugs:24154 Archived-At: > 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