constexpr versus run-time (lack of) efficiency

[Alf P. Steinbach]

Following a suggestion from David Brown I've looked at how to make my
simple `is_ascii` function `constexpr`, for C++11.

At first I coded it as simple tail-recursive, but this had the problem
that without optimization it could blow the machine stack when it was
applied to a long string. So I now changed it to divide-and-conquer
recursive, buying safety at the cost of potential inefficiency in the
case where the arguments don't allow compile time evaluation. I gave
this function a new name, `constexpr_is_ascii`, so that one can choose:
efficient compile time evaluation when one knows the arguments allow
that, or reasonably efficient checking for data known only at run time.

Is there any way to /automate/ that choice?

• • •

For completeness & context, the relevant code:

constexpr
inline auto is_ascii( In_<char> code )
-> bool
{ return Byte( code ) <= Byte( Ascii::del ); }

template< class Iter >
auto is_ascii( In_value_<Iter> first, In_value_<Iter> after )
-> bool
{
for( Iter it = first; it != after; ++it )
{
if( not is_ascii( *it ) ) { return false; }
}
return true;
}

// If this isn't optimized in a smart way then it can be
inefficient when the
// arguments don't allow compile time evaluation. In that case:
stack depth
// O(log2 n), number of calls O(n). The iterator must be random access.
template< class Iter >
constexpr
auto constexpr_is_ascii( In_value_<Iter> first, In_value_<Size> n )
-> bool
{
return( 0?0
: n == 0?
true
: n == 1?
is_ascii( *first )
: //else
constexpr_is_ascii( first, n/2 ) and
constexpr_is_ascii( first + n/2, n - n/2 )
);
}

// See comment above ↑.
template< class Iter >
constexpr
auto constexpr_is_ascii( In_value_<Iter> first, In_value_<Iter> after )
-> bool
{ return constexpr_is_ascii( first, after - first ); }


Cheers,

- Alf

[Marcel Mueller]

n 27.01.16 02.12, Alf P. Steinbach wrote:
> Following a suggestion from David Brown I've looked at how to make my
> simple `is_ascii` function `constexpr`, for C++11.

[...]
Well, your problem is C++11.

So either you have the option to use your implementation for C++11 and
ensure that the optimizer catches your code on your target platform(s)
or you rely on extensions that some compilers provide regarding constexpr.
Basically you are looking forward to C++14 which allows the trivial
implementation of is_ascii(string) as constexpr. This could be
distinguished by #if.

[two implementations]

> Is there any way to /automate/ that choice?

So you want to overload your function with and without constexpr?
AFAIK this is not possible.


Marcel

[Öö Tiib]

On Wednesday, 27 January 2016 03:13:15 UTC+2, Alf P. Steinbach wrote:
> Following a suggestion from David Brown I've looked at how to make my
> simple `is_ascii` function `constexpr`, for C++11.
>
> At first I coded it as simple tail-recursive, but this had the problem
> that without optimization it could blow the machine stack when it was
> applied to a long string. So I now changed it to divide-and-conquer
> recursive, buying safety at the cost of potential inefficiency in the
> case where the arguments don't allow compile time evaluation. I gave
> this function a new name, `constexpr_is_ascii`, so that one can choose:
> efficient compile time evaluation when one knows the arguments allow
> that, or reasonably efficient checking for data known only at run time.
>
> Is there any way to /automate/ that choice?

Following example may be of use:

#include <iostream>
#include <type_traits>

template<typename T>
constexpr typename std::remove_reference<T>::type makeprval(T && t)
{
return t;
}

#define isprvalconstexpr(e) noexcept(makeprval(e))

int main(int argc, char *argv[])
{
int a = 1;
const int b = 2;
constexpr int c = 3;
const int d = argc;

std::cout << isprvalconstexpr(a) << std::endl ;
std::cout << isprvalconstexpr(b) << std::endl ;
std::cout << isprvalconstexpr(c) << std::endl ;
std::cout << isprvalconstexpr(d) << std::endl ;
}

It outputs:

0
1
1
0

That can be perhaps used to select the algorithm? I think I took it
from SO answer of Johannes Schaub and there was something about
limitations but don't remember what question it was.

[Alf P. Steinbach]

That's pure genius. :)

But then, his trick for accessing private members was also pure genius.


Cheers, & thanks,

- Alf