emacs-orgmode@gnu.org archives
 help / color / mirror / code / Atom feed
From: Carsten Dominik <dominik@science.uva.nl>
To: Samuel Wales <samologist@gmail.com>
Cc: emacs-orgmode@gnu.org
Subject: Re: ido slow for outline path completion
Date: Mon, 15 Dec 2008 10:36:01 +0100	[thread overview]
Message-ID: <67E6FD56-F95F-4EEB-8BC3-4ED566B2ECAB@uva.nl> (raw)
In-Reply-To: <20524da70812121204x9a23736g5a03f8a04d8213d5@mail.gmail.com>

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

  reply	other threads:[~2008-12-15  9:36 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-12-12 20:04 ido slow for outline path completion Samuel Wales
2008-12-15  9:36 ` Carsten Dominik [this message]
2008-12-18 23:57   ` Samuel Wales
2008-12-19  8:39     ` Carsten Dominik
2008-12-19 18:04       ` Samuel Wales
2008-12-19 22:32         ` Samuel Wales
2008-12-21 11:49           ` Carsten Dominik
2008-12-21 11:49     ` Carsten Dominik
2008-12-21 21:24       ` Samuel Wales
2008-12-22  8:30         ` Carsten Dominik
2008-12-23 19:40           ` Samuel Wales

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.orgmode.org/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=67E6FD56-F95F-4EEB-8BC3-4ED566B2ECAB@uva.nl \
    --to=dominik@science.uva.nl \
    --cc=emacs-orgmode@gnu.org \
    --cc=samologist@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs/org-mode.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).