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: Fri, 16 May 2014 11:28:17 +0300 Message-ID: <837g5mm8ke.fsf@gnu.org> References: <83mwein6w1.fsf@gnu.org> <83fvkamg9v.fsf@gnu.org> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1400228918 30011 80.91.229.3 (16 May 2014 08:28:38 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 16 May 2014 08:28:38 +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 Fri May 16 10:28:32 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 1WlDVH-0006sz-Lb for ged-emacs-devel@m.gmane.org; Fri, 16 May 2014 10:28:31 +0200 Original-Received: from localhost ([::1]:34087 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlDVH-0000nj-A2 for ged-emacs-devel@m.gmane.org; Fri, 16 May 2014 04:28:31 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45752) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlDV9-0000nY-J3 for emacs-devel@gnu.org; Fri, 16 May 2014 04:28:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WlDV4-0003SU-DO for emacs-devel@gnu.org; Fri, 16 May 2014 04:28:23 -0400 Original-Received: from mtaout28.012.net.il ([80.179.55.184]:57045) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WlDV4-0003Ro-0t for emacs-devel@gnu.org; Fri, 16 May 2014 04:28:18 -0400 Original-Received: from conversion-daemon.mtaout28.012.net.il by mtaout28.012.net.il (HyperSendmail v2007.08) id <0N5N00D00R3EN600@mtaout28.012.net.il> for emacs-devel@gnu.org; Fri, 16 May 2014 11:26:28 +0300 (IDT) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout28.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0N5N00CPVRG4ND20@mtaout28.012.net.il>; Fri, 16 May 2014 11:26:28 +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.184 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:171873 Archived-At: > Date: Fri, 16 May 2014 10:44:44 +0300 > From: Alin Soare > Cc: Stefan Monnier , emacs-devel@gnu.org > > > > 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 values that need to be precomputed are the metrics of each "display element" (character glyph, stretch glyph, image glyph, etc.) that will (or would) be displayed when/if the line is shown on the screen. Your suggestion calls for precomputing those in advance, while the current implementation computes them only when they are actually needed. I very much doubt that your suggestion, if implemented, will be a net win. It might make sense to cache the values, once they are computed, so that any subsequent routines that need to access the same portions of buffer text won't need to recompute the same metrics. But before this kind of caching is attempted, Someone(TM) should demonstrate that the same portions of the long lines are traversed by the display engine more than once, because otherwise what you suggest will be pure overhead with no hope of any gains. > 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. "Premature optimization is the root of all evil." (Donald Knuth) I would suggest to study the relevant code and, more importantly, time it to find the _real_ (as opposed to imaginary) hot spots. Then present that data, and we could thereafter discuss whether your suggested solution might indeed speed up the code which takes up the lion's share of the time when Emacs needs to display very long lines. If indeed these techniques could help, patches will be very welcome, as this is an annoying problem, and there's a bug report for it (see http://debbugs.gnu.org/cgi/bugreport.cgi?bug=13675).