From mboxrd@z Thu Jan 1 00:00:00 1970 From: Carsten Dominik Subject: Re: ido slow for outline path completion Date: Mon, 15 Dec 2008 10:36:01 +0100 Message-ID: <67E6FD56-F95F-4EEB-8BC3-4ED566B2ECAB@uva.nl> References: <20524da70812121204x9a23736g5a03f8a04d8213d5@mail.gmail.com> Mime-Version: 1.0 (Apple Message framework v929.2) Return-path: Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LC9rz-0007wj-5H for emacs-orgmode@gnu.org; Mon, 15 Dec 2008 04:36:07 -0500 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LC9rx-0007wK-Qe for emacs-orgmode@gnu.org; Mon, 15 Dec 2008 04:36:05 -0500 Received: from [199.232.76.173] (port=55512 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LC9rx-0007wH-Iw for emacs-orgmode@gnu.org; Mon, 15 Dec 2008 04:36:05 -0500 Received: from ug-out-1314.google.com ([66.249.92.171]:16149) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1LC9rx-0003TF-1V for emacs-orgmode@gnu.org; Mon, 15 Dec 2008 04:36:05 -0500 Received: by ug-out-1314.google.com with SMTP id 36so180577uga.17 for ; Mon, 15 Dec 2008 01:36:04 -0800 (PST) In-Reply-To: <20524da70812121204x9a23736g5a03f8a04d8213d5@mail.gmail.com> List-Id: "General discussions about Org-mode." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org Errors-To: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org To: Samuel Wales Cc: emacs-orgmode@gnu.org Hi Samuel, I am sure that both org and ido will contribute to a slow start of this command when the lists are long. ido does have a noticeable on performance, but that is more than outweighed by the speedup of using its commands. However, I believe the more significant problem may be in Org in this case. The refile interface was written with the idea that refile targets are a limited set of entries. So when Org constructs the list of refile targets, it first finds each target according to its criteria, and then it adds all necessary information. When using the outline path, it scans back from the entry to top level and records all the parents and grand parents. If this assumption that the possible targets are not a limited subset of all entries in a file fails, then this implementation is a bad one because it requires potentially N^2 operations where N is the number of entries in the file. There are several ways that could be used to improve this situation: 1. Compile Org! Are you using byte-compiled files? In a case like this, the differences may be significant. 2. Improve the way Org finds information about the outline tree. Currently it uses `outline-up-heading', which was written with arbitrary outline settings in mind, I could probably write an org-mode specific one that could be a lot faster. ... hack hack .... OK, I just did that, seems to speed up the Org part of it by a factor to 3 or so... Better, but still not quite acceptable, I guess..... 3. Cacheing: We could cache the refile targets - in fact the first implementation of this feature did that, but I stepped away from this later because it requires the user to decide when an update of the cache should happen, and it relies on searches for the headline text, which may fail if there are several identical headings in a file. 4. Create the list of headings with full outline path in a single path of the file, similar to the tags matcher. This would avoid the N^2 operation I discussed above. ...... OK, I did some profiling, implemented the single-path construction of outline paths for the case where this is possible (the :maxlevel case wich is also used by org-goto), and also removed a stupid file name comparison wich unnecessarily constructed a file-truename for each and every hit in the list. There is also a new variable `org-goto-max-level' with a default of 5. This should be *a lot* faster now. Thanks for the report! - Carsten On Dec 12, 2008, at 9:04 PM, Samuel Wales wrote: > ido for refiling works very well and makes refiling easier > by orders of magnitude. Thank you Eric. Thank you Carsten. > > In org 6.14, I find that full path completion (which is the > only way that org-goto can use ido) can take 22-45 seconds > before it shows you the prompt. This is on a 1ghz mac and > about a 300k org file with lots of nesting. > > Is there a way to speed this up? Offhand I imagine: > > - allow org-goto to limit the depth of the tree. i do > this for org-refile to depth 5. this takes 3-5 seconds. > - to achieve this i show only the basename. is it > possible with the full path in org-refile? > - of course, it would be better not to have limits and do > profiling/caching/..., but i don't know what the issues > could be. is it ido or org? is it sorting? > > Here are my settings for ido, goto, refile, and remember > refiling: > > (ido-mode 1) > (ido-everywhere 1) > (setf ido-confirm-unique-completion t) > > (setq org-completion-use-ido t) > ;;slow (45 seconds before prompt shows, a week or two ago > ;;2008-12-12). but this is what i want. would be even > ;;better with uniquify type disambiguation. > (setf org-outline-path-complete-in-steps nil) > > ;;slow with ido 2008-12-12. takes 22 seconds on about 300k > ;;org file on 1ghz mac. use 'outline for searching and > ;;org-occur and navigation. i prefer olpath. > (setf org-goto-interface 'outline-path-completion) > ;;t does not work with making help stuff one window. i think this > ;;is moot unless for some reason you want outline. > (setf org-goto-auto-isearch nil) > > ;;for speed, set level to 5 and set this to nil. for full > ;;path completion, set level to be unlimited and/or set this > ;;to t. > (setf org-refile-use-outline-path nil) > ;;this is as slow as setting org-goto-interface to > ;;olpath completion. > ;;(setf org-refile-use-outline-path t) > ;;i would use this functionality for both goto and refile if there > ;;were a uniquify type disambiguation scheme. > ;;(setf org-refile-use-outline-path 'file) > ;;this is the most candidates i can handle the slowness of. it > ;;takes 5 seconds or so on about 300k org file on a 1ghz mac. > (setq org-refile-targets '((org-agenda-files . (:maxlevel . 5)))) > > ;;can be re also. this is for refile and remember. > (setf org-reverse-note-order t) > > ;;default is to use refile interface, which is what i want > ;;(setf org-remember-interactive-interface ...) > > Thanks. > > -- > Myalgic encephalomyelitis denialists are knowingly causing further > suffering and death by opposing biomedical research on this serious > infectious disease. Do you care about the world? > http://www.meactionuk.org.uk/What_Is_ME_What_Is_CFS.htm > > > _______________________________________________ > Emacs-orgmode mailing list > Remember: use `Reply All' to send replies to the list. > Emacs-orgmode@gnu.org > http://lists.gnu.org/mailman/listinfo/emacs-orgmode