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:19:11 -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 1521811050 3551 195.159.176.226 (23 Mar 2018 13:17:30 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 23 Mar 2018 13:17:30 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Mar 23 14:17:26 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 1ezMZS-0000pn-KL for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 14:17:26 +0100 Original-Received: from localhost ([::1]:38061 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezMbV-0002ak-N4 for ged-emacs-devel@m.gmane.org; Fri, 23 Mar 2018 09:19:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47722) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ezMbP-0002aY-CO for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:19:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ezMbL-0007QL-Do for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:19:27 -0400 Original-Received: from [195.159.176.226] (port=49077 helo=blaine.gmane.org) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1ezMbL-0007P7-7i for emacs-devel@gnu.org; Fri, 23 Mar 2018 09:19:23 -0400 Original-Received: from list by blaine.gmane.org with local (Exim 4.84_2) (envelope-from ) id 1ezMZE-0000bY-GC for emacs-devel@gnu.org; Fri, 23 Mar 2018 14:17:12 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 32 Original-X-Complaints-To: usenet@blaine.gmane.org Cancel-Lock: sha1:+3NmSkRBnGzQYljyxHX4zxF2HdQ= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 195.159.176.226 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:223962 Archived-At: > 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. > 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. 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. Stefan