profiling constexpr with const char array parameters shows run-time execution

Question

I do a lot of hashing in a program of mine, so I decided to hack up a constexpr function that can do at least some of the hashing for me at compile-time. After successfully implementing a constexpr hash function, I profiled the code and it is actually taking time - which is strange, because the calculations are supposed to happen at compile-time, not run-time. Using G++ 4.7.3.

Below is a bit of gprof output, as well as a demonstration program complete with a non-constexpr implementation since the constexpr function is hard to read, and also to show that it works.

I've taken the advice from the following link and made the char array constexpr as well as const: why is a const array not accessible from a constexpr function?

Note: Some things have been removed from the code to simplify this for demonstration, such as tests and assertions.

1.) Are my constexpr functions executing at runtime? (Seems pretty obvious to me that they are)

2.) If so, why? And how do I get it to execute at compile-time instead of run-time?

gprof:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 50.00      0.06     0.06   600012     0.09     0.09  string_length(char const*, unsigned int)
 36.36      0.10     0.04    50001     0.80     2.20  HASHOAT_CONSTEXPR(char const*, unsigned int, unsigned int, unsigned int)
  9.09      0.10     0.01  1100022     0.01     0.01  oat_part_two(unsigned int const&)
  4.55      0.11     0.01    50001     0.10     0.10  oat_part_six(unsigned int const&)
  0.00      0.11     0.00  1650033     0.00     0.00  oat_part_one(unsigned int const&, char)
  0.00      0.11     0.00   550011     0.00     0.00  oat_part_three(unsigned int const&)
  0.00      0.11     0.00   200004     0.00     0.00  oat_part_four(unsigned int const&)
  0.00      0.11     0.00   100002     0.00     0.00  oat_part_five(unsigned int const&)
  0.00      0.11     0.00        1     0.00     0.00  HashOAT(char const*, unsigned int)

Demonstration Program:

#include <cstdio>
#include <cstring>

// "One-at-a-time" Hash

// the non-constexpr implementation:
unsigned int HashOAT( const char *key, const unsigned int size = 1009 ); // size must be prime
unsigned int HashOAT( const char *key, const unsigned int size ) {
    unsigned int h = 0;
    const std::size_t len = strlen(key);

    for ( std::size_t i = 0; i < len; ++i ) {
        h += static_cast< unsigned int >( key[i] );
        h += ( h << 10 );
        h ^= ( h >> 6 );
    }

    h += ( h << 3 );
    h ^= ( h >> 11 );
    h += ( h << 15 );

    return h % size;
}

constexpr unsigned int HASHOAT_CONSTEXPR( const char* str, const std::size_t size=1009, const std::size_t idx=0, const std::size_t h=0 );
constexpr unsigned int oat_part_one( const std::size_t& h, const char c );
constexpr unsigned int oat_part_two( const std::size_t& h );
constexpr unsigned int oat_part_three( const std::size_t& h );
constexpr unsigned int oat_part_four( const std::size_t& h );
constexpr unsigned int oat_part_five( const std::size_t& h );
constexpr unsigned int oat_part_six( const std::size_t& h );

constexpr unsigned int oat_part_one( const std::size_t& h, const char c ) {
    return ( h + static_cast<unsigned int>( c ) );
}

constexpr unsigned int oat_part_two( const std::size_t& h ) {
    return ( h << 10 );
}

constexpr unsigned int oat_part_three( const std::size_t& h ) {
    return ( h >> 6 );
}

constexpr unsigned int oat_part_four( const std::size_t& h ) {
    return ( h << 3 );
}

constexpr unsigned int oat_part_five( const std::size_t& h ) {
    return ( h >> 11 );
}

constexpr unsigned int oat_part_six( const std::size_t& h ) {
    return ( h << 15 );
}

constexpr std::size_t string_length( const char* str, std::size_t index = 0 ) {
    return ( str == nullptr || str[index] == '\0' ) ? 0 : 1 + string_length( str, index+1 );
}

constexpr unsigned int HASHOAT_CONSTEXPR( const char* str, const std::size_t size, const std::size_t idx, const std::size_t h ) {
    return (
        ( idx == string_length( str ) ) ? (
            (
                (
                    ( h + oat_part_four( h ) ) ^
                    oat_part_five( h + oat_part_four( h ) )
                ) +
                oat_part_six(
                    ( h + oat_part_four( h ) ) ^
                    oat_part_five( h + oat_part_four( h ) )
                )
            ) % size
        ) : (
            HASHOAT_CONSTEXPR( str, size, idx+1,
                (
                    oat_part_one( h, str[idx] ) +
                    oat_part_two( h + static_cast< unsigned int>( str[idx] ) )
                ) ^
                oat_part_three( oat_part_one( h, str[idx] ) +
                            oat_part_two( oat_part_one( h, str[idx] ) )
                )
            )
        )
    );
}

int main ( void ) {
    constexpr const char* str="Some String";
    printf("Hash: %i\n", HashOAT(str) );
    printf("Hash: %i\n", HASHOAT_CONSTEXPR(str) );

    // make the program take some time so we can see if the constexpr function is actually taking run-time
    for ( int i=0; i<50000; ++i ) {
        HASHOAT_CONSTEXPR(str);
    }
    return 0;
}

Answer 1

20 days has gone by without an answer from anyone, so I decided to dig a little deeper.

It occurred to me to try various optimization levels when compiling (with g++ -O#)

I bumped the for loop to iterate a couple million times (on a fairly older computer) and timed the execution at optimization levels 0, 1, 2, 3, and 4.

I also compiled into ASM (with G++ -S) and examined the assembly the program produces.

The conclusion I came to is that constexpr functions, or perhaps particularly complex constexpr functions, are treated as normal functions on any optimization level below 2. At level 2 or higher, G++ evaluated the functions at compile time, and they did not make their way into the executable (from examining the assembly. The asm file was much, much shorter). The fully optimized executable completed execution in under a second, while the unoptimized executable took about ten times as long. Also, the optimized executable, when profiling with gprof, did not show any constexpr function in it's output.

Bottom line is constexpr only gets evaluated at compile time when compiling at optimization level 2 or higher.