c++ - 使用 const char 数组参数分析 constexpr 显示运行时执行

Question

我在我的程序中做了很多散列，所以我决定破解一个 constexpr 函数，它至少可以在编译时为我做一些散列。成功实现 constexpr 哈希函数后，我分析了代码，发现它实际上很花时间——这很奇怪，因为计算应该发生在编译时，而不是运行时。使用 G++ 4.7.3。

下面是 gprof 的一些输出，以及一个完整的演示程序，由于 constexpr 函数难以阅读，因此使用了非 constexpr 实现，同时也展示了它的工作原理。

我从以下链接中获取了建议，并将 char 数组设为 constexpr 和 const: why is a const array not accessible from a constexpr function?

注意:已从代码中删除一些内容以简化演示，例如测试和断言。

1.) 我的 constexpr 函数是否在运行时执行？ (对我来说似乎很明显)

2.) 如果是，为什么？我如何让它在编译时而不是运行时执行？

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)

演示程序:

#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 天过去了，没有任何人回答，所以我决定深入挖掘一下。

我想到在编译时尝试各种优化级别(使用 g++ -O#)

我将 for 循环迭代了几百万次(在相当老的计算机上)，并在优化级别 0、1、2、3 和 4 上计时执行。

我还编译成 ASM(使用 G++ -S)并检查程序生成的程序集。

我得出的结论是，constexpr 函数，或者可能特别复杂的 constexpr 函数，在低于 2 的任何优化级别上都被视为普通函数。在 2 级或更高级别，G++ 在编译时评估函数，并且它们没有进入可执行文件(通过检查程序集。asm 文件要短得多)。完全优化的可执行文件在不到一秒的时间内完成执行，而未优化的可执行文件花费了大约十倍的时间。此外，优化后的可执行文件在使用 gprof 进行分析时，未在其输出中显示任何 constexpr 函数。

底线是 constexpr 仅在以优化级别 2 或更高级别编译时在编译时进行评估。