2

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

下面是一些 gprof 输出，以及一个完整的演示程序，该程序包含一个非 constexpr 实现，因为 constexpr 函数很难阅读，并且也表明它可以工作。

我从以下链接中获取了建议，并制作了 char 数组 constexpr 和 const： 为什么无法从 constexpr 函数访问 const 数组？

注意：为了简化演示，我们从代码中删除了一些内容，例如测试和断言。

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;
}
4

1 回答 1

0

20 天过去了，没有人回答，所以我决定再深入一点。

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

我用 for 循环迭代了几百万次（在一台相当旧的计算机上），并在优化级别 0、1、2、3 和 4 上计时执行。

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

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

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

于 2013-10-18T19:42:16.390 回答