emacs-orgmode@gnu.org archives
 help / color / mirror / code / Atom feed
From: Maxim Nikulin <manikulin@gmail.com>
To: emacs-orgmode@gnu.org
Subject: [PATCH] optimize org-refile-get-targets
Date: Sat, 6 Mar 2021 23:15:35 +0700	[thread overview]
Message-ID: <s209r8$16en$1@ciao.gmane.io> (raw)
In-Reply-To: <CAJcAo8tmH9HuaozCnJyrcJiBTfXLPvXDj4gBPFMn5kAZwm0HGA@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 705 bytes --]

On 05/03/2021 04:03, Samuel Wales wrote:
> interesting.  that would be great to speed it up.  [i just meant that
> the file list used to be correct.]

I am a bit disappointed. I have managed to get x2 performance boost. At 
first, the result was x2 better but I realized that I did not added 
heading cleanup for the new strategy. It adds several regexp to the 
inner loop and severely hits performance. I do not like the idea to 
manually inline (with minor variations) existing functions and regexps, 
but the function is still slow.

For a while, improvement is significant, so I am attaching the patch 
that should make jumps using org-goto or org-refile faster. I hope, I 
have not broken anything.


[-- Attachment #2: refile-get-targets-outline-path-tests.patch --]
[-- Type: text/x-patch, Size: 2012 bytes --]

commit 45cfa5b15e9009fee4f6a688caa210ff543b1ac1
Author: Max Nikulin <manikulin@gmail.com>
Date:   Sat Mar 6 22:14:39 2021 +0700

    testing/lisp/test-org.el: More tests for `org-refile-get-targets'
    
    testing/lisp/test-org.el (test-org/refile-get-targets): Add a few more
    cases for the `org-refile-get-targets' function.
    
    - Fraction of completed subtasks is removed from heading.
    - `:level' filter ignores headings having over levels.
    - Outline path works with `:tag' filter.
    
    The aim is to increase coverage for experiments with optimizing
    of the function.

diff --git a/testing/lisp/test-org.el b/testing/lisp/test-org.el
index 2d727ba7a..da313b45b 100644
--- a/testing/lisp/test-org.el
+++ b/testing/lisp/test-org.el
@@ -6369,6 +6369,27 @@ Paragraph<point>"
 	    (let ((org-refile-use-outline-path t)
 		  (org-refile-targets `((nil :maxlevel . 1))))
 	      (mapcar #'car (org-refile-get-targets))))))
+  ;; When providing targets as paths, clean fraction cookie.
+  (should
+   (equal '("H1")
+	  (org-test-with-temp-text "* H1 [1/1]"
+	    (let ((org-refile-use-outline-path t)
+		  (org-refile-targets '((nil :maxlevel . 1))))
+	      (mapcar #'car (org-refile-get-targets))))))
+  ;; When providing targets as paths, intermediate paths are cached correctly.
+  (should
+   (equal '("H1/H2")
+	  (org-test-with-temp-text "* Skip 1\n* H1\n*** Skip 2\n** H2\n*** Skip 3"
+	    (let ((org-refile-use-outline-path t)
+		  (org-refile-targets '((nil :level . 2))))
+	      (mapcar #'car (org-refile-get-targets))))))
+  ;; When providing targets as paths, they are obtained correctly.
+  (should
+   (equal '("H1/H2" "H3")
+	  (org-test-with-temp-text "* Skip 1\n* H1\n** Skip 2\n** H2 :take:\n* H3 :take:"
+	    (let ((org-refile-use-outline-path t)
+		  (org-refile-targets '((nil :tag . "take"))))
+	      (mapcar #'car (org-refile-get-targets))))))
   ;; When `org-refile-use-outline-path' is `file', include file name
   ;; without directory in targets.
   (should

[-- Attachment #3: refile-get-targets-outline-path-optimize.patch --]
[-- Type: text/x-patch, Size: 4030 bytes --]

commit 58b477e999f3bb5b48c39fe0a4e5ad0d37e2bb9d
Author: Max Nikulin <manikulin@gmail.com>
Date:   Sat Mar 6 22:44:27 2021 +0700

    lisp/org-refile.el: Speed up `org-refile-get-targets'
    
    lisp/org-refile.el (org-refile-get-targets): Optimize performance
    by eliminating backward lookup of already seen headers.
    
    If configuration allows it, incrementally update current outline path.
    For dense target trees (`:maxlevel' and `:level') it allows to avoid
    "one step forward, two steps back" strategy that requires multiple
    backward searches for deeply nested headings.

diff --git a/lisp/org-refile.el b/lisp/org-refile.el
index 4e9f26eff..8e760f1c3 100644
--- a/lisp/org-refile.el
+++ b/lisp/org-refile.el
@@ -267,7 +267,8 @@ converted to a headline before refiling."
   (let ((case-fold-search nil)
 	;; otherwise org confuses "TODO" as a kw and "Todo" as a word
 	(entries (or org-refile-targets '((nil . (:level . 1)))))
-	targets tgs files desc descre)
+	targets tgs files desc descre
+	outline-path cache-outline-path target-outline-level)
     (message "Getting targets...")
     (with-current-buffer (or default-buffer (current-buffer))
       (dolist (entry entries)
@@ -281,6 +282,11 @@ converted to a headline before refiling."
 	 ((and (symbolp files) (boundp files))
 	  (setq files (symbol-value files))))
 	(when (stringp files) (setq files (list files)))
+	(setq cache-outline-path (and org-refile-use-outline-path
+				      (memq (car desc) '(:level :maxlevel))))
+	(setq target-outline-level
+	      (if (and cache-outline-path (eq (car desc) :level))
+		  (if org-odd-levels-only (1- (* 2 (cdr desc))) (cdr desc))))
 	(cond
 	 ((eq (car desc) :tag)
 	  (setq descre (concat "^\\*+[ \t]+.*?:" (regexp-quote (cdr desc)) ":")))
@@ -288,13 +294,13 @@ converted to a headline before refiling."
 	  (setq descre (concat "^\\*+[ \t]+" (regexp-quote (cdr desc)) "[ \t]")))
 	 ((eq (car desc) :regexp)
 	  (setq descre (cdr desc)))
-	 ((eq (car desc) :level)
+	 ((and (not target-outline-level) (eq (car desc) :level))
 	  (setq descre (concat "^\\*\\{" (number-to-string
 					  (if org-odd-levels-only
 					      (1- (* 2 (cdr desc)))
 					    (cdr desc)))
 			       "\\}[ \t]")))
-	 ((eq (car desc) :maxlevel)
+	 ((memq (car desc) '(:level :maxlevel))
 	  (setq descre (concat "^\\*\\{1," (number-to-string
 					    (if org-odd-levels-only
 						(1- (* 2 (cdr desc)))
@@ -318,13 +324,30 @@ converted to a headline before refiling."
 	       (org-with-wide-buffer
 		(goto-char (point-min))
 		(setq org-outline-path-cache nil)
+		(setq outline-path nil)
 		(while (re-search-forward descre nil t)
 		  (beginning-of-line)
 		  (let ((case-fold-search nil))
 		    (looking-at org-complex-heading-regexp))
 		  (let ((begin (point))
-			(heading (match-string-no-properties 4)))
-		    (unless (or (and
+			(heading (match-string-no-properties 4))
+			(heading-level (length (match-string-no-properties 1))))
+		    (when cache-outline-path
+		      (while (and outline-path (<= heading-level (caar outline-path)))
+			(pop outline-path))
+		      (push (cons heading-level
+				  ;; Taken from org--get-outline-path-1. It is really slow.
+				  (if (not heading)
+				      ""
+				    (org-trim
+				     (org-link-display-format
+				      (replace-regexp-in-string
+				       "\\[[0-9]+%\\]\\|\\[[0-9]+/[0-9]+\\]" ""
+				       heading)))))
+			    outline-path))
+		    (unless (or (and target-outline-level
+				    (not (eq heading-level target-outline-level)))
+				(and
 				 org-refile-target-verify-function
 				 (not
 				  (funcall org-refile-target-verify-function)))
@@ -349,7 +372,9 @@ converted to a headline before refiling."
 				   (_ nil))
 				 (mapcar (lambda (s) (replace-regexp-in-string
 						      "/" "\\/" s nil t))
-					 (org-get-outline-path t t)))
+					 (if outline-path
+					     (nreverse (mapcar #'cdr outline-path))
+					   (org-get-outline-path t t))))
 				"/"))))
 			(push (list target f re (org-refile-marker (point)))
 			      tgs)))

  reply	other threads:[~2021-03-06 16:16 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-03-02 17:15 org-refile-use-cache and jumps using org-refile or org-goto Maxim Nikulin
2021-03-03  2:34 ` Samuel Wales
2021-03-04 13:51   ` Maxim Nikulin
2021-03-04 21:03     ` Samuel Wales
2021-03-06 16:15       ` Maxim Nikulin [this message]
2021-04-25 12:25         ` [PATCH] optimize org-refile-get-targets Bastien
2021-04-25 15:24           ` Maxim Nikulin
2021-03-04 14:47 ` org-refile failed due to default option stored by org-goto Maxim Nikulin
2021-03-04 22:53   ` Samuel Wales
2021-03-09 11:57     ` Maxim Nikulin

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='s209r8$16en$1@ciao.gmane.io' \
    --to=manikulin@gmail.com \
    --cc=emacs-orgmode@gnu.org \
    /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).