From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: State of the overlay tree branch? Date: Fri, 23 Mar 2018 17:22:10 +0300 Message-ID: <837eq2j2i5.fsf@gnu.org> 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> Reply-To: Eli Zaretskii NNTP-Posting-Host: blaine.gmane.org X-Trace: blaine.gmane.org 1521814820 13276 195.159.176.226 (23 Mar 2018 14:20:20 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 23 Mar 2018 14:20:20 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 23 15:20:15 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 1ezNYF-0003MA-Mf for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 15:20:15 +0100 Original-Received: from localhost ([::1]:38295 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNaJ-0007Vk-3U for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 10:22:23 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:33688) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNaA-0007VU-JG for emacs-devel@gnu.org; Fri, 23 Mar 2018 10:22:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ezNa5-0004Ji-MH for emacs-devel@gnu.org; Fri, 23 Mar 2018 10:22:14 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:56344) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezNa5-0004JM-J5; Fri, 23 Mar 2018 10:22:09 -0400 Original-Received: from [176.228.60.248] (port=2533 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ezNa4-0001Te-Va; Fri, 23 Mar 2018 10:22:09 -0400 In-reply-to: (message from Stefan Monnier on Fri, 23 Mar 2018 09:19:11 -0400) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e 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:223965 Archived-At: > From: Stefan Monnier > Date: Fri, 23 Mar 2018 09:19:11 -0400 > > > I'd be interested to see a comparison with a code that ignores the > > markers entirely, and uses just these 4: > > > > CONSIDER (BUF_PT (b), BUF_PT_BYTE (b)); > > CONSIDER (BUF_GPT (b), BUF_GPT_BYTE (b)); > > CONSIDER (BUF_BEGV (b), BUF_BEGV_BYTE (b)); > > CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b)); > > I tried that, and in the synthetic benchmark which tries to reproduce > Sebastian's lsp-mode situation the result was indeed much better, but > then in other benchmarks it caused very significant slowdowns. In what benchmarks did it cause significant slowdowns? > > That's because BYTECHAR_DISTANCE_INCREMENT is probably a function of > > the number of markers. > > I haven't investigated closely enough to be sure, but in my tests with > INCREMENT=50 I reached points where adding more overlays did not make > things worse any more, so I suspect that the ideal INCREMENT depends on > the buffer size more than on the number of markers. Could be. My point was that it isn't a constant. > 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. Yes, agreed.