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: Fri, 16 May 2014 10:44:44 +0300 Message-ID: References: <83mwein6w1.fsf@gnu.org> <83fvkamg9v.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7bd75ecc51770e04f97f9628 X-Trace: ger.gmane.org 1400226301 24110 80.91.229.3 (16 May 2014 07:45:01 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 16 May 2014 07:45:01 +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 Fri May 16 09:44:53 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 1WlCp1-0006Bb-BL for ged-emacs-devel@m.gmane.org; Fri, 16 May 2014 09:44:51 +0200 Original-Received: from localhost ([::1]:33938 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlCp0-0003s3-Vx for ged-emacs-devel@m.gmane.org; Fri, 16 May 2014 03:44:50 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:37883) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlCoy-0003or-3O for emacs-devel@gnu.org; Fri, 16 May 2014 03:44:48 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WlCox-00055Z-AE for emacs-devel@gnu.org; Fri, 16 May 2014 03:44:48 -0400 Original-Received: from mail-ig0-x22b.google.com ([2607:f8b0:4001:c05::22b]:51944) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlCov-000558-No; Fri, 16 May 2014 03:44:45 -0400 Original-Received: by mail-ig0-f171.google.com with SMTP id c1so450901igq.16 for ; Fri, 16 May 2014 00:44:44 -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=RAgErIlPx38CCs+5laPbZuQEq3pUJM1TQ0ZqWUzusYo=; b=g3ioCM32Ejvo1Z8wxdH9Dj/sIzifTxWEalmVjPTjw/gamTNiwLiz72GEcly4vxovyV eeRr0VgwtJXmeSHfohxn1f8WnNotl7r4YTEvp/miVsahrrc648GJf1ERwnyWmw5TMohH So7NTw7gGX9apGP48ehfconWQC3+EfOVA9CIRIQgrred0RcRwxBjmxj5YW8g0KUP0VVV RcleK0DnVZO8148FzXdczWJP1B/C8/Cb/OsXcfc6F0AmqHiyPbSYPGwkkdn0GSKfgiP4 Wuv/7Ne2MkKczEbrbSZPllVaZvQzLlMuFjCsAf0q2n05TFMtegD77x73gp0itjBPMFkz E7gA== X-Received: by 10.50.154.73 with SMTP id vm9mr79260352igb.14.1400226284924; Fri, 16 May 2014 00:44:44 -0700 (PDT) Original-Received: by 10.43.142.70 with HTTP; Fri, 16 May 2014 00:44:44 -0700 (PDT) In-Reply-To: <83fvkamg9v.fsf@gnu.org> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4001:c05::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:171872 Archived-At: --047d7bd75ecc51770e04f97f9628 Content-Type: text/plain; charset=UTF-8 > > > > logarithmic in the worse case. > > Not in redisplay. It always moves to the next character, and > remembers the last place it was at, so it mostly only needs to advance > to the next character. > Whatever are the functions that scan the whole line of a buffer, slowing emacs, this can be improved if the values are precomputed and kept at the tree nodes, and when some change is made at a property, like the font, it will affect only some nodes, where it is precomputed. The solution of this problem is the red-black trees, by inserting at each node all the pre-computed characteristics of the block of text kept at the given node. Any modification will pre-compute a finite number of nodes, and when need to access them , only a logarithmic # of nodes will be taken in consideration for all possible operations. --047d7bd75ecc51770e04f97f9628 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

> logarithmic in the worse case.

Not in redisplay. =C2=A0It always moves to the next character, and remembers the last place it was at, so it mostly only needs to advance
to the next character.


Whatever are the functions that scan the whole line of a = buffer, slowing emacs, this can be improved if the values are precomputed a= nd kept at the tree nodes, and when some change is made at a property, like= the font, it will affect only some nodes, where it is precomputed.

The solutio= n of this problem is the red-black trees, by inserting at each node all the= pre-computed characteristics of the block of text kept at the given node. = Any modification will pre-compute a finite number of nodes, and when need t= o access them , only a logarithmic # of nodes will be taken in consideratio= n for all possible operations.


<= div class=3D"gmail_extra">
--047d7bd75ecc51770e04f97f9628--