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: Overlay mechanic improvements Date: Sun, 21 Sep 2014 20:31:11 -0400 Message-ID: References: <871tr6qup8.fsf@fencepost.gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1411345924 11375 80.91.229.3 (22 Sep 2014 00:32:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 22 Sep 2014 00:32:04 +0000 (UTC) Cc: dak@gnu.org, emacs-devel@gnu.org To: Richard Stallman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Sep 22 02:31:57 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XVrXo-0004RJ-OD for ged-emacs-devel@m.gmane.org; Mon, 22 Sep 2014 02:31:56 +0200 Original-Received: from localhost ([::1]:41569 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVrXo-0001Tr-7U for ged-emacs-devel@m.gmane.org; Sun, 21 Sep 2014 20:31:56 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50483) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVrXV-0001TL-Er for emacs-devel@gnu.org; Sun, 21 Sep 2014 20:31:45 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XVrXN-0000Uh-0o for emacs-devel@gnu.org; Sun, 21 Sep 2014 20:31:37 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:50203) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVrXF-0000Sh-5r; Sun, 21 Sep 2014 20:31:21 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArUGAIDvNVNFpZEG/2dsb2JhbABQCYMGg0rAPYEXF3SCJQEBAQECAVYPFAULCw4mEhQYDSSIBAjSGReOFglbB4Q4BIx1kyOJAYFqg0whgSw X-IPAS-Result: ArUGAIDvNVNFpZEG/2dsb2JhbABQCYMGg0rAPYEXF3SCJQEBAQECAVYPFAULCw4mEhQYDSSIBAjSGReOFglbB4Q4BIx1kyOJAYFqg0whgSw X-IronPort-AV: E=Sophos;i="4.97,753,1389762000"; d="scan'208";a="90501983" Original-Received: from 69-165-145-6.dsl.teksavvy.com (HELO pastel.home) ([69.165.145.6]) by ironport2-out.teksavvy.com with ESMTP/TLS/DHE-RSA-AES256-SHA; 21 Sep 2014 20:31:12 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 998BA61782; Sun, 21 Sep 2014 20:31:11 -0400 (EDT) In-Reply-To: (Richard Stallman's message of "Sun, 21 Sep 2014 17:48:15 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 206.248.154.181 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:174633 Archived-At: > Reasons for overlays being slow are: > - if you have N overlays, you have 2N markers, so every > insertion/deletion of text will involve a traversal of those 2N elements. > - when we need to move from bytepos to charpos (or vice versa), we go > through the 2N markers again. > - when the Elisp code didn't know to overlay-recenter, or when overlays > are added/removed from the "wrong" place (w.r.t to the overlay > "center"), every overlay creation/removal takes O(N) time. > Yes, that's true. > Moving overlays into a balanced binary tree will remove those > algorithmic performance problems. I'm not sue why you'd be opposed, > since it will provide the exact same functionality anyway. It's just an > internal detail of implementation. > Why not do it for all markers, then? We could try, but it wouldn't address the last problem above. > A large number of markers will cause the same slowdown even if they > are not made for overlays. Indeed. But I've never seen this problem, except via the creation of many overlays. Note that if/when overlays are made efficient and markers's efficiency becomes a problem, we can use the new overlay implementation for markers (in the worst case, representing markers as degenerate overlays). > A marker, whether it's on its own or an end of an overlay, has an > identity that is permanent, whereas intervals are split and recombined > whenever useful. I must say I'm troubled by your questions and objections. What is the problem with my proposal? Are you afraid it will make Emacs worse? Or are you afraid it simply won't work? Why do you care if we keep overlays in a tree instead of singly-linked lists? Stefan