From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Wed, 03 May 2017 15:40:23 -0400 Message-ID: References: <87d1jylv43.fsf@fastmail.com> <878tpiqiuc.fsf@hochschule-trier.de> <87shnppspb.fsf@hochschule-trier.de> <87o9yc9v30.fsf@hochschule-trier.de> <87a89vaes3.fsf@hochschule-trier.de> <87efz7n0g5.fsf@fastmail.com> <877f4uah6i.fsf@hochschule-trier.de> <83k28u1uyz.fsf@gnu.org> <871suxs9ad.fsf@hochschule-trier.de> <837f4pxpdc.fsf@gnu.org> <877f4lls9e.fsf@hochschule-trier.de> <838tp0q3k8.fsf@gnu.org> <87vas4owus.fsf@luca> <87r32rpfhv.fsf@luca> <87vas07zdn.fsf@luca> <877f1xu4ra.fsf@luca> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1493840439 30505 195.159.176.226 (3 May 2017 19:40:39 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 3 May 2017 19:40:39 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux) Cc: =?windows-1252?Q?Cl=E9ment?= Pit-Claudel , emacs-devel@gnu.org To: Andreas Politz Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 03 21:40:33 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d608W-0007mP-Uw for ged-emacs-devel@m.gmane.org; Wed, 03 May 2017 21:40:33 +0200 Original-Received: from localhost ([::1]:38373 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d608c-0000EQ-II for ged-emacs-devel@m.gmane.org; Wed, 03 May 2017 15:40:38 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:40116) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d608V-0000Dj-Q5 for emacs-devel@gnu.org; Wed, 03 May 2017 15:40:32 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d608R-0002PZ-OH for emacs-devel@gnu.org; Wed, 03 May 2017 15:40:31 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:37061) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d608R-0002OO-Ht for emacs-devel@gnu.org; Wed, 03 May 2017 15:40:27 -0400 Original-Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id v43JeNUG031143; Wed, 3 May 2017 15:40:23 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 62E5A61A2E; Wed, 3 May 2017 15:40:23 -0400 (EDT) In-Reply-To: <877f1xu4ra.fsf@luca> (Andreas Politz's message of "Wed, 03 May 2017 21:20:09 +0200") X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 2 Rules triggered EDT_SA_DN_PASS=0, RV6015=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6015> : inlines <5845> : streams <1743918> : uri <2420714> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.22 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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" Xref: news.gmane.org gmane.emacs.devel:214551 Archived-At: > I stopped working on this, since it wasn't clear where this will be > going (among other things). But I'm willing to pick it up again. > Following is a fairly concise status-report. What's missing for it to be "good enough for master" (which AFAIK means mostly that the code is clean, there are no known bugs, and the performance is varies between "no worse" and "much better" than what we currently have)? > I think it would be advantageous to represent overlays with identical > start values as a single node by utilizing a linked list. This would > improve performance in some degenerate cases (from a tree's > perspective), by combining the best aspects of the (current) list and > tree approaches. I don't think we should care too much about those degenerate cases. > We also talked about using the same data-structure for marker, but > there is no work done in this direction currently. Good. Maybe it's a good idea, but maybe not. There's no hurry to investigate (let alone make a decision on) this. Stefan