Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Alan Mackenzie]

Hi, Emacs.

I've measured the time Emacs takes to scroll a large C file, and how much
of this is due to the inefficiency in backwards `scan-lists's when
comments contain unbalanced string characters (with
open-paren-in-column-0-is-defun-start nil).

Please load this file into your Emacs:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Track down block comments with an odd number of apostrophe's in them */
(defconst odd-apostrophes
  "/\\*\\([^*']\\|\\*+[^*'/]\\)*\\(\\**'\\([^*']\\|\\*+[^*'/]\\)*\\**'\\([^*']\\|\\*+[^*'/]\\)*\\)*\\**\\('\\)\\([^*']\\|\\*+[^*'/]\\)*\\*+/"
  ;;     1                        2       3                             4                                5      6
)

(defun eradicate-odd-apostrophes ()
  (interactive)
  (let ((count 0))
    (while
        (re-search-forward odd-apostrophes nil t)
      (replace-match "`" nil t nil 5)
      (setq count (1+ count)))))

(defun time-backward-scrolls ()
  (interactive)
  (goto-char (point-max))
  (sit-for 1)
  (let (times this-time before (total 0.0))
    (while (condition-case nil
               (progn
                 (setq before (float-time))
                 (scroll-down-command)
                 (sit-for 0)
                 (setq this-time (- (float-time) before))
                 t)
             (error nil))
      (setq total (+ total this-time))
      (push this-time times)
      (sit-for 1))
    (message "%s scrolls, total time = %ss." (length times) total)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

First prepare a version of (Emacs 24) xdisp.c with all comments having
balanced string quotes.  Simply load xdisp.c into a buffer, place point
on L289 (just after the very large comment) and do M-x
eradicate-odd-apostrophes.  (The regexp `odd-apostrophes' matches a
block comment with an odd number of apostrophes, with submatch 5 matching
the last of these.)  Save this buffer under a new name, say
~/no-odd-xdisp.c.  (N.B. the regexp engine crashes out trying to match
the large comment.  In any case it's got 26 apostrophes, which is OK.)

Kill the buffer, then reload ~/no-odd-xdisp.c freshly.  Execute M-x
time-backward-scrolls.  This defun goes to EOB, then scrolls backwards to
BOB a page at a time.  It times the process.

Do the same with the original xdisp.c.

On my set up, a Linux virtual terminal with a window 65 lines high, I get
the following results:
    no-odd-xdisp.c: 492 scrolls, total time = 42.2749125957489s
           xdisp.c: 492 scrolls, total time = 69.40998315811157s.

69.4100 / 42.2749 = 1.642.  The original thus takes 64% longer (on
average) for a backward scroll operation.

It would seem worthwhile to consider optimising the code to eliminate
this 64%.  Two possibilities suggest themselves: (i) in syntax.c, by
making use of the syntax-ppss cache (or similar); (ii) In CC Mode, by
setting syntax-table text properties on unbalanced string quotes.

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Alan Mackenzie]

On Sat, Oct 18, 2014 at 06:19:38PM +0000, Alan Mackenzie wrote:
> Hi, Emacs.

> I've measured the time Emacs takes to scroll a large C file, and how much
> of this is due to the inefficiency in backwards `scan-lists's when
> comments contain unbalanced string characters (with
> open-paren-in-column-0-is-defun-start nil).

[ ... ]

> On my set up, a Linux virtual terminal with a window 65 lines high, I get
> the following results:
>     no-odd-xdisp.c: 492 scrolls, total time = 42.2749125957489s
>            xdisp.c: 492 scrolls, total time = 69.40998315811157s.

> 69.4100 / 42.2749 = 1.642.  The original thus takes 64% longer (on
> average) for a backward scroll operation.

I forgot to mention that this was on Emacs 24.3, with full .emacs loaded,
and with an up-to-date stand-alone CC Mode.

> It would seem worthwhile to consider optimising the code to eliminate
> this 64%.  Two possibilities suggest themselves: (i) in syntax.c, by
> making use of the syntax-ppss cache (or similar); (ii) In CC Mode, by
> setting syntax-table text properties on unbalanced string quotes.

I've just repeated the measurement on the Emacs trunk, with emacs -Q.  I
now get these results:
    no-odd-xdisp.c: 500 scrolls, total time = 104.21487808227539s.
           xdisp.c: 500 scrolls, total time = 167.73530864715576s.

I don't know why there are more scroll operations needed.  But the fact
that scrolling is taking two and a half times longer in the trunk than in
24..3 is noteworthy, and possibly disturbing.  I'm think I compiled both
version with the same optimisation level, etc.
    
> -- 
> Alan Mackenzie (Nuremberg, Germany).

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Ulrich Mueller]

>>>>> On Sat, 18 Oct 2014, Alan Mackenzie wrote:

> I've just repeated the measurement on the Emacs trunk, with emacs -Q.  I
> now get these results:
>     no-odd-xdisp.c: 500 scrolls, total time = 104.21487808227539s.
>            xdisp.c: 500 scrolls, total time = 167.73530864715576s.

> I don't know why there are more scroll operations needed.  But the fact
> that scrolling is taking two and a half times longer in the trunk than in
> 24..3 is noteworthy, and possibly disturbing.  I'm think I compiled both
> version with the same optimisation level, etc.

I don't see such a large degradation of performance between 24.3 and
trunk here.

   no-odd-xdisp.c:
   22.3:      415 scrolls, total time = 14.469409942626953s.
   23.4:      415 scrolls, total time = 14.116178750991821s.
   24.3:      415 scrolls, total time = 45.48526978492737s.
   24.4-rc1:  415 scrolls, total time = 44.03023886680603s.
   25.0.50:   415 scrolls, total time = 45.08613348007202s.

   xdisp.c:
   22.3:      415 scrolls, total time = 14.692334413528442s.
   23.4:      415 scrolls, total time = 14.051368474960327s.
   24.3:      415 scrolls, total time = 50.858959674835205s.
   24.4-rc1:  415 scrolls, total time = 58.63706636428833s.
   25.0.50:   415 scrolls, total time = 59.3416690826416s.

Tests were done with emacs -Q -nw in an xterm, 80 columns times
80 lines.

(What causes the big slowdown from 23.4 to 24.3, though?)

Ulrich

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Eli Zaretskii]

> Date: Sun, 19 Oct 2014 18:37:26 +0200
> From: Ulrich Mueller <ulm@gentoo.org>
> Cc: emacs-devel@gnu.org
> 
> Tests were done with emacs -Q -nw in an xterm, 80 columns times
> 80 lines.

Did you test in a GUI session as well?

> (What causes the big slowdown from 23.4 to 24.3, though?)

Bidirectional display is one, I guess.

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Ulrich Mueller]

>>>>> On Sun, 19 Oct 2014, Eli Zaretskii wrote:

>> Tests were done with emacs -Q -nw in an xterm, 80 columns times
>> 80 lines.

> Did you test in a GUI session as well?

Yes, but with smaller window size (80 x 40):

   no-odd-xdisp.c:
   22.3:      953 scrolls, total time = 16.126529455184937s.
   23.4:      942 scrolls, total time = 18.194140195846558s.
   24.3:      942 scrolls, total time = 49.906872510910034s.
   24.4-rc1:  942 scrolls, total time = 49.15416240692139s.
   25.0.50:   942 scrolls, total time = 50.233097314834595s.

   xdisp.c:
   22.3:      953 scrolls, total time = 16.09666872024536s.
   23.4:      942 scrolls, total time = 18.084166049957275s.
   24.3:      942 scrolls, total time = 53.44005608558655s.
   24.4-rc1:  942 scrolls, total time = 67.30650329589844s.
   25.0.50:   942 scrolls, total time = 64.4020631313324s.

Ulrich

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Stefan Monnier]

> I don't see such a large degradation of performance between 24.3 and
> trunk here.

>    no-odd-xdisp.c:
>    22.3:      415 scrolls, total time = 14.469409942626953s.
>    23.4:      415 scrolls, total time = 14.116178750991821s.
>    24.3:      415 scrolls, total time = 45.48526978492737s.
>    24.4-rc1:  415 scrolls, total time = 44.03023886680603s.
>    25.0.50:   415 scrolls, total time = 45.08613348007202s.

>    xdisp.c:
>    22.3:      415 scrolls, total time = 14.692334413528442s.
>    23.4:      415 scrolls, total time = 14.051368474960327s.
>    24.3:      415 scrolls, total time = 50.858959674835205s.
>    24.4-rc1:  415 scrolls, total time = 58.63706636428833s.
>    25.0.50:   415 scrolls, total time = 59.3416690826416s.

> Tests were done with emacs -Q -nw in an xterm, 80 columns times
> 80 lines.

Which version of cc-mode was used?  The one bundled with the respective
Emacs version or is it always the same version (presumably the
standalone version of CC-mode)?


        Stefan

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Ulrich Mueller]

>>>>> On Sun, 19 Oct 2014, Stefan Monnier wrote:

>> I don't see such a large degradation of performance between 24.3 and
>> trunk here.

>> [...]

> Which version of cc-mode was used? The one bundled with the
> respective Emacs version or is it always the same version
> (presumably the standalone version of CC-mode)?

The bundled one.

Ulrich

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[martin rudalics]

[-- Attachment #1: Type: text/plain, Size: 1333 bytes --]

Results for Windows XP with CPPFLAGS='-DGLYPH_DEBUG=1' CFLAGS='-O0 -g3'
--enable-checking=yes --enable-check-lisp-object-type=yes:


Unmodified xdisp.c from trunk:

24.3 1007 scrolls, total time = 105.60900020599365s.
24.4 1007 scrolls, total time = 73.21900010108948s.
25.0 1007 scrolls, total time = 318.5629997253418s.


xdisp.c from trunk with odd apostrophes eradicated:

24.3 1007 scrolls, total time = 100.1240005493164s.
24.4 1007 scrolls, total time = 60.13900017738342s.
25.0 1007 scrolls, total time = 197.95300006866455s.


I can't test with older versions since those don't have
`scroll-down-command' here.

So while it might be worthwhile to do such an optimization, here the
great differenece is the 3-to-5-fold increase of execution time from
24.4 to 25.0 for which I don't have an explanation.  The cc-mode used is
always the one bundled with the respective Emacs version.

martin



BTW, if you want to quickly visualize constructs like

(defconst odd-apostrophes
   "/\\*\\([^*']\\|\\*+[^*'/]\\)*\\(\\**'\\([^*']\\|\\*+[^*'/]\\)*\\**'\\([^*']\\|\\*+[^*'/]\\)*\\)*\\**\\('\\)\\([^*']\\|\\*+[^*'/]\\)*\\*+/"
)

without adding comments like

   ;;     1                        2       3                             4                                5      6

you can use the regexp-lock.el package I attached here ;-)

[-- Attachment #2: regexp-lock.el.gz --]
[-- Type: application/gzip, Size: 12605 bytes --]

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Alan Mackenzie]

[-- Attachment #1: Type: text/plain, Size: 2604 bytes --]

Hi, Martin.

On Mon, Oct 20, 2014 at 09:29:51AM +0200, martin rudalics wrote:
> Results for Windows XP with CPPFLAGS='-DGLYPH_DEBUG=1' CFLAGS='-O0 -g3'
> --enable-checking=yes --enable-check-lisp-object-type=yes:


> Unmodified xdisp.c from trunk:

> 24.3 1007 scrolls, total time = 105.60900020599365s.
> 24.4 1007 scrolls, total time = 73.21900010108948s.
> 25.0 1007 scrolls, total time = 318.5629997253418s.


> xdisp.c from trunk with odd apostrophes eradicated:

> 24.3 1007 scrolls, total time = 100.1240005493164s.
> 24.4 1007 scrolls, total time = 60.13900017738342s.
> 25.0 1007 scrolls, total time = 197.95300006866455s.


> I can't test with older versions since those don't have
> `scroll-down-command' here.

Just replace it with `scroll-down'.

> So while it might be worthwhile to do such an optimization, here the
> great differenece is the 3-to-5-fold increase of execution time from
> 24.4 to 25.0 for which I don't have an explanation.  The cc-mode used is
> always the one bundled with the respective Emacs version.

I got this, until I re-bootstrapped my trunk with full compiler
optimisation, no debugging set, and no extra checks enabled.  Then I got
pretty much the same results for the trunk as 24.4.

The main reason I did all this, which nobody's commented on so far, was
to get a handle on how much the `open-paren-in-column-0-is-defun-start',
now bound to nil at critical places in CC Mode, was actually costing on a
large C file.  On 24.4 you get 22%, on the trunk, 61%.  I get 31% in
24.4, and 32% in the trunk.

It seems that "instrumentation" is increasing the cost of
open-paren-etc.

> martin



> BTW, if you want to quickly visualize constructs like

> (defconst odd-apostrophes
>    "/\\*\\([^*']\\|\\*+[^*'/]\\)*\\(\\**'\\([^*']\\|\\*+[^*'/]\\)*\\**'\\([^*']\\|\\*+[^*'/]\\)*\\)*\\**\\('\\)\\([^*']\\|\\*+[^*'/]\\)*\\*+/"
> )

> without adding comments like

>    ;;     1                        2       3                             4                                5      6

> you can use the regexp-lock.el package I attached here ;-)

Neat!

What I actually use is a little tool I wrote called pp-regexp.  Given a
string, it dumps a readable representation of the regexp into *scratch*,
something like:

/\*\(     \|         \)*\(                                                  \)*\**\( \)\(     \|         \)*\*+/
     [^*']  \*+[^*'/]     \**'\(     \|         \)*\**'\(     \|         \)*        '    [^*']  \*+[^*'/]
                                [^*']  \*+[^*'/]         [^*']  \*+[^*'/]

See attached file.

-- 
Alan Mackenzie (Nuremberg, Germany).


[-- Attachment #2: pp-regexp.el.gz --]
[-- Type: application/octet-stream, Size: 1105 bytes --]

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[martin rudalics]

 > I got this, until I re-bootstrapped my trunk with full compiler
 > optimisation, no debugging set, and no extra checks enabled.  Then I got
 > pretty much the same results for the trunk as 24.4.
 >
 > The main reason I did all this, which nobody's commented on so far, was
 > to get a handle on how much the `open-paren-in-column-0-is-defun-start',
 > now bound to nil at critical places in CC Mode, was actually costing on a
 > large C file.  On 24.4 you get 22%, on the trunk, 61%.  I get 31% in
 > 24.4, and 32% in the trunk.
 >
 > It seems that "instrumentation" is increasing the cost of
 > open-paren-etc.

All my builds are configured the same way.  So this doesn't explain why
24.4 (which IIUC binds `open-paren-in-column-0-is-defun-start' to nil
too) is four times faster.

martin

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Óscar Fuentes]

martin rudalics <rudalics@gmx.at> writes:

> All my builds are configured the same way.  So this doesn't explain why
> 24.4 (which IIUC binds `open-paren-in-column-0-is-defun-start' to nil
> too) is four times faster.

Testing performance with optimizations turned off is pointless when you
want to evaluate user's experience. The differences you see can be
caused by new asserts and other code constructs that cause zero overhead
with optimizations enabled but are very costly otherwise.

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Stefan Monnier]

>> Which version of cc-mode was used? The one bundled with the
>> respective Emacs version or is it always the same version
>> (presumably the standalone version of CC-mode)?
> The bundled one.

Thanks.  So the performance differences could also come from CC-mode
rather than from Emacs's C code.


        Stefan

Re: Scrolling xdisp.c. Room for optimisation in syntax.c/CC Mode.

[Ulrich Mueller]

>>>>> On Mon, 20 Oct 2014, Stefan Monnier wrote:

> So the performance differences could also come from CC-mode rather
> than from Emacs's C code.

Indeed. If I run all tests with CC Mode 5.32.5 then the large
difference between Emacs 23.4 and 24.3 disappears:

   no-odd-xdisp.c:
   23.4:      415 scrolls, total time = 45.01029920578003s.
   24.3:      415 scrolls, total time = 43.775553941726685s.

   xdisp.c:
   23.4:      415 scrolls, total time = 48.97985076904297s.
   24.3:      415 scrolls, total time = 47.60138463973999s.

My previous numbers using the CC Mode version bundled with Emacs
(i.e., 5.31.8 and 5.32.4 for Emacs 23.4 and 24.3, respectively) were:

   no-odd-xdisp.c:
   23.4:      415 scrolls, total time = 14.116178750991821s.
   24.3:      415 scrolls, total time = 45.48526978492737s.

   xdisp.c:
   23.4:      415 scrolls, total time = 14.051368474960327s.
   24.3:      415 scrolls, total time = 50.858959674835205s.

Again, tests done with emacs -Q -nw in an xterm, 80 columns times
80 lines.

Ulrich