Allow inline functions to be evaluated in different contexts

[TONGARI J]

We currently have 2 evaluation contexts in standrard C++:

• normal context
  
• constant context

In non-standard world, we also have language-extensions like CUDA and C++AMP that provides GPU evaluation context.

Before C++11, we only had normal context in standrard. Everytime a new evaluation context is introduced into the language, it also requires us to 'mark' the functions manually in order to adopt the new context, for example:

• constant expression - `constexpr`
  
• CUDA - `__device__`
  
• C++AMP - `restrict(amp)`
  
• coroutine - probably `resumable` or `async`
  
• etc...

This is annoying, why can't the compiler treat inline functions in a context-agnostic way?

Here's an interesting example about `constexpr`, consider how `std::min` is defined:

template<class T>
constexpr const T& min( const T& a, const T& b )
{
    return (b < a) ? b : a;
}

Given a class `A` which doesn't have a constexpr `<` operator:

struct A
{
    bool operator<(A const&) const
    {
        return false;
    }
};

It's OK to call `min(A{}, A{})`, which results in a runtime value.

But if we define a non-template `minA` specifically for `A`, it won't compile:

constexpr const A& minA(const A& a, const A& b)
{
    return (b < a) ? b : a;
}

It's interesting that the template one compiles while the non-template one fails.

The way standard algorithms exploits `constexpr` thus seems 'hacky' -- it makes use of the weakness of `constexpr` that it can't check if the functions called are really `constexpr` if they depend on the template args.

A more reasonable way is to allow inline functions to be context-agnostic so we can define `min` as:

template<class T>
inline const T& min( const T& a, const T& b )
{
    return (b < a) ? b : a;
}

When evaluated in constant context, the restrictions of constant-expression are automatically imposed, for example:

A a1, a2;
constexpr const A& a = min(a1, a2); // error!
const A& a = min(a1, a2); // ok

Note that I'm not arguing the usefulness of `constexpr` on functions, I acknowledge that it's still useful in restricting the function explicitly.

What I'm arguing is to make such marking optional, so we don't have to mark functions `constexpr` to make them constant-expressions.

I'm aware of the concerns shown here:

http://stackoverflow.com/a/19830673/2969631

If it'd better not to change the semantic of `inline`, we can introduce a new keyword `generic` to explicitly specify that the functions should be able to be evaluated in different contexts.

Then we could mark the STL functions `generic` instead of the more restricted `constexpr` to accomadate the future-context-to-come.

Thoughts?

[Nicol Bolas]

On Sunday, October 4, 2015 at 8:52:53 AM UTC-4, TONGARI J wrote:

We currently have 2 evaluation contexts in standrard C++:

• normal context
  
• constant context

In non-standard world, we also have language-extensions like CUDA and C++AMP that provides GPU evaluation context.

Before C++11, we only had normal context in standrard. Everytime a new evaluation context is introduced into the language, it also requires us to 'mark' the functions manually in order to adopt the new context, for example:

• constant expression - `constexpr`
  
• CUDA - `__device__`
  
• C++AMP - `restrict(amp)`
  
• coroutine - probably `resumable` or `async`
  
• etc...

This is annoying, why can't the compiler treat inline functions in a context-agnostic way?

Because each of those contexts have restrictions on what is allowed within them. `constexpr` is quite restrictive compared to runtime. I don't know what goes on in `__device__` or `restrict(amp)`, but I'd bet they are also restrictive as well.

If I write code that I intend to be able to run at constexpr time, I want the compiler to make sure that I've written it correctly. I don't want the compiler to allow me to write invalid `constexpr` code and not tell me just because all of my uses of that function happen to be evaluated at runtime.

It's interesting that the template one compiles while the non-template one fails.

 

The way standard algorithms exploits `constexpr` thus seems 'hacky' -- it makes use of the weakness of `constexpr` that it can't check if the functions called are really `constexpr` if they depend on the template args.

It's not exploring "weakness" in `constexpr`; it's exploiting rules in template instantiation. When you write a template function, whether the operations are constexpr or not depends on the template arguments passed in. So the compiler cannot detect any errors. And more importantly, the user cannot know if they've done the right thing or not.

Therefore, the rules are different for template functions than non-template functions (no matter how much Bjarne seems to want to turn them into the same thing). In non-template code, you're saying "This function will be constexpr." In template code, you're saying, "Declare this function constexpr if all of the substituted operations are constexpr." I'm not positive, but I'd bet that the first phase of two-phase-lookup for template constexpr will statically fail if non-dependent operations are not constexpr.

I understand what you want. I just don't know why you want it. Why do you want to shut off compile-time checking?

I'm aware of the concerns shown here:

http://stackoverflow.com/a/19830673/2969631

It's interesting that you linked to the second answer, but seem to have ignored all of the (very good) points in the first answer. That argues more strongly even against you `generic` idea.

[TONGARI J]

2015-10-04 21:47 GMT+08:00 Nicol Bolas <jmck...@gmail.com>:

On Sunday, October 4, 2015 at 8:52:53 AM UTC-4, TONGARI J wrote:

We currently have 2 evaluation contexts in standrard C++:

• normal context
  
• constant context

In non-standard world, we also have language-extensions like CUDA and C++AMP that provides GPU evaluation context.

Before C++11, we only had normal context in standrard. Everytime a new evaluation context is introduced into the language, it also requires us to 'mark' the functions manually in order to adopt the new context, for example:

• constant expression - `constexpr`
  
• CUDA - `__device__`
  
• C++AMP - `restrict(amp)`
  
• coroutine - probably `resumable` or `async`
  
• etc...

This is annoying, why can't the compiler treat inline functions in a context-agnostic way?

Because each of those contexts have restrictions on what is allowed within them. `constexpr` is quite restrictive compared to runtime. I don't know what goes on in `__device__` or `restrict(amp)`, but I'd bet they are also restrictive as well.

If I write code that I intend to be able to run at constexpr time, I want the compiler to make sure that I've written it correctly. I don't want the compiler to allow me to write invalid `constexpr` code and not tell me just because all of my uses of that function happen to be evaluated at runtime.

No disagreement here, but that's not the point. I'm not asking the compiler to allow me to write invalid `constexpr` code, I'm just asking it to allow me to write `generic` code that could be potentially treated as constant expression.

 

It's interesting that the template one compiles while the non-template one fails.

 

The way standard algorithms exploits `constexpr` thus seems 'hacky' -- it makes use of the weakness of `constexpr` that it can't check if the functions called are really `constexpr` if they depend on the template args.

It's not exploring "weakness" in `constexpr`; it's exploiting rules in template instantiation. When you write a template function, whether the operations are constexpr or not depends on the template arguments passed in. So the compiler cannot detect any errors. And more importantly, the user cannot know if they've done the right thing or not.

Therefore, the rules are different for template functions than non-template functions (no matter how much Bjarne seems to want to turn them into the same thing). In non-template code, you're saying "This function will be constexpr." In template code, you're saying, "Declare this function constexpr if all of the substituted operations are constexpr."

That's the source of confusing. A better constexpr design, IMHO, should restrict the template one as well.

That is, in my example, if the function template `min` is declared constexpr, `min(A{}, A{})` should fail to compile, to make it generic, it should be declared as `generic` instead.

 

I'm not positive, but I'd bet that the first phase of two-phase-lookup for template constexpr will statically fail if non-dependent operations are not constexpr.

I understand what you want. I just don't know why you want it. Why do you want to shut off compile-time checking?

I think the reason is obvious. Yesterday we introduced constant expression into the language, what happened? the STL are now updated with bunch of `constexpr` here and there, and the user code that wants to take advantage of that also needs to be manually marked. Tomorrow we introduce another fancy-context and now, we need to mark the code again to adopt the new context. What a frustrating process.

What if I, as the author of the function, want to tell the compiler that this function has the potential to be evaluated in any context? We need a way to do that, and that could be `inline`, or better yet,`generic`.

 

I'm aware of the concerns shown here:

http://stackoverflow.com/a/19830673/2969631

It's interesting that you linked to the second answer, but seem to have ignored all of the (very good) points in the first answer. That argues more strongly even against you `generic` idea.

Well, the arguments are just not promising to me. When you call a generic function, if it's not applicable to a certain context, it just fails to compile, and you'll get the error, no harm will be caused.

[Andrew Tomazos]

On Sun, Oct 4, 2015 at 2:52 PM, TONGARI J <tong...@gmail.com> wrote:

A more reasonable way is to allow inline functions to be context-agnostic so we can define `min` as:

template<class T>
inline const T& min( const T& a, const T& b )
{
    return (b < a) ? b : a;
}

When evaluated in constant context, the restrictions of constant-expression are automatically imposed,

This has been suggested before.  You are essentially asking that all functions that could be constexpr, be implicitly constexpr.  Likewise for the other "contexts".

The problem is compile-time.  Compiling a constexpr function (for example) is expensive.  Doing it automatically for all function definitions would increase compile times too much.

You have to explicitly mark the functions you want to use in constexpr contexts, so the compiler knows it doesn't have to do the extra analysis for all the other ones.

[TONGARI J]

Yeah, I'm aware of that, please see the tail of my mail. I was suggesting a new keyword `generic` if that's an issue. `generic` won't introduce more overhead than `constexpr `, so what currently marked `constexpr ` in STL could be marked as `generic` when feasible.

[Agustín K-ballo Bergé]

On 10/4/2015 12:07 PM, Andrew Tomazos wrote:
> The problem is compile-time. Compiling a constexpr function (for
> example) is expensive. Doing it automatically for all function
> definitions would increase compile times too much.

The problem is not only compile-time, `constexpr` may affects whether
the program is well-formed. Constexpr functions are potentially
instantiated in unevaluated contexts. Have a look at CWG1581 for the
gory details, or check https://llvm.org/bugs/show_bug.cgi?id=23141 for
an actual case of `constexpr`-induced breakage.

> You have to explicitly mark the functions you want to use in constexpr
> contexts, so the compiler knows it doesn't have to do the extra analysis
> for all the other ones.

...nor breaks your program by doing something you did not want it to do.

Regards,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com

[Jeremy Maitin-Shepard]

I'm not sure I understand this point.  I am not really aware of exactly how constexpr evaluation is handled in compilers, but I assume it comes down to storing some type of AST when the function is parsed, and then either evaluating directly based on that or possibly converting it to some intermediate representation, which could presumably be done in a JIT fashion when actually required.  In terms of just processing the definition, I don't see how there can be a significantly greater cost to a function marked inline constexpr compared to a function just marked inline (or a template).

It seems that the only extra work should come when the function is actually being evaluated in a constexpr context, i.e.

constexpr auto x = foo();

If it is never evaluated in a constexpr context, the extra cost should never occur.  Of course even in a runtime context the compiler may choose to do constant folding, but it already may do that even for functions not marked constexpr, so again there is no added cost to constexpr.

Another key point is that when designing a library, or any code designed to be reusable, there tends to be no way to know that something would not potentially be useful at compile-time, except if it is simply impossible, e.g. because it involves a system call.  Gradually every utility function and algorithm in the c++ standard library is being marked constexpr.  If we get dynamic memory allocation at compile-time, which I hope we will, then every data structure would also become fully constexpr, essentially leaving just the C library, iostreams, and threading non-constexpr, and we could potentially even allow threading at compile time.  constexpr on functions is starting to become just a syntactic tax.

[Jeremy Maitin-Shepard]

On Sunday, October 4, 2015 at 10:37:07 AM UTC-7, Agustín K-ballo Bergé wrote:

On 10/4/2015 12:07 PM, Andrew Tomazos wrote:
> The problem is compile-time.  Compiling a constexpr function (for
> example) is expensive.  Doing it automatically for all function
> definitions would increase compile times too much.

The problem is not only compile-time, `constexpr` may affects whether
the program is well-formed. Constexpr functions are potentially
instantiated in unevaluated contexts. Have a look at CWG1581 for the
gory details, or check https://llvm.org/bugs/show_bug.cgi?id=23141 for
an actual case of `constexpr`-induced breakage.

I don't see a specific resolution listed for that issue, specifically in regards to the "Note from the April, 2013 meeting", which seems to address the critical part.

[Nicol Bolas]

On Sunday, October 4, 2015 at 11:03:59 AM UTC-4, TONGARI J wrote:

2015-10-04 21:47 GMT+08:00 Nicol Bolas <jmck...@gmail.com>:

On Sunday, October 4, 2015 at 8:52:53 AM UTC-4, TONGARI J wrote:

We currently have 2 evaluation contexts in standrard C++:

I'm aware of the concerns shown here:

http://stackoverflow.com/a/19830673/2969631

It's interesting that you linked to the second answer, but seem to have ignored all of the (very good) points in the first answer. That argues more strongly even against you `generic` idea.

Well, the arguments are just not promising to me. When you call a generic function, if it's not applicable to a certain context, it just fails to compile, and you'll get the error, no harm will be caused.

The strongest argument (to me) made in that post against your idea has to do with contracts.

A function signature is a contract between me, the user of that function, and you, the writer of that function. When you put a parameter into that signature, it is my responsibility to provide a value for that parameter when I call your function. And C++ statically checks that this contract is being fulfilled.

Similarly, when you put `constexpr` in a function's signature, you are saying that it is legal for me to use this function in constant contexts. When you put `constexpr` in a template function's signature, you are saying that it is legal for me to use this function in constant contexts when instantiated with types that fulfill certain conditions (which due to lack of syntax, are currently un-specifiable).

OK, so what does `generic` mean? What contract does that create?

It certainly does not mean `constexpr`; I have no guarantees that the function with such a decoration will be executable in a constant expression context. So what does it mean to me?

If you give me a library function that is `constexpr`, I am free to use it in a `constexpr` way. However, if you later update that library to remove `constexpr` from the function's signature, that represents a breaking change. Which you should inform people of before giving them an update.

The most important part of this breaking change is this: it did not happen by accident (probably). To make this change, you had to change the function's signature. And thereby change the contract with the user. You couldn't do that by accident.

If you give me a library function that is `generic`... what can I do with that? Even if your current implementation happens to permit usage in constant expressions, what guarantee do I have that you won't change that in the future? A function signature is supposed to be a contract, but yours is very... loose. It tells me nothing about where I may use it.

Even worse, you can change the contract by accident. If none of your tests use the function in constant expressions, then you can accidentally do something that is not constexpr-legal. Your code won't complain at all. You will have changed the contract without being aware of it. And therefore, you will have broken me without knowing that you should tell me first.

To protect myself from such dangerous, accidental changes, I will have no choice but to treat your `generic` functions as though they were not potentially `constexpr`. I'll likely write a non-constexpr wrapper function that forwards from/to it.

So you've ultimately gained nothing.

[Agustín K-ballo Bergé]

You don't see a resolution because that issue is still active.

[Andrew Tomazos]

On Sun, Oct 4, 2015 at 7:48 PM, Jeremy Maitin-Shepard <jer...@jeremyms.com> wrote:

On Sunday, October 4, 2015 at 8:07:56 AM UTC-7, Andrew Tomazos wrote:

On Sun, Oct 4, 2015 at 2:52 PM, TONGARI J <tong...@gmail.com> wrote:

A more reasonable way is to allow inline functions to be context-agnostic so we can define `min` as:

template<class T>
inline const T& min( const T& a, const T& b )
{
    return (b < a) ? b : a;
}

When evaluated in constant context, the restrictions of constant-expression are automatically imposed,

This has been suggested before.  You are essentially asking that all functions that could be constexpr, be implicitly constexpr.  Likewise for the other "contexts".

The problem is compile-time.  Compiling a constexpr function (for example) is expensive.  Doing it automatically for all function definitions would increase compile times too much.

You have to explicitly mark the functions you want to use in constexpr contexts, so the compiler knows it doesn't have to do the extra analysis for all the other ones.

I'm not sure I understand this point.  I am not really aware of exactly how constexpr evaluation is handled in compilers, but I assume it comes down to storing some type of AST when the function is parsed, and then either evaluating directly based on that or possibly converting it to some intermediate representation, which could presumably be done in a JIT fashion when actually required.

I just tested it (gcc 5.2) and observed that a 5-line C++14 constexpr function definition takes 5% longer to compile (~105us) than the same inline function (~100us) (even if it isn't used).  This is less than I expected, but still quite significant.

It is unclear to me whether this completely highlights the performance concerns about implicit constexpr.  Admittedly I am reporting them second-hand.

[TONGARI J]

Out of curiosity, is your test function templated or not?

[Andrew Tomazos]

not.

[TONGARI J]

It's interesting to know that the paper P0069R0[1] claims that they've implemented the "inline-is-generic" idea (or sort of) already, quoting from the paper [2.2]:

The C++AMP specification defined a new “restrict” keyword which restricted the language features allowed in the code region and also identified the code to compile for the accelerator. However, in hindsight the “restrict” keyword has several downsides. Composing functions becomes tricky as the “restrict” keyword tends to ripple through the call hierarchy. Additionally, re-using existing code is nontrivial, even in cases where the functions are short and available in header files (e.g. std::min). HCC employs a more sophisticated mechanism so that compiler effort focuses on the parallel loops, and only generates and optimizes accelerator code where required. As described in the previous section, HCC provides several mechanisms for programmers to mark parallel regions - specifically hc::parallel_for_each and [[hc_grid_launch]]. These markers indicate that the marked functions will execute on the accelerator. Likewise, any functions called by these marked functions execute on the accelerator. Thus the compiler can identify which functions will execute on the accelerator and, in cases where the functions are defined in header files, can automatically generate correct accelerator code without the need for additional function attributes.

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0069r0.pdf