From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: line buffer as Red Black Trees instead of linear Date: Wed, 21 May 2014 20:03:22 +0300 Message-ID: <83zjibm5d1.fsf@gnu.org> References: <83mwein6w1.fsf@gnu.org> <83fvkamg9v.fsf@gnu.org> <837g5mm8ke.fsf@gnu.org> <83ha4jnotl.fsf@gnu.org> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1400691814 24553 80.91.229.3 (21 May 2014 17:03:34 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 21 May 2014 17:03:34 +0000 (UTC) Cc: monnier@iro.umontreal.ca, emacs-devel@gnu.org To: Alin Soare Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 21 19:03:26 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 1Wn9vK-0004rr-1O for ged-emacs-devel@m.gmane.org; Wed, 21 May 2014 19:03:26 +0200 Original-Received: from localhost ([::1]:32781 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn9vJ-0001vU-F6 for ged-emacs-devel@m.gmane.org; Wed, 21 May 2014 13:03:25 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35123) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn9vC-0001ub-Hc for emacs-devel@gnu.org; Wed, 21 May 2014 13:03:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wn9v7-0006Rp-8z for emacs-devel@gnu.org; Wed, 21 May 2014 13:03:18 -0400 Original-Received: from mtaout24.012.net.il ([80.179.55.180]:57063) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn9v6-0006RT-T0 for emacs-devel@gnu.org; Wed, 21 May 2014 13:03:13 -0400 Original-Received: from conversion-daemon.mtaout24.012.net.il by mtaout24.012.net.il (HyperSendmail v2007.08) id <0N5X00E00O7QK000@mtaout24.012.net.il> for emacs-devel@gnu.org; Wed, 21 May 2014 20:00:08 +0300 (IDT) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout24.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0N5X00DCGOK8XS20@mtaout24.012.net.il>; Wed, 21 May 2014 20:00:08 +0300 (IDT) In-reply-to: X-012-Sender: halo1@inter.net.il X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 80.179.55.180 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:171998 Archived-At: > Date: Wed, 21 May 2014 19:00:49 +0300 > From: Alin Soare > Cc: Stefan Monnier , emacs-devel@gnu.org > > > > Ideally, at each node all the text should have the same properties > > (marks, > > > fonts, etc), and chaging 1 such property can be implemented by splitting > > > the node or removing a few nodes, and their text be preserved in 1 node > > > (only the field owner must be changed when a few nodes are joined in only > > > 1). > > > > That would mean we will need to rearrange the tree each time text > > properties or overlays change, something we avoid today. > > > > Yes, each time ! But however, a simple mental computation is still much > faster than now, because the computation is made only 1 for each change, > and there will be lots of simple pre-computations that never repeat. Not necessarily. One scenario that comes to mind is when you visit a large buffer, and have jit-stealth enabled, which fontifies the buffer when Emacs is idle. With your suggestion, each stealth fontification will cause tree rearrangement; most of these will be in portions of the buffer that are never displayed at all. More generally, the savings from maintaining face information as part of the buffer text are highly dependent on the usage patterns, and it is not clear to me they will always be a win. Once again, I urge you to measure and time the relevant code, and also collect the various popular use cases relevant to the issue, because otherwise you will be most probably optimizing in the wrong place. > > Also please note that 'display' properties can specify that Emacs > > displays something entirely different from buffer text, so the display > > engine will still need to consult Lisp strings, in addition to the > > text. (Yes, it's lots of fun.) > > What is displayed will be all the time pre-computed for each node, and this > will never be re-computed for that node before modifications. The attribute > NODE->what-to-display-data perhaps will be evaluated at the 1st display, > not at the node creation. So this means you will also have to rearrange the tree whenever display properties change, which is more work, and non-trivial one at that (access to overlay strings is not very efficient in Emacs, when there are many of them). And what happens with text that is covered with an invisible text property? Does it disappear from the tree?