all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Ihor Radchenko <yantar92@gmail.com>
To: Eli Zaretskii <eliz@gnu.org>
Cc: casouri@gmail.com,  emacs-devel@gnu.org
Subject: Optimizing performance of buffer markers (was: Exposing buffer text modifications to Lisp)
Date: Sat, 25 Jun 2022 12:47:38 +0800	[thread overview]
Message-ID: <87edzdwdqt.fsf@localhost> (raw)
In-Reply-To: <831qvikxqo.fsf@gnu.org>

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



  reply	other threads:[~2022-06-25  4:47 UTC|newest]

Thread overview: 64+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-05-19  1:35 Tree-sitter integration on feature/tree-sitter Kiong-Ge Liau
2022-05-20  2:01 ` Yuan Fu
2022-06-16 19:03   ` Yuan Fu
2022-06-16 19:25     ` [External] : " Drew Adams
2022-06-17  1:11       ` Yuan Fu
2022-06-17 14:22         ` Drew Adams
2022-06-17  1:24     ` Po Lu
2022-06-18  0:09       ` Yuan Fu
2022-06-17  2:00     ` Ihor Radchenko
2022-06-17  2:25       ` Lower-level change hook immune to with-silent-modifications Yuan Fu
2022-06-17  2:55         ` Stefan Monnier
2022-06-17  5:28           ` Eli Zaretskii
2022-06-17 10:10             ` Ihor Radchenko
2022-06-17 11:03               ` Eli Zaretskii
2022-06-17  5:23       ` Tree-sitter integration on feature/tree-sitter Eli Zaretskii
2022-06-17 10:40         ` Ihor Radchenko
2022-06-17 11:42           ` Exposing buffer text modifications to Lisp (was: Tree-sitter integration on feature/tree-sitter) Eli Zaretskii
2022-06-18  5:52             ` Ihor Radchenko
2022-06-18  7:01               ` Eli Zaretskii
2022-06-18  7:23                 ` Ihor Radchenko
2022-06-18  7:44                   ` Eli Zaretskii
2022-06-18  8:13                     ` Ihor Radchenko
2022-06-18  8:47                       ` Exposing buffer text modifications to Lisp Eli Zaretskii
2022-06-20 11:58                         ` Ihor Radchenko
2022-06-20 12:32                           ` Eli Zaretskii
2022-06-20 14:14                             ` Stefan Kangas
2022-06-21  3:56                               ` Ihor Radchenko
2022-06-21  4:36                             ` Ihor Radchenko
2022-06-21 12:27                               ` Eli Zaretskii
2022-06-25  4:47                                 ` Ihor Radchenko [this message]
2022-06-25  8:29                                   ` Optimizing performance of buffer markers Stefan Monnier
2022-06-25  8:44                                     ` Eli Zaretskii
2022-06-25  9:07                                       ` Stefan Monnier
2022-06-25  9:20                                         ` Eli Zaretskii
2022-06-25  9:27                                           ` Stefan Monnier
2022-06-25  9:47                                         ` Ihor Radchenko
2022-06-25  9:53                                           ` Stefan Monnier
2022-06-26 10:32                                   ` Robert Pluim
2022-06-22 15:45                             ` Exposing buffer text modifications to Lisp Basil L. Contovounesios
2022-06-22 16:13                               ` Eli Zaretskii
2022-06-25  4:54                                 ` Ihor Radchenko
2022-06-25  5:46                                   ` Eli Zaretskii
2022-06-29 12:24                                     ` Ihor Radchenko
2022-06-20 14:33                           ` Alan Mackenzie
2022-06-21  3:58                             ` Ihor Radchenko
2022-06-17  6:15     ` Tree-sitter integration on feature/tree-sitter Eli Zaretskii
2022-06-17  7:17       ` Yuan Fu
2022-06-17 10:37         ` Eli Zaretskii
2022-06-18  0:14           ` Yuan Fu
2022-06-18  6:22             ` Eli Zaretskii
2022-06-18  8:25               ` Yuan Fu
2022-06-18  8:50                 ` Eli Zaretskii
2022-06-18 20:07                   ` Yuan Fu
2022-06-19  5:39                     ` Eli Zaretskii
2022-06-20  3:00                       ` Yuan Fu
2022-06-20 11:44                         ` Eli Zaretskii
2022-06-20 20:01                           ` Yuan Fu
2022-06-21  2:26                             ` Eli Zaretskii
2022-06-21  4:39                               ` Yuan Fu
2022-06-21 10:18                                 ` Eli Zaretskii
2022-06-22  0:34                                   ` Yuan Fu
2022-06-17 11:06     ` Jostein Kjønigsen
2022-06-18  0:28       ` Yuan Fu
2022-06-18 20:57         ` Jostein Kjønigsen

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87edzdwdqt.fsf@localhost \
    --to=yantar92@gmail.com \
    --cc=casouri@gmail.com \
    --cc=eliz@gnu.org \
    --cc=emacs-devel@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.