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.

StayOnTarget
  • 11,743
  • 10
  • 52
  • 81
Amir Gonnen
  • 3,525
  • 4
  • 32
  • 61
  • 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 01 '13 at 17:08
  • @Mysticial I went over the [optimization command line options](http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-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. – Amir Gonnen Oct 01 '13 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 01 '13 at 17:57
  • in C++ you could calculate it in compile-time with `constexpr` – Abyx Oct 01 '13 at 18:15
  • 5
    btw, optimizer can convert `33 * hash` to shift and add by itself. – Abyx Oct 01 '13 at 18:23
  • fwiw, clang (svn from a couple of days ago) does the constant folding fine with a string of length 70. – rici Oct 01 '13 at 19:43
  • AHAHAHAHA, I totally derailed this question by baiting everyone to post answers in C++ instead of C. :D – Mysticial Oct 01 '13 at 20:54
  • @Mysticial, very interesting how a language agnostic question about the capacity of a particular compiler (gcc) became a forum to advocate C++ features. Guys this was a question about compiler optimization, not on how to force optimization in this or that language. I can probably come up with a preprocessor written in perl that would to the trick. But I wouldn't do that, this wasn't the question. – Jens Gustedt Oct 01 '13 at 21:29
  • @JensGustedt To be fair, it wasn't intentional. All I said was that it might be possible with C++ TMP. Then I asked about it in chat. The result was that everyone poured in to answer with C++. The question also had no language to tag to start. I added the C tag because it looked like C and there was no C++ specific code. – Mysticial Oct 01 '13 at 21:31
  • @Mysticial, sure I wouldn't blame *you*, but I just found it interesting how easily such a question is monopolized by people from the C++ camp. As you say, the question is definitively C, no C++ in sight. – Jens Gustedt Oct 01 '13 at 21:36
  • @AmirGonnen You might want to clarify what language you're allowed to use (C or C++). Since there does appear to be a bit of a dispute over the tags on your question. I initially tagged it C since it had nothing C++ in it, but most of the answers you've been getting are C++. – Mysticial Oct 02 '13 at 02:58
  • @Mysticial I've added a clarification. Templates/constexpr answers are interesting but unfortunately they won't help me in my case. I was surprised how people allowed themselves freely remove and add tags to my question (for example remove gcc tag when "gcc" is part of the title...) – Amir Gonnen Oct 02 '13 at 05:26

4 Answers4

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;
}
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • You can get the correct result employing a tail-recursive helper function, see my answer. – fredoverflow Oct 01 '13 at 18:43
  • @FredOverflow: Yeah, you can, but I'm not sure it makes enough difference to justify the extra work/code. – Jerry Coffin Oct 01 '13 at 18:45
  • why there is the first `static_cast`? – Abyx Oct 01 '13 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](http://coliru.stacked-crooked.com/a/2cd132818fa29683) – Abyx Oct 01 '13 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. – TemplateRex Oct 01 '13 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.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
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

fredoverflow
  • 256,549
  • 94
  • 388
  • 662
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.

Adam Burry
  • 1,904
  • 13
  • 20