Compile time hash with constexpr

Question

I have found this example/class in a book for creating SDBM hashes at compile time. Unfortunately it does not compile (neither with c++11 nor c++14). I am getting error: call to non-constexpr function. I've tried around a little bit, but I can't seem to make this work. So here is my question:

1. Why is it not working and how could it be fixed? (I am sorry, I know it's a generic question, but at least for a very specific case)

Full (not working) example for you to test:

#include <iostream>

template <int stringLength>
struct SDBMCalculator
{
    static inline int Calculate(const char* const stringToHash, int& value)
    {
            int character = SDBMCalculator<stringLength - 1>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            std::cout << static_cast<char>(character) << std::endl << value << std::endl << std::endl;
            return stringToHash[stringLength - 1];
    }

    static inline int CalculateValue(const char* const stringToHash)
    {
            int value = 0;
            int character = SDBMCalculator<stringLength>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            std::cout << static_cast<char>(character) << std::endl << value << std::endl << std::endl;
            return value;
    }
};

template <>
struct SDBMCalculator<1>
{
    static inline int Calculate(const char* const stringToHash, int& value)
    {
            return stringToHash[0];
    }
};


int main()
{
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");
  std::cout << eventID << std::endl;
}

Thanks a lot in advance for your time and effort!

Answer 1

Read the error message: you are calling a non-constexpr function when evaluating a constexpr value. Have you tried fixing that?

When you make all relevant functions as constexpr you will get a few additional errors needing your attention. Some remarks:

• Make sure you compile with -std=c++14. C++11 is not good enough for this.
• remove all operations on std::cout from within SDBMCalculator functions - those are not permitted at compile-time

• change int into unsigned int in all relevant computations. When left shift overflows on int type you get an undefined behavior. Left shift on unsigned type is computed modulo its maximum value+1 instead.

  error: shift expression ‘(4723229 << 16)’ overflows
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello")
  

With all the above fixes your code will work. I get the result:

2873473298

Answer 2

So as the http://en.cppreference.com says:

A constexpr variable must satisfy the following requirements:

the full-expression of its initialization, including all implicit conversions, constructors calls, etc, must be a constant expression

Inside the assign expression:

constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");

We use CalculateValue that is not marked with constexpr.

Then we have two choices:

• Just change constexpr to const

• Or try to make CalculateValue a constexpr function

As the first one is really boring let's focus on te second one to better understand how constant expressions work!

So we start with marking CalculateValue as constexpr

static constexpr inline int CalculateValue(const char* const stringToHash)

Now CalculateValue must call only constexpr functions. So we must make Calculate a constexpr too.

static constexpr inline int Calculate(const char* const stringToHash, int& value)

And that triggers a lot of compilers errors.

Fortunatelly we can notice that streams are not a good thing to be put into constexprs because operations on streams are not marked with constexpr. ( operator<< is just like a normal function and it's not constexpr ).

So let's remove the std::cout from there!

Well it's almost there. We must also make Calculate in the SDBMCalculator<1> a constexpr too because it may be called by both calculation functions.

The final code looks like this:

#include <iostream>

template <int stringLength>
struct SDBMCalculator
{
    static constexpr inline int Calculate(const char* const stringToHash, int& value)
    {
            int character = SDBMCalculator<stringLength - 1>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            return stringToHash[stringLength - 1];
    }

    static constexpr inline int CalculateValue(const char* const stringToHash)
    {
            int value = 0;
            int character = SDBMCalculator<stringLength>::Calculate(stringToHash, value);
            value = character + (value << 6) + (value << 16) - value;
            return value;
    }
};

template <>
struct SDBMCalculator<1>
{
    static constexpr inline int Calculate(const char* const stringToHash, int& value)
    {
            return stringToHash[0];
    }
};


int main()
{
  constexpr int eventID = SDBMCalculator<5>::CalculateValue("Hello");
  std::cout << eventID << std::endl;
}

And of course IT DOES NOT COMPILE! We get:

error: shift expression '(4723229 << 16)' overflows [-fpermissive]

value = character + (value << 6) + (value << 16) - value;

It's because the compiler does not want to have overflows in constant expressions.

We can unsafely ignore this error adding -fpermissive flag when compiling the code.

g++ example.cpp -o example.exe -fpermissive

Now it COMPILES and works really fine! The constant expression modifier makes the compiler calculate the hash when compilling.

It's fine because we don't waste runtime resources for that but if you use overwhelming amount of such templates and constexprs and make compiler calculate all that it will be deadly slow compilation!

I hope you understand constexpr behaviour better now :)