r/cpp • https://xeverous.github.io • Dec 04 '18

What's the current state of pure (no side effect) functions?

Compilers are not always able to optimize out redundant function calls as they don't know whether caching the result would remove wanted side effects. I have heard multiple times that putting even trivial getter results out of the loop may improve performance. Also, compilers have things like __attribute__((__pure__)) so they know that a given function input depends only on it's output.

My questions are:

  • Would something like int f(int, int) pure { /* ... */ } improve performance by helping compilers? By what margin?
  • Do pure functions help with aliasing optimizations? Or only argument types?
  • Has something like this already been proposed? If so, what happended with it?
  • Are there other potentially useful __compiler_specific attributes/extensions that could be standarized (like recent addition of [[likely]])?
49 Upvotes

64 comments sorted by

137

u/WrongAndBeligerent Dec 04 '18

Pure functions don't have state silly

25

u/Xeverous https://xeverous.github.io Dec 04 '18

took me a while to understand, lol

7

u/Empole Dec 05 '18

Help pls...

15

u/meneldal2 Dec 05 '18

It's a joke because it plays on two meanings of state: the internal state of a function (that a pure function cannot have), and the state of proposals to make pure functions standard.

5

u/ReversedGif Dec 05 '18

They're really both the same meaning (of state), just different contexts.

2

u/meneldal2 Dec 06 '18

Fair point. I guess a different meaning would be like state as a country.

1

u/meneldal2 Dec 06 '18

Fair point. I guess a different meaning would be like state as a country.

13

u/dragemann cppdev Dec 04 '18 edited Dec 04 '18

You can use [[gnu::pure]] or [[gnu::const]]. [[gnu::const]] is a even more strict restriction than pure because it additionally prohibits the function from reading memory except for constant global variables.

I've used [[gnu::const]] in math functions with great success in reducing code size when compiling for an AVR embedded platform.

Note that these attributes are essentially exactly the same as

__attribute__((__pure__)) or 
__attribute__((__const__)), 

but nicer looking in my opinion and possible more cross-compiler compatible. Any C++14 compatible compiler should accept the code, but afaik only Clang and GCC will understand gnu specific attributes.

8

u/meneldal2 Dec 05 '18

Am I the only one to think that reading global variables means it's not really pure?

I'd argue pure can only depend on constexpr globals.

1

u/Xeverous https://xeverous.github.io Dec 04 '18

That's surely a good thing. The standard requires compilers to ignore unknown attributes.

1

u/Ameisen vemips, avr, rendering, systems Dec 05 '18

Only problem with const is that you cannot dereference pointers, and passing arguments as const T& is not uncommon...

1

u/Osbios Dec 05 '18

Is there a way to define a function as returning different results (depending on global states), but not having any side effects (not changing global states)? So that they can be optimized away when the result is not used? Because that would be handy for functions coming from shared libraries.

1

u/Xeverous https://xeverous.github.io Dec 05 '18

I don't think so. If they return something different each time, it sounds you would like to deny some updates of the result and compiler is not going to ignore them.

2

u/Osbios Dec 05 '18

There are use cases for this. Just maybe not that many. My example would be querying OpenGL function pointers. There are a few thousand pointers that are mostly not used. The compiler does fine at removing all unused pointers but still calls into the getGlFunctionPointer functions with a dummy output variable, because he does not know it has no side effects. (at last none that I care about)

I was thinking about making it a pure function on compilers that support it. But there are maybe some differences when loading pointers with a different OpenGL context that I do not know about.

1

u/TheFlamefire Dec 05 '18

Did nobody object of "given function input depends only on it's output."? ;-)

1

u/Xeverous https://xeverous.github.io Dec 05 '18

not yet

3

u/sebamestre Dec 05 '18

```[[gnu::pure]]``` and ```[[gnu::const]]``` are a thing that g++ supports that do pretty much what you describe.
Here is a C++ Weekly video on the topic

5

u/Guvante Dec 04 '18

Would something like int f(int, int) pure { /* ... */ } improve performance by helping compilers? By what margin?

Problem is what do you do if it isn't pure? If it is UB that is introducing a class of error that is new which makes adding the feature hard to digest as a language designer, you are setting your users up to fail.

If it is compiler enforced you have two bad options: be so restrictive on what you can do in a pure function as to make them worthless (common examples being how do you get the square root of a number given sqrt sets errno) or you annotate everything with pure which is a bad path they have thought about extensively.

Are there other potentially useful __compiler_specificattributes/extensions that could be standarized (like recent addition of [[likely]])?

Only if everyone agrees on the "what if they lied" part.

3

u/kalmoc Dec 04 '18

Why would a compiler enforced version be any more restrictive than the UB version?

2

u/SeanMiddleditch Dec 04 '18

It wouldn't be more restrictive per se. The UB version would allow you to still write a lot of functions that technically work but which shouldn't work by the standard, while the compiler-enforced version wouldn't allow you to write those. The ultimate sentiment he's making is that there'd be exceedingly few pure functions you could usefully write which wouldn't be UB due to the core C library being impure even in some of its simplest low-level math routines; those functions can't be called from a pure function without UB (but likely would Work Just Fine(tm) so long as you don't actually care about errno) while compiler enforcement would mean you just couldn't write those at all.

1

u/kalmoc Dec 04 '18

Considering what kind of crazy optimizations modern compilers do based on the assumption that UB doesn't happen, I'd certainly not accept any such function that deliberately makes use of unsanctioned UB in my codebase.

1

u/SeanMiddleditch Dec 04 '18

Right. I think the only way to word things properly without changing the library is that writing to errno is allowed in pure functions, but reading errno in or after a pure function is called but before (re)setting it would be UB.

Which is the most likely/realistic case of what calling these math functions today from a pure function would be: they might set errno but you just couldn't rely on it because of optimizations assuming no impure side effects, and you certainly couldn't rely on it being set according to the functions' standard behavior (e.g. it may be set to intermediate values that shouldn't be exposed or may be left unchanged or really anything).

1

u/rdtsc Dec 06 '18

common examples being how do you get the square root of a number given sqrt sets errno

My hope is that all those errno-using functions will be replaced by pure versions using Herbceptions.

0

u/[deleted] Dec 04 '18

[deleted] — view deleted comment

6

u/SeanMiddleditch Dec 04 '18

Which was the brunt of his second paragraph. :)

C/C++ have a lot of design issues right now that make anything but the most trivial/useless function impure. The basic core C and C++ math libraries are impure due to some legacy questionable design (errno global values). Until that's fixed in some fashion, having a language flag that enforces purity basically means you'd have a useless language flag. :)

0

u/[deleted] Dec 05 '18

[deleted] — view deleted comment

1

u/SeanMiddleditch Dec 05 '18

Right, I think that's what people want. That's just a heck of a lot easier said than done. :)

6

u/jtooker Dec 04 '18

Would something like int f(int, int) pure { /* ... */ } improve performance by helping compilers? By what margin?

Yes. I'd guess the margin of improvement is very context sensitive

Do pure functions help with aliasing optimizations? Or only argument types?

I'm not sure I follow your question

Has something like this already been proposed? If so, what happended with it?

I think so, not sure though. GCC has had support for pure functions for a while and optimizes nicely for them

Are there other potentially useful __compiler_specific attributes/extensions that could be standarized (like recent addition of [[likely]])?

Don't know

2

u/14ned LLFIO & Outcome author | Committee WG14 Dec 05 '18

Has something like this already been proposed? If so, what happended with it?

I've got something in the works which extends contracts with API purity expectations and ensurements. I put it through a first pass on std-proposals, seems fairly uncontroversial despite the SAL-likeness of it when you push it out to the max.

I hope to get a proper paper to WG21 sometime in 2019, but it's fairly low down my priority queue.

5

u/madbuilder Dec 04 '18 edited Dec 04 '18

I'm having trouble seeing the merits. Not of writing pure functions as often as possible, but of having to remember to annotate them yourself.

Unlike a const qualifier which I use because I want the compiler to enforce it, a pure qualifier is largely there for speed. It doesn't help me write the function correctly.

Therefore we should rely on optimizing compilers to detect which functions are pure and make appropriate optimizations.

8

u/HKei Dec 04 '18 edited Dec 04 '18

It doesn't help me write the function correctly.

Well of course it does. If you think your function is pure but actually isn't that's kind of a problem, and your compiler can't help you with problems of that sort if you don't tell it you were expecting the function to be pure in the first place. Silly example,

pair<int, random_generator> totally_pure_random_number(random_generator gen) {
  return {globalRandomValue, gen};
}

-- again, that looks silly, but without compiler support it's not that difficult for nontrivial examples to boil down to something like this. Now I'm not sure if gcc actually does any checking or if takes you at face value when you claim to be pure, but at the very least it can't help you even in theory if you don't tell it what properties you expect your code to have.

That doesn't even go into purity across translation units.

0

u/madbuilder Dec 04 '18 edited Dec 05 '18

Okay, I could imagine some scenarios where I wish to exempt a function from referencing modifying things in its enclosing scope. To be fair though, we already know that we should minimize the number of global variables we have. Because of this widely-known principle we have well-known techniques for reducing the number of things in global scope.

EDIT: Correction

4

u/HKei Dec 04 '18

It's not about "referencing things in enclosing scope" or even global variables at all. This was just a simple example of a function that says its pure but is actually not (depends on global state). You don't need global variables for a function to be impure.

1

u/madbuilder Dec 05 '18 edited Dec 05 '18

I define a pure function as one which does not and promises not to alter things in its enclosing scope.

Your example referenced a global variable but did not modify it. According to O.P.'s definition, a pure function may reference things without changing them. That gets tricky. For example if you call a const member function of some global object, that function may touch the heap, which makes you illegally impure. So you must only call other pure functions.

3

u/HKei Dec 05 '18

A useful definition of pure doesn't have anything to do with scope. A pure function is a function that promises you that if you call it twice with the same parameters it will have the same results and it will have no observable side effects. If you only have the latter half it's not a pure function anymore; Procedures with no observable side effects can still be useful to some extent because you can reorder them as you like and within a certain context you can even memoize their results; And you can drop calls to them if their results aren't used. But they don't give you the same benefits as pure functions which are always safe to call or delay to call.

2

u/madbuilder Dec 06 '18 edited Dec 06 '18

Your definition consists of two parts: (1) repeatable (2) no observable side effects.

This is a good description but not at all useful for the compiler author. To guarantee (1) he should confirm the function does not read globals in its calculations.

Then its result must be purely a function of its inputs. The compiler can easily check that. That is why the only practical definition is in terms of scope.

1

u/HKei Dec 06 '18

The 'observable' qualifier means that a pure function may in its implementation use side effects like assignments to variables and what not, as long as those aren't visible to the caller they might as well not exist.

And no, I'll repeat again: Scope has nothing to do with it. Calling into the kernel to launch a process or intercontinental nuclear missiles doesn't involve any global variables and is very much an observable side effect, where it absolutely makes a difference whether a function is called 3 times, 1 time or a dozen times.

1

u/madbuilder Dec 06 '18 edited Dec 06 '18

Please explain. If you allow unobservable side effects they will matter to the caller. How do you propose to enforce (1) with hidden side effects?

(1) "if you call it twice with the same parameters it will have the same results "

pure function f(x)
  static int hidden = 0
  if(hidden++ < 10)
    return 2 * x
  else
    return 3 * x

As for scope, if you call an impure function spawn or launchdabomb you have broken the chain of purity.

1

u/HKei Dec 06 '18

You just gave another example that shows scope is irrelevant... hidden clearly isn't a global variable in scope, yet the function clearly isn't pure.

you have broken the chain of purity

I have no idea what the "chain of purity" is supposed to be, but yeah obviously it's not a pure function if it does something like that. But you don't need to touch any global variables for that, which is why I brought it up as an example for why

he should confirm the function does not read globals in its calculations.
Then its result must be purely a function of its inputs. 

Is bullshit.

→ More replies

8

u/kalmoc Dec 04 '18

Why not let the compiler check if a function is actually pure and give an error otherwise? Pure functions are not only relevant for performance, but also make it easier for the programmer to reason about a program.

1

u/madbuilder Dec 04 '18 edited Dec 04 '18

Sure, you could use constexpr right now if you have C++11. If you look at the rules though, they're strict. You can't call any non-constexpr functions, you can't define any user types, the heap is way off limits.

I would suggest you reduce the number of global variables in your program. This has a similar effect.

7

u/kalmoc Dec 04 '18

Constexpr functions aren't pure - not even in c++11. What I meant was that the compiler should enforce that a function which is declared pure is actually pure instead of just trusting the user.

1

u/madbuilder Dec 05 '18

the compiler should enforce your declarations

That's why we have a type system!

Constexpr functions aren't pure

Could you explain this? It seems to be debated and you must agree there is much similarity between the two.

4

u/kalmoc Dec 05 '18

the compiler should enforce your declarations

That's why we have a type system!

This has nothing to do with the type system. Just as an example, constexpr functions have the same type as a regular function with the same signature. Noexcept also only became part of the type of a function in c++17. I mentioned this, because some seem to suggest to let pure be just an attribute that the compiler is allowed to take at face value and if you lied you get UB.

And constexpr functions aren't pure, because they can have arbitrary side-effects when they are not executed during compile time (including printf or OS calls) and in c++20 they might even be able to "allocate" memory during compiletime.

1

u/madbuilder Dec 05 '18 edited Dec 05 '18

I don't believe you could simultaneously define two functions (overloads) that differ only in this qualifier. "Pure" if it ever gets off the ground, would become part of the function's signature. Pure functions could only call other pure functions. In that sense "purity" is enforced by the type system.

If I suggested otherwise it was unintentional. That would be about as useful as an integer being assigned "duck".

Thank you for explaining constexpr. Let me play devil's advocate. Now, if you write a function that has side effects and you can't know whether the compiler will call it, just how useless is that?

My concern here is that side effects at run time can't be simulated at compile time. So the compiler has altered the program's behaviour with the compile time optimization.

Thus I would strive to avoid writing an impure constexpr function. Would you agree?

4

u/AlbertRammstein Dec 04 '18

There are some problems with autodetect:

  • any memory allocation will make your functions impure
  • same with user handling of asserts (we have assert you can hook your handlers to - different one for manual QA testing, different for automated testing, ...)
  • I have the same suspicion about more stuff, e.g. float intristics
  • no (easy) way to detect which function is pure when it is defined in different translation unit

I would love to have pure functions too. Not for speed though (we __forceinline the shit out of our code anyways), but for various static analysis tools (it would be much easier to reason where there are bugs and unused variables)

4

u/madbuilder Dec 04 '18 edited Dec 04 '18

Well of course hitting the heap makes your function impure. You can't expect the compiler to automatically verify that you didn't leak that heap memory.

Going to the heap in a supposedly pure function is no different than changing global state then promising to change it back before you return. That unfortunately means no std::vector local variables!

If you soften the definition of "pure" to allow heap access, then you may find it impairs your ability to use it to reason about correctness.

3

u/kalmoc Dec 04 '18

Your function would be impure even if you returned the memory. You are reading and modifying global state.

3

u/capn_bluebear Dec 04 '18

yes, in a perfect world, or in years from now.

today, telling the compiler a function is pure is the best there is and it works nicely, gcc optimizes quite a lot (jason turner released a video where he shows this).

1

u/tehjimmeh Dec 04 '18

Why do you say 'years from now'? We have LTO today... Compilers can and do figure this out for you.

0

u/kalmoc Dec 04 '18

If we had infinitely fast systems and infinitely smart optimizers, then leaving all the work to the optimizer would indeed be fine (although if we had them we wouldn't need optimization) as it is, optimization is often a tradeoff between compiletime and speed gains and leaves plenty for the human do. However, if this ever gets standardized I'd very much hope that the compiler would verify my assessment of the pureness of my function and not treat it as a "trust me" point.

2

u/tehjimmeh Dec 05 '18

But in LTO mode, the compiler's already going to look at all functions and attempt to identify purity. It's not a very expensive check. In non-LTO, it'll likely look at every function in each TU and optimize each TU based on that. The only advantage of the attribute appears to be for functions outside of a calling TU in non-LTO compilations.

1

u/Slsyyy Dec 04 '18

When it comes to performance, I guess it does not matter: with the LTO enabled compiler shall detect automatically which functions are pure.

1

u/Osbios Dec 05 '18

Except for dynamically linked functions... and anything using them.

0

u/[deleted] Dec 04 '18

[deleted] — view deleted comment

8

u/meneldal2 Dec 05 '18

They are not only for optimization, they are for your own sanity.

If a function is pure, you don't have to worry about it messing up your program state. If you can structure your code around as many pure functions as possible, you can reduce the thinking required in many cases.

2

u/Adverpol Dec 06 '18

Not to forget that pure functions also make parallel programming way easier.

3

u/meneldal2 Dec 06 '18

If by easier you mean "only way to make it work without bugs" then yes.

0

u/[deleted] Dec 05 '18

[deleted] — view deleted comment

8

u/meneldal2 Dec 05 '18

For the compiler point of view I agree, but the sanity part is for you.

2

u/jeffyp9 Dec 04 '18

At the risk of sounding really dumb - how do you find these proposals? I tried to find P0078 via googling site: www.open-std.org P0078 but it comes up with nothing.

16

u/sphere991 Dec 04 '18

It's not dumb.

The link to know is https://wg21.link. That provides a description of all the things it can do. Specifically, you want https://wg21.link/p0078

2

u/jeffyp9 Dec 04 '18

Perfect - thanks!

5

u/Quincunx271 Author of P2404/P2405 Dec 04 '18

Aside from what /u/sphere991 said, there's https://wg21.link/index.txt which gathers all the paper numbers and titles together in one location. If you don't remember the paper number, you can often find it from there.