From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
To: Andreas Politz <mail@andreas-politz.de>
Cc: gerd.moellmann@gmail.com, matt@rfc20.org, 58361@debbugs.gnu.org,
eliz@gnu.org
Subject: bug#58361: 29.0.50; noverlay branch is O(N) for important calls
Date: Fri, 07 Oct 2022 14:38:31 -0400 [thread overview]
Message-ID: <jwvfsfz5vx9.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <D54E3787-D89B-43E1-A03E-75DFC6A34A62@andreas-politz.de> (Andreas Politz's message of "Fri, 7 Oct 2022 18:51:14 +0200")
> 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 then
> either delegate to one or both trees, depending on the operation. The trick
> 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@rfc20.org>:
>>
>> To 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.
>>
>> 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.
>>
>>
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>
>>>> 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
>>>
>>> The core operation in itree.c is the equivalent of `overlays-in/at`.
>>
>> [...]
>>
>> 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.
>>
>>> Realistic benchmarks would be most welcome.
>>
>> 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.
>>
>>
>>> [ 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. ]
>>>
>>> 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.
>>>
>>> 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).
>>
>> 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.
>>
>> This is why I keep coming back to the idea of storing both BEG and END
>> positions in ordered collections at all times.
>>
>>
>>> 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).
>>
>> ...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.
next prev parent reply other threads:[~2022-10-07 18:38 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-06 23:25 bug#58342: 29.0.50; noverlay branch is O(N) for important calls Matt Armstrong
2022-10-07 1:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 7:09 ` Eli Zaretskii
2022-10-07 13:36 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 13:57 ` Eli Zaretskii
2022-10-07 14:47 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 15:23 ` Matt Armstrong
2022-10-07 16:51 ` bug#58361: " Andreas Politz
2022-10-07 18:38 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors [this message]
2022-10-07 17:11 ` bug#58342: " Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-07 20:37 ` Matt Armstrong
2022-10-07 21:22 ` Drew Adams
2022-10-08 0:27 ` Drew Adams
2022-10-07 21:58 ` Dmitry Gutov
2022-10-08 6:20 ` Eli Zaretskii
2022-10-08 13:08 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-08 17:24 ` Drew Adams
2022-10-08 23:08 ` Matt Armstrong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=jwvfsfz5vx9.fsf-monnier+emacs@gnu.org \
--to=bug-gnu-emacs@gnu.org \
--cc=58361@debbugs.gnu.org \
--cc=eliz@gnu.org \
--cc=gerd.moellmann@gmail.com \
--cc=mail@andreas-politz.de \
--cc=matt@rfc20.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).