From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms11 with LMTPS id yO2uBNaqQ2B3BgAA0tVLHw (envelope-from ) for ; Sat, 06 Mar 2021 16:16:22 +0000 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id +KhoANaqQ2CdBQAAbx9fmQ (envelope-from ) for ; Sat, 06 Mar 2021 16:16:22 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 79285CE76 for ; Sat, 6 Mar 2021 17:16:21 +0100 (CET) Received: from localhost ([::1]:50682 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lIZbI-0002DG-Mm for larch@yhetil.org; Sat, 06 Mar 2021 11:16:20 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:37428) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lIZam-0002D9-Fi for emacs-orgmode@gnu.org; Sat, 06 Mar 2021 11:15:48 -0500 Received: from ciao.gmane.io ([116.202.254.214]:55614) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lIZak-0000ll-Fh for emacs-orgmode@gnu.org; Sat, 06 Mar 2021 11:15:48 -0500 Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1lIZaf-000AOX-EZ for emacs-orgmode@gnu.org; Sat, 06 Mar 2021 17:15:41 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: emacs-orgmode@gnu.org From: Maxim Nikulin Subject: [PATCH] optimize org-refile-get-targets Date: Sat, 6 Mar 2021 23:15:35 +0700 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------4B8CFD31830C9217CEF1F988" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.7.1 In-Reply-To: Content-Language: en-US Received-SPF: pass client-ip=116.202.254.214; envelope-from=geo-emacs-orgmode@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: 28 X-Spam_score: 2.8 X-Spam_bar: ++ X-Spam_report: (2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, FORGED_GMAIL_RCVD=1, FORGED_MUA_MOZILLA=2.309, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, NML_ADSP_CUSTOM_MED=0.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-orgmode@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "General discussions about Org-mode." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-orgmode-bounces+larch=yhetil.org@gnu.org Sender: "Emacs-orgmode" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1615047381; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post; bh=fB14Ytm06SMdZLwLa7iq9hNQ5HcOmrIr/Eommi8tUz4=; b=fwLuw1Rq/t81pSksMQQQKPfhDszT3bqRkd8ziguON79Jrd6EljG/Kf2+TxmNFN5PcW2W8O +FOlVDWJGqYbHnOs8eNE5yrl8k1tnsDccWkdzqBvT/gMd5LgrNXzxwChSa1tvYdk469wt7 KIYbTYDwOfYGfYlUrt6JmrIMopp/Q19baE0wfejMnQmlRAhu1HTiJNrI1uavvATGT4Tdkc 3sqzuorU3ZLGHUr6MzF/g6FeOfU7AdMFnbG4GcX+Yw6TlUJOd+5c86/TVv9wst3Yu4/9dV yMvxWSOIUVFKc5fMusxkHYA3nT5GtIHpvDWDhm1YxJwIaR678BeAiWkiBkUwpA== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1615047381; a=rsa-sha256; cv=none; b=O4sU9jXXTRv6cDwJBqQU/Tr76MGnT3oJsUIf2nq04jb2HshqhQdcVuq7o8ZqxU0JQgjA4l wX/zAYcEXOzaSxXUxJ9SSQKrUBaWg4qE/WTWDgCPEMxg5wx7aQTZIluZAlXm96Lll7lGPr NcqWgPjfCVjAQruMDkC+BLCr/b96DgSgjSLLrV27zbLUevTohCJ76L/pzOR0As8ZC8apK1 CFKZpn4MBw3gVuaU3SZn6O3OzHIBH+dhPl6ObRS/lEYQV8KtS3L9CODExrTawC9aKFc3tW LELmPvixR2rievWKh9xCR6HiVGlWSPEYYuiPE6K35PbaeJPY1LjzRjFpl+KlKw== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=none; spf=pass (aspmx1.migadu.com: domain of emacs-orgmode-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=emacs-orgmode-bounces@gnu.org X-Migadu-Spam-Score: -1.77 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=fail reason="SPF not aligned (relaxed), No valid DKIM" header.from=gmail.com (policy=none); spf=pass (aspmx1.migadu.com: domain of emacs-orgmode-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=emacs-orgmode-bounces@gnu.org X-Migadu-Queue-Id: 79285CE76 X-Spam-Score: -1.77 X-Migadu-Scanner: scn0.migadu.com X-TUID: 5f8WZDZ7WWHa This is a multi-part message in MIME format. --------------4B8CFD31830C9217CEF1F988 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit 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. --------------4B8CFD31830C9217CEF1F988 Content-Type: text/x-patch; charset=UTF-8; name="refile-get-targets-outline-path-tests.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="refile-get-targets-outline-path-tests.patch" commit 45cfa5b15e9009fee4f6a688caa210ff543b1ac1 Author: Max Nikulin 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" (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 --------------4B8CFD31830C9217CEF1F988 Content-Type: text/x-patch; charset=UTF-8; name="refile-get-targets-outline-path-optimize.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="refile-get-targets-outline-path-optimize.patch" commit 58b477e999f3bb5b48c39fe0a4e5ad0d37e2bb9d Author: Max Nikulin 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))) --------------4B8CFD31830C9217CEF1F988--