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 12:07:48 -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 1411315716 597 80.91.229.3 (21 Sep 2014 16:08:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 21 Sep 2014 16:08:36 +0000 (UTC) Cc: David Kastrup , emacs-devel@gnu.org To: Richard Stallman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Sep 21 18:08:25 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 1XVjgT-000384-VZ for ged-emacs-devel@m.gmane.org; Sun, 21 Sep 2014 18:08:22 +0200 Original-Received: from localhost ([::1]:40049 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVjgT-0007Cu-Ek for ged-emacs-devel@m.gmane.org; Sun, 21 Sep 2014 12:08:21 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35465) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVjgI-0007Cb-JV for emacs-devel@gnu.org; Sun, 21 Sep 2014 12:08:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XVjgB-00067g-3l for emacs-devel@gnu.org; Sun, 21 Sep 2014 12:08:10 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.181]:57013) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XVjg3-000679-8j; Sun, 21 Sep 2014 12:07:55 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArUGAIDvNVNFpZEG/2dsb2JhbABZgwaDSsA9gRcXdIIlAQEBAQIBVg8UBQsLDiYSFBgNJIgECNIZF4lMhEpkB4Q4BIx1kyOJAYFqg0whgSw X-IPAS-Result: ArUGAIDvNVNFpZEG/2dsb2JhbABZgwaDSsA9gRcXdIIlAQEBAQIBVg8UBQsLDiYSFBgNJIgECNIZF4lMhEpkB4Q4BIx1kyOJAYFqg0whgSw X-IronPort-AV: E=Sophos;i="4.97,753,1389762000"; d="scan'208";a="90476775" 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 12:07:48 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id ACF64640EC; Sun, 21 Sep 2014 12:07:48 -0400 (EDT) In-Reply-To: (Richard Stallman's message of "Sun, 21 Sep 2014 09:35:35 -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:174610 Archived-At: > The existing code should be fat if you recenter the overlays > frequently at point, unless you have lots of overlays on one screen. > Do you recenter them? If so, why is it slow? 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. We rarely suffer from overlay's performance issues because most codes that could suffer from it simply avoid using overlays (or they try to minimize the number of overlays used, e.g. by flushing those overlays currently not visible), even when they would be the right tool. Or they add calls to overlay-recenter when the performance problem is diagnosed. 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. Note that I suggest to use the balanced binary tree used by text-properties, but there is no need for the two trees to be linked. We could as well use a separate tree for overlays. I'm not sure which of the two options is best in this regard, but at least I don't see any obvious reason why re-using the existing intervals.c tree wouldn't work well. Of course, I don't know for a fact that the end result will be better than what we currently have. We will of course need to experiment with it a bit. > Why aren't text properties right for this? There are various things which are difficult to do with text-properties. E.g. the lack of after/before_string is the most obvious difference. Stefan