dbbd dbbd - 1 month ago 9
C++ Question

c++ compile-time assertion

I'm using a macro that might be dangerous:

#define REMAINDER(v, size) ((v) & (size -1))


obviously it assumes that size is a power of 2.

I would like to make sure size is indeed a power of 2, but at compile time. (testing at run time is easy, but is NOT what I want).

A sufficient test for me would be that size is always a constant (never a variable).

I would use
BOOST_STATIC_ASSERT
, but I cannot figure out how to use it for what I need.

Answer

First things first: that micro optimization is not needed. Any decent compiler with optimizations enabled will convert a % b into that construct when b is a compile time constant that is actually a power of 2.

Then on the particular assert, you can use the same construct to assert it [*]:

BOOST_STATIC_ASSERT( !(size & (size-1)) );

[*] Note that as Matthieu M points out this only works if size is an unsigned type. And that should be asserted --the lesser requirement that the argument is non-negative cannot be asserted at compile time:

BOOST_STATIC_ASSERT( (X(0)-1) > X(0) ); // where X is the type of the argument

EDIT after last comment:

You are missing the point here. For a static assertion macro to work, the size must be a compile time constant. If it is a compile time constant then just assert when the constant is defined which is also the best place, as it will serve as documentation, and will point to the precise point of code that needs modification:

template <typename N>
class hash_map {
public:
   const std::size_t size = N;
   BOOST_STATIC_ASSERT( !(size & (size-1) ) ); // N must be power of 2 for fast %
   //...
};

At the same time that asserting that the invariant is held at compile time is important for efficiency, obscuring the code is not: Just leave the modulo operation in place, as the compiler will optimize:

std::size_t hash_map::index_of( std::size_t hash ) const {
   return hash % size;
}

Because size is a compile time constant, and it is a power of two (you asserted that before) the optimizer will translate % into the optimized operation, while the code is still readable by humans that need to maintain it.