From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: =?UTF-8?Q?Cl=c3=a9ment_Pit-Claudel?= Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Wed, 3 May 2017 20:54:32 -0400 Message-ID: References: <87d1jylv43.fsf@fastmail.com> <877f53ftab.fsf@hochschule-trier.de> <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; charset=windows-1252 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1493859739 16165 195.159.176.226 (4 May 2017 01:02:19 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 4 May 2017 01:02:19 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 Cc: Stefan Monnier , emacs-devel@gnu.org To: Andreas Politz Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu May 04 03:02:16 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 1d659r-000488-Mk for ged-emacs-devel@m.gmane.org; Thu, 04 May 2017 03:02:15 +0200 Original-Received: from localhost ([::1]:39232 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d659x-0007vD-7G for ged-emacs-devel@m.gmane.org; Wed, 03 May 2017 21:02:21 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:57020) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1d652V-00023d-5X for emacs-devel@gnu.org; Wed, 03 May 2017 20:54:40 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1d652S-0006FV-47 for emacs-devel@gnu.org; Wed, 03 May 2017 20:54:39 -0400 Original-Received: from mail-qt0-x236.google.com ([2607:f8b0:400d:c0d::236]:33287) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1d652R-0006EM-Vr for emacs-devel@gnu.org; Wed, 03 May 2017 20:54:36 -0400 Original-Received: by mail-qt0-x236.google.com with SMTP id m36so4809080qtb.0 for ; Wed, 03 May 2017 17:54:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:references:cc:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding; bh=yDJaCBpbiZtuGvN5jluG6kGeOFR05ccA8sCvggoEBik=; b=K0Y++QDI4WzKkmP8tr7ltVdaKHUG0z4UP3vzbeSRJlbOTLHaxZlgmTDSvXCULsTq4C E0jV2kRRIWPdcMFNvndHljxbewzIRB6Q1G1agQdxyBYdoxkIyn0oGWwYh0Q4KZdSN6xs 8EetxWV050VAOuKYm7e875IkZvjagGmBPBcSawOS+Z9d+ExBRhtgESJ1s6j/BoL65c9i tRKyCwlzDgq1vWnXGXRRQ1bLyMnNflj0+trax+lZYNssp8G+pwPeV8f8YJKlzNLS36zr qw6aVLP8SB+XbtGtIXltVTNuzxbsLI0C3nmBntNdQE3F1PVthvCG12jNKAKVWA+VNMmx cd0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding; bh=yDJaCBpbiZtuGvN5jluG6kGeOFR05ccA8sCvggoEBik=; b=QJg4oFdD3QcJAAnPzheXR5fNn7js7V53kuIbxNF8osR2uBD+JOzYFKDz5STwBw6fKm VXpXNKMRdJbbcOW2skwIYub9/NcI+gx+COsgMYGam589gkLR8EQ0+zuaoaX70whRoG8x B4AGb+FTiN21AmujJxxAwU2Wizh99HEAF1TZ0do2qxnknSR4TD+xVedRaaqR4u/jjD2v lZwz1TrdikDxXYmpgh0//SJ/YSdA83pwJeBhFC2vAK+ODjiagSWh5hFNSd4lCO6vTc+5 wGL/RSJKqyV91RI7sPMjUvZiZ5QP56klK69P9PXmN6HKYo+mqDikmIfesHHxjZx8MCpY NhFA== X-Gm-Message-State: AN3rC/59bS6o7r6bJjIZL5+NbFn1TPLkzJnbHvIzlhW8/PbzC5kEPlQU +WFJmFZ1UYEDvA== X-Received: by 10.237.40.2 with SMTP id r2mr38365999qtd.173.1493859273885; Wed, 03 May 2017 17:54:33 -0700 (PDT) Original-Received: from [18.189.26.125] (dhcp-18-189-26-125.dyn.mit.edu. [18.189.26.125]) by smtp.gmail.com with ESMTPSA id h6sm500612qkd.56.2017.05.03.17.54.32 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 03 May 2017 17:54:33 -0700 (PDT) In-Reply-To: <877f1xu4ra.fsf@luca> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:400d:c0d::236 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:214556 Archived-At: On 2017-05-03 15:20, Andreas Politz wrote: > 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. That would be wonderful. Overlay performance is a recurring issue in Flycheck and PG. I will try to run your branch and benchmark it with Flycheck, but I remember seeing great results. > 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. Could this comment be included in Emacs' TODO list? This sounds like a nice potential improvement over your current implementation, but it doesn't sound like its absence should prevent a merge. Thanks for working on this! Clément.