Register keyword and "as if" rule...

[Thad Smith]

Jack Klein said:

On Fri, 13 Oct 2006 20:40:20 +0000, Richard Heathfield

The best reason not to
bother with register is that modern compilers are far better at deciding
what to put into registers than the vast majority of programmers.

[snip]

Can you point to any actual tests that back up this often made and, in
my experience, totally incorrect truism?

I'd put the boot on the other foot, and ask the programmer who wishes to use
'register' to show that it reduces the runtime significantly[1]. If it
does, fine, let him use it.

Well, yes, that's the whole point. The programmer says that it makes a
significant difference by using the register attribute. If it doesn't,
in fact, help him meet the criteria, he will remove it (or ignore it if
he doesn't care).

[1] Which leads to the question "when is a runtime reduction 'significant'?"

When the programmer says it is! One example is the difference between
keeping up with a fixed rate, no flow control, incoming data stream or
not, but I am sure there are many others.

 

[Keith Thompson]

Richard Heathfield wrote: [...]

I'd put the boot on the other foot, and ask the programmer who
wishes to use 'register' to show that it reduces the runtime
significantly[1]. If it does, fine, let him use it.

Well, yes, that's the whole point. The programmer says that it makes
a significant difference by using the register attribute. If it
doesn't, in fact, help him meet the criteria, he will remove it (or
ignore it if he doesn't care).

A programmer will use the "register" keyword if he *thinks* it makes a
significant difference.

[1] Which leads to the question "when is a runtime reduction
'significant'?"

When the programmer says it is! One example is the difference between
keeping up with a fixed rate, no flow control, incoming data stream or
not, but I am sure there are many others.

When a *competent* programmer says it is. Not all programmers are
sufficiently competent to know when "register" is actually useful.

A runtime reduction is significant when it's significant, whether the
programmer says so or not.

(I'm not commenting on any programmers posting here.)

 

[Richard]

Richard Heathfield wrote: [...]

I'd put the boot on the other foot, and ask the programmer who
wishes to use 'register' to show that it reduces the runtime
significantly[1]. If it does, fine, let him use it.

Well, yes, that's the whole point. The programmer says that it makes
a significant difference by using the register attribute. If it
doesn't, in fact, help him meet the criteria, he will remove it (or
ignore it if he doesn't care).

A programmer will use the "register" keyword if he *thinks* it makes a
significant difference.

"register" has another side purpose too : it tells the reader/maintainer
what the original programmer saw as the critical data structure/pointer
- regardless of whether it really was effective at reducing run time or
not. Nothing wrong with "hints" like that when tracking down issues in
older legacy code and documentation/comments are minimum.

 

[Thad Smith]

I'd put the boot on the other foot, and ask the programmer who
wishes to use 'register' to show that it reduces the runtime
significantly[1]. If it does, fine, let him use it.

Well, yes, that's the whole point. The programmer says that it makes
a significant difference by using the register attribute. If it
doesn't, in fact, help him meet the criteria, he will remove it (or
ignore it if he doesn't care).

A programmer will use the "register" keyword if he *thinks* it makes a
significant difference.

Right. And if it matters, he verifies and makes adjustments to get the
best results. It's another tool.

[1] Which leads to the question "when is a runtime reduction
'significant'?"

When the programmer says it is! One example is the difference between
keeping up with a fixed rate, no flow control, incoming data stream or
not, but I am sure there are many others.

When a *competent* programmer says it is. Not all programmers are
sufficiently competent to know when "register" is actually useful.

Should we write compilers for competent programmers that can, in
critical situations, benefit from the assist, or only incompetent
programmers and non-critical tasks? I would prefer compilers that
benefit both, providing a good automatic optimization and register
allocation by default and honoring requests such as explicit register
allocation when requested.

I don't understand the argument that because register isn't needed in
most situations and some programmers cannot use it wisely that it
shouldn't be provided. I suppose the compiler could provide a option
switch that says ignore register requests and make it on by default.

 

[Keith Thompson]

Richard Heathfield wrote: [snip]
[1] Which leads to the question "when is a runtime reduction
'significant'?"

When the programmer says it is! One example is the difference between
keeping up with a fixed rate, no flow control, incoming data stream or
not, but I am sure there are many others.

When a *competent* programmer says it is. Not all programmers are
sufficiently competent to know when "register" is actually useful.

Should we write compilers for competent programmers that can, in
critical situations, benefit from the assist, or only incompetent
programmers and non-critical tasks? I would prefer compilers that
benefit both, providing a good automatic optimization and register
allocation by default and honoring requests such as explicit register
allocation when requested.

That sounds reasonable (unless compilers are *universally* better than
programmers at register allocation).

I don't understand the argument that because register isn't needed in
most situations and some programmers cannot use it wisely that it
shouldn't be provided. I suppose the compiler could provide a option
switch that says ignore register requests and make it on by default.

Personally, I've never made such an argument.

The common wisdom is that "register" is no longer useful, and can
often be harmful, because the compiler is likely to be better than the
programmer at deciding which variables should be assigned to
registers. I've never seen enough hard data *either way* to know
whether that's actually true. (Then again, I've never really looked
for such data.)

One advantage an optimizing compiler has is that it can re-analyze the
entire program every time it's compiled. If some seemingly irrelevant
modification changes the program's behavior in such a way that
performance can be improved by putting *this* variable rather than
*that* variable in a register, the compiler can do so; it can even
make far-reaching changes in the generated code in response to a small
change in the source. A programmer typically lacks (or *should* lack)
the patience to do that kind of thing.

But that doesn't necessarily argue against the use of "register";
rather it implies that optimization should be a joint effort between
the programmer and the compiler -- with the compiler doing the bulk of
the grunt work whenever possible.

 

[Jack Klein]

On 13 Oct 2006 17:07:04 -0700, (e-mail address removed) wrote in comp.lang.c: [...]

For the past ten years, the register keyword has been useless anyway.

Interesting assertion. Can you point to any measured test data to
back it up?

Do you have any measured test data to refute it?

(The question is not meant to imply that you don't have such data.)

Yes, for a wide variety of embedded compilers and for some PC based
ones, for specific situations. Going into detail would be off-topic
here.

But suffice it to say that the use of the register, inline, and
restrict keywords are nothing more or less than optimizations
techniques. Like all such techniques they are often used prematurely
and improperly. And like all such techniques, they can be used
properly and tested to verify that they do indeed achieve the desired
optimization.

 

[Kenneth Brody]

The register keyword tells the compiler
that you think that you know more about optimization
than the compiler does.

Compilers have gotten smarter over the years in terms of
optimization, while the human programmers haven't improved
that much. (Okay, the programmers writing the compiler
optimizers have learned more about optimizations, and in
doing so have made the compilers "smarter", while those
who use the compilers haven't improved siginificantly in
the area of optimization techniques.)

The only way to use "register" effectively,
is on a per implementation basis with timed tests.

In most "modern" compilers, the only likely effect of the
register keyword is that you are forbidden from taking the
arress of the variable, even if the compiler decides to not
use a register for it. (Remember the "as if" rule.)

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Keith Thompson]

In most "modern" compilers, the only likely effect of the
register keyword is that you are forbidden from taking the
arress of the variable, even if the compiler decides to not
use a register for it. (Remember the "as if" rule.)

The "as if" rule doesn't really apply here. Despite the spelling of
the keyword, "register" doesn't tell the compiler to store the
object in a register.

C99 6.7.1:

A declaration of an identifier for an object with storage-class
specifier register suggests that access to the object be as fast
as possible. The extent to which such suggestions are effective is
implementation-defined.

And a footnote:

The implementation may treat any register declaration simply as an
auto declaration. However, whether or not addressable storage is
actually used, the address of any part of an object declared with
storage-class specifier register cannot be computed, either
explicitly (by use of the unary & operator as discussed in
6.5.3.2) or implicitly (by converting an array name to a pointer
as discussed in 6.3.2.1). Thus, the only operator that can be
applied to an array declared with storage-class specifier register
is sizeof.

Hmm, I just noticed that sentence that "The extent to which such
suggestions are effective is implementation-defined." That means the
implementation is required to document it.

 

[dcorbit]

On 13 Oct 2006 17:07:04 -0700, (e-mail address removed) wrote in comp.lang.c: [...]
For the past ten years, the register keyword has been useless anyway.

Interesting assertion. Can you point to any measured test data to
back it up?

Do you have any measured test data to refute it?

(The question is not meant to imply that you don't have such data.)

Yes, for a wide variety of embedded compilers and for some PC based
ones, for specific situations. Going into detail would be off-topic
here.

I expect that my experience is different because I program large
systems (typically hundreds of thousands to millions of lines of code).

Register allocation is provably NP-hard, and is solved by very compute
intensive algorithms like graph coloring (though linear scan looks
promising for some situations):
http://www.research.ibm.com/jalapeno/papers/toplas99.pdf
There are some savants and incredibile calculators like "brain man":
http://www.abc.net.au/catalyst/stories/s1740757.htm
who might have some faint chance of outcalculating the algorithms used
in register allocation for a medium sized system, but I doubt that any
such instance has ever come about (for systems with hundreds of
thousands of lines or more) that would be able to outthink current
compilers.

For a large software system, no human on earth has the ability to
out-think the compiler when it comes to register allocation.

On the other, other hand, embedded compilers may be primitive in their
ability to optimize register allocation and the embedded software
systems tend to be very small so in such a circumstance it may be
possible to do better than the compiler. On rare circumstances, when
measurements indicated a problem, I have been able to outguess the
compiler with __forceinline__ but that is a different matter, not
related to the register keyword. With a half millions or so lines of
code, it is literally impossible for me to outguess the compiler with
register allocation.

But suffice it to say that the use of the register, inline, and
restrict keywords are nothing more or less than optimizations
techniques. Like all such techniques they are often used prematurely
and improperly. And like all such techniques, they can be used
properly and tested to verify that they do indeed achieve the desired
optimization.

For commercial compilers designed for large systems, I would be very
annoyed at any compiler that did not ignore the register keyword
completely. For embedded systems, you probably know a lot better than
I do.

 

[Frederick Gotham]

Keith Thompson posted:

The "as if" rule doesn't really apply here. Despite the spelling of
the keyword, "register" doesn't tell the compiler to store the
object in a register.

C99 6.7.1:

A declaration of an identifier for an object with storage-class
specifier register suggests that access to the object be as fast
as possible. The extent to which such suggestions are effective is
implementation-defined.

By that explanation, I would use register _all_ the time. I mean -- who
doesn't want their access to be as fast as possible?

 

[Richard]

Keith Thompson posted:



By that explanation, I would use register _all_ the time. I mean -- who
doesn't want their access to be as fast as possible?

Fortunately you would be aware of C, how it came about and how certain
constructs are there for the wily programmer to try and maximise
compiler hints. And that there are limited registers available depending
on the target processor.


--

 

[dcorbit]

Keith Thompson posted:



By that explanation, I would use register _all_ the time. I mean -- who
doesn't want their access to be as fast as possible?

When that access to something that does not need it prevents it from
happening to something that does need it.

If you have argc in main declared as a register, and the compiler
honors your request, and you have a one register machine, then the
nested inner loop array address won't get one.

I guess that 99% of register requests I see in source code (if honored)
would make programs slower. Even with the intelligent ones (e.g. an
address stride in a nested loop) the compiler is going to know if the
request is optimal[1].

[1] Apparently not, with embedded compilers. So caveat emptor. I
further guess that unless you are Jack Klein or some other really,
really smart guy, you still won't outguess even a badly designed
compiler.

 

[Eric Sosman]

Compilers have gotten smarter over the years in terms of
optimization, while the human programmers haven't improved
that much. (Okay, the programmers writing the compiler
optimizers have learned more about optimizations, and in
doing so have made the compilers "smarter", while those
who use the compilers haven't improved siginificantly in
the area of optimization techniques.)

It's not merely that fancier optimization techniques have
been invented, but also that the machines running the compilers
are bigger and faster. It was once out of the question for the
compiler to trace out all the execution paths and discover when
a variable had reached the end of its "useful" lifetime -- there
simply wasn't enough memory to hold the graph, nor CPU cycles to
conduct searches in it. The increases in speed, size, and power
benefit the compilers just as they benefit the applications, and
techniques that were once infeasible are now routine.

 

[Thad Smith]

I expect that my experience is different because I program large
systems (typically hundreds of thousands to millions of lines of code).

Register allocation is provably NP-hard, and is solved by very compute
intensive algorithms like graph coloring (though linear scan looks
promising for some situations):

I think this is missing the point. The problem is not hand allocating
registers for all million line of code, but rather let the compiler do a
good job for everything except where the programmer determines that

1) register allocation makes a significant difference
2) he can improve on the default allocation by specifying register
allocation of certain variables.

In C the programmer can specify where he wants specific allocation by
using the register keyword and allow default allocation everywhere else
by not specifying register.

This is similar to doing a good printed circuit board layout -- let the
autorouter do high 90s% of the work and allow the human to tweak the
routing where needed, if needed. The best result is a synergy between
man and machine.

For a large software system, no human on earth has the ability to
out-think the compiler when it comes to register allocation.

Man or machine is a false dichotomy. The best result is achieved by
using both in an intelligent way.

Part of the problem is the compiler not knowing the optimization
criteria. A compiler may be great at optimizing overall, but I may need
the minimum execution time between an interrupt and writing a servo
control. The rest of the code may be much less critical in terms of
timing. It may be better for that application to allocate 50% of the
registers to optimizing 10 lines of code in the critical path.
Allocating the variables for the critical path code is probably the
solution and yes, it needs to be verified.

On the other, other hand, embedded compilers may be primitive in their
ability to optimize register allocation and the embedded software
systems tend to be very small so in such a circumstance it may be
possible to do better than the compiler.

Unfortunately, that is often true. It seems ironic that usually more
effort is applied to optimizing targets with lots of resources and not
those with minimal resources. :-( Some low-end targeted compilers are
much better than others.

On rare circumstances, when
measurements indicated a problem, I have been able to outguess the
compiler with __forceinline__ but that is a different matter, not
related to the register keyword.

Actually I would consider it similar to the use of register. You are
saying "I need speed right here!" to the compiler for your particular
application.

With a half millions or so lines of
code, it is literally impossible for me to outguess the compiler with
register allocation.

And you don't need to do it for all lines, only the critical ones, just
the way you specified selective inlining. ;-)

For commercial compilers designed for large systems, I would be very
annoyed at any compiler that did not ignore the register keyword
completely.

"My code is good, compiler, except for use of 'register', in which case
you should assume that I am babbling nonsense". I recommend a
compile-time option to cater to that certain class of programmer.