From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#16830: [Bug] 24.3.50; massive slow down in forward-line Date: Mon, 10 Mar 2014 20:58:22 +0200 Message-ID: <83txb5op81.fsf@gnu.org> References: <20140221121606.GO7560@pille.home> <83lhx44pep.fsf@gnu.org> <20140221155119.GP7560@pille.home> <20140222083926.GC27381@pille.home> <838ut34ib3.fsf@gnu.org> <20140222110857.GF27381@pille.home> <831tyv4c7n.fsf@gnu.org> <20140222122747.GH27381@pille.home> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1394477950 2336 80.91.229.3 (10 Mar 2014 18:59:10 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 10 Mar 2014 18:59:10 +0000 (UTC) Cc: 16830@debbugs.gnu.org To: "Stefan-W. Hahn" , Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Mar 10 19:59:18 2014 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WN5Pw-0006oq-N1 for geb-bug-gnu-emacs@m.gmane.org; Mon, 10 Mar 2014 19:59:16 +0100 Original-Received: from localhost ([::1]:50653 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WN5Pw-0001mK-CT for geb-bug-gnu-emacs@m.gmane.org; Mon, 10 Mar 2014 14:59:16 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54516) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WN5Po-0001iY-8A for bug-gnu-emacs@gnu.org; Mon, 10 Mar 2014 14:59:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WN5Pi-00080I-SR for bug-gnu-emacs@gnu.org; Mon, 10 Mar 2014 14:59:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:59392) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WN5Pi-00080D-PB for bug-gnu-emacs@gnu.org; Mon, 10 Mar 2014 14:59:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WN5Pi-00076Y-4P for bug-gnu-emacs@gnu.org; Mon, 10 Mar 2014 14:59:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 10 Mar 2014 18:59:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 16830 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 16830-submit@debbugs.gnu.org id=B16830.139447792227266 (code B ref 16830); Mon, 10 Mar 2014 18:59:02 +0000 Original-Received: (at 16830) by debbugs.gnu.org; 10 Mar 2014 18:58:42 +0000 Original-Received: from localhost ([127.0.0.1]:60574 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WN5PN-00075h-8K for submit@debbugs.gnu.org; Mon, 10 Mar 2014 14:58:41 -0400 Original-Received: from mtaout20.012.net.il ([80.179.55.166]:53277) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WN5PK-00075U-64 for 16830@debbugs.gnu.org; Mon, 10 Mar 2014 14:58:39 -0400 Original-Received: from conversion-daemon.a-mtaout20.012.net.il by a-mtaout20.012.net.il (HyperSendmail v2007.08) id <0N2800F00HUFKD00@a-mtaout20.012.net.il> for 16830@debbugs.gnu.org; Mon, 10 Mar 2014 20:58:36 +0200 (IST) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout20.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0N2800F1CI1NK220@a-mtaout20.012.net.il>; Mon, 10 Mar 2014 20:58:36 +0200 (IST) In-reply-to: <20140222122747.GH27381@pille.home> X-012-Sender: halo1@inter.net.il X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.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-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:86723 Archived-At: > Date: Sat, 22 Feb 2014 13:27:47 +0100 > From: "Stefan-W. Hahn" > Cc: 16830@debbugs.gnu.org > > my original org-mode file: > emacs 24.3.50.1 2.065 sec (cache-long-scans nil, set local) > emacs 24.3.1 0.722 sec (cache-long-line-scan nil; as it was) > > test-neuter.org: > emacs 24.3.50.1 0.925 sec (cache-long-scans nil, set local) > emacs 24.3.1 0.381 sec (cache-long-line-scan nil; as it was) So I think it's a very Good Thing that we have this bug report, because looking into this issue produced a surprising (for me) discovery: turning off the newline cache makes forward-line significantly (5 to 20 times, depending on the file) faster than when the cache is turned on, for files with relatively short lines. It looks like the GCC implementation of memchr, used by the "dumb loop" in find_newline, is so efficient that it easily outperforms the "smart loop" which uses the cache, unless lines are very long, like at least 400 characters, at which point the code performs with and without the cache at the same speed. This striking difference in speed goes mostly unnoticed, because typically Emacs seldom if ever calls forward-line too much (see below for how much should "too much" for this to become visible). However, typing "C-c C-c" in the OP's Org file does just that -- it causes forward-line be invoked a huge number of times, because it walks the (29K line) Org file one line at a time with this function: (defsubst org-goto-line (N) (save-restriction (widen) (goto-char (point-min)) (forward-line (1- N)))) IOW, to move from line N to line N+1, this goes back to the beginning, and then traverses all the N lines again, plus one more line. Not a very efficient way, to put it mildly. So I suggest that Org developers look into making this use case more efficient, no matter whether the changes suggested below are or aren't installed. Inspired by the above function, I profiled find_newline, which is the workhorse of forward-line, using xdisp.c as the test file and this silly program: (let ((n 1)) (while (not (eobp)) (goto-char 1) (forward-line n) (setq n (1+ n)))) Running this program on xdisp.c calls find_newline 30K times and exercises its inner loop, which looks for the next newline, 450 million times. On my machine and in an optimized build, this takes about 1 min 14 sec with the cache turned on, and only 12 sec with it turned off, a factor of 6. By careful optimization of find_newline, I have succeeded to slash the time of the above loop by a factor of 2, see the proposed patch below. The "C-c C-c" command in the OP's Org file runs 3 times faster with those changes, and takes only 2 sec instead of 6.5. This still leaves the no-cache operation faster by a factor of about 3, though, in both these test cases. Again, this is for files whose average line length is 30 to 50 characters. For files whose lines are at least 10 times longer, the times with and without cache become almost identical, and for longer lines the cache starts to win. It would be nice to be able to turn the cache on and off dynamically, depending on the actual line length of the buffer. I tried to implement this, but my naive implementation didn't work well, because sampling of the lines tends to be extremely un-representative. If someone can come up with a smarter implementation, please show it. Until we can dynamically estimate the line length and turn the cache on only for long lines, I suggest to leave the default ON, and install the patches below. My reasoning is that in most situations the slow-down is negligible, while for very long lines the speedup can be significant. For the record, here are the measurements I made, before and after the changes, with 2 test cases: xdisp.c scanning with the above program, and the "neutered" Org file posted by Stefan-W. Hahn: Test Code Optimized? Cache ON Cache OFF --------------------------------------------------- Org old NO 11.3s 0.8s Org new NO 3.6s 0.8s Org old YES 6.5s 0.3s Org new YES 2.0s 0.25s xdisp.c old NO 2m11.8s 14.7s xdisp.c new NO 1m03.3s 14.8s xdisp.c old YES 1m14.4s 12.0s xdisp.c new YES 32.5s 11.8s And here are the patches I propose. (Note that I only handled the forward scan; the backward scan is used much less, so I left it alone, but if someone thinks the asymmetry might be confusing, I can do the same surgery with backward scan.) Any objections to committing this? --- src/search.c.~2~ 2014-01-02 07:07:04.000000000 +0200 +++ src/search.c 2014-03-10 19:40:08.607562800 +0200 @@ -715,18 +715,61 @@ find_newline (ptrdiff_t start, ptrdiff_t examine. */ ptrdiff_t tem, ceiling_byte = end_byte - 1; - /* If we're looking for a newline, consult the newline cache - to see where we can avoid some scanning. */ + /* If we're using the newline cache, consult it to see whether + we can avoid some scanning. */ if (newline_cache) { ptrdiff_t next_change; + int result = 1; + immediate_quit = 0; - while (region_cache_forward - (cache_buffer, newline_cache, start, &next_change)) - start = next_change; - immediate_quit = allow_quit; + while (start < end && result) + { + ptrdiff_t lim1; - start_byte = CHAR_TO_BYTE (start); + result = region_cache_forward (cache_buffer, newline_cache, + start, &next_change); + if (result) + { + start = next_change; + lim1 = next_change = end; + } + else + lim1 = min (next_change, end); + + /* The cache returned zero for this region; see if + this is because the region is known and includes + only newlines. While at that, count any newlines + we bump into, and exit if we found enough off them. */ + start_byte = CHAR_TO_BYTE (start); + while (start < lim1 + && FETCH_BYTE (start_byte) == '\n') + { + start_byte++; + start++; + if (--count == 0) + { + if (bytepos) + *bytepos = start_byte; + return start; + } + } + /* If we found a non-newline character before hitting + position where the cache will again return non-zero + (i.e. no newlines beyond that position), it means + this region is not yet known to the cache, and we + must resort to the "dumb loop" method. */ + if (start < next_change && !result) + break; + result = 1; + } + if (start >= end) + { + start = end; + start_byte = end_byte; + break; + } + immediate_quit = allow_quit; /* START should never be after END. */ if (start_byte > ceiling_byte) @@ -762,9 +805,9 @@ find_newline (ptrdiff_t start, ptrdiff_t unsigned char *nl = memchr (lim_addr + cursor, '\n', - cursor); next = nl ? nl - lim_addr : 0; - /* If we're looking for newlines, cache the fact that - this line's region is free of them. */ - if (newline_cache) + /* If we're using the newline cache, cache the fact that + the region we just traversed is free of newlines. */ + if (newline_cache && cursor != next) { know_region_cache (cache_buffer, newline_cache, BYTE_TO_CHAR (lim_byte + cursor), @@ -840,7 +883,7 @@ find_newline (ptrdiff_t start, ptrdiff_t /* If we're looking for newlines, cache the fact that this line's region is free of them. */ - if (newline_cache) + if (newline_cache && cursor != prev + 1) { know_region_cache (cache_buffer, newline_cache, BYTE_TO_CHAR (ceiling_byte + prev + 1),