GNU logs - #58361, boring messages

Message sent to bug-gnu-emacs@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
To: Matt Armstrong <matt@HIDDEN>
Cc: gerd.moellmann@HIDDEN, 58361 <at> debbugs.gnu.org, eliz@HIDDEN, monnier@HIDDEN
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>
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:

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
To: Andreas Politz <mail@HIDDEN>
Cc: gerd.moellmann@HIDDEN, matt@HIDDEN, 58361 <at> debbugs.gnu.org, eliz@HIDDEN
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
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.