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

[Ihor Radchenko <yantar92@gmail.com>]

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

Maxim Nikulin <manikulin@gmail.com> writes:

> I am trying to minimize number of regexp searches. Mostly it is applied 
> when information concerning multiple headings is required (agenda, 
> refile targets). It unlikely will get some benefits during interactive 
> calls related to single heading.

> Having the tree, it is possible to instantly find heading for 
> *arbitrary* position in the buffer. Likely the next operation is goto to 
> the heading or to it parent and parsing the line for more detailed 
> properties. The latter is cacheable, structure for heading properties 
> can be expanded.

Thanks for the explanation! I very much like this idea, though I do not
think that it is going to be practical on actual large files. Your code
runs for 0.25sec on my largest file:

| scan x10                         | 2.482179163 | 1 | 0.38996822200002157 |
| btree x10                        | 0.103329151 | 0 |                 0.0 |
| scan+btree x10                   | 2.666915096 | 1 |  0.3657946569999808 |
| find random x10 000              | 0.048668756 | 0 |                 0.0 |
| nodes                            |       16641 |   |                     |

> Since there is no operations as insertion or deletion of nodes from 
> tree, no complex code is required to implement balancing rotations. That 
> is why I think that avl-tree is an overkill.

Yet, if we could keep the tree in sync with buffer modifications... And
we can, using org-element-cache. It already uses AVL-tree and already
syncs it automatically on buffer edits. The only problem is that it does
not work with headlines. However, I wrote some code adding headline
support to org-element-cache in https://github.com/yantar92/org.

Some benchmarks:

| scan x10                                 |        2.179845106 | 0 |               0.0 |
| btree x10                                |        0.474887597 | 1 | 0.364201286999986 |
| scan+btree x10                           |        2.318029902 | 0 |               0.0 |
| scan using org-element-cache x10         | 2.8941826990000004 | 0 |               0.0 |
| populating the cache x1                  |       11.332366941 | 5 | 2.040159146999997 |
| find random x10 000                      |        0.053074866 | 0 |               0.0 |
| find random in org-element-cache x10 000 |        0.007963375 | 0 |               0.0 |
| nodes                                    |              16641 |   |                   |

Scan through the file takes pretty much the same time with the btree
approach. Sometimes more, sometimes less. And most of the time is really
just re-search-forward. Find random showcases that avl-tree vs. btree
really makes a difference on such large number of headings.

On the worse side, initial population of the org-element-cache takes
quite a bit of time. However, it is normally done asynchronously during
idle time and does not really affect the user except the first loading
(which might be further optimised if we store cache between Emacs
sessions). Later, cache is updated automatically with buffer
modifications.

Moreover, the org-element-cache will already provide the parsed
headlines, including titles (and tags and other useful staff). No need
to match headline text with regexp.

For me, the idea of storing headlines in cache looks promising. I can
imagine many other Org functions using the cache after trivial
modifications. At least org-get-tags, org-get-category, org-entry-get
can be easily adapted to use the cache. What do you think?

> See the attachment for experimental (thus almost untested) code. Likely 
> you will find code style quite ugly. I am not happy with 0.1 sec for a 
> moderately large file. It is close to the limit for comfortable 
> interactive operations.

No worries about the style. It is testing anyway.

I modified your code slightly for testing the org-element-cache. See the
attached diff.

Best,
Ihor


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: diff-btree.diff --]
[-- Type: text/x-diff, Size: 3548 bytes --]

diff -u /tmp/nm-btree-1.org /tmp/nm-btree.org
--- /tmp/nm-btree-1.org	2021-05-10 23:04:21.286395360 +0800
+++ /tmp/nm-btree.org	2021-05-10 23:02:17.586396326 +0800
@@ -1,3 +1,6 @@
+:PROPERTIES:
+:ID:       0aba93db-491d-46f7-b952-e138ba179a12
+:END:
 
 #+begin_src elisp :results none
 
@@ -38,6 +41,26 @@
 		(push props parents))))
 	  (and headings (cons headings count)))))))
 
+(defun nm-buffer-headings-reversed-cache (buffer)
+  (with-current-buffer buffer
+    (save-restriction
+      (save-excursion
+	(widen)
+	(goto-char (point-min))
+	(let ((count 0)
+	      (headings ())
+	      (parents ()))
+	  (while (re-search-forward org-outline-regexp-bol nil t)
+            (let ((cached (org-element--cache-find (line-beginning-position))))
+              (if (eq (org-element-property :begin cached) (line-beginning-position))
+                  (push cached headings)
+                (push (org-element-at-point) headings)))
+            
+            ;; (save-excursion
+            ;;   (beginning-of-line)
+            ;;   (org-element-at-point 'cached))
+            ))))))
+
 
 ;; binary search tree
 (defun nm-btree-new-node ()
@@ -103,6 +126,7 @@
 
 #+begin_src elisp
 (byte-compile #'nm-buffer-headings-reversed)
+(byte-compile #'nm-buffer-headings-reversed-cache)
 (byte-compile #'nm-btree-from-reversed)
 (byte-compile #'nm-btree-find-left)
 
@@ -125,13 +149,44 @@
 	     (let* ((scan-result1 (nm-buffer-headings-reversed buffer))
 		    (tree1 (nm-btree-from-reversed scan-result1)))
 	       tree1)))
+   (append '("scan using org-element-cache x10")
+           (progn
+             (let ((org-element-cache-sync-duration 1000.0))
+               (org-element-cache-reset)
+	       (org-element--cache-buffer-stealthly))
+	     (benchmark-run 10
+	       (nm-buffer-headings-reversed-cache buffer))))
+   (append '("populating the cache x1")
+	   (benchmark-run 1
+             (with-current-buffer buffer
+               ;; Disable async processing.
+               (let ((org-element-cache-sync-duration 1000.0))
+                 (org-element-cache-reset)
+	         (org-element--cache-buffer-stealthly)))))
    (append '("find random x10 000")
 	   (benchmark-run 10000
 	     (nm-btree-find-left tree (random lim))))
+   (append '("find random in org-element-cache x10 000")
+	   (benchmark-run 10000
+             (org-element-lineage
+	      (org-element--cache-find (random lim))
+              '(headlines) t)))
    (list "nodes" (cdr scan-result) "" "")))
 #+end_src
 
 #+RESULTS:
+| scan x10                                 |          1.693757321 | 0 |                 0.0 |
+| btree x10                                |          0.552682783 | 1 | 0.43690057000000593 |
+| scan+btree x10                           |   2.3174109880000002 | 0 |                 0.0 |
+| scan using org-element-cache x10         |   2.9140550789999997 | 0 |                 0.0 |
+| populating the cache x1                  |          10.83575134 | 9 |  3.9872376689999953 |
+| find random x10 000                      | 0.061988949999999994 | 0 |                 0.0 |
+| find random in org-element-cache x10 000 |          0.003262685 | 0 |                 0.0 |
+| nodes                                    |                16641 |   |                     |
+
+
+
+
 | scan x10            |   0.8611382689999999 | 0 |                 0.0 |
 | btree x10           |  0.07705962400000001 | 1 | 0.05648322199999978 |
 | scan+btree x10      |          0.940467238 | 1 | 0.05685373699999996 |

Diff finished.  Mon May 10 23:04:27 2021