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: State of the overlay tree branch? Date: Fri, 23 Mar 2018 09:55:38 -0400 Message-ID: References: <834lldp18f.fsf@gnu.org> <9646341d-700b-4240-216b-8c0e753fa79f@arkona-technologies.de> <86d03e78-9984-f33e-a3f3-3faa4b34d78b@arkona-technologies.de> <83vadso9ad.fsf@gnu.org> <5155d5e2-6b5c-581e-89fe-4f3af717304f@arkona-technologies.de> <4c82fcbd-961a-c6ca-b1f0-6b85665cb339@arkona-technologies.de> <1ea4248a-11ce-00a9-0644-df7b2e5a3a58@arkona-technologies.de> <838tajhsau.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1521813257 31472 195.159.176.226 (23 Mar 2018 13:54:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 23 Mar 2018 13:54:17 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: Emacs developers To: Noam Postavsky Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 23 14:54:13 2018 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 1ezN93-00085v-EU for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 14:54:13 +0100 Original-Received: from localhost ([::1]:38190 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNB6-0002iG-Lj for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 09:56:20 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:55304) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNAX-0002hp-NQ for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:55:46 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ezNAU-0006Xh-M3 for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:55:45 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:56731) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNAU-0006Vi-H2 for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:55:42 -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 w2NDtcOm032454; Fri, 23 Mar 2018 09:55:39 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id E2CD760223; Fri, 23 Mar 2018 09:55:38 -0400 (EDT) In-Reply-To: (Noam Postavsky's message of "Fri, 23 Mar 2018 09:37:55 -0400") 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, RV6249=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6249> : inlines <6514> : streams <1782034> : uri <2613419> 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:223964 Archived-At: >> If we want to really solve this problem, we should use an algorithm with >> at most an O(log N) complexity, e.g. keeping the markers in >> a red-black tree, or inside a sorted array (probably with a gap like we >> have for the buffer text) so we can do a binary search. > > Is this related to Bug#24548 "Long GC delays with many non-detached > markers (PATCH)" > aka Bug#29439 "Quadratic complexity in sweep_markers"? Not directly, no, Stefan