Maxim Nikulin <maniku...@gmail.com> writes: > I have not tested the patch due to I do not use agenda. My interest was > stimulated solely by my attempts to make org-refile-get-targets faster.
Thanks for the feedback! > I consider it as an improvement. I have noticed the only thing that must > be fixed: comments with old variant of the function. Reaction to my > other comments is optional. Oops. Fixed. > In org-agenda.el org-up-heading-safe function is called only from > org-find-top-headline. That's probably not the slowest part. org-agenda also calls org-up-heading-safe indirectly. In particular, org-get-tags is calling org-up-heading-safe to get inherited tags. It is org-get-tags that is taking >50% time of agenda generation in my agendas. And org-up-heading-safe was the largest contributor to that >50% time. > ... So the purpose of the dance with backward > searches is to get top level headings. My expectation is that scan > through the whole buffer and storing result in a structure that allows > binary search of position (array, red-black tree, etc) may be even > faster. Scan through the whole buffer could be faster, but it is not always desired. Most of Org code only need information for current headline. Re-scanning the whole buffer would be costly. Also, I tried to compare avl-tree with hash table. However, avl-tree does not give much benefit for my test case of an agenda with ~12000 todo items. Since avl-tree requires much more custom code, hash table should be better. ;; No cache ;; org-up-heading-safe 180493 285.37713697 0.0015810980 ;; org-up-heading-safe 134876 199.44584854 0.0014787349 ;; org-up-heading-safe 134872 198.23494205 0.0014698005 ;; Hash cache ;; org-up-heading-safe 180493 5.0327451709 2.788...e-05 ;; org-up-heading-safe 134872 1.3568663460 1.006...e-05 ;; org-up-heading-safe 134872 0.7527555679 5.581...e-06 ;; AVL cache ;; org-up-heading-safe 180500 5.1044455589 2.827...e-05 ;; org-up-heading-safe 134872 1.2781428280 9.476...e-06 ;; org-up-heading-safe 134872 1.2866258809 9.539...e-06 > Alternatively lazily obtained position of top heading could be stored in > cache to reduce number of iterations on org-find-top-line. That one is used for org-agenda-filter-by-top-headline. I do not really use it, so I have no clue if there is much need to optimise it specifically. Yet, caching org-up-heading-safe will indeed speed it up as well. >> + (let ((level-cache (gethash (point) org--up-heading-cache))) >> + (if (and level-cache >> + (eq (buffer-chars-modified-tick) org--up-heading-cache-tick)) > > If buffer-chars-modified-tick is faster than gethash then reordering > might result in very slight improvement of performance. Sure. Done. >> + ;; Parent is inside accessible part of the buffer. >> + (progn (goto-char level-cache) >> + (funcall outline-level))) > > I do not see any reason why outline level can not be cached in pair with > position. Hmm. You are right. Benchmarking with and without additional caching shows that it can give extra ~2x improvement: ;; Hash cache ;; org-up-heading-safe 180493 5.0327451709 2.788...e-05 ;; org-up-heading-safe 134872 1.3568663460 1.006...e-05 ;; org-up-heading-safe 134872 0.7527555679 5.581...e-06 ;; Hash cache + outline-level cache ;; org-up-heading-safe 180507 4.3326449169 2.400...e-05 ;; org-up-heading-safe 134872 0.4952472380 3.671...e-06 ;; org-up-heading-safe 134879 0.5298789350 3.928...e-06 So, outline-level is also cached in the new version of the patch. >> + (let (result) >> + (setq result > > I am not a lisp guru, so from my point of view this can be reduced to > (let ((result ... Sure. >> + (format "^\\*\\{1,%d\\} " level-up) nil t) > > \t as an alternative to " " is used in org-refile.el, > e.g. "^\\*+[ \t]+". Unsure which variant is canonical one and I see that > regexp is taken from original function, so no regression is expected. I do not know either. Actually, I wish if Org mode code base used less literal strings and more regexp variables from org-element.el and org.el. Best, Ihor
>From d40b2bbb1dc5113d3085be2fae52ebe5ac1b023d Mon Sep 17 00:00:00 2001 Message-Id: <d40b2bbb1dc5113d3085be2fae52ebe5ac1b023d.1620299446.git.yanta...@gmail.com> From: Ihor Radchenko <yanta...@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 | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-) diff --git a/lisp/org.el b/lisp/org.el index 0ff13c79c..c7e87a804 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 (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 @@ -20449,10 +20453,26 @@ (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) + (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