GNU bug report logs - #2963
wishlist: improve speed of `make-overlay'

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 2963 in the body.
You can then email your comments to 2963 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Werner LEMBERG <wl <at> gnu.org>
To: bug-gnu-emacs <at> gnu.org
Subject: wishlist: improve speed of `make-overlay'
Date: Sat, 11 Apr 2009 16:02:50 +0200 (CEST)

The complexity of `make-overlay' appears to be O(N), which makes it
unbearably slow for larger buffers.  In my test case, it started with
about 1000 calls per second, and after about 10000 calls it already
reduced to approx. 100 calls per second.

On the other hand, handling text properties is O(log N), which works
fine even for my 400000 line document.

Stefan says:

  But note that it's not just `make-overlay': every time we make a
  modification to the buffer, we have to update the position of all
  the overlays (and markers) after point.  So, yes, a better
  data-structure for overlays (and markers) would be very welcome.



      Werner

Message #12 received at 2963 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Andreas Politz <politza <at> hochschule-trier.de>
Cc: Werner LEMBERG <wl <at> gnu.org>, 2963 <at> debbugs.gnu.org
Subject: Re: bug#2963: wishlist: improve speed of `make-overlay'
Date: Sun, 18 Jul 2021 23:04:51 +0200

Werner LEMBERG <wl <at> gnu.org> writes:

> The complexity of `make-overlay' appears to be O(N), which makes it
> unbearably slow for larger buffers.

Andreas did a lot of work on reimplementing the overlay internals a few
years back -- but I see that it was never merged?

Andreas, what's the state of the feature/noverlay branch?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Message #15 received at 2963 <at> debbugs.gnu.org (full text, mbox):

From: Mauro Aranda <maurooaranda <at> gmail.com>
To: 2963 <at> debbugs.gnu.org
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, wl <at> gnu.org,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, politza <at> hochschule-trier.de
Subject: Re: bug#2963: wishlist: improve speed of `make-overlay'
Date: Sat, 21 Oct 2023 08:33:34 -0300

Lars Ingebrigtsen <larsi <at> gnus.org> writes:

> Werner LEMBERG <wl <at> gnu.org> writes:
>
>> The complexity of `make-overlay' appears to be O(N), which makes it
>> unbearably slow for larger buffers.
>
> Andreas did a lot of work on reimplementing the overlay internals a few
> years back -- but I see that it was never merged?
>
> Andreas, what's the state of the feature/noverlay branch?

This message was 2 years ago.  Meanwhile the feature/noverlay branch got
merged.  Maybe this can be closed.  CCing Stefan M.

Message #18 received at 2963 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Mauro Aranda <maurooaranda <at> gmail.com>
Cc: larsi <at> gnus.org, wl <at> gnu.org, 2963 <at> debbugs.gnu.org, monnier <at> iro.umontreal.ca,
 politza <at> hochschule-trier.de
Subject: Re: bug#2963: wishlist: improve speed of `make-overlay'
Date: Sat, 21 Oct 2023 14:43:34 +0300

> Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, wl <at> gnu.org,
>  Stefan Monnier <monnier <at> iro.umontreal.ca>, politza <at> hochschule-trier.de
> Date: Sat, 21 Oct 2023 08:33:34 -0300
> From: Mauro Aranda <maurooaranda <at> gmail.com>
> 
> Lars Ingebrigtsen <larsi <at> gnus.org> writes:
> 
>  > Werner LEMBERG <wl <at> gnu.org> writes:
>  >
>  >> The complexity of `make-overlay' appears to be O(N), which makes it
>  >> unbearably slow for larger buffers.
>  >
>  > Andreas did a lot of work on reimplementing the overlay internals a few
>  > years back -- but I see that it was never merged?
>  >
>  > Andreas, what's the state of the feature/noverlay branch?
> 
> This message was 2 years ago.  Meanwhile the feature/noverlay branch got
> merged.  Maybe this can be closed.  CCing Stefan M.

I think it should be closed, indeed.

Message #23 received at 2963-done <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>, Mauro Aranda <maurooaranda <at> gmail.com>
Cc: larsi <at> gnus.org, wl <at> gnu.org, 2963-done <at> debbugs.gnu.org,
 monnier <at> iro.umontreal.ca, politza <at> hochschule-trier.de
Subject: Re: bug#2963: wishlist: improve speed of `make-overlay'
Date: Sat, 21 Oct 2023 04:52:15 -0700

Eli Zaretskii <eliz <at> gnu.org> writes:

>> Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, wl <at> gnu.org,
>>  Stefan Monnier <monnier <at> iro.umontreal.ca>, politza <at> hochschule-trier.de
>> Date: Sat, 21 Oct 2023 08:33:34 -0300
>> From: Mauro Aranda <maurooaranda <at> gmail.com>
>>
>> Lars Ingebrigtsen <larsi <at> gnus.org> writes:
>>
>>  > Werner LEMBERG <wl <at> gnu.org> writes:
>>  >
>>  >> The complexity of `make-overlay' appears to be O(N), which makes it
>>  >> unbearably slow for larger buffers.
>>  >
>>  > Andreas did a lot of work on reimplementing the overlay internals a few
>>  > years back -- but I see that it was never merged?
>>  >
>>  > Andreas, what's the state of the feature/noverlay branch?
>>
>> This message was 2 years ago.  Meanwhile the feature/noverlay branch got
>> merged.  Maybe this can be closed.  CCing Stefan M.
>
> I think it should be closed, indeed.

Yup, done.

Previous Next

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