From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Fri, 17 Feb 2017 05:58:34 +0100 Message-ID: <871suxs9ad.fsf@hochschule-trier.de> References: <87d1jylv43.fsf@fastmail.com> <87fujv64mn.fsf@hochschule-trier.de> <87fujvpkzc.fsf@fastmail.com> <87vasr5tqd.fsf@hochschule-trier.de> <87d1ex4kon.fsf@hochschule-trier.de> <87d1evod6x.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> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1487307589 11301 195.159.176.226 (17 Feb 2017 04:59:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 17 Feb 2017 04:59:49 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) Cc: emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Feb 17 05:59:43 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 1ceadw-0002Ds-Mx for ged-emacs-devel@m.gmane.org; Fri, 17 Feb 2017 05:59:40 +0100 Original-Received: from localhost ([::1]:51556 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ceae2-0007w0-KH for ged-emacs-devel@m.gmane.org; Thu, 16 Feb 2017 23:59:46 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38881) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ceadG-0007tr-PP for emacs-devel@gnu.org; Thu, 16 Feb 2017 23:59:00 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ceadF-000869-Ks for emacs-devel@gnu.org; Thu, 16 Feb 2017 23:58:58 -0500 Original-Received: from gateway-a.fh-trier.de ([143.93.54.181]:45287) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1cead9-0007oe-OM; Thu, 16 Feb 2017 23:58:52 -0500 X-Virus-Scanned: by Amavisd-new + McAfee uvscan + ClamAV [Rechenzentrum Hochschule Trier (RZ/HT)] Original-Received: from localhost (ip5f5bdee7.dynamic.kabel-deutschland.de [95.91.222.231]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: politza) by gateway-a.fh-trier.de (Postfix) with ESMTPSA id 3679D179A672; Fri, 17 Feb 2017 05:58:35 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha1; c=simple/simple; d=hochschule-trier.de; s=default; t=1487307515; bh=v/QsBW8iikdcysAU716fufHJJa4=; h=From:To:Cc:Subject:References:Date:In-Reply-To:Message-ID: MIME-Version:Content-Type; b=QvKi+bpjs0ILENSGpDlBkEU472vm4RSzYPVN6lEQ2/wr/sHVfosIYye9CuQvFqoz4 MEP1vCkRzMiP1MbUXVv55ITjgCfogGCPpcGP3CkGkLPpxOvV1p3Q32l/lYa1aQtWgI UfzkOumXyjq4FB2uFMe0K45Pf+jVUNeWvdISWiUc= In-Reply-To: <83k28u1uyz.fsf@gnu.org> (Eli Zaretskii's message of "Mon, 13 Feb 2017 08:11:00 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x [fuzzy] X-Received-From: 143.93.54.181 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:212428 Archived-At: So, I did as you ask and developed a couple of performance tests based on 3 variables. Let N = #overlays. 1. How the overlays are created + Either sequentially, one overlay per every other line or randomly, with random start and random length from 0 to 70. 2. What property to use + One of face, display (with a string) or invisible. 3. How the overlays are accessed + Either start at the top scroll down and up again, or jump to N/25 random positions and re-display there. This gives 2*3*2=12 different tests. In all of them I + ran all tests once with N=12.500 and 37500 overlays. + used a buffer with 2*N lines and 70 columns, + measured display time only, i.e. not make-overlay etc. . + ran each test thrice and took the average. *--------------------------------------------------------------* +----------------------------------+ | 12.5K | 37.5K | creation/property/action | list tree | list tree | ================================================================ |sequential/display/scroll | 6.32 5.24 | 37.59 16.47 | | | | | |sequential/display/random | 4.47 4.60 | 30.41 13.03 | +---------------------------+----------------+-----------------+ |sequential/face/scroll | 7.07 5.75 | 38.18 18.64 | | | | | |sequential/face/random | 4.25 4.13 | 30.50 13.23 | +---------------------------+----------------+-----------------+ |sequential/invisible/scroll| 6.63 5.02 | 36.62 16.02 | | | | | |sequential/invisible/random| 3.98 3.64 | 29.93 11.10 | +---------------------------+----------------+-----------------+ |random/display/scroll | 20.39 18.6 | 88.84 58.18 | | | | | |random/display/random | 7.57 7.22 | 77.65 21.14 | +---------------------------+----------------+-----------------+ |random/face/scroll | 11.16 8.75 | 88.31 27.72 | | | | | |random/face/random | 6.19 5.59 | 105.0 17.05 | +---------------------------+----------------+-----------------+ |random/invisible/scroll | 9.91 7.99 | 87.01 25.97 | | | | | |random/invisible/random | 6.58 5.75 | 86.73 17.01 | +---------------------------+----------------+-----------------+ | | list | tree | +---------------------------+----------------------------------+ |make-lines-invisible | 812.67 | 1.43 | | | | | |line-numbering | >15m * | 112.79 | ================================================================ As you can see they stick pretty close together in the cases with 12500 overlays, while the tree performs at least twice times better with 37500 overlays. After that I took 2 real-world cases. The first one stems from this [1] thread, where a user complains about the performance of his function make-lines-invisible. The function puts overlays with an invisible property on all lines matching a given regexp. The function also messages the number of hidden lines after every found match, which may be the reason for its bad performance with the current implementation, speak re-display. This test measures the creation of these overlays, no scrolling. For the other case, I wrote a very simple linum.el clone. This function creates an overlay with a margin property containing the line-number for every line in the buffer. Here I measured creation of the overlays as well as a full scroll up and down. Both of the final tests were run on a ~300000 lines file with one english word per line (/usr/share/dict/words). * I gave up and quit the test after nothing seemed to happen on the screen for more than 15 minutes. So, I think this looks pretty decent. Finally, let me note, that the tree implementation is not completely free of quadratic worst-case performance. There are certain patterns of overlay layout, which trigger this kind of thing. Though, it can be argued how likely these are to occur in a real-world scenario. Maybe I'll write a bit more about that later. -ap [1] https://lists.gnu.org/archive/html/emacs-devel/2009-04/msg00242.html