From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Stephen J. Turnbull" Newsgroups: gmane.emacs.devel Subject: Re: Release plans Date: Wed, 03 Sep 2008 14:08:11 +0900 Message-ID: <87myip4y10.fsf@uwakimon.sk.tsukuba.ac.jp> References: <878wusz0v9.fsf@uwakimon.sk.tsukuba.ac.jp> <87vdxp27z6.fsf@uwakimon.sk.tsukuba.ac.jp> <87prnxe5hc.fsf@rattlesnake.com> <873aktck5d.fsf@uwakimon.sk.tsukuba.ac.jp> <87k5e5dsvq.fsf@rattlesnake.com> <48B44802.1080302@emf.net> <48B5D5EF.2030501@emf.net> <20080827220906.GB5374@muc.de> <48B5FB11.6090708@emf.net> <48BC4DF0.3090908@emf.net> <87ljybp6t1.fsf@uwakimon.sk.tsukuba.ac.jp> <48BDA56C.10502@emf.net> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1220418216 17565 80.91.229.12 (3 Sep 2008 05:03:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 3 Sep 2008 05:03:36 +0000 (UTC) Cc: Stefan Monnier , rms@gnu.org, emacs-devel@gnu.org To: Thomas Lord Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Sep 03 07:04:30 2008 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1KakXd-0007TF-Rf for ged-emacs-devel@m.gmane.org; Wed, 03 Sep 2008 07:04:30 +0200 Original-Received: from localhost ([127.0.0.1]:52828 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KakWe-0000Br-MQ for ged-emacs-devel@m.gmane.org; Wed, 03 Sep 2008 01:03:28 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KakWW-0000Aq-Gt for emacs-devel@gnu.org; Wed, 03 Sep 2008 01:03:20 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KakWU-0000AX-5Y for emacs-devel@gnu.org; Wed, 03 Sep 2008 01:03:18 -0400 Original-Received: from [199.232.76.173] (port=41648 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KakWU-0000AU-20 for emacs-devel@gnu.org; Wed, 03 Sep 2008 01:03:18 -0400 Original-Received: from mtps01.sk.tsukuba.ac.jp ([130.158.97.223]:53135) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1KakWO-0003v5-E8; Wed, 03 Sep 2008 01:03:12 -0400 Original-Received: from uwakimon.sk.tsukuba.ac.jp (uwakimon.sk.tsukuba.ac.jp [130.158.99.156]) by mtps01.sk.tsukuba.ac.jp (Postfix) with ESMTP id 7FB361535B3; Wed, 3 Sep 2008 14:03:10 +0900 (JST) Original-Received: by uwakimon.sk.tsukuba.ac.jp (Postfix, from userid 1000) id 42C271A260E; Wed, 3 Sep 2008 14:08:11 +0900 (JST) In-Reply-To: <48BDA56C.10502@emf.net> X-Mailer: VM 8.0.12-devo-585 under 21.5 (beta28) "fuki" 78738a40e31e XEmacs Lucid (x86_64-unknown-linux) X-detected-kernel: by monty-python.gnu.org: Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:103486 Archived-At: Thomas Lord writes: > It says extents are implemented as a pair of gap buffers. Well, yes and no. The extent lists used by redisplay are implemented as a pair of gap buffers; this allows O(log N) -- where N is always the number of objects (here, extents) -- identification of the display-order-maximal extent containing a buffer location, and also is the correct order for redisplay to process extents so that redisplay of an Emacs window can be O(number of buffer characters visible in window). However, extents themselves are full-fledged Lisp objects allocated on the heap, and that is where position information is kept. And it turns out that in many common cases finding a particular extent is O(N) (consider the case where the desired extent happens to cover the whole buffer and the location is (point-max), while any extent *could* have the desired property). How does your splay tree scheme handle that? > It also talks about the concept of cached stacks of events -- e.g., > a cache of the list of extents at a given point from which the > extents over a nearby point can be quickly computed. With the caveat above, this is the current scheme. > The splay tree of gap buffers should do considerably better with > [the] access patterns [Steve described]. That's the theory, > anyway: OK. > The new data structure has an operation equivalent > to "move the gap" (so, e.g., insertions just write to > a linear piece of memory) however gap motion > is O(log N) buffer size in terms of operations and > O(1) for the amount of text that has to move. Marker > updates, getting the position of a marker, and Urk. Markers are not interesting AFAICS. What needs to be efficient is extents (whether text properties or overlays), because they carry display properties and other things that may be referenced many times in a pass over the buffer (eg, font-lock or building a parse tree). What is difficult (for me, anyway) is extents. > getting back a list of text properties over a given point are all > O(log N) -- O(1) with good locality. This last I'll want to see. I suspect it will be expensive in space. > If extents are still the double gap buffer + extent stack > cache then I can see where you'd have problems like those > you describe. In theory, this new thing does better in > those cases. Well, we'll see. I've found it quite easy to develop O(log N) algorithms for markers. But (except for redisplay, where the two-sorted-list scheme is great), common operations on extents can involve O(N) algorithms.