Re: profiling latency in large org-mode buffers (under both main & org-fold feature)

[Max Nikulin]

On 27/02/2022 13:43, Ihor Radchenko wrote:
> Now, I did an extended profiling of what is happening using perf:
>
>       6.20%   [.] buf_bytepos_to_charpos

Maybe I am interpreting such results wrongly, but it does not look like 
a bottleneck. Anyway thank you very much for such efforts, however it is 
unlikely that I will join to profiling in near future.

> buf_bytepos_to_charpos contains the following loop:
>
>    for (tail = BUF_MARKERS (b); tail; tail = tail->next)
>      {
>        CONSIDER (tail->bytepos, tail->charpos);
>
>        /* If we are down to a range of 50 chars,
>          don't bother checking any other markers;
>          scan the intervening chars directly now.  */
>        if (best_above - bytepos < distance
>            || bytepos - best_below < distance)
>         break;
>        else
>          distance += BYTECHAR_DISTANCE_INCREMENT;
>      }
>
> I am not sure if I understand the code correctly, but that loop is
> clearly scaling performance with the number of markers

I may be terribly wrong, but it looks like an optimization attempt that 
may actually ruin performance. My guess is the following. Due to 
multibyte characters position in buffer counted in characters may 
significantly differ from index in byte sequence. Since markers have 
both values bytepos and charpos, they are used (when available) to 
narrow down initial estimation interval [0, buffer size) to nearest 
existing markers. The code below even creates temporary markers to make 
next call of the function faster.

It seems, buffers do not have any additional structures that track size 
in bytes and in characters of spans (I would not expect that 
representation of whole buffer in memory is single contiguous byte 
array). When there are no markers at all, the function has to iterate 
over each character and count its length.

The problem is that when the buffer has a lot of markers far aside from 
the position passed as argument, then iteration over markers just 
consumes CPU with no significant improvement of original estimation of 
boundaries.

If markers were organized in a tree than search would be much faster (at 
least for buffers with a lot of markers.

In some cases such function may take a hint: previous known 
bytepos+charpos pair.

I hope I missed something, but what I can expect from the code of 
buf_bytepos_to_charpos is that it is necessary to iterate over all 
markers to update positions after each typed character.

> Finally, FYI. I plan to work on an alternative mechanism to access Org
> headings - generic Org query library. It will not use markers and
> implement ideas from org-ql. org-refile will eventually use that generic
> library instead of current mechanism.

I suppose that markers might be implemented in an efficient way, and 
much better performance may be achieved when low-level data structures 
are accessible. I am in doubts concerning attempts to create something 
that resembles markers but based purely on high-level API.