From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Ihor Radchenko Newsgroups: gmane.emacs.bugs Subject: bug#35453: 26.1; Poor performance of vertical-motion in large org buffer Date: Sun, 05 May 2019 09:05:46 +0800 Message-ID: <87k1f5ww0l.fsf@yantar92-laptop.i-did-not-set--mail-host-address--so-tickle-me> References: <87pnpaob79.fsf@yantar92-laptop.i-did-not-set--mail-host-address--so-tickle-me> <83zhoatavq.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="149778"; mail-complaints-to="usenet@blaine.gmane.org" Cc: 35453@debbugs.gnu.org To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun May 05 03:07:18 2019 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hN5cZ-000cov-K5 for geb-bug-gnu-emacs@m.gmane.org; Sun, 05 May 2019 03:07:15 +0200 Original-Received: from localhost ([127.0.0.1]:34759 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hN5cU-0002jm-Qd for geb-bug-gnu-emacs@m.gmane.org; Sat, 04 May 2019 21:07:10 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:49992) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hN5cN-0002jd-UA for bug-gnu-emacs@gnu.org; Sat, 04 May 2019 21:07:05 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hN5cM-0000Ki-L5 for bug-gnu-emacs@gnu.org; Sat, 04 May 2019 21:07:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:39169) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1hN5cM-0000KY-HF; Sat, 04 May 2019 21:07:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1hN5cM-0002dz-58; Sat, 04 May 2019 21:07:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Ihor Radchenko Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org, emacs-orgmode@gnu.org Resent-Date: Sun, 05 May 2019 01:07:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 35453 X-GNU-PR-Package: emacs,org-mode Original-Received: via spool by 35453-submit@debbugs.gnu.org id=B35453.155701841510152 (code B ref 35453); Sun, 05 May 2019 01:07:02 +0000 Original-Received: (at 35453) by debbugs.gnu.org; 5 May 2019 01:06:55 +0000 Original-Received: from localhost ([127.0.0.1]:52713 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hN5cF-0002df-6u for submit@debbugs.gnu.org; Sat, 04 May 2019 21:06:55 -0400 Original-Received: from mail-pl1-f174.google.com ([209.85.214.174]:45273) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1hN5cD-0002dS-PD for 35453@debbugs.gnu.org; Sat, 04 May 2019 21:06:54 -0400 Original-Received: by mail-pl1-f174.google.com with SMTP id o5so4535353pls.12 for <35453@debbugs.gnu.org>; Sat, 04 May 2019 18:06:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:in-reply-to:references:date:message-id :mime-version; bh=lTztffiHv1NUVpnMXeHtwcu/9yxBsBnVGiR8cysgmCg=; b=hGaeY8SlrLDPA9nQPwAE7YUB0QqMgZPvTWBBpQ9EzYhENQ9sh1UhT5pYQmyvYzEu0p fhbAHHf9Q/yr+rBaFY18rf8+1KSKH8indgv9YdDTGLiGJnQAlRCEDzS8MwS0klbqydYY 0tqy8DhB/mPaCOcE2OcNPMNMAtIxxNlKhiC2zNqvsLlQ+G7GWxxbbH4BNmwxf7YTPaNQ JmlkLeMBSX+CMs55Acw/De2IA7W/8loBjRO2idS5j1aK1dxpLe3ymNX9VZIvOEI2ak4M +aLLRs/+nmP5lBXlRCwcJ97dZBYW6zSVmzpV+7U4BHds94ByXhjNb3qK+p9VPo6BCRSi bq9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version; bh=lTztffiHv1NUVpnMXeHtwcu/9yxBsBnVGiR8cysgmCg=; b=TCKy1h/IX4q2az8oRKTQ3pic98qNd//cpVvoRi7l7+dUBkWBWr38wViVmLt7SScUUA mm4wOxRwssRW+acTPWbMISJ7+Y7kntuWrRu8YcLc5PodNFQw0saF3DKqsArSKYiE//vz +vZBoXP68f+X+wpwbYQjCny3BRYLqqUBCAgC0GXMxs8Jr0QhkBSeoMjUfOLQ0+w+7ztb 0ELIvtLNFfzyya/mq8uZEN18bhCSf+DFXG4lXvvgXMTOok03PKKXN6Xeymcv1PVUJfi5 rEucla5MHyJlE9Esq4UqhuR3hCapMfWf0hFuWSA+EYhKhjuo1CutdCjjrt3efLGrKJYQ PyIA== X-Gm-Message-State: APjAAAVPyY7hdHj6HWcWTtspBRlr9nEZz7cPEv2B6huwv50xmCYTB8lm +OiTwDmA7lIjlK9uDzksxHE= X-Google-Smtp-Source: APXvYqxZDuZRo9s7Q6i9pDdfk2bK2tpTW0+FtuvOJjC7AsU6GQCam15WR1dOUlHZ61U8mI6VGeDTKQ== X-Received: by 2002:a17:902:2825:: with SMTP id e34mr22332001plb.264.1557018407761; Sat, 04 May 2019 18:06:47 -0700 (PDT) Original-Received: from localhost ([104.237.95.59]) by smtp.gmail.com with ESMTPSA id q5sm8720505pfb.51.2019.05.04.18.06.45 (version=TLS1_3 cipher=AEAD-AES256-GCM-SHA384 bits=256/256); Sat, 04 May 2019 18:06:46 -0700 (PDT) In-Reply-To: <83zhoatavq.fsf@gnu.org> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.51.188.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:158771 Archived-At: Not sure why, but my reply did not show up in the mailing list. Resending. > I'm not sure I understand: is your problem with vertical-motion, or in > general with moving by lines in that file's buffer? The problem is actually more general. I had a poor performance on line motion, re-search-forward, and outline-based motion. However, performance of the latter commands seems to depend on the visibility state of the buffer. I was only able to reproduce the issue for vertical-motion. > So instead of skipping > all that hidden text in one go, vertical-motion loops over those 17.5K > overlays examining the properties of each one of them. And that takes > time. Make sense. Though it was very weird for me that I did not have a gradual performance degradation on that file. The motion suddenly became much slower in a single day (the file size did not change significantly). I do not remember for sure, but I suspect that it might have something to deal with org-lint, which somehow introduced extra property drawers in the file. > Of course, if someone comes up with ideas how to speed up > vertical-motion without changing what Org does with overlays and/or > how overlays are implemented, such ideas will be most welcome. Rather dumb idea. Currently, vertical-motion just loops over all the intervals in the buffer. What if we optimise next-single-char-property-change and use it in vertical-motion? Say, the interval data structure can extended. In addition to the currently available pointers to next and previous intervals, each (or just 'invisible') property of the interval might also contain a pointer to next/previous interval with different property value. Then, by increasing the structure size a bit, we can significantly speed up the buffer motion commands. Best, Ihor Eli Zaretskii writes: >> From: 'Ihor Radchenko' >> Date: Thu, 25 Apr 2019 14:23:06 +0800 >> >> C-n and C-p are extremely slow (>10 sec to move one visual line) when >> moving around a large org buffer in overview state, especially right >> after opening the file. >> The issue seems to be with low-level vertical-motion command - M-: >> (vertical-motion 1) also takes >10sec on some lines. >> >> Steps to reproduce (emacs -Q): >> 1. Open the attached org file >> 2. C-n, C-n, C-n, C-n >> 3. Observe emacs hanging for >10sec. > > I'm not sure I understand: is your problem with vertical-motion, or in > general with moving by lines in that file's buffer? > > If the problem is the latter, then my advice to Org users is to use > "C-c C-n/C-p" and "C-c C-f/C-b", not the normal cursor motion > commands, because Org makes the latter very slow when a large portion > of a large buffer is hidden. I will now try to explain why. > > This buffer's size is around 1MB and 42K lines, and the part between > the 3rd and the 4th heading holds its lion's share: almost 40K lines > of text. When C-n calls vertical-motion, the latter needs to find the > buffer position displayed directly below the place where you typed > C-n. Since much of the text between these places, vertical-motion > needs to skip the invisible text as quickly as possible, because from > the user's POV that text "doesn't exist": it isn't on the screen. > However, Org makes this skipping exceedingly hard, because (1) it uses > overlays (as opposed to text properties) to hide text, and (2) it puts > an awful lot of overlays on the hidden text: there are 18400 overlays > in this file's buffer, 17500 of them between the 3rd and the 4th > heading. Because of this, vertical-motion must examine each and every > overlay as it moves through the text, because each overlay can > potentially change the 'invisible' property of text, or it might have > a display string that needs to be displayed. So instead of skipping > all that hidden text in one go, vertical-motion loops over those 17.5K > overlays examining the properties of each one of them. And that takes > time. > > Profiling shows that 80%(!) of the CPU time is spent in the function > overlays_at which looks for overlays at a given buffer position, and > 10% more in marker_position (because overlay endpoints are markers). > So 90% of the time you wait for the cursor to move is spent processing > overlays. > > Compare this with Outline mode, which places a single overlay on the > entire hidden text between headings. If you visit the same file in > Outline mode, C-n will be much, much faster. > > So with the current implementation of Org and overlays, Org users are > well advised not to make such large bodies in their Org files, and if > they do, definitely not to use C-n and C-p for vertical motion. > > Of course, if someone comes up with ideas how to speed up > vertical-motion without changing what Org does with overlays and/or > how overlays are implemented, such ideas will be most welcome. -- Ihor Radchenko