From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: arthur miller Newsgroups: gmane.emacs.devel Subject: Re: Gap buffer problem? Date: Thu, 12 Dec 2024 23:40:36 +0000 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="_000_DU2PR02MB101095CEE538BB4CBB3712EC9963F2DU2PR02MB10109eu_" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="26877"; mail-complaints-to="usenet@ciao.gmane.io" Cc: "emacs-devel@gnu.org" To: "gerd.moellmann@gmail.com" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Dec 13 08:13:27 2024 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1tLzra-0006qz-Ph for ged-emacs-devel@m.gmane-mx.org; Fri, 13 Dec 2024 08:13:27 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1tLzqm-0004Gg-1k; Fri, 13 Dec 2024 02:12:37 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1tLssN-0002VF-6n for emacs-devel@gnu.org; Thu, 12 Dec 2024 18:45:51 -0500 Original-Received: from mail-db5eur02olkn2082e.outbound.protection.outlook.com ([2a01:111:f403:2e08::82e] helo=EUR02-DB5-obe.outbound.protection.outlook.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1tLssI-0002jm-2y for emacs-devel@gnu.org; Thu, 12 Dec 2024 18:45:45 -0500 ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=IQAdkVIsr0QTtR/NqsBlybs4eEGqMHk0JyAAVyQk/VXo8X9kby39Et1x+DGTRakrRiUEIpo347kvYP8VTeWCZtPShbsLIDLSohBd6Nf8RVplQfXFAzY7o9iCV4SRk3DT7/UKy+YZRmoCrOMB6lVAMJW74vcDKY133sGqSUkSdplfWj+UBkxIwMG/WYoWurFOG0Q1hb5bXbYR5nz6sx6U35DrXck3mmrFKJBPssOfMghkmHoIt6vGP1BQd77Gm5mPEo4iVlFABF3yuTcAAZ4AZeLMFLmAl8SXP6DvKtD0lFEj3bXDit3jmIyPpCzejJnJ0Ao/I+1VbvsLXs/YA9d+pg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=8vJ0MMuz9fC+nZxz/qbAY7nAVjdKHJdXuZpizHdQ++o=; b=LDyK2NB89CnJ3kCxVLJg/P/1V/T0AGeEXB1lRRIDxHlHNrCloVCgtvXs1oyQpNI0Ua7mQT0aixIW4OOO4+xohzNOxnBaVxOFFmaXEBwUo3klF7nRS65SySDFwWB+mufJ8ch0sQHVEWydb+UWImOWHgcmKT+cvVxBab4iwXZVI1sPZSRZWM4DvJDBvVXX1xP89113QriK8yAJSD6cj7wWvFrHY2wB/Bfwo/nzvMGJrH9GAllXnhOGREjBo8uuz6IedAAslElEsvlfhdL3GyB7TtDjG5g0gfW3G5G3WmGq8/SrOxuBJ0cSw4gHZcqWZnA3JEUGuoYvOqhkqrXUsaWFlQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=live.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=8vJ0MMuz9fC+nZxz/qbAY7nAVjdKHJdXuZpizHdQ++o=; b=GbwF8mE+CIV6EtUThF6FNIOcAaSlIHxRwhTscbcm9061lFrVt+0Es33+lNuJK1DED1Pqj6QovYIWAMtDAEZ9bmrtzWfjyolPf/GSaHgHSkBKYgxEtGOYimyt6R6F6EHxXyYH3jzAksBdChImuRTi9vuskIcBtowBzmPWARAwiUBrYQjLgV8dfej+xf92UhJLYb04yIi/i7u6g78AKzVYOptL0K6ErCn6ZO40ME9FNw/yzNYXvcmMGdan51YtU5taoZb5EFr0tP74OKHKTd7ZjxJc2wRUQSVVWvG3pm6xSbBctvvrjpw7n8hpKNi7/Q96e0oJ8b2PN3Fbrfh+lQFtnQ== Original-Received: from DU2PR02MB10109.eurprd02.prod.outlook.com (2603:10a6:10:497::14) by GV2PR02MB9469.eurprd02.prod.outlook.com (2603:10a6:150:d2::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.8251.15; Thu, 12 Dec 2024 23:40:36 +0000 Original-Received: from DU2PR02MB10109.eurprd02.prod.outlook.com ([fe80::f3c9:d4cb:290:d487]) by DU2PR02MB10109.eurprd02.prod.outlook.com ([fe80::f3c9:d4cb:290:d487%5]) with mapi id 15.20.8251.008; Thu, 12 Dec 2024 23:40:36 +0000 Thread-Topic: Gap buffer problem? Thread-Index: AQHbTOXQRHDH04akjkOBC0h2/IOyAQ== Accept-Language: sv-SE, en-US Content-Language: sv-SE x-ms-exchange-messagesentrepresentingtype: 1 x-ms-publictraffictype: Email x-ms-traffictypediagnostic: DU2PR02MB10109:EE_|GV2PR02MB9469:EE_ x-ms-office365-filtering-correlation-id: 07e1c891-8495-4c11-64d4-08dd1b06609e x-microsoft-antispam: BCL:0; ARA:14566002|9000799050|461199028|12050799009|8060799006|8062599003|5062599005|7092599003|15030799003|19110799003|1680799054|9400799030|15080799006|10035399004|3412199025|440099028|4302099013|102099032|1602099012; x-microsoft-antispam-message-info: =?iso-8859-1?Q?x5XUFATDTu1xCglf56A3HVmtbNpmudmpxChFN+z0B8gIBgWdcQqnsUo0VK?= =?iso-8859-1?Q?fq3BHt1zlmEx7QWq9wpidPaJFO9Wa9RMj0nRoBSx/lg8jLbX3J0s72w0zw?= =?iso-8859-1?Q?RetiUi0qK/u6EIEtsqyuZNkm0ND7zqVgXTS5DRGKNDl0LMERIwH3yD2o53?= =?iso-8859-1?Q?Uxyww/2dBiK81WEp9r/qo8dQGVfpwpbYny60wehYXhG7mNuex7lIA/6y/S?= =?iso-8859-1?Q?8D3TwHTXeaUTzVzZOI15yNquIC+p0sEUSD0LVn36PSe6Mpx9ygQxeQVOk3?= =?iso-8859-1?Q?+3BFeAESVoStPy45U7UBXacpcoQFe+Egoh3uD/oNwFX09KF3neUc0PwC2W?= =?iso-8859-1?Q?NjDOX+88lHYCSD0WGXOrkw4pLwAzNsQVfGJuTsH1XdPhCd7ADpvPqXTo6O?= =?iso-8859-1?Q?Q+gdtkV+cDEAb3YKQsm3ethKPv8glZD4PPgE3xTov6opacn7KrjxiJpQo/?= =?iso-8859-1?Q?787EqWBOblHwN+6StchF8eaaWTuKtwTcZ1FJdJrkQ5JjJOGbsb6zrqurzS?= =?iso-8859-1?Q?DwqX/I4p88oocrmHSpdq36EoKzQq5cRaTfxhAQAtMsgiJ5AYTQfpzunIaF?= =?iso-8859-1?Q?os2rkXnk5t/LsV7uSDqZMkP/iiWgLNkJNUj9a/MXb7EI4N50xyUEENFg9L?= =?iso-8859-1?Q?LfC x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?iso-8859-1?Q?wTzyMy6CPDD2yYrvuuHTfrlQVxxnlJTF8jMjSGxRH5du2wOdtLsapIIRqW?= =?iso-8859-1?Q?PF+5y++xDY8I6a5bzVn6qsad2Cu+hJzmuZoaZMDrpeZ8Njc6sco2NBV2PV?= =?iso-8859-1?Q?TtxEL28RGJdvWqUMTvH9Kd/F3OrH3/XEKuBiXo6LjA6vwMS7GPvxm+eA4T?= =?iso-8859-1?Q?C4H3Euglap2Z8Tw/Sj7D5BS+FwTug9J8Ddlisi2KrIRy//5y/Y1srDzQLv?= =?iso-8859-1?Q?16JQyQD4m78CJQOv6ooYJab8eeoWSAEzpv7EeLayeAWsWtP5Omx/vlfcjC?= =?iso-8859-1?Q?z2B20+RkHIXTxnHvxmtqT5uws6OFc4sbT0PLgexAIiL6k5uh1VKaSno2PQ?= =?iso-8859-1?Q?aUTkbT9hZBbSkcrKlFLbjHjPnpEhyjK0gxaoShnTv5A9A8LZp18YMigDeE?= =?iso-8859-1?Q?ByM2z1DyHiWoGdYwP4kF7x3SqO3FEoQtuOGbtzlDtB8TnkEWmhYrcTZgpY?= =?iso-8859-1?Q?2Bt6B4rjdjG8C4KklxZiAjzKsTOnHxw47YfAJYbf+sWS1peggCPU4CyMPo?= =?iso-8859-1?Q?iSII7F8bseRMi3jsP0RCmI7Qh/fXYO3crbKu+t95LxoeJ+lxZnyYJxZO/h?= =?iso-8859-1?Q?7UNNRBCNfI6eSOa870WlB/e9pAjs4l+HajIA22knt6Ay+1qOBrs3x+bXnO?= =?iso-8859-1?Q? X-OriginatorOrg: sct-15-20-7828-19-msonline-outlook-12d23.templateTenant X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: DU2PR02MB10109.eurprd02.prod.outlook.com X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-CrossTenant-Network-Message-Id: 07e1c891-8495-4c11-64d4-08dd1b06609e X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Dec 2024 23:40:36.1139 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-rms-persistedconsumerorg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: GV2PR02MB9469 Received-SPF: pass client-ip=2a01:111:f403:2e08::82e; envelope-from=arthur.miller@live.com; helo=EUR02-DB5-obe.outbound.protection.outlook.com X-Spam_score_int: -10 X-Spam_score: -1.1 X-Spam_bar: - X-Spam_report: (-1.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FREEMAIL_REPLY=1, HTML_MESSAGE=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_REMOTE_IMAGE=0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Fri, 13 Dec 2024 02:12:34 -0500 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:326449 Archived-At: --_000_DU2PR02MB101095CEE538BB4CBB3712EC9963F2DU2PR02MB10109eu_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable >>> From: Gerd M=F6llmann >>> Cc: emacs-devel@gnu.org, ofv@wanadoo.es, pipcet@protonmail.com >>> Date: Wed, 11 Dec 2024 16:51:56 +0100 >>> >>> Eli Zaretskii 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 performanc= e >>> > 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 goo= d >>> > 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=E1 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): https://github.com/lem-project/lem [https://opengraph.githubassets.com/936483c1586b682884e2dfee10ced041f6306d2= 9afd3df15a26830cc9eb47f65/lem-project/lem] GitHub - lem-project/lem: Common Lisp editor/IDE with high expansibility Common Lisp editor/IDE with high expansibility. Contribute to lem-project/lem dev= elopment 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. --_000_DU2PR02MB101095CEE538BB4CBB3712EC9963F2DU2PR02MB10109eu_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable 
&=
gt;>> From: Gerd M=F6llmann <gerd.moellmann@gmail.com>
>>> Cc: emacs-devel@gnu.o=
rg,  ofv@wanadoo.es,  pipcet@protonmail.com
>>> Date: Wed, 11 Dec 2024 16:51:56 +0=
100
>>>
>>&g=
t; Eli Zaretskii <eliz@gnu.org> writes:
>>>
>>> > Unless you have a huge (and I mean a HUGE) buffer,=
 and some Lisp that
>&g=
t;> > moves point, then inserts a small number of characters, then mo=
ves
>>> > poin=
t far away and again inserts a small number of characters, etc.,
>>> > I'd be very surpri=
sed if the gap buffer caused significant performance
>>> > problems on a modern CPU.
>>> >
>>> =
> Can you profile that case and post the expanded profile?  I'm alw=
ays
>>> > happ=
y to be wrong about performance bottlenecks, and profiles are good
>>> > at proving me wr=
ong.
>>>
>>> Maybe I'll try to inv=
estigate that further at some point. Such things
>>> always tend to be so time consuming...<=
/div>
>>
>> I meant profiling with "M-x=
 profile-start", then run your slow-down
>> recipe.  That sh=
ould 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.
<=
br>
There is a paper by R. Strandh & others from they work on Climacs.&n=
bsp;

They have, by now a 20 old year Flexichain implements a circular ga=
p
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 w=
here they use a double
lin=
ked list of lines. The "open" line is a gap buffer. As they say
in the introduction, the si=
miliar strategy was used in Multics Emacs.
The idea is to allow for incremental editing, a l=E1
=

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/downlo=
ad/StrandhVilleneuveMoore.pdf
https://www.european-lisp-workshop.org/archive=
s/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.editi=
ng <-- a text editor sans the
application based on the Cluffer

https://github.com/robert-strandh/Second-Climacs <--=
 text editor
application b=
ased 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):

https://github.com/lem-project/lem
=

3D""
GitHub
 - lem-project/lem: Common Lisp editor/IDE with high expansibility
Common
 Lisp editor/IDE with high expansibility. Contribute to lem-project/lem dev=
elopment 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. Have=
n't seen those papers mentioned anywhere
in this discussion, so thought they=
 might be of interest to some of you.
--_000_DU2PR02MB101095CEE538BB4CBB3712EC9963F2DU2PR02MB10109eu_--