Re: [PATCH] Use cache in org-up-heading-safe

[Ihor Radchenko]

Maxim Nikulin <manikulin@gmail.com> writes:

> Though I still have not tested the patch, I think, it is an improvement 
> and it is helpful in its current form. I am unable to tell if it follows 
> code style.

FYI, this patch may also slightly improve the performance of
org-get-outline-path.

> My bad, you mentioned tags earlier, but I grepped org-agenda.el only.
> My new idea is that org-get-tags may have its own cache as well. Unsure 
> if it should be tried.

I am trying it now ;) No benchmarks yet, but it also provides a
subjective improvement. However, I am trying to reuse org-element-cache
for tags. org-element-cache is smart enough to update itself partially
on buffer changes. However, there are (known) bugs in org-element-cache.
I managed to track down some, but still need to test thoughtfully before
submitting upstream.

> Did you just replace gethash by avl-tree?

Yes

> Likely my idea is based on a 
> wrong assumption. I hoped that having positions of headers it is 
> possible to avoid jumps (goto-char ...) preceded or followed by regexp 
> matching almost completely. Previous header for arbitrary initial 
> position can be found using binary search through structure obtained 
> during scan.

Sorry, I cannot follow what you mean. The call to goto-char in
org-up-heading-safe is required by function docstring - we need to move
point to the parent heading.

>> +                        (re-search-backward
>> +                             (format "^\\*\\{1,%d\\} " level-up) nil t)
>> +                        (funcall outline-level))))
>
> Unsure concerning the following optimization from the point of 
> readability and reliability in respect to future modifications. Outline 
> level can be derived from the length of matched string without the 
> funcall requiring extra regexp.

I am not sure here. outline-level also consults outline-heading-alist,
though I found no references to that variable in Org mode code.
Otherwise, outline-level already reuses match-data. There is no regexp
matching there. 

P.S. I just found that hash-tables are created by reference, so we need
to call make-hash-table separately in each buffer with cache. Updated
patch attached.

>From 08a175752b14f84767a71665773aa64807606af4 Mon Sep 17 00:00:00 2001
Message-Id: 
<08a175752b14f84767a71665773aa64807606af4.1620316036.git.yantar92@gmail.com>
From: Ihor Radchenko <yantar92@gmail.com>
Date: Thu, 6 May 2021 14:13:20 +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 | 30 ++++++++++++++++++++++++++----
 1 file changed, 26 insertions(+), 4 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index 0ff13c79c..7c58f0e2e 100644
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -20440,6 +20440,10 @@ (defun org-up-heading-all (arg)
 With argument, move up ARG levels."
   (outline-up-heading arg t))
 
+(defvar-local org--up-heading-cache nil
+  "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
@@ -20449,10 +20453,28 @@ (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)
+      (unless org--up-heading-cache
+        (setq org--up-heading-cache (make-hash-table)))
+      (if (and (eq (buffer-chars-modified-tick) org--up-heading-cache-tick)
+               (setq level-cache (gethash (point) org--up-heading-cache)))
+          (when (<= (point-min) (car level-cache) (point-max))
+            ;; Parent is inside accessible part of the buffer.
+            (progn (goto-char (car level-cache))
+                   (cdr level-cache)))
+        ;; Buffer modified.  Invalidate cache.
+        (unless (eq (buffer-chars-modified-tick) org--up-heading-cache-tick)
+          (setq-local org--up-heading-cache-tick
+                      (buffer-chars-modified-tick))
+          (clrhash org--up-heading-cache))
+        (let* ((level-up (1- (funcall outline-level)))
+               (pos (point))
+               (result (and (> level-up 0)
+                           (re-search-backward
+                             (format "^\\*\\{1,%d\\} " level-up) nil t)
+                           (funcall outline-level))))
+          (when result (puthash pos (cons (point) result) 
org--up-heading-cache))
+          result)))))
 
 (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