Maxim Nikulin 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