From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.devel Subject: Re: State of the overlay tree branch? Date: Fri, 23 Mar 2018 09:37:55 -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; charset="UTF-8" X-Trace: blaine.gmane.org 1521812165 17309 195.159.176.226 (23 Mar 2018 13:36:05 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 23 Mar 2018 13:36:05 +0000 (UTC) Cc: Emacs developers To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 23 14:36:00 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 1ezMrP-0004Kq-W3 for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 14:36:00 +0100 Original-Received: from localhost ([::1]:38127 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezMtT-0003W6-AD for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 09:38:07 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51980) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezMtK-0003VC-93 for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:38:00 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ezMtJ-0003Ka-5l for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:37:58 -0400 Original-Received: from mail-ot0-x230.google.com ([2607:f8b0:4003:c0f::230]:41178) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1ezMtJ-0003Js-1Y for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:37:57 -0400 Original-Received: by mail-ot0-x230.google.com with SMTP id i28-v6so13241801otf.8 for ; Fri, 23 Mar 2018 06:37:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=9ho8yjCJQu7LOvXlO6eKSirNailThtgJpMgzrQ6kZfw=; b=YuonK+lQRYv9gXFkbwMBfHBF4KEYxz47kpw5kv+8O/jOlBO2XW9IxWQ82qRQPsUVtU mu7OB5q5Q0bQftj/TAHJlvaBx/wV78NiSbfToO94359ukjcYC912s20PcYnSVZ22hfDg 6L9kDMdZ43ODL1hw2krV7pIMzr6artiU0iJkWAWCJEw017INXQDKg0cQwjFDGw4pUyb9 +JcZ98La6HGd1/WP9JS3g/MZ3RDX6qDEu2SdStUzJAmmMJn5jA/8b8GpcoY6KnEj8x0k kbfsbyNkn8UzAN20sQheo8NlRQ+/UbdpkTrPLrR0yM+8MARQlvEZeGp3HuMiPXc0ajyW YxRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=9ho8yjCJQu7LOvXlO6eKSirNailThtgJpMgzrQ6kZfw=; b=l2Ot7EviYixuS3R1yPX3YZLltVteRIA9VPCvICUZt9NCxXCXI5rBX0biyW5rcgQyEs UrrBM6o196GwY9bRI98dbadAKdks4D9AJJU5TsvQar+iP0QFZp8kZwAveCZyy6Se4fbF ulGVW68U602Dn2t86dpkghxCdFvMP0pOilpvViiyrghZSHH+Tkf2pCZNzhJONcIxk4OE wkLUor0X+n/6zYAtj/hXx6LBjKeTzvklC7h9+FgFFWvzla/ZYSP6mn61B1MuEYSPQ3TC WYBIaCrfFBntnIqIJhQgNdrolq19yQtCjXlSI7wkCDZ1Ut32hGmtMXStjrlnCR2RBVNK 19AA== X-Gm-Message-State: AElRT7FLogc/mPnKUvzTO9mKx4zcTIr1O53HUOlpGpzk5bYOaPPwYTZT b0tUq7KMVt4wNFJMsBFJbSDNLe2sFIyk7qTBFs0= X-Google-Smtp-Source: AIpwx48Tnvrr60Lz8xh3kyTXs7J7npy8AChQn0BJa6LiCjCYjUn60eFb0WH5jmmCwXAcISeV1KTbIgzjkdbRewMBqug= X-Received: by 2002:a9d:4469:: with SMTP id f38-v6mr38623otj.335.1521812276355; Fri, 23 Mar 2018 06:37:56 -0700 (PDT) Original-Received: by 10.74.212.23 with HTTP; Fri, 23 Mar 2018 06:37:55 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4003:c0f::230 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:223963 Archived-At: On 23 March 2018 at 09:19, Stefan Monnier wrote: > In any case, my patch is just a "quick hack" to try and reduce the pain, > but it doesn't really solve the problem: the slow down with many markers > and a large buffer still grows pretty significantly with the size of > the buffer. I think it's worse than O(sqrt N). > > 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"? https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24548 https://debbugs.gnu.org/cgi/bugreport.cgi?bug=29439