emacs-orgmode
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Maxim Nikulin
Subject: Re: [PATCH] Use cache in org-up-heading-safe
Date: Sat, 8 May 2021 18:28:41 +0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1

On 07/05/2021 09:08, Ihor Radchenko wrote:
Maxim Nikulin writes:
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.

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.

For a file having 3000 headings, scanning though it takes ~0.1sec to get the following properties: position, level, list of parents (with same properties). Note that no expensive operations are performed like cleaning up of heading title.

Having list of headings (and its length), it is possible to build a tree for binary search in linear time. It takes ~0.01sec.

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.

Hash works only for fixed set of positions, to use hash it is necessary to find position of the heading at first. On the other hand, to take advantage of binary tree, more substantial modification of code is required.

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.

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.

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

Sorry. You are right. The function does what I proposed to write explicitly. For some reason I believed that outline-level calls something like looking-at. Maybe I checked it earlier and completely forgot.

Attachment: nm-btree.org
Description: Text document


reply via email to

[Prev in Thread] Current Thread [Next in Thread]