Stefan Kangas <stefankangas@HIDDEN>
to control <at> debbugs.gnu.org.
Full text available.
Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 18:39:16 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 14:39:16 2022
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>
To: Andreas Politz <mail@HIDDEN>
Subject: Re: 29.0.50; noverlay branch is O(N) for important calls
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-Debbugs-Envelope-To: submit
Cc: Gerd =?windows-1252?Q?M=F6llmann?= <gerd.moellmann@HIDDEN>,
Matt Armstrong <matt@HIDDEN>, bug-gnu-emacs@HIDDEN,
Eli Zaretskii <eliz@HIDDEN>
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.
bug-gnu-emacs@HIDDEN:bug#58361; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 7 Oct 2022 18:14:41 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Fri Oct 07 14:14:41 2022 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) Subject: Re: 29.0.50; noverlay branch is O(N) for important calls 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> To: Matt Armstrong <matt@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-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Fri, 07 Oct 2022 14:14:39 -0400 Cc: =?utf-8?Q?Gerd_M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, bug-gnu-emacs@HIDDEN, Eli Zaretskii <eliz@HIDDEN>, Stefan Monnier <monnier@HIDDEN> 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.
Andreas Politz <mail@HIDDEN>:bug-gnu-emacs@HIDDEN.
Full text available.bug-gnu-emacs@HIDDEN:bug#58361; Package emacs.
Full text available.
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.