Org-mode mailing list
 help / color / mirror / Atom feed
From: Ihor Radchenko <yantar92@gmail.com>
To: emacs-orgmode@gnu.org
Subject: [PATCH] Use cache in org-up-heading-safe
Date: Tue, 04 May 2021 23:08:22 +0800
Message-ID: <874kfieduh.fsf@localhost> (raw)

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

Hello,

While testing another patch for agenda fontification, I noticed that
agenda can spend up to half!! time doing org-up-heading-safe. Mostly
inside queries for inherited tags and properties.

I managed to make org-up-heading-safe up to 50x faster using position
cache.

If this patch also works for others, org-agenda-use-tag-inheritance
might become much less of an issue.

Benchmark:

1. (elp-instrument-function #'org-up-heading-safe)
2. Run agenda
3. (elp-results) ;; function, # calls, total time, avg time

Without cache:
org-up-heading-safe  27555       8.4234025759  0.0003056941

With cache, first run:
org-up-heading-safe  23227       0.5300747539  2.282...e-05

With cache, second run on unchanged buffer:
org-up-heading-safe  23227       0.1447754880  6.233...e-06

Best,
Ihor


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Use-cache-in-org-up-heading-safe.patch --]
[-- Type: text/x-diff, Size: 4449 bytes --]

From fe1e7094a7b76ba6bf282c5c4409a32b36827d56 Mon Sep 17 00:00:00 2001
Message-Id: <fe1e7094a7b76ba6bf282c5c4409a32b36827d56.1620140628.git.yantar92@gmail.com>
From: Ihor Radchenko <yantar92@gmail.com>
Date: Tue, 4 May 2021 22:55:14 +0800
Subject: [PATCH] Use cache in org-up-heading-safe

* lisp/org.el (org-up-heading-safe): Use buffer-local cache to store
positions of parent headings.  The cache is invalidated when buffer
text is changed, according to `buffer-chars-modified-tick'.
(org--up-heading-cache):  Buffer-local hash-table storing the cache.
(org--up-heading-cache-tick):  The buffer modification state for
currently active `org--up-heading-cache'.

The optimisation is critical when running agenda or org-entry-get
queries using property/tag inheritance.  In such scenarios
`org-up-heading-safe' can be called thousands of times.  For example,
building todo agenda on large number of headings lead to the following
benchmark results:

Benchmark:

1. (elp-instrument-function #'org-up-heading-safe)
2. Run agenda
3. (elp-results) ;; function, # calls, total time, avg time

Without cache:
org-up-heading-safe  27555       8.4234025759  0.0003056941

With cache, first run:
org-up-heading-safe  23227       0.5300747539  2.282...e-05

With cache, second run on unchanged buffer:
org-up-heading-safe  23227       0.1447754880  6.233...e-06

The final speedup is 1-2 orders of magnitude (~15-56 times).
---
 lisp/org.el | 43 +++++++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index b8678359f..4385903ee 100644
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -19434,6 +19434,10 @@ (defun org-up-heading-all (arg)
 With argument, move up ARG levels."
   (outline-up-heading arg t))
 
+(defvar-local org--up-heading-cache (make-hash-table)
+  "Buffer-local `org-up-heading-safe' cache.")
+(defvar-local org--up-heading-cache-tick nil
+  "Buffer `buffer-chars-modified-tick' in `org--up-heading-cache'.")
 (defun org-up-heading-safe ()
   "Move to the heading line of which the present line is a subheading.
 This version will not throw an error.  It will return the level of the
@@ -19443,10 +19447,41 @@ (defun org-up-heading-safe ()
 because it relies on stars being the outline starters.  This can really
 make a significant difference in outlines with very many siblings."
   (when (ignore-errors (org-back-to-heading t))
-    (let ((level-up (1- (funcall outline-level))))
-      (and (> level-up 0)
-	   (re-search-backward (format "^\\*\\{1,%d\\} " level-up) nil t)
-	   (funcall outline-level)))))
+    (let ((level-cache (gethash (point) org--up-heading-cache)))
+      (if (and level-cache
+               (eq (buffer-chars-modified-tick) org--up-heading-cache-tick))
+          (when (<= (point-min) level-cache (point-max))
+            ;; Parent is inside accessible part of the buffer.
+            (progn (goto-char level-cache)
+                   (funcall outline-level)))
+        ;; Buffer modified.  Invalidate cache.
+        (when level-cache
+          (clrhash org--up-heading-cache)
+          (setq-local org--up-heading-cache-tick
+                      (buffer-chars-modified-tick)))
+        (let ((level-up (1- (funcall outline-level)))
+              (pos (point)))
+          (let (result)
+            (setq result
+                  (and (> level-up 0)
+	               (re-search-backward
+                        (format "^\\*\\{1,%d\\} " level-up) nil t)
+	               (funcall outline-level)))
+            (when result
+              (puthash pos (point) org--up-heading-cache))))))))
+;; (defun org-up-heading-safe ()
+;;   "Move to the heading line of which the present line is a subheading.
+;; This version will not throw an error.  It will return the level of the
+;; headline found, or nil if no higher level is found.
+
+;; Also, this function will be a lot faster than `outline-up-heading',
+;; because it relies on stars being the outline starters.  This can really
+;; make a significant difference in outlines with very many siblings."
+;;   (when (ignore-errors (org-back-to-heading t))
+;;     (let ((level-up (1- (funcall outline-level))))
+;;       (and (> level-up 0)
+;; 	   (re-search-backward (format "^\\*\\{1,%d\\} " level-up) nil t)
+;; 	   (funcall outline-level)))))
 
 (defun org-up-heading-or-point-min ()
   "Move to the heading line of which the present is a subheading, or point-min.
-- 
2.26.3


             reply	other threads:[~2021-05-04 15:05 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-05-04 15:08 Ihor Radchenko [this message]
2021-05-05 16:40 ` Maxim Nikulin
2021-05-06 14:34   ` Ihor Radchenko
2021-05-06 17:02     ` Maxim Nikulin
2021-05-07  2:08       ` Ihor Radchenko
2021-05-08 11:28         ` Maxim Nikulin
2021-05-10 15:14           ` Ihor Radchenko
2021-05-15 11:58         ` Bastien
2021-05-16  6:15 ` Bastien
2021-05-16  6:36   ` Ihor Radchenko
2021-05-16  8:53     ` Bastien

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://orgmode.org

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

  git send-email \
    --in-reply-to=874kfieduh.fsf@localhost \
    --to=yantar92@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

Org-mode mailing list

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://orgmode.org/list/0 list/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 list list/ https://orgmode.org/list \
		emacs-orgmode@gnu.org
	public-inbox-index list

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.yhetil.org/yhetil.emacs.orgmode
	nntp://news.gmane.io/gmane.emacs.orgmode


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git