GNU logs - #58361, boring messages


Message sent to bug-gnu-emacs@HIDDEN:


X-Loop: help-debbugs@HIDDEN
Subject: bug#58361: 29.0.50; noverlay branch is O(N) for important calls
Resent-From: Andreas Politz <mail@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Fri, 07 Oct 2022 18:15:02 +0000
Resent-Message-ID: <handler.58361.B.16651664816409 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: report 58361
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Matt Armstrong <matt@HIDDEN>
Cc: gerd.moellmann@HIDDEN, 58361 <at> debbugs.gnu.org, eliz@HIDDEN, monnier@HIDDEN
X-Debbugs-Original-Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, bug-gnu-emacs@HIDDEN, Eli Zaretskii <eliz@HIDDEN>, Stefan Monnier <monnier@HIDDEN>
Received: via spool by submit <at> debbugs.gnu.org id=B.16651664816409
          (code B ref -1); Fri, 07 Oct 2022 18:15:02 +0000
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 18:14:41 +0000
Received: from localhost ([127.0.0.1]:37329 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1ogrrs-0001fH-PQ
	for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 14:14:41 -0400
Received: from lists.gnu.org ([209.51.188.17]:49324)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mail@HIDDEN>) id 1ogqZO-00085B-8m
 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 12:51:30 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:57950)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <mail@HIDDEN>)
 id 1ogqZN-0001pK-Nw
 for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 12:51:29 -0400
Received: from mout.kundenserver.de ([212.227.126.130]:55023)
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <mail@HIDDEN>)
 id 1ogqZK-00041N-PN; Fri, 07 Oct 2022 12:51:29 -0400
Received: from smtpclient.apple ([77.181.178.184]) by mrelayeu.kundenserver.de
 (mreue012 [213.165.67.97]) with ESMTPSA (Nemesis) id
 1MJnnV-1oRe291dqT-00K9io; Fri, 07 Oct 2022 18:51:16 +0200
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
From: Andreas Politz <mail@HIDDEN>
Mime-Version: 1.0 (1.0)
Date: Fri, 7 Oct 2022 18:51:14 +0200
Message-Id: <D54E3787-D89B-43E1-A03E-75DFC6A34A62@HIDDEN>
References: <878rlrfyje.fsf@HIDDEN>
In-Reply-To: <878rlrfyje.fsf@HIDDEN>
X-Mailer: iPad Mail (19G82)
X-Provags-ID: V03:K1:fzXBlZNteNLENboVA/hlyJcvuu1kDBiI4uNkLz7grifTm+Iw4Vk
 WRvP022ngLL0DJ/V6F9/+Tj4DQXJxs4CP5ZVc4Zuoek3Z1Q+y8jzc3Aul+inIBgfLhTYgEl
 vgK5HY4tHZTUvOUQOO5G+8tV57a8M0lzi6m9QyErXkaM8Wo5KfzZzRB06Vt5pJNRVljO72Q
 RK/bBLfThOLfRs82kh/sg==
X-Spam-Flag: NO
X-UI-Out-Filterresults: notjunk:1;V03:K0:oxOSyS6HEzY=:5woV7akfpcILVaBLPZiHMm
 Ad2OLhUwJZrMow4S3dK8kXSie0sItgCH6pDGALHtCIb5rR/aFzzU2Ku6FR3mtayl7FsMMV1bo
 QNQ/LHLAPtdctmwxK0/Y/jT41SJJSBQS4o1kWI111M1pXc63T6t4MvoZeAKoLRQ0EfpT3t4sY
 c27uAYHzAzQdv8xEfMSCk/gVnQy87Qcn4HerX1ZAZ0BjvRvEXnj9b42tM4BwrTZH+95SsQHDV
 gEbcodPhhyiGYPSJcMr1j9vUQsmlC/Sj5Vwqy35FEGywyXmTLAsVHdzN2+YBnDYGjEVxFz6Jv
 Cv1nFbnA+S3YGLMqYQ9kruqhSC8wnk1sqbKNtRg80J29WB6QepM0rNhVSOh948JqzepOPzM7I
 CMcGhzhUGosOtuM9io2DEju4HQfFxc7U2YknoPWffh0e6/UTb838jsV9CotaUgZITS2WmHe5t
 kNqaOxvp5t+H6Na5P3nLRwHSdcpFn6XFz8UMPjEL6r1YsjGcYQu6rmnQR4qX2NjvT9PNKQ0x7
 S8bOk4p03WUhef6WAte/mYgWyZG2MAP0FHCzg6tpQqVJO0hoYkn7fi+/VN76jqt1Y+U3Mz2nd
 W98RajWddSWOVb5EuLFDzg4azHlY6gApVmKQvDNpbrmIZCS4DVwkqXJNEUZZKjN+kSNrgm5YM
 al1X90V/nIdIiUPvUU2iZQi+c1pNlUA5+OFuC2i9dDFTuXpWzajOpGmCfvjytrtu6aPBNxdSB
 1r4+39bCood2pDXGzsbXYBTUeIC6g1XXLURLPAlP7EBSL0s6na+UeXpUbpm2eo5hN3HrL3IWH
 Ur6kcLa660KZWKXkFZHUswueU7HQw==
Received-SPF: none client-ip=212.227.126.130;
 envelope-from=mail@HIDDEN; helo=mout.kundenserver.de
X-Spam_score_int: -18
X-Spam_score: -1.9
X-Spam_bar: -
X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001,
 RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001,
 SPF_NONE=0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -2.3 (--)
X-Mailman-Approved-At: Fri, 07 Oct 2022 14:14:39 -0400
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)

I think, a straightforward way   to use 2 trees, one for begin and one for e=
nd, could be to create another abstraction above those trees, while for the m=
ost part  duplicating the existing  interface.  This abstraction would then e=
ither delegate to one or both trees, depending on the operation. The trick w=
ould be to kinda multiplying the end-tree by -1,  i.e. reverse begin and end=
 and multiply with -1 all inputs and outputs of this tree.

Would that work ?

> Am 07.10.2022 um 17:23 schrieb Matt Armstrong <matt@HIDDEN>:
>=20
> =EF=BB=BFTo start, I don't think this issue should delay a merge to master=
.  I
> don't think it is clear we need to fix anything here.
>=20
> I would like a note or FIXME in code noting the potentially slow
> algorithm (patch sent), because it is currently well hidden behind a
> generator loop.
>=20
>=20
> Stefan Monnier <monnier@HIDDEN> writes:
>=20
>>> Here we traverse overlays in ASCENDING order of BEG positions.  The best=

>>> we can say is that this loop executes in O(K*log(N)) time, where K is
>>> the MIN of number of overlays that overlap POS and the number of valid
>>=20
>> The core operation in itree.c is the equivalent of `overlays-in/at`.
>=20
> [...]
>=20
> Yes, and for this O(K*log(N)) performance is a good result.  The key
> insight is that previous and next overlay changes require examining a
> large K (in worst case, extending all the way to the beginning or end of
> the buffer) because there is no ordering by END positions.
>=20
>> Realistic benchmarks would be most welcome.
>=20
> I am working on polishing off
> https://git.sr.ht/~matta/emacs-overlay-perftests.  Good news is that
> redisplay is faster on the noverlay branch for the "realistic" case of
> overlaping not overlapping eachother in pathalogical ways.
>=20
>=20
>> [ Site note: `previous-overlay-change` is probably not very important in
>>  practice, but `next-overlay-change` OTOH is indeed important because
>>  it's used during redisplay.  So if someone comes up with a trick to
>>  speed up only one direction, it should be good enough.  ]
>>=20
>> Maybe one way to improve the behavior is to accept the worst-case
>> bound but to try and avoid paying it over-and-over each time the
>> redisplay needs the "next change".  IOW instead of a
>> `next_overlay_change` function which takes a POS and returns the next
>> change after that, the xdisp.c might benefit from having a
>> `next_overlay_changes` *generator* which takes a starting POS and
>> returns an iterator which will return (each time it's called) the
>> successive positions where there's an overlay change.
>>=20
>> Hopefully this way we'd pay the O(N) cost once per redisplayed window
>> rather than once per "small step in the rendering engine" (i.e. per
>> next_overlay_change).
>=20
> At the moment I can't think of a reasonable way to implement such a
> generator efficiently without, effectively, computing a temporary
> ordered collection over overlay END positions.
>=20
> This is why I keep coming back to the idea of storing both BEG and END
> positions in ordered collections at all times.
>=20
>=20
>> Another way to do basically the same is to let next_overlay_change
>> fill up a cache of change-positions which would be flushed whenever
>> some overlay is modified/added/removed (or the current_buffer is
>> different from last time).  That might be easier to use with the
>> current code since xdisp.c wouldn't need to pass around this iterator
>> (which could require significant reworks).
>=20
> ...possibly, but the problem with caching is the time spent filling the
> cache back up.  I like the idea of storing both BEG and END positions in
> an ordered collection because in that case the (potentially slow)
> recomputation need not occur with every key press.  If we're not worried
> about that kind per-key-press of delay, then I argue there is no need
> for a cache either.





Message sent:


Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Andreas Politz <mail@HIDDEN>
Subject: bug#58361: Acknowledgement (29.0.50; noverlay branch is O(N) for
 important calls)
Message-ID: <handler.58361.B.16651664816409.ack <at> debbugs.gnu.org>
References: <D54E3787-D89B-43E1-A03E-75DFC6A34A62@HIDDEN>
X-Gnu-PR-Message: ack 58361
X-Gnu-PR-Package: emacs
Reply-To: 58361 <at> debbugs.gnu.org
Date: Fri, 07 Oct 2022 18:15:02 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-gnu-emacs@HIDDEN

If you wish to submit further information on this problem, please
send it to 58361 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
58361: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D58361
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems


Message sent to bug-gnu-emacs@HIDDEN:


X-Loop: help-debbugs@HIDDEN
Subject: bug#58361: 29.0.50; noverlay branch is O(N) for important calls
Resent-From: Stefan Monnier <monnier@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Fri, 07 Oct 2022 18:40:02 +0000
Resent-Message-ID: <handler.58361.B.16651679568867 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 58361
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Andreas Politz <mail@HIDDEN>
Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, 58361 <at> debbugs.gnu.org, eliz@HIDDEN
X-Debbugs-Original-Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, Matt Armstrong <matt@HIDDEN>, bug-gnu-emacs@HIDDEN, Eli Zaretskii <eliz@HIDDEN>
Received: via spool by submit <at> debbugs.gnu.org id=B.16651679568867
          (code B ref -1); Fri, 07 Oct 2022 18:40:02 +0000
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 18:39:16 +0000
Received: from localhost ([127.0.0.1]:37358 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1ogsFg-0002Iv-9S
	for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 14:39:16 -0400
Received: from lists.gnu.org ([209.51.188.17]:39630)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <monnier@HIDDEN>) id 1ogsFd-0002Il-Sr
 for submit <at> debbugs.gnu.org; Fri, 07 Oct 2022 14:39:15 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:51884)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
 id 1ogsFZ-000086-7B
 for bug-gnu-emacs@HIDDEN; Fri, 07 Oct 2022 14:39:12 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:9898)
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <monnier@HIDDEN>)
 id 1ogsF4-0001su-D8; Fri, 07 Oct 2022 14:38:59 -0400
Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 5F1E18004C;
 Fri,  7 Oct 2022 14:38:35 -0400 (EDT)
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 50FA380401;
 Fri,  7 Oct 2022 14:38:33 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1665167913;
 bh=TfRJTRm0zM57+oiReAoWVUmuMZkOqz0SJtRY/HWhT6Q=;
 h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
 b=d9Iht9JQBzpoMQq3sIPI9glDmwxLa0fStR7KLPd9WiNSo/s3UgRNnE27jAG5RMdhQ
 m3R+Tk1TRSvkZYrMot/4GOi9nnOH8skkrnpokGe0HqiRlMjmfs7ZiHzwQbFdYhktrR
 Ouc7M2dZK5pFgTTdRPKTpDlrXUb0uafv+YK3raaPUTm1cRB8aA7Lp/qRg+e3ui3dTI
 dN3/Ke5cNtYNcyK98tjU91TOjniFp8vgZARwovDqewBZrUYHO62sELDShX5avzReIZ
 /JkIaNv7OWrOlWWX4L+zh8yHdsOOkL/QNSVZwEdg3nhq7QGqML+WlFSyFNtdYhRMZN
 u3Q0ojOb+Q2yw==
Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id D1BA212047D;
 Fri,  7 Oct 2022 14:38:32 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <D54E3787-D89B-43E1-A03E-75DFC6A34A62@HIDDEN> (Andreas
 Politz's message of "Fri, 7 Oct 2022 18:51:14 +0200")
Message-ID: <jwvfsfz5vx9.fsf-monnier+emacs@HIDDEN>
References: <878rlrfyje.fsf@HIDDEN>
 <D54E3787-D89B-43E1-A03E-75DFC6A34A62@HIDDEN>
Date: Fri, 07 Oct 2022 14:38:31 -0400
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.139 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
 KAM_SHORT               0.001 Use of a URL Shortener for very short URL
X-SPAM-LEVEL: 
Received-SPF: pass client-ip=132.204.25.50;
 envelope-from=monnier@HIDDEN; helo=mailscanner.iro.umontreal.ca
X-Spam_score_int: -42
X-Spam_score: -4.3
X-Spam_bar: ----
X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
 DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3,
 SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: -1.3 (-)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)

> I think, a straightforward way   to use 2 trees, one for begin and one for
> end, could be to create another abstraction above those trees, while for =
the
> most part  duplicating the existing  interface.  This abstraction would t=
hen
> either delegate to one or both trees, depending on the operation. The tri=
ck
> would be to kinda multiplying the end-tree by -1,  i.e. reverse begin and
> end and multiply with -1 all inputs and outputs of this tree.
>
> Would that work ?

Could be but I'm not sure we want to pay this memory&cpu price to try
and fix a performance bug that's still hypothetical.
For all we know, in those cases where this performance problem could
bite, other performance problems bite us harder anyway.


        Stefan


>> Am 07.10.2022 um 17:23 schrieb Matt Armstrong <matt@HIDDEN>:
>>=20
>> =EF=BB=BFTo start, I don't think this issue should delay a merge to mast=
er.  I
>> don't think it is clear we need to fix anything here.
>>=20
>> I would like a note or FIXME in code noting the potentially slow
>> algorithm (patch sent), because it is currently well hidden behind a
>> generator loop.
>>=20
>>=20
>> Stefan Monnier <monnier@HIDDEN> writes:
>>=20
>>>> Here we traverse overlays in ASCENDING order of BEG positions.  The be=
st
>>>> we can say is that this loop executes in O(K*log(N)) time, where K is
>>>> the MIN of number of overlays that overlap POS and the number of valid
>>>=20
>>> The core operation in itree.c is the equivalent of `overlays-in/at`.
>>=20
>> [...]
>>=20
>> Yes, and for this O(K*log(N)) performance is a good result.  The key
>> insight is that previous and next overlay changes require examining a
>> large K (in worst case, extending all the way to the beginning or end of
>> the buffer) because there is no ordering by END positions.
>>=20
>>> Realistic benchmarks would be most welcome.
>>=20
>> I am working on polishing off
>> https://git.sr.ht/~matta/emacs-overlay-perftests.  Good news is that
>> redisplay is faster on the noverlay branch for the "realistic" case of
>> overlaping not overlapping eachother in pathalogical ways.
>>=20
>>=20
>>> [ Site note: `previous-overlay-change` is probably not very important in
>>>  practice, but `next-overlay-change` OTOH is indeed important because
>>>  it's used during redisplay.  So if someone comes up with a trick to
>>>  speed up only one direction, it should be good enough.  ]
>>>=20
>>> Maybe one way to improve the behavior is to accept the worst-case
>>> bound but to try and avoid paying it over-and-over each time the
>>> redisplay needs the "next change".  IOW instead of a
>>> `next_overlay_change` function which takes a POS and returns the next
>>> change after that, the xdisp.c might benefit from having a
>>> `next_overlay_changes` *generator* which takes a starting POS and
>>> returns an iterator which will return (each time it's called) the
>>> successive positions where there's an overlay change.
>>>=20
>>> Hopefully this way we'd pay the O(N) cost once per redisplayed window
>>> rather than once per "small step in the rendering engine" (i.e. per
>>> next_overlay_change).
>>=20
>> At the moment I can't think of a reasonable way to implement such a
>> generator efficiently without, effectively, computing a temporary
>> ordered collection over overlay END positions.
>>=20
>> This is why I keep coming back to the idea of storing both BEG and END
>> positions in ordered collections at all times.
>>=20
>>=20
>>> Another way to do basically the same is to let next_overlay_change
>>> fill up a cache of change-positions which would be flushed whenever
>>> some overlay is modified/added/removed (or the current_buffer is
>>> different from last time).  That might be easier to use with the
>>> current code since xdisp.c wouldn't need to pass around this iterator
>>> (which could require significant reworks).
>>=20
>> ...possibly, but the problem with caching is the time spent filling the
>> cache back up.  I like the idea of storing both BEG and END positions in
>> an ordered collection because in that case the (potentially slow)
>> recomputation need not occur with every key press.  If we're not worried
>> about that kind per-key-press of delay, then I argue there is no need
>> for a cache either.





Message received at control <at> debbugs.gnu.org:


Received: (at control) by debbugs.gnu.org; 13 Oct 2022 13:47:54 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Thu Oct 13 09:47:54 2022
Received: from localhost ([127.0.0.1]:60037 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1oiyZ0-0005FG-7k
	for submit <at> debbugs.gnu.org; Thu, 13 Oct 2022 09:47:54 -0400
Received: from mail-oa1-f43.google.com ([209.85.160.43]:37840)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <stefankangas@HIDDEN>) id 1oiyYt-0005Bc-IA
 for control <at> debbugs.gnu.org; Thu, 13 Oct 2022 09:47:47 -0400
Received: by mail-oa1-f43.google.com with SMTP id
 586e51a60fabf-12c8312131fso2343689fac.4
 for <control <at> debbugs.gnu.org>; Thu, 13 Oct 2022 06:47:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=to:subject:message-id:date:mime-version:from:from:to:cc:subject
 :date:message-id:reply-to;
 bh=+gm07CA0L9YBFMumCGeLKxzDiR4G1fhWytrleXMuJ20=;
 b=GFmG7J3gm99XcLmi2Li/Jyad+14lJSrZg4zx20W0kS77a0HAVzufxGyUvMdWgmmr4l
 HL82hs4wGRqHzTZ6+Zwxc84opuWgMC9D95KFxvE/1OHVOrB7RHHZmL6bVzPzpx3SXdcg
 BEBF5L6UKDcIM0hDY8NySClga0ass81/btjCvqK0HhvjVcmHZw4DIzR04aon4nLKu5Ao
 sSbU4c1A1Zo8RXuzzNOIpuFZ6A76Tqc0YKKU+4Wn4/S8JotxIjRBcf35QrDF5MjsG4zb
 8pczmenmX1VHUHQR3ktc6yoYGMpIFNi4OXbjz6F9F0Mouzfq1pnsyvRWUkPEGfFz9Vsk
 4Zqg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=to:subject:message-id:date:mime-version:from:x-gm-message-state
 :from:to:cc:subject:date:message-id:reply-to;
 bh=+gm07CA0L9YBFMumCGeLKxzDiR4G1fhWytrleXMuJ20=;
 b=4VzSlJ0C2cNw+tJWXBSAiP8WxzVXdST1yyY/faXtkq1JEPp+dgpRZOJJGZznk4rjD6
 L1xS9oZukXx8iUBxzRNDFJUhvyGZEfmDkxNcLXeh5oHEGxKfX2fz2EtoqbbV/tEJBNg0
 yiuYZv9BpW0SPUoJ5KifaT6PrGrUQwgQPbxDP/qWrXmg/f+pBjx9d0VwSW55988/gVIR
 WeCvrqyyCbc2Kq+W9DCge7LVSs4PtAYG8oELKaqmNMYl7UuPAgP7ahiNIsHxZM7I6hgz
 +NFVG4vaPkKJOG3cdYcIhJ53uIzSML3iKQAQ5yxbjjr5K4G0JuvvElaOKd0vJpKQ08Gb
 38OQ==
X-Gm-Message-State: ACrzQf0EXM0FoO7yTtFVwO+gQLU/k3VDytEQiDAUXqFDkAtExD99sB3J
 TOHx2xkwlSHj80j12uQy6IBfLqbG9EeKRntZNSu4rTXX
X-Google-Smtp-Source: AMsMyM5d2rd+olCLUoEiB7Fo9O2ArDkvzwYsjGRBPae3jQ9jvG7M/v+YMmzjpmQVTNwE6zQj96FskJE1gVvDIQmWfr0=
X-Received: by 2002:a05:6870:9126:b0:132:b724:e96c with SMTP id
 o38-20020a056870912600b00132b724e96cmr5568065oae.199.1665668867284; Thu, 13
 Oct 2022 06:47:47 -0700 (PDT)
Received: from 753933720722 named unknown by gmailapi.google.com with
 HTTPREST; Thu, 13 Oct 2022 15:47:46 +0200
From: Stefan Kangas <stefankangas@HIDDEN>
X-Hashcash: 1:20:221013:control <at> debbugs.gnu.org::53k1gOqqctfJbwFL:QWj
MIME-Version: 1.0
Date: Thu, 13 Oct 2022 15:47:46 +0200
Message-ID: <CADwFkmkKZRkWBa_FZzo2Q=KVWGM-YcCiuCwoZGOD5HR8-WE=zg@HIDDEN>
Subject: control message for bug #58361
To: control <at> debbugs.gnu.org
Content-Type: text/plain; charset="UTF-8"
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: control
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

forcemerge 58361 58342
quit





Last modified: Thu, 13 Oct 2022 14:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.