__builtin_expect (was: Re: master b0ba0d42b0f: * src/lisp.h (EQ): Improve generated code.)

__builtin_expect (was: Re: master b0ba0d42b0f: * src/lisp.h (EQ): Improve generated code.)

[Pip Cet via Emacs development discussions.]

On Thursday, November 28th, 2024 at 15:02, Andrea Corallo <acorallo@gnu.org> wrote:
> Pip Cet pipcet@protonmail.com writes:
> > On Thursday, November 28th, 2024 at 10:35, Andrea Corallo acorallo@gnu.org wrote:
> > 
> > > branch: master
> > > commit b0ba0d42b0fdf70a20cd7a070128db8abe4a0826
> > > Author: Andrea Corallo acorallo@gnu.org
> > > 
> > > Commit: Andrea Corallo acorallo@gnu.org
> > > 
> > > * src/lisp.h (EQ): Improve generated code.
> > > 
> > > Outside compilation 'symbols_with_pos_enabled' is always false, so ask
> > > the compiler to organize the most likely execution path in a sequential
> > > fashion in order to favor run-time performance.
> > 
> > Are we officially using __builtin_expect now?
> 
> config.h AFAIU defines it to a nop if the compiler does not support it.

It does, thanks!

I'm not sure that isn't a mere accident, though: currently, gnulib pulls in the builtin-expect module because it's used by gnulib internally, not because we explicitly requested it. If we want to use __builtin_expect in general, not just for special configurations (Android), we need to tell gnulib to pull in the `builtin-expect' module.

IOW, config.h isn't part of the Emacs sources, and whether it includes a section from builtin-expect.m4 depends on gnulib internals that may change without notice. We're talking about a compiler "feature" that the GCC manual advises us not to use, so I think that's a possibility.

But even if we can rely on the existence of the macro, "happens to be available" is not the same as "officially something we use". I still think it's a major decision, and needs to be discussed.

> > I think that's a major change to the way Emacs C code is written, and a decision which might benefit from further discussion.
> > 
> > To quote the GCC manual:
> > In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform.
> > 
> > Maybe we should use __builtin_expect_with_probability instead, in
> > those rare cases when we are certain we're making a correct
> > prediction? Or, my preference, avoid using __builtin_expect entirely,
> > so our scarce resources can be spent on more important issues?
> > 
> > I also don't think the assumption you're telling GCC to make in this specific case (more than 90% of calls to EQ happen while syms_with_pos_enabled == false) is obviously correct.
> 
> I think it is correct when we are not compiling, and as mentioned in the
> commit msg that's the case the patch is optimizing for.

The code isn't specific to "when we are not compiling", and the compiler won't read your commit message.

As it stands, we're telling GCC it's okay to make the "slow" case slower by a factor of 5.5 if it believes the "fast" case will be twice as fast.

Pip

Re: __builtin_expect

[Andrea Corallo]

Pip Cet <pipcet@protonmail.com> writes:

> On Thursday, November 28th, 2024 at 15:02, Andrea Corallo <acorallo@gnu.org> wrote:
>> Pip Cet pipcet@protonmail.com writes:
>> > On Thursday, November 28th, 2024 at 10:35, Andrea Corallo acorallo@gnu.org wrote:
>> > 
>> > > branch: master
>> > > commit b0ba0d42b0fdf70a20cd7a070128db8abe4a0826
>> > > Author: Andrea Corallo acorallo@gnu.org
>> > > 
>> > > Commit: Andrea Corallo acorallo@gnu.org
>> > > 
>> > > * src/lisp.h (EQ): Improve generated code.
>> > > 
>> > > Outside compilation 'symbols_with_pos_enabled' is always false, so ask
>> > > the compiler to organize the most likely execution path in a sequential
>> > > fashion in order to favor run-time performance.
>> > 
>> > Are we officially using __builtin_expect now?
>> 
>> config.h AFAIU defines it to a nop if the compiler does not support it.
>
> It does, thanks!
>
> I'm not sure that isn't a mere accident, though: currently, gnulib
> pulls in the builtin-expect module because it's used by gnulib
> internally, not because we explicitly requested it. If we want to use
> __builtin_expect in general, not just for special configurations
> (Android), we need to tell gnulib to pull in the `builtin-expect'
> module.
>
> IOW, config.h isn't part of the Emacs sources, and whether it includes
> a section from builtin-expect.m4 depends on gnulib internals that may
> change without notice. We're talking about a compiler "feature" that
> the GCC manual advises us not to use, so I think that's a possibility.

If you feel this need to be fixed could you please submit a patch?

> But even if we can rely on the existence of the macro, "happens to be available" is not the same as "officially something we use". I still think it's a major decision, and needs to be discussed.

It was already in use in the Emacs code-base before my commit, and I
don't see any specific reason why we should not use it where deemed to
be useful.  I'm not a fan at all of the spread use of manually annotated
branches, but this case is pretty obvious and important at the same
time.

>> > I think that's a major change to the way Emacs C code is written, and a decision which might benefit from further discussion.
>> > 
>> > To quote the GCC manual:
>> > In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform.
>> > 
>> > Maybe we should use __builtin_expect_with_probability instead, in
>> > those rare cases when we are certain we're making a correct
>> > prediction? Or, my preference, avoid using __builtin_expect entirely,
>> > so our scarce resources can be spent on more important issues?
>> > 
>> > I also don't think the assumption you're telling GCC to make in this specific case (more than 90% of calls to EQ happen while syms_with_pos_enabled == false) is obviously correct.
>> 
>> I think it is correct when we are not compiling, and as mentioned in the
>> commit msg that's the case the patch is optimizing for.
>
> The code isn't specific to "when we are not compiling", and the compiler won't read your commit message.

I don't understand sorry, no compiler is reading commit messages, but
people commenting on emacs-devel should.

  Andrea

Re: __builtin_expect

[Pip Cet via Emacs development discussions.]

On Thursday, November 28th, 2024 at 16:12, Andrea Corallo <acorallo@gnu.org> wrote:
> Pip Cet pipcet@protonmail.com writes:
> 
> > On Thursday, November 28th, 2024 at 15:02, Andrea Corallo acorallo@gnu.org wrote:
> > 
> > > Pip Cet pipcet@protonmail.com writes:
> > > 
> > > > On Thursday, November 28th, 2024 at 10:35, Andrea Corallo acorallo@gnu.org wrote:
> > > > 
> > > > > branch: master
> > > > > commit b0ba0d42b0fdf70a20cd7a070128db8abe4a0826
> > > > > Author: Andrea Corallo acorallo@gnu.org
> > > > > 
> > > > > Commit: Andrea Corallo acorallo@gnu.org
> > > > > 
> > > > > * src/lisp.h (EQ): Improve generated code.
> > > > > 
> > > > > Outside compilation 'symbols_with_pos_enabled' is always false, so ask
> > > > > the compiler to organize the most likely execution path in a sequential
> > > > > fashion in order to favor run-time performance.
> > > > 
> > > > Are we officially using __builtin_expect now?
> > > 
> > > config.h AFAIU defines it to a nop if the compiler does not support it.
> > 
> > It does, thanks!
> > 
> > I'm not sure that isn't a mere accident, though: currently, gnulib
> > pulls in the builtin-expect module because it's used by gnulib
> > internally, not because we explicitly requested it. If we want to use
> > __builtin_expect in general, not just for special configurations
> > (Android), we need to tell gnulib to pull in the `builtin-expect'
> > module.
> > 
> > IOW, config.h isn't part of the Emacs sources, and whether it includes
> > a section from builtin-expect.m4 depends on gnulib internals that may
> > change without notice. We're talking about a compiler "feature" that
> > the GCC manual advises us not to use, so I think that's a possibility.
> 
> If you feel this need to be fixed could you please submit a patch?

To enable __builtin_expect, or to remove it? I think for now we should do the latter.

> > But even if we can rely on the existence of the macro, "happens to be available" is not the same as "officially something we use". I still think it's a major decision, and needs to be discussed.
> 
> 
> It was already in use in the Emacs code-base before my commit,

You mean the two usages in src/android.c? We don't support arbitrary compilers for Android code, only clang (and maybe GCC again if that has been fixed), so that's hardly precedent to build on when modifying lisp.h.

> and I
> don't see any specific reason why we should not use it where deemed to
> be useful.

At the very least, we'd need to establish it actually is useful. Going by intuition isn't the right answer here.

> I'm not a fan at all of the spread use of manually annotated
> branches, but this case is pretty obvious and important at the same
> time.

It's not obvious to me, sorry.

> > > > I think that's a major change to the way Emacs C code is written, and a decision which might benefit from further discussion.
> > > > 
> > > > To quote the GCC manual:
> > > > In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform.
> > > > 
> > > > Maybe we should use __builtin_expect_with_probability instead, in
> > > > those rare cases when we are certain we're making a correct
> > > > prediction? Or, my preference, avoid using __builtin_expect entirely,
> > > > so our scarce resources can be spent on more important issues?
> > > > 
> > > > I also don't think the assumption you're telling GCC to make in this specific case (more than 90% of calls to EQ happen while syms_with_pos_enabled == false) is obviously correct.
> > > 
> > > I think it is correct when we are not compiling, and as mentioned in the
> > > commit msg that's the case the patch is optimizing for.
> > 
> > The code isn't specific to "when we are not compiling", and the compiler won't read your commit message.
> 
> I don't understand sorry, no compiler is reading commit messages, but

You said that your assumption holds "when we are not compiling", but your code change applies to the other case, too.

Pip

Re: __builtin_expect

[Andrea Corallo]

Pip Cet <pipcet@protonmail.com> writes:

> On Thursday, November 28th, 2024 at 16:12, Andrea Corallo <acorallo@gnu.org> wrote:
>> Pip Cet pipcet@protonmail.com writes:
>> 
>> > On Thursday, November 28th, 2024 at 15:02, Andrea Corallo acorallo@gnu.org wrote:
>> > 
>> > > Pip Cet pipcet@protonmail.com writes:
>> > > 
>> > > > On Thursday, November 28th, 2024 at 10:35, Andrea Corallo acorallo@gnu.org wrote:
>> > > > 
>> > > > > branch: master
>> > > > > commit b0ba0d42b0fdf70a20cd7a070128db8abe4a0826
>> > > > > Author: Andrea Corallo acorallo@gnu.org
>> > > > > 
>> > > > > Commit: Andrea Corallo acorallo@gnu.org
>> > > > > 
>> > > > > * src/lisp.h (EQ): Improve generated code.
>> > > > > 
>> > > > > Outside compilation 'symbols_with_pos_enabled' is always false, so ask
>> > > > > the compiler to organize the most likely execution path in a sequential
>> > > > > fashion in order to favor run-time performance.
>> > > > 
>> > > > Are we officially using __builtin_expect now?
>> > > 
>> > > config.h AFAIU defines it to a nop if the compiler does not support it.
>> > 
>> > It does, thanks!
>> > 
>> > I'm not sure that isn't a mere accident, though: currently, gnulib
>> > pulls in the builtin-expect module because it's used by gnulib
>> > internally, not because we explicitly requested it. If we want to use
>> > __builtin_expect in general, not just for special configurations
>> > (Android), we need to tell gnulib to pull in the `builtin-expect'
>> > module.
>> > 
>> > IOW, config.h isn't part of the Emacs sources, and whether it includes
>> > a section from builtin-expect.m4 depends on gnulib internals that may
>> > change without notice. We're talking about a compiler "feature" that
>> > the GCC manual advises us not to use, so I think that's a possibility.
>> 
>> If you feel this need to be fixed could you please submit a patch?
>
> To enable __builtin_expect, or to remove it?

__builtin_expect it's already enabled, I'm talking about
builtin-expect.m4 following your comment on it.

> I think for now we should do the latter.

Noted

>> > But even if we can rely on the existence of the macro, "happens to
>> > be available" is not the same as "officially something we use". I
>> > still think it's a major decision, and needs to be discussed.
>> 
>> 
>> It was already in use in the Emacs code-base before my commit,
>
> You mean the two usages in src/android.c?

grep is your friend

> We don't support arbitrary
> compilers for Android code, only clang (and maybe GCC again if that
> has been fixed),

so what?

> so that's hardly precedent to build on when modifying
> lisp.h.
>
>> and I
>> don't see any specific reason why we should not use it where deemed to
>> be useful.
>
> At the very least, we'd need to establish it actually is useful. Going by intuition isn't the right answer here.

I didn't use my intuition, it generates better code and IME faster code.

>> I'm not a fan at all of the spread use of manually annotated
>> branches, but this case is pretty obvious and important at the same
>> time.
>
> It's not obvious to me, sorry.

I'm sorry as well.  Hope my next point clarifies better.

>> > > > I think that's a major change to the way Emacs C code is written, and a decision which might benefit from further discussion.
>> > > > 
>> > > > To quote the GCC manual:
>> > > > In general, you should prefer to use actual profile feedback
>> > > > for this (-fprofile-arcs), as programmers are notoriously bad
>> > > > at predicting how their programs actually perform.
>> > > > 
>> > > > Maybe we should use __builtin_expect_with_probability instead, in
>> > > > those rare cases when we are certain we're making a correct
>> > > > prediction? Or, my preference, avoid using __builtin_expect entirely,
>> > > > so our scarce resources can be spent on more important issues?
>> > > > 
>> > > > I also don't think the assumption you're telling GCC to make
>> > > > in this specific case (more than 90% of calls to EQ happen
>> > > > while syms_with_pos_enabled == false) is obviously correct.
>> > > 
>> > > I think it is correct when we are not compiling, and as mentioned in the
>> > > commit msg that's the case the patch is optimizing for.
>> > 
>> > The code isn't specific to "when we are not compiling", and the compiler won't read your commit message.
>> 
>> I don't understand sorry, no compiler is reading commit messages, but
>
> You said that your assumption holds "when we are not compiling", but your code change applies to the other case, too.

Indeed, but Emacs is rarely compiling, Emacs is not primary a compiler,
and I hope it's clear that we want to optimize for its everyday typical
use.  Given in that case 'syms_with_pos_enabled' is simply false all the
time, this is just the way to express that to the compiler so it can
generate the right code.

Actually AFAIU/R the presence of 'syms_with_pos_enabled' there *is* an
optimization to mitigate the performance impact of this feature on the
most common Emacs usecase (the one my patch optimized further).

Re: __builtin_expect

[Pip Cet via Emacs development discussions.]

On Thursday, November 28th, 2024 at 21:32, Andrea Corallo <acorallo@gnu.org> wrote:
> Pip Cet pipcet@protonmail.com writes:
> > > > But even if we can rely on the existence of the macro, "happens to
> > > It was already in use in the Emacs code-base before my commit,
> > 
> > You mean the two usages in src/android.c?
> 
> grep is your friend

That's quite rude (obviously, grep only finds the two usages in android.c and usages in lib/, outside of the Emacs code base).  I won't continue this discussion.

Pip

Re: __builtin_expect

[Eli Zaretskii]

> From: Andrea Corallo <acorallo@gnu.org>
> Cc: Emacs Devel <emacs-devel@gnu.org>
> Date: Thu, 28 Nov 2024 16:32:25 -0500
> 
> > You said that your assumption holds "when we are not compiling", but your code change applies to the other case, too.
> 
> Indeed, but Emacs is rarely compiling, Emacs is not primary a compiler,
> and I hope it's clear that we want to optimize for its everyday typical
> use.  Given in that case 'syms_with_pos_enabled' is simply false all the
> time, this is just the way to express that to the compiler so it can
> generate the right code.

I agree.

> Actually AFAIU/R the presence of 'syms_with_pos_enabled' there *is* an
> optimization to mitigate the performance impact of this feature on the
> most common Emacs usecase (the one my patch optimized further).

Right.