LWN: Comments on "Implications of pure and constant functions"

Pure and constant external functions

giraffedata — Sat, 21 Jun 2008 03:28:09 +0000

Has anyone thought of having the compiler generate header files?
http://kerneltrap.org/node/16293

The reference is to a posting about kbuild and dependencies and build issues. I don't see any mention of having the compiler generate header files.

Pure and constant external functions

olecom — Thu, 19 Jun 2008 19:38:20 +0000

> Has anyone thought of having the compiler generate header files?

http://kerneltrap.org/node/16293

C89 includes blocks you know...

jlokier — Thu, 19 Jun 2008 17:23:19 +0000

Hardly.  C code with blocks and variables declared inside blocks is trivially convertible to a
flat function with all variables at the start, and in trivial time.  Same goes for the control
flow blocks: they are trivially replacable with if (variable) gotos.

So the proof difficulty is identical with/without blocks and local declarations in the
language.

Possible advantage

giraffedata — Wed, 18 Jun 2008 02:00:53 +0000

Of all the bugs I've analyzed with GDB, I'd say about 5% stop manifesting when I disable optimization. One was a compiler optimizer bug, one was me lying to the compiler (unintentionally, of course), and the rest were wild pointers causing stack corruption.

Of course, this is mostly with older compilers. (The new ones are too slow for me).

Possible advantage

roelofs — Tue, 17 Jun 2008 21:38:17 +0000

But when I debug at the machine level I add -O0 to the compile options. That's usually described as "don't optimize", but as I consider optimization to be an integral part of the compiler's job, I view it as, "Make the machine program track the source code as closely as possible."

"...and watch your bug go away." :-)

That seems to happen to me more often than not. Most recently it turned out to be a gcc code-generation bug, 32-bit only, 3.4.x only. (Pretty sure not related to const, though C++ is a different beast, so I'm not 100% certain.)

Greg

Implications of pure and constant functions

nix — Sun, 15 Jun 2008 12:34:18 +0000

Thanks to rarely-used glibc extensions, printf() and friends must be 
assumed by optimizers to be able to change *anything*, both because the 
information could be sent to a custom stream (-> calling arbitrary 
functions), and because they can contain specifiers for which custom 
conversion have been defined (-> calling arbitrary functions).

Constant function declaration: is it cheating?

giraffedata — Sat, 14 Jun 2008 16:34:02 +0000

If you can look at a function, and the way it behaves in your program, and guarantee "at any time in my program, during proper usage, this function will always return the same answer" then sure, call it constant, and you're not cheating or lying to the compiler, you're just being 100% accurate and using the attribute properly.

That's all I'm suggesting. The "constant" attribute must always mean the function is constant, not that you want the compiler to treat it as if it were constant. (It's none of your business what the compiler does with the information).

The only question is the definition of constant. The article's use of the term "cheating" suggests to me a definition of constant that is exactly what the compiler would determine on its own, e.g. if the function accesses global memory, it's not constant. But the examples given are of cases where the function really is constant under the broader definition.

Constant function declaration: is it cheating?

jimparis — Sat, 14 Jun 2008 06:52:45 +0000

> Is it really cheating or trickery to declare a function constant even though it accesses the
larger environment? Or is it just helping the compiler properly classify the function when it
doesn't have enough information to do it itself?

Yes!  Well, maybe it's not cheating, but it's definitely lying, and you'd better start
expecting your code to start failing in mysterious ways when you add more stuff to your
program or you switch to a new or different compiler.
Really, if you want to help the compiler, help it directly, don't try to trick the optimizer
into doing what you want.  If you're concerned about
  if (count(foo))  bar(count(foo));
where count() isn't really constant, but in this one case you know for a fact that it the
result won't change, just write
  tmp = count(foo); if (tmp) bar(tmp);

> All programs make assumptions about their environment. For example, that there isn't another
thread running around overwriting the memory in which the program's variables are stored.

There's a difference between valid documented assumptions (that my kernel separates processes
properly) and non-guaranteed observations (hey, if I lie to the compiler here then it seems to
generate better code).  In the first case, a problem is clearly a bug in the kernel and so it
would be fixed if it showed up.  In the second, it's your own bug when the assumption proves
wrong.

> So isn't it legitimate to make the environmental assumption that a certain file's contents
don't change while the program runs? With that assumption, a function whose result depends
upon the contents of the file is constant.

Aah, now that's different.  If you can look at a function, and the way it behaves in your
program, and guarantee "at any time in my program, during proper usage, this function will
always return the same answer" then sure, call it constant, and you're not cheating or lying
to the compiler, you're just being 100% accurate and using the attribute properly.

My concern with the article it suggests you might declare a function constant, even when it's
not(!), if it helps generate better code.  And that's definitely cheating and just asking for
problems.

Implications of pure and constant functions

etienne_lorrain@yahoo.fr — Fri, 13 Jun 2008 16:44:35 +0000

 Sometimes, I would also like an attribute to say "no content of parameter-pointers" are
changed by a function, in fact nothing important is changed in memory by a function.
 The main example would be printf(), or any function name used to print a debugging string -
with variable number of argument that cannot be prefixed by "const"
 (we cannot compile "void dbgprintf (const char *, const ...);").
 Then, if the compiler see some code like:
if (error)
    dbgprintf ("here is the context address %x %s %s\n", &s1, s1, s2);
 it has anyway to update in memory all content of pointer passed, but it does not have to
reload all those values to register after the call.
 The main problem of those dbgprintf() is that there may be a lot of them, and it would be
nice if they did not interfer too much with execution time or other optimisation. True that
for x86 there is not enough register to notice the problem, but it is bad to see a lot of
unused register on other arch because the compiler has to keep in sync the memory and
registers too often.

Pure and constant external functions

giraffedata — Fri, 13 Jun 2008 16:38:45 +0000

Has anyone thought of having the compiler generate header files?

In addition to saving one from having to code every function declaration twice, it would let the compiler detect attributes like pureness that I'm too lazy to declare manually.

Alternatively, the compiler might warn when the declaration doesn't have all the apparently applicable attributes.

Constant function declaration: is it cheating?

giraffedata — Fri, 13 Jun 2008 16:31:58 +0000

Is it really cheating or trickery to declare a function constant even though it accesses the larger environment? Or is it just helping the compiler properly classify the function when it doesn't have enough information to do it itself?

All programs make assumptions about their environment. For example, that there isn't another thread running around overwriting the memory in which the program's variables are stored. Where the user doesn't assure that assumed environment, the program's behavior is arbitrary.

So isn't it legitimate to make the environmental assumption that a certain file's contents don't change while the program runs? With that assumption, a function whose result depends upon the contents of the file is constant.

Possible advantage

giraffedata — Fri, 13 Jun 2008 16:17:50 +0000

I don't really see any advantage of making the code resemble the output of the compiler.

Hear, hear. There are two distinct ways to look at a program: 1) instructions to a computer; 2) description of the solution of a computational problem. The primary audience for (1) is a computer; for (2) it's a human. In view (2), a compiler's job is to produce a machine program that computes the solution described by the source code. A lot of programmers like to do that work themselves, but I think that is an inefficient use of brain power (for everyone who works on that code).

The closer the resemblance between source and executable, the more chance you have of understanding what you're seeing in the debugger.

That's definitely my experience. But there is a middle ground. I write human-oriented code and let the compiler do its job normally. But when I debug at the machine level I add -O0 to the compile options. That's usually described as "don't optimize", but as I consider optimization to be an integral part of the compiler's job, I view it as, "Make the machine program track the source code as closely as possible."

Implications of pure and constant functions

quotemstr — Thu, 12 Jun 2008 20:38:49 +0000

The key here is "check in". If somebody can check a change in, he can wreak all sorts of
havoc, much of it even more subtle than function attribute changes.

Besides, using function attributes like this to be a sort of post-benchmarking magic that
undergoes strict code review.

Implications of pure and constant functions

mtorni — Thu, 12 Jun 2008 20:04:36 +0000

Are there any security implications of labeling a function pure or constant? Can a malicious user introduce a security bug by checking in a change which changes a function to const? Say ssl_verify_certificate() or sasl_authenticate()? Both are fictitious functions.

C89 includes blocks you know...

davecb — Thu, 12 Jun 2008 16:08:21 +0000

Interestingly, allowing the internal block structure 
can increase the difficulty of doing logic on
the code to the point where building proof tools become
NP-complete (or at least insanely hard).

This is relevant if you're tying to use static analysis
tools, not just if you're trying to prove theoroms (;-))

--dave (who proveth not, but analyzeth a lot) c-b

Implications of pure and constant functions

Flameeyes — Thu, 12 Jun 2008 14:26:27 +0000

> I hope you're not suggesting that projects where entry is more closed,
> such as proprietary development do not experience "widely varying
> quality" of code.

In my experience, it isn't much varying... it usually is so bad it's not 
even funny to think of it twice.

On the other hand, proprietary software that is written badly is more 
easily discarded, as it fails to work at all in most cases - unless it's 
so proprietary you can't switch for a different one. On Free Software, 
badly written software can easily be patched up so that it works, and is 
kept in circulation of months and years.

I think the problem is in the big numbers, there is probably way more 
Free Software than proprietary software being developed by amateurs.

Omitting extra braces is a boon

IkeTo — Thu, 12 Jun 2008 13:41:08 +0000

> you have to scan the entire function to get to know what variables it will use.

I don't use any IDE other than plain Emacs.  But there is a search function, so the "scan"
that you mentioned is really by the editor program, not by myself.  On the other hand, I don't
find it overly useful to know what variables a function will use.  It is much more useful to
know what the function will do.  Since I don't usually trust comments in code, this is a
difficult task by itself, and it is much easier if there is not a dozen of variables springing
up at the same point of code which are not used for a dozen of lines (and I have to repeatedly
use the editor's search function to know about it, and then keep forgetting it 5 seconds after
doing that).  With C99/C++ style "declare variable on first use", I can tell easily which
assignment is an initialization and which is a modification to previously assigned value, the
latter I'll need to take much more care than the former.

> Having the code go too far to the right is a sign that you should probably break the
function

Of course.  But nothing beats a function that have just one or two levels of indentations: it
doesn't overload myself mentally.  Indentation is a necessary evil, it loads my mental
capability, but if you have a loop body you have to somehow differentiate it from the code
outside the loop, so it is still the best choice.  Using braces also for just variable
declaration leads to quite a few more levels than what I usually want to see in the code,
especially those written by somebody else.

And "break the function" is not always practicible.  Yes it is usually good, and when it is
good it is the best choice.  But at the same time usually it is not good: at times it creates
a whole brunch of functions that has little meaning by itself and has to be called from a
particular context to be useful at all, and the context is in a form of very complex
preconditions involving its arguments, sometimes involving additional structures to hold the
results, the structures, of course, are of little meaning by themselves as well.  A language
feature that provides an alternative when such "golden rule" is not practicible can only be a
good thing.

Times are changing

madscientist — Thu, 12 Jun 2008 13:00:53 +0000

Since we're talking about the C standard here, not the C++ standard, I'm not sure I understand your concern about the capabilities of C++ in GCC back "in the day". Although, you are definitely correct in your assessments, IMO.

What difference would it make to the C99 WG, what RMS's position was on C vs. C++, or the state of C++ in GCC at the time? There's no question that GCC was, even then, one of the most widely used C compilers around. My reference to proprietary compilers was meant to say that WG members couldn't/shouldn't be expected to pay for proprietary compiler licenses so they could learn about them: it's quite reasonable to expect those companies to pony up some $$ to send someone to the WG. For free software, there's nothing stopping the existing members from examining the docs and even the implementations directly, and/or asking questions on the mailing list to get details. Engaging the community that way, rather than requiring WG attendance or else ignoring the compiler, would have worked better for all concerned.

Implications of pure and constant functions

ekj — Thu, 12 Jun 2008 11:57:21 +0000

This low barrier to entry, though, is also probably the cause of the widely varying quality of the code of these projects.

I hope you're not suggesting that projects where entry is more closed, such as proprietary development do not experience "widely varying quality" of code.

C89 includes blocks you know...

nix — Thu, 12 Jun 2008 10:54:27 +0000

OK, broken compilers it is. (It's surprising that a language as apparently simple as C can
still trip one up with unexpected corners like this after so long.)

Times are changing

khim — Thu, 12 Jun 2008 08:35:05 +0000

At the time GCC's support was confusing and no company had the time and money to support a member at committee meetings.

The biggest problem at the time was RMS's position: GCC was supposed to be GNU C Compiler - and all other frontends were second-class citizens. Including C++. State-of-the-art GCC (the venerable 2.7.2.3) had awful C++ support and few developers used it as C++-compiler-of-choice. Eventually EGCS split happened, C++ support was improved to the point that now GCC is one of the C++ compilers - but all this happened after standard was finished. Today WG pays very serious attention to GCC: if some feature is flat-out rejected by GCC team it'll need A LOT OF supporters to be even considered. Thankfully GCC too pays close attention to what WG is doing so it's not a problem.

To WG difference between free compiler and proprietary one is NOT important. Difference between obscure and popular one is. As GCC's C++ compiler moved from obscurity to the compiler-of-choice it importance to WG moved similarly...

C89 includes blocks you know...

eru — Thu, 12 Jun 2008 05:17:36 +0000

Really? Everything I've found, including my reading of the text of C89, seems to say that initializers of automatic variables must be constant (and I use a number of compilers on a daily basis that reject non-constant initializers in C89 mode).

Well, they are broken compilers. Complain to the vendor.

A cite from C89 that supports your interpretation would be nice.

From my photocopy the original X3.159-1989:
3.5.7 Initialization
[syntax omitted]
Constraints
[...]
All the expressions in an initializer for an object that has static storage duration or in an initializer list for an object that has aggregate or union type shall be constant expressions.

Since the standard does not specify such constantness constraint for all objects with automatic storage duration, they can be runtime values.

The Rationale section for 3.5.7 makes this even more clear: According to it, the committee even considered allowing automatic aggregate initializers to consist of series of or arbitrary runtime expressions, but did not go that far in the end. The rationale also mentions that a function call that returns a structure is permitted as an initializer for an automatic variable with structure type. I have used some old compilers that had problems with this kind of structure initialization, but they still allowed automatic scalars to be initialized with runtime values. I think even K&R C allowed this.

Omitting extra braces is a boon

dododge — Thu, 12 Jun 2008 00:08:05 +0000

If your point is that people write horrible over-long functions, no argument there. The C89 rules certainly didn't stop them doing it, though, and frankly if I'm dealing with some 1000-line monstrosity of a function I'd rather be able to put the declarations on the same screen as the code using them, so that 1) I don't have to keep skipping back and forth to remember the types, and 2) I don't have to worry about what the 200 lines of code between the start of the function and the spot I'm looking at might have done with those variables.

But the main point, as already stated, is that from a practical standpoint you can't easily make your local variables const unless you either use mixed declarations or futz about with bracing and deep nesting. As someone who marks as much const as I can, and tries to limit scope as much as possible, I do make heavy use of mixed declarations and it's one of the C99 features that would be hardest to give up.

Omitting extra braces is a boon

jengelh — Wed, 11 Jun 2008 19:11:46 +0000

That's not the point.

Omitting extra braces is a boon

bronson — Wed, 11 Jun 2008 18:43:19 +0000

Doesn't your editor or IDE color the variable declarations?

Std C

madscientist — Wed, 11 Jun 2008 16:51:41 +0000

I really hope you're right, but in previous versions of the standard there was no interest by
the standards committee in how GCC does things.  Basically their attitude was "if GCC wants
their compiler considered, they'll send someone to the standards committee to represent it.
If not, too bad." (I'm greatly paraphrasing comments by committee members posted on
comp.std.c).  This might be understandable if GCC was a proprietary compiler that you had to
pay for... but it isn't of course.  At the time GCC's support was confusing and no company had
the time and money to support a member at committee meetings.

Hopefully things will be better this time.

Std C

cate — Wed, 11 Jun 2008 12:16:02 +0000

It is a working document (and a subsequent document document "const", giving better hints that
pure is allowed to read memory).
Anyway the version in standard should behave as gcc (or ev. as microsoft c compiler). They
really don't want (in next revision) to create alternate behaviors.

Std C

Yorick — Wed, 11 Jun 2008 11:44:33 +0000

That document is not quite consistent. It defines the attribute stdc_pure to indicate that a function "has no side effects and depends only on the values of the arguments passed". It then gives strlen as an example of such a pure function, contradicting the definition. It is unclear whether stdc_pure would correspond to GCC's const or pure attributes.

C89 includes blocks you know...

ballombe — Wed, 11 Jun 2008 11:31:10 +0000

I cannot provide you with one, but info gcc document this extension seems to imply the C89 restriction only apply to aggregate initializers.

5.18 Non-Constant Initializers
==============================

As in standard C++ and ISO C99, the elements of an aggregate
initializer for an automatic variable are not required to be constant
expressions in GNU C.  Here is an example of an initializer with
run-time varying elements:

     foo (float f, float g)
     {
       float beat_freqs[2] = { f-g, f+g };
       /* ... */
     }

C89 includes blocks you know...

nix — Wed, 11 Jun 2008 10:23:32 +0000

Really? Everything I've found, including my reading of the text of C89, seems to say that
initializers of automatic variables must be constant (and I use a number of compilers on a
daily basis that reject non-constant initializers in C89 mode).

A cite from C89 that supports your interpretation would be nice.

C89 includes blocks you know...

Yorick — Wed, 11 Jun 2008 10:07:19 +0000

No, local (automatic) variables may have non-const initialisers in c89.

Std C

cate — Wed, 11 Jun 2008 08:16:12 +0000

FYI the attribute concept, along with "pure" and "const" sttribute should enter in next C1x
standard, but possibly with other name.
See http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1273.pdf

Omitting extra braces is a boon

jengelh — Wed, 11 Jun 2008 07:08:46 +0000

Allowing mixing of declarations and code the C99/C++ way I consider a disadvantage, because you have to scan the entire function to get to know what variables it will use. And some people write horribly long functions without breaking them up asterisk comes to mind. Having the code go too far to the right is a sign that you should probably break the function (see CodingStyle).

Implications of pure and constant functions

nix — Wed, 11 Jun 2008 06:45:27 +0000

A classic example of a common class of functions that can't be optimized 
over even though you'd think it could be is *printf(). Standard printf() 
without %n can be freely optimized over, but alas glibc has an extension 
(user-defined format masks) that means printf() can call arbitrary 
functions for you.

That nobody ever uses this extension is irrelevant: the compiler must 
assume that you might be.

Implications of pure and constant functions

nix — Wed, 11 Jun 2008 06:42:17 +0000

Or "functions declared 'const' are implicitly 'pure', but not vice versa."

Implications of pure and constant functions

rriggs — Wed, 11 Jun 2008 03:00:17 +0000

Try this for clarity: "but not all pure functions are constant functions."

Implications of pure and constant functions

droundy — Wed, 11 Jun 2008 02:21:16 +0000

Indeed, the article should have stated that two consecutive calls to the same pure function
with the same arguments will give the same result, that's the difference between pure and
constant functions (constant functions always return the same for the same input).

With regard to your suggestion to just use Haskell, I'd point out that ghc doesn't support
CSE.  I love Haskell, and it's a great language, but this sort of optimization is not one of
its strengths.  Laziness interferes with its strengths as a pure functional language in this
case.  The trouble is that it's hard to determine when using the memory to store the result of
a computation is worth paying to avoid recomputing it.  For primitive data types the answer is
obvious, and we should do CSE, but ghc doesn't perform that analysis, and even if it did, I
wouldn't be happy with a CSE pass that only worked on functions returning Int/Double/Bool etc.

Of course, dead code elimination comes for free in Haskell, so that does gain us something.
But as the article points out, it's really only useful for things like conditional compilation,
which is much less of a gain than CSE.

Implications of pure and constant functions

rsidd — Wed, 11 Jun 2008 01:40:52 +0000

As MisterIO points out, the statement "pure functions cannot be constant functions" is obviously wrong.

Another point: in a language like C, surely the pureness of a function depends on all the other functions in a program? For example, you say (accurately, as far as the definition of "pure" goes): "Because the global memory state remains untouched, two calls to the same pure function with the same parameters will have to return the same value." Your example is the strlen() function. But what if some other function has tampered with the contents addressed by your pointer in between the two calls, without modifying the pointer itself?

You hint at this issue later when you say of an example: "(The pure function is called just once) because there was no change to global memory known to the compiler between the two calls of the pure function." So the compiler needs to determine whether the memory addressed could have changed. This is not always possible, unless the compiler decides that any intervening non-pure function call could have changed the memory addressed -- a drastic assumption since in practice most such calls are probably harmless.

My take is, if you care about pure functions, use Haskell :)

Implications of pure and constant functions

MisterIO — Wed, 11 Jun 2008 01:18:03 +0000

"As you can guess, constant functions are also pure functions, but pure functions cannot be
constant functions."

Shouldn't it be :
"As you can guess, constant functions are also pure functions, but pure functions can be not
constant functions." ?

Possible advantage

tialaramex — Wed, 11 Jun 2008 00:38:40 +0000

I'd say, from a little experience that it's an advantage during debugging. The closer the
resemblance between source and executable, the more chance you have of understanding what
you're seeing in the debugger.

If, for example, you used an unnecessary temporary, the debugger cannot show you the value of
that temporary. If you call a side-effect free function like strlen() several times the actual
code may call it just once, meaning that breaking on entry to strlen() will not do what you
expect. I recently deleted some code which read something like as follows...

int cache[CACHE_WIDTH];
if (!cache) {
  log_critical("Could not allocate cache");
}

A naive programmer might be quite surprised to see his debugger skip the last three of those
lines during single stepping, but in reality not a single byte of code was emitted or executed
for them due to a trivial optimisation.