From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: `make-overlay' very slow Date: Fri, 10 Apr 2009 19:36:21 -0400 Message-ID: References: <20090410.215424.136009858.wl@gnu.org> <20090410.235059.24212167.wl@gnu.org> <20090411.004248.247201382.wl@gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1239406607 3308 80.91.229.12 (10 Apr 2009 23:36:47 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Apr 2009 23:36:47 +0000 (UTC) Cc: acm@muc.de, schwab@linux-m68k.org, emacs-devel@gnu.org To: Werner LEMBERG Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Apr 11 01:38:05 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1LsQIO-0008Nn-F8 for ged-emacs-devel@m.gmane.org; Sat, 11 Apr 2009 01:38:04 +0200 Original-Received: from localhost ([127.0.0.1]:39066 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LsQGz-0007vv-QH for ged-emacs-devel@m.gmane.org; Fri, 10 Apr 2009 19:36:37 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LsQGs-0007s0-W2 for emacs-devel@gnu.org; Fri, 10 Apr 2009 19:36:31 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LsQGn-0007jb-R0 for emacs-devel@gnu.org; Fri, 10 Apr 2009 19:36:30 -0400 Original-Received: from [199.232.76.173] (port=51336 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LsQGn-0007jI-Fe for emacs-devel@gnu.org; Fri, 10 Apr 2009 19:36:25 -0400 Original-Received: from ironport2-out.pppoe.ca ([206.248.154.182]:12306 helo=ironport2-out.teksavvy.com) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1LsQGl-0000yG-PP; Fri, 10 Apr 2009 19:36:23 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkIGAPp030lLd+7D/2dsb2JhbACBUskGg3sGhRQ X-IronPort-AV: E=Sophos;i="4.40,170,1238990400"; d="scan'208";a="36886680" Original-Received: from 75-119-238-195.dsl.teksavvy.com (HELO pastel.home) ([75.119.238.195]) by ironport2-out.teksavvy.com with ESMTP; 10 Apr 2009 19:36:22 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id E23D883B6; Fri, 10 Apr 2009 19:36:21 -0400 (EDT) In-Reply-To: <20090411.004248.247201382.wl@gnu.org> (Werner LEMBERG's message of "Sat, 11 Apr 2009 00:42:48 +0200 (CEST)") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:110201 Archived-At: > and I found out that it is, alas, unusable. It starts with about 1000 > replacements per second on my GNU/Linux box (using simply `-' as the > regexp), but soon the speed decreases: After approx. 10000 > replacements it only can handle 100 replacements per second -- the > attached code now contains a small counter to show the progress. If > you comment out the call to `make-overlay', the code really flies... > Am I doing something wrong? overlays have a poor algorithmic behavior (many operations take a time proportional to the number of overlays in the buffer). Better use text-properties (which are implemented with a tree and should provide something closer to O(log N) complexity instead). Stefan