From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Alin Soare Newsgroups: gmane.emacs.devel Subject: Re: line buffer as Red Black Trees instead of linear Date: Wed, 21 May 2014 19:00:49 +0300 Message-ID: References: <83mwein6w1.fsf@gnu.org> <83fvkamg9v.fsf@gnu.org> <837g5mm8ke.fsf@gnu.org> <83ha4jnotl.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11335cf29ef96604f9eb1969 X-Trace: ger.gmane.org 1400688102 2798 80.91.229.3 (21 May 2014 16:01:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 21 May 2014 16:01:42 +0000 (UTC) Cc: Stefan Monnier , emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 21 18:01:34 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 1Wn8xS-0002Ug-Ee for ged-emacs-devel@m.gmane.org; Wed, 21 May 2014 18:01:34 +0200 Original-Received: from localhost ([::1]:60636 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn8xS-0002Lz-2E for ged-emacs-devel@m.gmane.org; Wed, 21 May 2014 12:01:34 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:46996) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn8wo-0001KB-Hv for emacs-devel@gnu.org; Wed, 21 May 2014 12:00:56 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Wn8wn-0000nL-BM for emacs-devel@gnu.org; Wed, 21 May 2014 12:00:54 -0400 Original-Received: from mail-ie0-x22b.google.com ([2607:f8b0:4001:c03::22b]:44092) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Wn8wk-0000ma-He; Wed, 21 May 2014 12:00:51 -0400 Original-Received: by mail-ie0-f171.google.com with SMTP id to1so2195173ieb.2 for ; Wed, 21 May 2014 09:00:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Q6WaALvDhCHlpQpCS+O2zjSPUEPVs7kCeLex26Ypj2U=; b=jMYelJ0/BJuNXdeqht64j7472icUeQcNQUCBwpMTOPtpF75zxakvcY+2OZhv+EhOoi /SVXA4J6WO7MkehgStU7xXa5szxF+yGGk2nErrj5EASJNMHaBMJr6h+tX/aH39tFVuw+ C3/DyZ6tK5EztaIAy8NzbaR49sisbCqcVy/vNEfvbxkQOeVS+LBNU4rnSnhvKRGLI2gc 6PiOG20lma2UKspBmhBlj9HW1fVMbGyK7WzyI27Me9fTRa/WjOhNEx2SYrc6tKxaDDSk hngJnyqI0mg7t6UjlvyPk0RET0T/j2YxBNtK6OE1eQvm8ynb+1eg21OE0W9ieLrLlzMG ggMw== X-Received: by 10.51.18.100 with SMTP id gl4mr14591715igd.1.1400688049320; Wed, 21 May 2014 09:00:49 -0700 (PDT) Original-Received: by 10.43.142.70 with HTTP; Wed, 21 May 2014 09:00:49 -0700 (PDT) In-Reply-To: <83ha4jnotl.fsf@gnu.org> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c03::22b 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:171994 Archived-At: --001a11335cf29ef96604f9eb1969 Content-Type: text/plain; charset=UTF-8 2014-05-21 18:17 GMT+03:00 Eli Zaretskii : > > Date: Wed, 21 May 2014 11:34:10 +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 all the attributes will be pre-computed at the creation of the node. Some attributes, like # of newlines on the text at the left of the node and on the self will be precomputed at the creation. The Node->marks will be perhaps precomputed when some mark is added in the text within the node. Display props are pre-computed when the redisplay-internal requires it, so kind of lazy. > 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. Note also that I will do such that each node keeps not a block of text, but a linked list of blocks of text, such that to be fast to manipulate operations like join and split. Apart from search in buffer and reading the text at a given offset(point), that will be a little slower because the problem of page cache, all the other functions will be faster (at a first sight). We will see. When i start working, I will send you private message to ask you to read what I did. Try since October on to do it. --001a11335cf29ef96604f9eb1969 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable



2014-05-21 18:17 GMT+03:00 Eli Zaretskii <eliz@gnu.org>:<= br>
> Date: Wed, 21 May 2014 11:34:10 +0300
> From: Alin Soare <as1789@gmail.com>
> Cc: Stefan Monnier <mon= nier@iro.umontreal.ca>, emacs= -devel@gnu.org
>
> Ideally, at each node all the text should have t= he same properties (marks,
> fonts, etc), and chaging 1 such property can be implemented by splitti= ng
> the node or removing a few nodes, and their text be preserved in 1 nod= e
> (only the field owner must be changed when a few nodes are joined in o= nly
> 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 r= epeat. Not all the attributes will be pre-computed at the creation of the n= ode. Some attributes, like # of newlines on the text at the left of the nod= e and on the self will be precomputed at the creation. The Node->marks w= ill be perhaps precomputed when some mark is added in the text within the n= ode. Display props are pre-computed when the redisplay-internal requires it= , so kind of lazy.


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. =C2=A0(Yes, it's lots of fun.)


What is displayed will be all the time pre-computed for ea= ch node, and this will never be re-computed for that node before modificati= ons. The attribute NODE->what-to-display-data perhaps will be evaluated = at the 1st display, not at the node creation.

Note also that I will do such that each node keeps not = a block of text, but a linked list of blocks of text, such that to be fast = to manipulate operations like join and split.

Apart from search in buffer and reading the text at a given offset(point), = that will be a little slower because the problem of page cache, all the oth= er functions will be faster (at a first sight).

We will see. When i start working, I will send you private message to ask y= ou to read what I did. Try since October on to do it.

<= div>

=C2=A0

--001a11335cf29ef96604f9eb1969--