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

Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.

Package: emacs; Severity: minor; Reported by: Werner LEMBERG <wl@HIDDEN>; merged with #26051; dated Sat, 11 Apr 2009 14:10:04 UTC; Maintainer for emacs is bug-gnu-emacs@HIDDEN.
Forcibly Merged 2963 26051. Request was from Lars Ingebrigtsen <larsi@HIDDEN> to control <at> debbugs.gnu.org. Full text available.
Severity set to `wishlist' from `normal' Request was from Chong Yidong <cyd@HIDDEN> to control@HIDDEN. Full text available.

Message received at submit@HIDDEN:


Received: (at submit) by emacsbugs.donarmstrong.com; 11 Apr 2009 14:02:59 +0000
From werner.lemberg@HIDDEN Sat Apr 11 07:02:59 2009
X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02
	(2008-06-10) on rzlab.ucr.edu
X-Spam-Level: 
X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available.
	hammytokens:Tokens not available.
X-Spam-Status: No, score=0.0 required=4.0 tests=none autolearn=ham
	version=3.2.5-bugs.debian.org_2005_01_02
Received: from lists.gnu.org (lists.gnu.org [199.232.76.165])
	by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n3BE2tkw007390
	for <submit@HIDDEN>; Sat, 11 Apr 2009 07:02:57 -0700
Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43)
	id 1LsdnL-0003ai-Nl
	for bug-gnu-emacs@HIDDEN; Sat, 11 Apr 2009 10:02:55 -0400
Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43)
	id 1LsdnF-0003TX-Hu
	for bug-gnu-emacs@HIDDEN; Sat, 11 Apr 2009 10:02:53 -0400
Received: from [199.232.76.173] (port=55331 helo=monty-python.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43)
	id 1LsdnF-0003TD-CT
	for bug-gnu-emacs@HIDDEN; Sat, 11 Apr 2009 10:02:49 -0400
Received: from mail.gmx.net ([213.165.64.20]:50675)
	by monty-python.gnu.org with smtp (Exim 4.60)
	(envelope-from <werner.lemberg@HIDDEN>)
	id 1LsdnE-0008HR-Ld
	for bug-gnu-emacs@HIDDEN; Sat, 11 Apr 2009 10:02:49 -0400
Received: (qmail invoked by alias); 11 Apr 2009 14:02:46 -0000
Received: from 77-20-101-114-dynip.superkabel.de (EHLO localhost) [77.20.101.114]
  by mail.gmx.net (mp067) with SMTP; 11 Apr 2009 16:02:46 +0200
X-Authenticated: #54312696
X-Provags-ID: V01U2FsdGVkX199cFMvHdN9dM4/5JoR/oIWOiPud8nOx3xRhgIEx9
	hISBSr6ngpI3vg
Date: Sat, 11 Apr 2009 16:02:50 +0200 (CEST)
Message-Id: <20090411.160250.235838581.wl@HIDDEN>
To: bug-gnu-emacs@HIDDEN
Subject: wishlist: improve speed of `make-overlay'
From: Werner LEMBERG <wl@HIDDEN>
X-Mailer: Mew version 6.2.50 on Emacs 22.3.1 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Y-GMX-Trusted: 0
X-FuHaFi: 0.72
X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized.


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





Acknowledgement sent to Werner LEMBERG <wl@HIDDEN>:
New bug report received and forwarded. Copy sent to Emacs Bugs <bug-gnu-emacs@HIDDEN>. Full text available.
Report forwarded to bug-submit-list@HIDDEN, Emacs Bugs <bug-gnu-emacs@HIDDEN>:
bug#2963; Package emacs. Full text available.
Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.
Last modified: Mon, 25 Nov 2019 12:00:02 UTC

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