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: Tue, 14 Apr 2009 09:03:09 -0400 Message-ID: References: <20090410.235059.24212167.wl@gnu.org> <20090411.004248.247201382.wl@gnu.org> <20090411.081150.169736792.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 1239714225 29244 80.91.229.12 (14 Apr 2009 13:03:45 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 14 Apr 2009 13:03:45 +0000 (UTC) Cc: acm@muc.de, schwab@linux-m68k.org, emacs-devel@gnu.org To: Kenichi Handa Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Apr 14 15:05:04 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 1LtiJm-0001GF-GU for ged-emacs-devel@m.gmane.org; Tue, 14 Apr 2009 15:04:51 +0200 Original-Received: from localhost ([127.0.0.1]:46034 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LtiIO-0005Nw-2p for ged-emacs-devel@m.gmane.org; Tue, 14 Apr 2009 09:03:24 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LtiIJ-0005NX-Vn for emacs-devel@gnu.org; Tue, 14 Apr 2009 09:03:20 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LtiIF-0005MS-9g for emacs-devel@gnu.org; Tue, 14 Apr 2009 09:03:19 -0400 Original-Received: from [199.232.76.173] (port=53741 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LtiIF-0005MP-4R for emacs-devel@gnu.org; Tue, 14 Apr 2009 09:03:15 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.182]:41922) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1LtiIA-0008JG-LT; Tue, 14 Apr 2009 09:03:10 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvIEAGQm5ElLd+7D/2dsb2JhbACBUs06g3wGhRc X-IronPort-AV: E=Sophos;i="4.40,185,1238990400"; d="scan'208";a="37009414" Original-Received: from 75-119-238-195.dsl.teksavvy.com (HELO pastel.home) ([75.119.238.195]) by ironport2-out.teksavvy.com with ESMTP; 14 Apr 2009 09:03:09 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id B2C4080EF; Tue, 14 Apr 2009 09:03:09 -0400 (EDT) In-Reply-To: (Kenichi Handa's message of "Tue, 14 Apr 2009 21:03:33 +0900") 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:110271 Archived-At: >> Yes, that would be great. 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. > I have not yet thought about this idea in deep but perhaps > we can use one more interval tree for overlays. Yes, to speed up overlays algorithmically, we'd want to implement them with some kind of tree. If we could share some of the code with the text properties's interval tree that would be great, indeed. > More radical idea, not related to overlays, is to make one > interval tree for one text property; i.e. one for `face', > one for `fontified'... I think it not only improves the > processing speed, but also reduces the memory usage > (next-property-change will get slower, but we use > next-single-property-change more often). I've been tempted as well, but I'm not sure it'd be much of an improvement. You'd end up with many trees, so might need a hash-table or some other tree to map text-property names to the corresponding interval tree. Stefan