From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Wed, 21 Sep 2016 19:43:12 +0300 Message-ID: <83eg4dfbkv.fsf@gnu.org> References: <87d1jylv43.fsf@fastmail.com> <83k2e5fdmo.fsf@gnu.org> Reply-To: Eli Zaretskii NNTP-Posting-Host: blaine.gmane.org X-Trace: blaine.gmane.org 1474476215 4587 195.159.176.226 (21 Sep 2016 16:43:35 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 21 Sep 2016 16:43:35 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Sep 21 18:43:30 2016 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bmkbx-0006ls-PZ for ged-emacs-devel@m.gmane.org; Wed, 21 Sep 2016 18:43:05 +0200 Original-Received: from localhost ([::1]:44165 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bmkbw-0000ZR-4Z for ged-emacs-devel@m.gmane.org; Wed, 21 Sep 2016 12:43:04 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34930) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bmkbn-0000Xq-KM for emacs-devel@gnu.org; Wed, 21 Sep 2016 12:42:56 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bmkbj-0005qH-Vf for emacs-devel@gnu.org; Wed, 21 Sep 2016 12:42:54 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:39909) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bmkbj-0005qB-Sl; Wed, 21 Sep 2016 12:42:51 -0400 Original-Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:4090 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.82) (envelope-from ) id 1bmkbi-0002VH-Vj; Wed, 21 Sep 2016 12:42:51 -0400 In-reply-to: (message from Stefan Monnier on Wed, 21 Sep 2016 12:24:30 -0400) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.devel:207667 Archived-At: > From: Stefan Monnier > Cc: emacs-devel@gnu.org > Date: Wed, 21 Sep 2016 12:24:30 -0400 > > >> > Speaking of which, is the byte position stored in a marker of any > >> > significance in an overlay? Otherwise I could at least get rid of > >> > those. > >> AFAIK, the byte-position of markers is used, but the byte-position of > >> overlays isn't, so you should be able to get rid of them. > > Why bother? > > AFAIK there'd be no benefit at all until/unless you add extra code to > try and use those byte-positions somewhere. > I know of two cases where we use such byte-positions, currently: > - in goto-char, but that never receives an overlay as argument. > - when converting charpos <-> bytepos (where we use the table of > markers as a kind of cache of existing translations) That's a larger issue about markers, AFAU, it has nothing in particular to do with overlays. My point was that if overlay edges are implemented as markers, their movement with buffer changes is for free, and doesn't need to be reimplemented. I also envision other subtleties that rely on them being markers (e.g., the buffer-modification hooks). I see no reason why Joakim should add to his immediate job, which is large already, also the job of replacing start/end markers and dealing with the fallout. That should IMO be a separate job. > - This hack of (ab)using markers can occasionally lead to bad > performance because it makes the charpos<->bytepos conversion O(N) > in the worst case where N is the number of markers which can get very > large). > - It can also lead to bad performance in the other case: lack of > markers around the "destination" makes the conversion O(N) in the > worst case where N is the size of the displacement. Do you have numbers to back that up? IME, this is a non-issue. in any case, I was only talking about the overlay start/end implementation, not about the byte position of markers in general.