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.