branch probability hinting

branch probability hinting

[Frank Ch. Eigler]

Hi -

In cgen-generated files, as well as in other places in the simulator,
code such as the following occurs in some critical places:

	void foo () {
		process_a_bit ();
		if (error) {
			elaborate_error_handling () ;
		}
		process_a_bit_more ();
		if (need_to_trace) {
			elaborate_tracing ();
		}
		process_dangly_bits ();
	}

The elaborate_* pieces of code are very rarely or never executed
in normal high-speed modes, but nevertheless, the compiler must
emit code.  Without other knowledge, the compiler usually leaves
the generated code right in line, and branches around the mostly-dead
code.  If the compiler had enough information, it could move these
blocks of code out of line (and out of the hot parts of the icache).

How to give it this information?  Two ways -- profile-directed
feedback, or manual hints.  While infrequently used, they are not
that difficult.  The second (manual hinting) is particularly
straightforward in gcc, using the "__builtin_expect" function.
I plan to commit to sid some changes that add macros that
conveniently wrap this hinting:

#ifdef __GNUC__
#define LIKELY(expression) (__builtin_expect(!!(expression), 1))
#define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
#else
#define LIKELY(expression) (expression)
#define UNLIKELY(expression) (expression)
#endif

One is used thusly (and the other, vice versa):

	void foo () {
		process_a_bit ();
		if UNLIKELY(error) {
			elaborate_error_handling () ;
		}
		process_a_bit_more ();
		if UNLIKELY(need_to_trace) {
			elaborate_tracing ();
		}
		process_dangly_bits ();
	}

I plan to commit to cgen changes to emit calls to UNLIKELY(),
just for the tracing calls in sid decoding and semantics blocks:
all the sid/component/cgen-cpu/*/FOO-sem.cxx and FOO_decode.cxx
files would be minorly affected.  At the same time, I looked
through a couple pieces of other sid code (sidutil, scheduler,
mapper, memory, etc.), and added some hinting to a few obvious
places.  (No need to go overboard.)

While other command-line options are often required
(-O2/-O3/-freorder-blocks), depending on gcc version) to activate
the more aggressive optimizations that use these hints, the mere
presence of the hints, if unused, doesn't cause any degradation.
In other words, I think it is safe to add these hints now, even
if your builds doen't use them -- someday, they will help somewhat.

In the mean time, I'm running a couple of crude speed tests to
see whether the effect is detectable right now.


- FChE
-- 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE6nX0pVZbdDOm/ZT0RApqeAJ0R6LDz3hklRFv96nOtzXbAqiTXzgCeMF0y
ACt32qHNTcGJXpdNubQEb0M=
=8aGi
-----END PGP SIGNATURE-----

Re: branch probability hinting

[Greg McGary]

"Frank Ch. Eigler" <fche@redhat.com> writes:

> One is used thusly (and the other, vice versa):
> [ ... ]
> 		if UNLIKELY(error) {

Cool.  Only one nit to pick:

Please don't encourage people to write code that appears to be
syntactically invalid.  I know that the parens are part of the
expansion of LIKELY & UNLIKELY, but lexical tools such as indent get
confused.  I'd rather see uses like this:

		if (UNLIKELY(error)) {

Greg

re: branch probability hinting

[matthew green]

i like this, but i don't like the name very much.  in NetBSD,
we've added predict_true() and predict_false().


.mrg.

Re: branch probability hinting

[Eric Christopher]

matthew green wrote:
> 
> i like this, but i don't like the name very much.  in NetBSD,
> we've added predict_true() and predict_false().

Well, builtin is the default name for compiler um.. well.. builtins. 
It's been around for a while.

Unless you meant the name that Frank chose, yeah, it could be better. 
Personally, I like expect as a name for it, tells you what you are
telling the compiler to expect to happen.

-eric

re: branch probability hinting

[matthew green]

   matthew green wrote:
   > 
   > i like this, but i don't like the name very much.  in NetBSD,
   > we've added predict_true() and predict_false().
   
   Well, builtin is the default name for compiler um.. well.. builtins. 
   It's been around for a while.

uh, i mean, we define predict_true() to make use of this feature :-)
   
   Unless you meant the name that Frank chose, yeah, it could be better. 
   Personally, I like expect as a name for it, tells you what you are
   telling the compiler to expect to happen.

i don't really care much either way, but "UNLIKELY" is very ugly to me.


.mrg.

Re: branch probability hinting

[Frank Ch. Eigler]

Hi -

echristo suggests "expect", which I don't like because
it doesn't have a natural opposite ("unexpect"?).  mrg
suggests "predict_true". which I don't like because it's
too verbose.  I like "LIKELY" because it's short,
eyecatching, and a reversible adjective/adverb that
suggests a meta-function rather than an ordinary function.

I'd like to stick with LIKELY/UNLIKELY for now, until
a better candidate comes along later, riding alongside
a champion who is eager enough to do the renaming.

- FChE
-- 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE6noM1VZbdDOm/ZT0RAldgAJwNQ0DScXDkEhF7eqSxpGXybsAk3gCdEDF0
6rB7vgG4eDZghKEwF76K5ZA=
=FPaq
-----END PGP SIGNATURE-----

Re: branch probability hinting

[Dave Brolley]

Frank Ch. Eigler wrote:

> Hi -
> 
> echristo suggests "expect", which I don't like because
> it doesn't have a natural opposite ("unexpect"?).  mrg
> suggests "predict_true". which I don't like because it's
> too verbose.  I like "LIKELY" because it's short,
> eyecatching, and a reversible adjective/adverb that
> suggests a meta-function rather than an ordinary function.
> 
> I'd like to stick with LIKELY/UNLIKELY for now, until
> a better candidate comes along later, riding alongside
> a champion who is eager enough to do the renaming.
> 
> - FChE

The problem I have with

if (LIKELY (test))
  ...code...

is that to a casual reader it looks like it's an actual test for 
something which is likely (a heuristic?) rather than an optimization hint.

Dave

Re: branch probability hinting

[Greg McGary]

Dave Brolley <brolley@redhat.com> writes:

> The problem I have with
> 
> if (LIKELY (test))
>   ...code...
> 
> is that to a casual reader it looks like it's an actual test for 
> something which is likely (a heuristic?) rather than an optimization hint.

I generally don't buy such arguments.  The casual reader generally
deserves any misunderstandings s/he has.  If it's truly casual
reading, then the misunderstandings are inconsequential.  If someone
really cares to know what's going on, then it's time to become more
circumspect and track down the definition.  This same procedure
applies to zillions of other names in a program that might be
unfamiliar.  LIKELY/UNLIKELY is as evocative of its real meaning for
me as some other choice of names is for you.  As Abe Lincoln once
said: "You can please some of the people all of the time, you can
please all of the people some of the time, but you can't please all of
the people all of the time."

Greg

Re: branch probability hinting

[Greg McGary]

"Frank Ch. Eigler" <fche@redhat.com> writes:

> echristo suggests "expect", which I don't like because
> it doesn't have a natural opposite ("unexpect"?).  mrg
> suggests "predict_true". which I don't like because it's
> too verbose.  I like "LIKELY" because it's short,
> eyecatching, and a reversible adjective/adverb that
> suggests a meta-function rather than an ordinary function.
> 
> I'd like to stick with LIKELY/UNLIKELY for now, until
> a better candidate comes along later, riding alongside
> a champion who is eager enough to do the renaming.

I don't normally waste bandwidth with "me too" messages, but since
some expressed their distaste for Frank's naming, I thought I'd offer
some counterweight.  I like Frank's names and capitalization for all
the reasons he explains.  The terminology also meshes with MIPS
jargon.

Greg