From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Werner LEMBERG Newsgroups: gmane.emacs.bugs Subject: bug#2963: wishlist: improve speed of `make-overlay' Date: Sat, 11 Apr 2009 16:02:50 +0200 (CEST) Message-ID: <20090411.160250.235838581.wl@gnu.org> Reply-To: Werner LEMBERG , 2963@emacsbugs.donarmstrong.com NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1239459852 16375 80.91.229.12 (11 Apr 2009 14:24:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 11 Apr 2009 14:24:12 +0000 (UTC) To: bug-gnu-emacs@gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sat Apr 11 16:25:31 2009 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1Lse9A-0006qC-SM for geb-bug-gnu-emacs@m.gmane.org; Sat, 11 Apr 2009 16:25:29 +0200 Original-Received: from localhost ([127.0.0.1]:56844 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Lse7m-0004Ns-BY for geb-bug-gnu-emacs@m.gmane.org; Sat, 11 Apr 2009 10:24:02 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Lse7h-0004N7-IX for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:23:57 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Lse7d-0004LE-N6 for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:23:57 -0400 Original-Received: from [199.232.76.173] (port=34786 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Lse7d-0004Ku-4H for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:23:53 -0400 Original-Received: from rzlab.ucr.edu ([138.23.92.77]:55135) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1Lse7b-0004Qr-J7 for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:23:52 -0400 Original-Received: from rzlab.ucr.edu (rzlab.ucr.edu [127.0.0.1]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n3BENnOG012999; Sat, 11 Apr 2009 07:23:49 -0700 Original-Received: (from debbugs@localhost) by rzlab.ucr.edu (8.13.8/8.13.8/Submit) id n3BEA4ws009577; Sat, 11 Apr 2009 07:10:04 -0700 X-Loop: owner@emacsbugs.donarmstrong.com Resent-From: Werner LEMBERG Resent-To: bug-submit-list@donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Sat, 11 Apr 2009 14:10:04 +0000 Resent-Message-ID: Resent-Sender: owner@emacsbugs.donarmstrong.com X-Emacs-PR-Message: report 2963 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Original-Received: via spool by submit@emacsbugs.donarmstrong.com id=B.12394585797399 (code B ref -1); Sat, 11 Apr 2009 14:10:04 +0000 Original-Received: (at submit) by emacsbugs.donarmstrong.com; 11 Apr 2009 14:02:59 +0000 X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. Original-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 ; Sat, 11 Apr 2009 07:02:57 -0700 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LsdnL-0003ai-Nl for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:02:55 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LsdnF-0003TX-Hu for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:02:53 -0400 Original-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@gnu.org; Sat, 11 Apr 2009 10:02:49 -0400 Original-Received: from mail.gmx.net ([213.165.64.20]:50675) by monty-python.gnu.org with smtp (Exim 4.60) (envelope-from ) id 1LsdnE-0008HR-Ld for bug-gnu-emacs@gnu.org; Sat, 11 Apr 2009 10:02:49 -0400 Original-Received: (qmail invoked by alias); 11 Apr 2009 14:02:46 -0000 Original-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 X-Mailer: Mew version 6.2.50 on Emacs 22.3.1 / Mule 5.0 (SAKAKI) X-Y-GMX-Trusted: 0 X-FuHaFi: 0.72 X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Resent-Date: Sat, 11 Apr 2009 10:23:57 -0400 X-BeenThere: bug-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:27077 Archived-At: 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