Optimizing performance of buffer markers (was: Exposing buffer text modifications to Lisp)

[Ihor Radchenko <yantar92@gmail.com>]

I think that we settled something workable regarding buffer
modifications. I will try the proposed solutions and see if issues pop
up on Org ML.

Changing subject to reflect the remaining point of the discussion better.

Eli Zaretskii <eliz@gnu.org> writes:

>> Clarification: I was asking about C-level trees to store marker list.
>> I did not have moving Org AST from Lisp to C-level in mind. We currently
>> use built-in Lisp implementation of AVL-tree to search across AST (which
>> is not ideal, but good enough for moderately large files).
>
> Ah, okay.  Sorry for my misunderstanding.
>
> Trees could indeed be relevant, but maybe other data structures as
> well?  E.g., why not hash tables?  Not that I consider myself an
> expert on efficient search algorithms...

AFAIU, buf_bytepos_to_charpos tries to search for the closest marker
near the requested bytepos. It currently does it using the following
heuristics (roughly):

(let ((threshold 50))
 (dolist (marker markers)
  (if (or (< (abs (- marker bytepos)) threshold)
          (< (abs (- nearest_previous_marker bytepos)) threshold))
     (throw 'found marker)
   (cl-incf threshold 50))))

If we store markers in a hash table, there will be no benefit - Hash
table will only allow to find marker at exact position, not nearby.

AFAIK, the most natural data structure to search for data
before/after given key is a binary tree. There are more exotic data
structures, like skip list, but I do not expect skip lists to be
implemented in Emacs C code.

Best,
Ihor