>>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>>> Cc: emacs-devel@gnu.org, ofv@wanadoo.es, pipcet@protonmail.com
>>> Date: Wed, 11 Dec 2024 16:51:56 +0100
>>>
>>> Eli Zaretskii <eliz@gnu.org> writes:
>>>
>>> > Unless you have a huge (and I mean a HUGE) buffer, and some Lisp that
>>> > moves point, then inserts a small number of characters, then moves
>>> > point far away and again inserts a small number of characters, etc.,
>>> > I'd be very surprised if the gap buffer caused significant performance
>>> > problems on a modern CPU.
>>> >
>>> > Can you profile that case and post the expanded profile? I'm always
>>> > happy to be wrong about performance bottlenecks, and profiles are good
>>> > at proving me wrong.
>>>
>>> Maybe I'll try to investigate that further at some point. Such things
>>> always tend to be so time consuming...
>>
>> I meant profiling with "M-x profile-start", then run your slow-down
>> recipe. That should be easy and should not consume any significant
>> time. Analyzing the profile could, but producing it shouldn't.
>
>Plus making it reproducible, if it is.
There is a paper by R. Strandh & others from they work on Climacs.
They have, by now a 20 old year Flexichain implements a circular gap
buffer with the explicit goal to workaround that case. At the same time
it also turns gap buffer into a flexible array usable for other use-cases
like qeues and stacks.
However, they have also gone away from the gap buffer, to something they
call "Cluffer", and which is a strategy where they use a double
linked list of lines. The "open" line is a gap buffer. As they say
in the introduction, the similiar strategy was used in Multics Emacs.
The idea is to allow for incremental editing, a lá
tree sitter I guess, and it is also suitable for multiple cursors. They
also say that for modern hardware the additional memory cost of double
linked lists is not prohibitive.
For those interested relevant papers and sources are here:
https://flexichain.common-lisp.dev/download/StrandhVilleneuveMoore.pdf
https://www.european-lisp-workshop.org/archives/2004/slides/Strandh-slides.pdf
https://github.com/robert-strandh/Flexichain
http://metamodular.com/cluffer.pdf
https://hal.science/hal-01887230v1/file/5-incremental-parsing.pdf
https://research.gold.ac.uk/id/eprint/2351/1/climacssyntax.pdf
https://github.com/robert-strandh/Cluffer
https://github.com/scymtym/text.editing <-- a text editor sans the
application based on the Cluffer
https://github.com/robert-strandh/Second-Climacs <-- text editor
application based on the above text.editing and Cluffer
There is also Lem which uses a similar strategy for its text representation
(if I am not misstaken, long time ago I looked at their code):
| Common
Lisp editor/IDE with high expansibility. Contribute to lem-project/lem development by creating an account on GitHub. github.com |
Don't know if it is of use for you or not, but perhaps there is some
inspiration there. Haven't seen those papers mentioned anywhere
in this discussion, so thought they might be of interest to some of you.