9

gcc 似乎对复杂的常量折叠有一些限制。这是一个例子：

static inline unsigned int DJBHash(const char *str)
{
   int i;
   unsigned int hash = 5381;

   for(i = 0; i < strlen(str); i++)
   {
      hash = ((hash << 5) + hash) + str[i];   
   }

   return hash;
}

int f(void)
{   
    return DJBHash("01234567890123456");
}

当以 -O3 优化级别（gcc 4.8）运行时，它会很好地展开 DJBHash 中的循环，并在编译期间计算该字符串的哈希值。

但是，当使字符串变长一个字符时return DJBHash("012345678901234567");，它不再折叠它并生成一个带有条件跳转指令的循环。

我想将任意长度的文字字符串折叠为其哈希值作为编译时间常数。
这可以做到吗？

澄清

我的问题是关于 gcc 上的常量折叠优化（请参阅标题 - 请不要删除gcc和编译器标签）
这里的许多答案试图用模板或 constexpr 解决问题。很高兴了解这些选项，并感谢您发布它们以造福所有人。但是，他们没有直接回答我的问题。

实际上，我正在开发一个 gcc 端口，因此如果需要，我可以更改和构建 gcc 源代码。但我仅限于 C，我想在这个范围内解决这个问题。

4

4 回答 4

9

这是一个使用constexpr. 它在一个方面与其他的略有不同——因为是递归的，可以这么说，最容易将字符串哈希回前面。例如，它为“abc”提供的值将是您通常期望从“cba”获得的值。我认为这不会对使用产生任何真正的影响，只要您始终如一地使用其中一种（但考虑到散列的变幻莫测，我可能是错的）。

但它确实在编译时进行评估——例如，我们可以将结果用作switch语句中的标签：

#include <iostream>

unsigned constexpr const_hash(char const *input) {
    return *input ?
           static_cast<unsigned>(*input) + 33 * const_hash(input + 1) :
           5381;
}

int main(int argc, char **argv) {
    switch (const_hash(argv[1])) {
    case const_hash("one"): std::cout << "one"; break;
    case const_hash("two"): std::cout << "two"; break;
    }
}

显然，可能会发生冲突，因此您通常不希望将其用作 case 语句标签——我这样做主要是为了强制导致如果结果不是编译时常量，它将无法编译的情况。

编辑：如果您关心哈希算法是否“正确”，我想这更准确（感谢@Abyx）：

unsigned constexpr const_hash(char const *input, unsigned hash = 5381) {
    return *input ?
        const_hash(input + 1, hash * 33 + static_cast<unsigned>(*input)): 
        hash;
}
于 2013-10-01T18:41:56.507 回答
7

OP 对 C 中的常量折叠感兴趣，但仅针对其 C++ 兄弟：在 C++14 中，您可以简单地将constexpr两个函数放在前面，并修改循环以补偿strlen()不存在constexpr

#include<iostream>

static inline constexpr unsigned int DJBHash(const char *str)
{
   unsigned int hash = 5381;

   for(auto i = 0; i < 512; ++i) {
      if (*str == '\0') return hash;
      hash = ((hash << 5) + hash) + static_cast<unsigned int>(*str);   
   }

   return hash;
}

constexpr unsigned int f(void)
{   
    return DJBHash("01234567890123456");
}

int main()
{
    constexpr auto h = f(); 
    std::cout << std::hex << h << "\n"; // 88a7b505
}

使用Clang 3.4 SVN 和-std=c++1y.

注意：当前的 Clang 实现不能使用while(*str != '\0'). 相反，内部带有返回条件的 512 的有限循环可以完成这项工作。

于 2013-10-01T20:17:42.250 回答
3

也许 C++ TMP 或许能够做到。不过我不确定。

如果您不介意使用可变字符文字列表而不是字符串文字，则可以：

#include <type_traits>
#include <iostream>

template<unsigned acc, char... values>
struct DJBhash_helper
     : std::integral_constant<unsigned, acc> {};

template<unsigned acc, char head, char... tail>
struct DJBhash_helper<acc, head, tail...>
     : DJBhash_helper<(acc << 5) + acc + head, tail...> {};

template<char... str>
struct DJBhash
     : DJBhash_helper<5381, str...> {};

int main()
{
    std::cout << DJBhash<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                         '0', '1', '2', '3', '4', '5', '6', '7'>::value << '\n';
}

ideone现场演示

于 2013-10-01T18:32:42.790 回答
1

不是答案，只是另一个数据点。

下面的实现更糟糕。GCC 4.7.3 正确地应用 TCO 来将此实现变成一个循环，但它只在编译时评估为“0”！

static inline unsigned int DJBHash2(const char *str, unsigned int hash) {
   return *str ? DJBHash2(str + 1, 33 * hash + *str) : hash; }

从好的方面来说，递归版本短了 7 个字节。

其他人提到了 clang，所以这里是 clang 3.1 -O3 的结果。它为两个版本的 DJBHash 生成不同的代码，但它们的字节数相同。有趣的是，它将原始版本的移位和加法转换为乘法。它将两个版本都优化为最多 100 个字符的字符串的常量。最后，clang 代码比最短的 GCC 代码短 5 个字节。

于 2013-10-01T18:25:38.000 回答