From: Eli Zaretskii <eliz@gnu.org>
To: Ihor Radchenko <yantar92@gmail.com>
Cc: casouri@gmail.com, emacs-devel@gnu.org
Subject: Re: Exposing buffer text modifications to Lisp
Date: Sat, 18 Jun 2022 11:47:57 +0300 [thread overview]
Message-ID: <83fsk2nyrm.fsf@gnu.org> (raw)
In-Reply-To: <878rpuv17q.fsf@localhost> (message from Ihor Radchenko on Sat, 18 Jun 2022 16:13:13 +0800)
> From: Ihor Radchenko <yantar92@gmail.com>
> Cc: casouri@gmail.com, emacs-devel@gnu.org
> Date: Sat, 18 Jun 2022 16:13:13 +0800
>
> > AFAIU, the right fix for this is to fix performance degradation when a
> > buffer has many markers, not avoiding the use of markers.
> >
> > Here's one conclusion from this discussion that indicates changes
> > required to be done in core (other than a low-level modification hook
> > for buffer text) to take care of your AST implementation.
> >
> > We already have a TODO item for making markers more efficient; any
> > takers?
>
> This is trickier than it may appear.
> Each element in Org AST has 3-7 markers.
> My real-life large org buffer contains ~200k Org syntax elements
> (actually more, but not all the elements are ever queried).
> So, we are talking about 600k-1.4M markers in buffer if Org AST were to
> use markers.
>
> Now, imagine an edit somewhere near the beginning of Org buffer. Such
> edit means that Emacs will have to shift positions of nearly all the
> markers in the buffer. All the >1M markers. On every
> self-insert-command.
The inner loop of adjust_markers_for_insert is just 40 machine
instructions. (This is in unoptimized code; it could be fewer
instruction in an optimized build.) Assuming a 3GHz CPU clock, 40
instructions should take just 13 nsec, and 1 million of these should
take 13 milliseconds -- a very short time indeed. I expect that to be
between 5 and 7 msec in an optimized build.
(Compare that with inserting the characters itself: the first
insertion could potentially mean moving the gap, which in a large
buffer means moving megabytes of bytes -- not a negligible feat.)
So I don't think the performance degradation due to markers is because
the insert/delete operations on buffer text need to update many
markers. I think the real slowdown comes from the functions which
convert character positions to byte positions and vice versa: these
use markers. There are a lot of such calls all over our code, and
that's where the current linear-linked-list implementation of markers
slows us down.
Of course, the right method to show the bottleneck(s) is to profile
the code with a tool like 'prof', and take it from there. So here's
one more interesting job for someone to volunteer.
> Org parser goes around this issue by updating AST positions on idle and
> maintaining asynchronous request queue. This works relatively well
> because AST queries are skewed to be near the buffer region being
> edited. I am not sure if similar approach (not trivial to start with)
> can be efficiently utilized by Emacs. IDK the typical marker access
> pattern in Emacs core.
If you already have a workaround for marker-related problems, then why
do you need to hook into insertion and deletion on the lowest level?
> >> The situation is third-party code doing bloody murder with
> >>
> >> (with-silent-modifications
> >> (insert "Some text not triggering modification hooks))
> >>
> >> Another scenario is modifying text in indirect buffers created with
> >> make-indirect-buffer. (where there is no chance to install
> >> before/after-change-functions via clone-indirect-buffer-hook).
> >
> > In at least the latter case the idea for a proper solution was
> > outlined by Stefan.
>
> I haven't read through his email carefully yet. A quick response is that
> I have seen a lot of code in the wild that simply uses
> make-indirect-buffer. Expecting compliance is unreliable in practice. (I
> may need to think more about this though)
If this is a frequent problem, perhaps we should introduce a special
variant of add-hook which would cater to the indirect-buffer case.
Discussion of several such cases could point to that conclusion, or it
can point to something else.
And that is my long-standing gripe aimed at developers of 3rd party
packages: they should come here (or bug-gnu-emacs@gnu.org) and present
the cases where they needed some missing infrastructure, instead of
trying to jump through hoops to work around what they perceive as
Emacs restrictions that (they think) cannot be possibly lifted. Doing
the former will have at least two benefits: (a) it will facilitate
Emacs development into a better platform, and (b) it will avoid giving
birth to some of the horrible kludges out there, which eventually
don't work well enough, and thus make Emacs seem less professional
than it should be.
And if that is my expectation from developers of 3rd party packages, I
definitely expect that from packages that are bundled, such as Org.
Since Org is basically part of the core Emacs, it makes little sense
to me to realize that it goes to such lengths trying to work around
the limitations, instead of asking the core team to improve the
existing implementation or add some missing ones. I could perhaps
understand if the request existed, but no one volunteered to work on
it, but not having the requests in the first place I cannot
understand.
next prev parent reply other threads:[~2022-06-18 8: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 ` Eli Zaretskii [this message]
2022-06-20 11:58 ` Exposing buffer text modifications to Lisp 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 ` Optimizing performance of buffer markers (was: Exposing buffer text modifications to Lisp) Ihor Radchenko
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
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=83fsk2nyrm.fsf@gnu.org \
--to=eliz@gnu.org \
--cc=casouri@gmail.com \
--cc=emacs-devel@gnu.org \
--cc=yantar92@gmail.com \
/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 public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).