9

It seems that gcc has some limitation on complex constant folding. Here is an example:

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");
}

When running with -O3 optimization level (gcc 4.8), it unfolds the loop in DJBHash nicely and calculates the hash value for that string during compile time.

However, when making the string one character longer return DJBHash("012345678901234567"); it does not fold it any more and generates a loop with a conditional jump instruction.

I would like to fold a literal string in any length into its hash value as a compile time constant.
Could this be done?

Clarification

My question was about the constant-folding optimizations on gcc (see the title - please do not remove gcc and compiler tags)
Many answers here try to solve the problem with either Templates or constexpr. It's good to know about these options and thanks for posting them for the benefit of all. However, they do not directly answer my question.

Practically, I'm working on a gcc port so I could change and build gcc source code, if needed. But I'm limited to C and I would like to solve this problem in this scope.

12
  • 1
    There's probably an option within GCC that lets you set some threshold where it will decide to unfold something. Constant unfolding is a potentially endless process. Furthermore, deciding whether or not unfolding will ever terminate is probably the halting problem.
    – Mysticial
    Oct 1, 2013 at 17:08
  • @Mysticial I went over the optimization command line options but I could not find anything related to constant folding. I tried changing the loop unrolling parameter max-unroll-times but this did not seem to have any effect. Oct 1, 2013 at 17:52
  • Then there probably isn't much you can do. There's only so much you can rely on a compiler to do. And this is definitely pushing the boundaries. At some point you need to be explicit. Perhaps C++ TMP might be able to do it. I'm not sure though.
    – Mysticial
    Oct 1, 2013 at 17:57
  • in C++ you could calculate it in compile-time with constexpr
    – Abyx
    Oct 1, 2013 at 18:15
  • 5
    btw, optimizer can convert 33 * hash to shift and add by itself.
    – Abyx
    Oct 1, 2013 at 18:23

4 Answers 4

9

Here's a version using constexpr. It's slightly different from the others in one respect -- being recursive, it was easiest to hash the string back to front, so to speak. For example, the value it gives for "abc" will be what you'd normally expect from "cba" instead. I don't think this should make any real difference in use, as long as you use one or the other consistently (but given the vagaries of hashing, I could be wrong about that).

It does evaluate at compile time though -- for example, we can use the results as labels in a switch statement:

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

Obviously, there could be collisions, so you generally wouldn't want to use it as case statement labels -- I mostly did that to force a situation in which it would fail to compile if the result wasn't a compile-time constant.

Edit: if you care about the hash algorithm being "correct", I guess this is more accurate (with thanks to @Abyx):

unsigned constexpr const_hash(char const *input, unsigned hash = 5381) {
    return *input ?
        const_hash(input + 1, hash * 33 + static_cast<unsigned>(*input)): 
        hash;
}
5
  • You can get the correct result employing a tail-recursive helper function, see my answer. Oct 1, 2013 at 18:43
  • @FredOverflow: Yeah, you can, but I'm not sure it makes enough difference to justify the extra work/code. Oct 1, 2013 at 18:45
  • why there is the first static_cast?
    – Abyx
    Oct 1, 2013 at 18:46
  • the tail-recursive version doesn't need a helper function. it looks exactly like @AdamBurry's DJBHash2, but the hash should have default value = 5381. And there is a reason why this version is better. When you use const_hash in runtime, it will run faster and won't eat stack. link
    – Abyx
    Oct 1, 2013 at 19:07
  • 1
    Upvoted. Note that this code will have a short shelf life: as soon as C++14 constexpr (already available in Clang 3.4 SVN) becomes more widely available, you can use my answer. Oct 1, 2013 at 20:20
7

The OP is interested in constant-folding in C, but just for its C++ sibling: in C++14, you can simply put constexpr in front of both functions, and modify the loop to to compensate for strlen() not being 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
}

Live Example using Clang 3.4 SVN with -std=c++1y.

NOTE: the current Clang implementation does not properly run with a while(*str != '\0'). Instead, a finite loop of 512 with a return condition inside does the job.

3
  • In case of constexpr, how does Clang compute the final value ? By directly interpreting the AST or jit compiling the function ?
    – elmattic
    Aug 10, 2015 at 12:34
  • @Stringer the former, the language guarsntees that h is evaluated before launching the program Aug 10, 2015 at 15:30
  • Excuse me, but inline is redundant on constexpr, because it implies that implicitly.
    – Melardev
    May 11, 2019 at 10:20
3

Perhaps C++ TMP might be able to do it. I'm not sure though.

It is possible if you don't mind using variadic character literal lists instead of string literals:

#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 live demo

1
  • you can use boost::mpl::string.
    – Abyx
    Oct 1, 2013 at 18:36
1

Not an answer, just another data point.

The following implementation is even worse. GCC 4.7.3 properly applies TCO to turn this implementation into a loop, but it only evaluates up to "0" at compile time!

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

On the plus side, the recursive version is 7 bytes shorter.

Someone else mentioned clang, so here are results for clang 3.1 -O3. It generates different code for the two versions of DJBHash, but they are the same number of bytes. Interestingly, it converts the shift and add from the original version into a multiply. It optimizes both versions down to constants for strings up to 100 characters. And finally, the clang code is 5 bytes shorter than the shortest GCC code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.