Re: emacs-26 eec71eb: Speed up replace-buffer-contents

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Glenn Morris]

Eli Zaretskii wrote:

> branch: emacs-26
> commit eec71ebdb50c3110bb747db57c7d7f04b6d14ad1

This didn't merge cleanly to master; please could you check I didn't
mess it up...

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Paul Eggert]

Glenn Morris wrote:
> This didn't merge cleanly to master; please could you check I didn't
> mess it up...

Looks OK to me, though Eli is better positions to check.

Probably could tune that code more. I'll see if I can spring free some time to 
do that.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Cc: Eli Zaretskii <eliz@gnu.org>
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Mon, 2 Jul 2018 23:25:03 -0700
> 
> Glenn Morris wrote:
> > This didn't merge cleanly to master; please could you check I didn't
> > mess it up...
> 
> Looks OK to me, though Eli is better positions to check.

Looks OK to me too.  Thanks for merging, Glenn.

> Probably could tune that code more. I'll see if I can spring free some time to 
> do that.

I just made a simple change that sped up the bug#31888 recipe by 30%.
Profiling shows that 'diag' takes 32% of the CPU time, and
buffer_chars_equal takes another 45%.  So any significant gains will
be in buffer_chars_equal, I think.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Paul Eggert]

Eli Zaretskii wrote:
> Profiling shows that 'diag' takes 32% of the CPU time, and
> buffer_chars_equal takes another 45%.  So any significant gains will
> be in buffer_chars_equal, I think.

Yes, that was what my intuition was pointing at as well. Among other things, we 
can fix the quit problem without having a rbc_quitcounter variable.

I typically measure effectiveness of performance tweaks when using the 
'configure' default of CFLAGS='-g3 -O2', since that's how it's typically built 
downstream. If this particular problem is all about CFLAGS=-O0 please let me 
know, as I guess I can look at that too (but would rather not).

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Cc: rgm@gnu.org, emacs-devel@gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 3 Jul 2018 13:14:29 -0700
> 
> Eli Zaretskii wrote:
> > Profiling shows that 'diag' takes 32% of the CPU time, and
> > buffer_chars_equal takes another 45%.  So any significant gains will
> > be in buffer_chars_equal, I think.
> 
> Yes, that was what my intuition was pointing at as well. Among other things, we 
> can fix the quit problem without having a rbc_quitcounter variable.

Fix how?  Since the command can run for quite a few seconds, it is
imperative that we give the user the possibility to quit.  I
originally had maybe_quit there, but profiling showed that it used a
lot of CPU (because it accesses Lisp symbols, and was called for each
character 'diag' wanted to compare), so I switched to rarely_quit.
Last profile indicates rarely_quit takes about 6% of CPU time, which I
think is a reasonably low price to pay for responsiveness.

If you mean you have an idea for calling rarely_quit or its equivalent
in a more elegant way (e.g., without a static counter), then it would
be good, of course.  But I'm not sure that will speed up the code, and
we should be very careful not to slow it down just for QUIT's sake.

> I typically measure effectiveness of performance tweaks when using the 
> 'configure' default of CFLAGS='-g3 -O2', since that's how it's typically built 
> downstream. If this particular problem is all about CFLAGS=-O0 please let me 
> know, as I guess I can look at that too (but would rather not).

Which particular problem were did you allude to?

I didn't (yet) profile the code in an optimized build, only in a -O0
build.  It could be that the optimized build will show a different
picture, although I doubt that.  I might try an optimized build in a
couple of days (but I never use -O3 in Emacs, only -O2).

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Paul Eggert]

Eli Zaretskii wrote:

> If you mean you have an idea for calling rarely_quit or its equivalent
> in a more elegant way (e.g., without a static counter), then it would
> be good, of course.

Yes, that's the idea.

> Which particular problem were did you allude to?

Sorry, I've lost context and don't know what this question refers to.

> It could be that the optimized build will show a different
> picture, although I doubt that.  I might try an optimized build in a
> couple of days (but I never use -O3 in Emacs, only -O2).

Yes, -O2 is what I usually use for benchmarks too, since it's what is normally 
used in production. Its execution profile can differ quite a bit from -O0, due 
to inlining and other things. For rarely_quit, with -O2 typically the overhead 
of the rarely_quit call (including computing its argument) is typically just two 
CPU instructions (a test and a conditional branch that is predicted correctly, 
so both instructions are cheap). This is way better than -O0.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Cc: rgm@gnu.org, emacs-devel@gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 3 Jul 2018 23:36:44 -0700
> 
> > Which particular problem were did you allude to?
> 
> Sorry, I've lost context and don't know what this question refers to.

It refers to this exchange:

> > I typically measure effectiveness of performance tweaks when using the 
> > 'configure' default of CFLAGS='-g3 -O2', since that's how it's typically built 
> > downstream. If this particular problem is all about CFLAGS=-O0 please let me 
> > know, as I guess I can look at that too (but would rather not).

> Which particular problem were did you allude to?

You said "if this particular problem is about ...", and I asked what
was the particular problem you were talking about.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 3 Jul 2018 23:36:44 -0700
> Cc: rgm@gnu.org, emacs-devel@gnu.org
> 
> For rarely_quit, with -O2 typically the overhead 
> of the rarely_quit call (including computing its argument) is typically just two 
> CPU instructions (a test and a conditional branch that is predicted correctly, 
> so both instructions are cheap). This is way better than -O0.

It's not rarely_quit that is expensive, it's the few calls to
maybe_quit it does, because maybe_quit accesses two Lisp symbols.  I
think.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Paul Eggert]

>>> Which particular problem were did you allude to?
>>
>> Sorry, I've lost context and don't know what this question refers to.
> 
> It refers to this exchange:
> 
>>> I typically measure effectiveness of performance tweaks when using the
>>> 'configure' default of CFLAGS='-g3 -O2', since that's how it's typically built
>>> downstream. If this particular problem is all about CFLAGS=-O0 please let me
>>> know, as I guess I can look at that too (but would rather not).
> 
>> Which particular problem were did you allude to?
> 
> You said "if this particular problem is about ...", and I asked what
> was the particular problem you were talking about.

Ah, I meant the particular performance problem that the recent changes have been 
trying to alleviate.

> It's not rarely_quit that is expensive, it's the few calls to
> maybe_quit it does, because maybe_quit accesses two Lisp symbols.  I
> think.

If that's the case, there's still a performance bug in there. The point of 
rarely_quit is to avoid calling maybe_quit in the vast majority of cases. If 
maybe_quit is being called so often that it's a performance hog, then it's being 
called too often.

By the way, accessing Lisp symbols should not be a serious performance 
bottleneck. builtin_lisp_symbol takes zero machine instructions unless compiling 
with -fcheck-pointer-bounds or compiling without optimization. If 
builtin_lisp_symbol is a serious performance issue when compiling without 
optimization (which it shouldn't be), then we need to tune its uses for the 
non-optimized case (though I'd rather avoid that sort of thing, as it is a 
throwback to the 1970s to be hand-optimizing to work around lousy compilers!). 
But before resorting to this, I'd first rather understand the maybe_quit problem 
mentioned above.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Cc: rgm@gnu.org, emacs-devel@gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 4 Jul 2018 11:30:12 -0700
> 
> If that's the case, there's still a performance bug in there. The point of 
> rarely_quit is to avoid calling maybe_quit in the vast majority of cases. If 
> maybe_quit is being called so often that it's a performance hog, then it's being 
> called too often.

Maybe I'm mistaken, then.  I will see what an optimized build shows.

> If builtin_lisp_symbol is a serious performance issue when compiling
> without optimization (which it shouldn't be)

It is a serious bottleneck in an unoptimized build, if you call
builtin_lisp_symbol half a dozen times for each pair of characters
'compareseq' wants to examine -- which is what the original code did,
due to all the assertions it had there, some of them really paranoid
(like asserting that A + X is more than A after asserting that X is
positive).  I think the original code spent almost 50% of its time
inside builtin_lisp_symbol.

> then we need to tune its uses for the 
> non-optimized case (though I'd rather avoid that sort of thing, as it is a 
> throwback to the 1970s to be hand-optimizing to work around lousy compilers!). 

I don't think we need to optimize builtin_lisp_symbol, since the
situation in replace-buffer-contents is quite a unique one.

> But before resorting to this, I'd first rather understand the maybe_quit problem 
> mentioned above.

The maybe_quit problem is/was due to its accessing 2 Lisp symbols,
which again involves calling builtin_lisp_symbol, and originally I
added a call to maybe_quit to buffer_chars_equal, so it would be
called for each pair of characters 'compareseq' wanted to examine.
That's why I switched to rarely_quit.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Date: Wed, 04 Jul 2018 21:40:22 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: rgm@gnu.org, emacs-devel@gnu.org
> 
> > Cc: rgm@gnu.org, emacs-devel@gnu.org
> > From: Paul Eggert <eggert@cs.ucla.edu>
> > Date: Wed, 4 Jul 2018 11:30:12 -0700
> > 
> > If that's the case, there's still a performance bug in there. The point of 
> > rarely_quit is to avoid calling maybe_quit in the vast majority of cases. If 
> > maybe_quit is being called so often that it's a performance hog, then it's being 
> > called too often.
> 
> Maybe I'm mistaken, then.  I will see what an optimized build shows.

Profiling the optimized build shows that 60% of the time is spent
inside buffer_chars_equal, and another 26% inside compareseq.
rarely_quit and maybe_quit are nowhere in sight in the profile.

And on my machine, the original recipe of bug#31888 completes in 2.5
sec of CPU time in the optimized build, which is "fast enough", IMO.

So I think we have no performance problem we need to fix, right?

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Paul Eggert]

Eli Zaretskii wrote:
> Profiling the optimized build shows that 60% of the time is spent
> inside buffer_chars_equal, and another 26% inside compareseq.
> rarely_quit and maybe_quit are nowhere in sight in the profile.

That's what I would expect: rarely_quit is inlined, so you don't see it in the 
profile (even though it's there and has some cost), and maybe_quit is called so 
rarely that you don't see it in the profile.

> So I think we have no performance problem we need to fix, right?

It sounds like we never had a performance problem in optimized builds that we 
needed to fix. I.e., the recent patch was needed only for unoptimized builds. 
Which is unfortunate, as we shouldn't have to hand-optimize unoptimized builds. 
I'll keep that in mind if I ever find time to look into the performance problem.

Re: emacs-26 eec71eb: Speed up replace-buffer-contents

[Eli Zaretskii]

> Cc: rgm@gnu.org, emacs-devel@gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Sat, 7 Jul 2018 11:22:33 -0700
> 
> It sounds like we never had a performance problem in optimized builds that we 
> needed to fix. I.e., the recent patch was needed only for unoptimized builds. 

No, the calls to BUF_BEGV and the determination whether each buffer is
unibyte or not (inside buffer_chars_equal) affected the optimized
builds as well.