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

[Maxim Nikulin]

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.

Despite continuing discussion, I am unsure if it could be significantly 
better.

On 06/05/2021 21:34, Ihor Radchenko wrote:
> Maxim Nikulin writes:
> > 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.

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.

> 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.

Did you just replace gethash by avl-tree? 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.

> +                           (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.

If originally this code path had 50% contribution and performance 
already becomes several times better, further optimization of this part 
does not matter.