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!

Amphitropous

The only thing I can say to this is to repeat the error message: you are calling a function that is not marked as constexpr. Your Calculate and CalculateValue functions are not constexpr. You cannot call non-constexpr functions when evaluating a constexpr value. – Mornay

You probably want const there. The value of the the function is not known during compile time as you supply an argument during run-time. – Geo

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

Mornay

@Geo With signed int the behaviour is undefined. There's no functionality to change from. – Dockery

@n.m. I see. Appreciate it. – Geo

Quick and painful answer. Thanks. Learned something. – Amphitropous

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 :)

Succubus

Thanks for your detailed answer! Very nice, I wish I could select two answers. I feel like people should read CygnusX1 answer first and then come to yours if they want/need more background information. – Amphitropous

Note on the overflow part. The error is there not because its compile time, but because overflowing << on signed integers is an undefined behavior. constexpr just allowed the compiler to detect the UB at compile time. What you really should do is to use unsigned int instead. Overflowing that has a well-defined behavior and works both at run-time and compile-time without any errors/warnings. – Mornay