5
\$\begingroup\$

I've implemented a div_by_power_of_2() function, which lets me force the compiler to use left-shifting rather than proper division, in cases when the developer know the divisor will be a power of 2, but does not know which power of 2; and the compiler cannot prove to itself that this is the case.

template <typename P> constexpr P log2_of_power_of_2(P non_negative_power_of_2) noexcept
{
    static_assert(std::is_integral<P>::value, "Only integral types are supported");
    static_assert(sizeof(P) <= sizeof(unsigned long long), "Unexpectedly large type");
    using cast_target_type = typename
        std::conditional<sizeof(P) <= sizeof(unsigned),
            unsigned,
            typename std::conditional<sizeof(P) <= sizeof(unsigned long),
                unsigned long, 
                unsigned long long
            >::type
        >::type;
    return log2_of_power_of_2<cast_target_type>(
        static_cast<cast_target_type>(non_negative_power_of_2));
}
template <> 
constexpr unsigned 
log2_of_power_of_2<unsigned>(unsigned non_negative_power_of_2) noexcept 
{ return __builtin_ctz  (non_negative_power_of_2); }

template <> 
constexpr unsigned long 
log2_of_power_of_2<unsigned long>(unsigned long non_negative_power_of_2)  noexcept
{ return __builtin_ctzl (non_negative_power_of_2); }

template <>
constexpr unsigned long long 
log2_of_power_of_2<unsigned long long>(unsigned long long non_negative_power_of_2) noexcept 
{ return __builtin_ctzll(non_negative_power_of_2); }

template <typename I, typename P>
constexpr I div_by_power_of_2(I dividend, P power_of_2_divisor) noexcept
{ return dividend >> log2_of_power_of_2(power_of_2_divisor); }

Questions:

  • Is my approach to covering the possible types of power_of_2 appropriate? Can it perhaps be made less verbose but with the same effect?
  • Am I reinventing the wheel with this code?
  • Currently, this depends on certain compiler intrinsics available in GCC and clang but not necessarily elsewhere. I could generalize it a bit using this method to also support MSVC. Is there a better approach to generalizing the code?
  • Should I change the return type of log2_of_power_of_2 functions to be uniform rather than I? e.g. an unsigned?
  • Any other comments/suggestions are welcome.

Notes:

  • This is intended to be C++11; obviously with C++17 I could simplify it further
  • The constexpr qualifier is not very meaningful, since in a constexpr context we could just do plain division, but I've tacked it on nonetheless. To make the use of these utility function(s) more uniform.
\$\endgroup\$
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 3 → 2 \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 29 at 16:31
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ: But I didn't change my code; the edit was just a clarification. \$\endgroup\$ – einpoklum May 29 at 16:34
  • \$\begingroup\$ I think this is a waste of time. The compiler is already smart enough to use the fastest method for division (if this is a shift left it will already do it). If your compiler is not using this optimization it obviously does not think it is worth it so why do you think you know better than the compiler. As the maintainer of the code I would not trust another human over the compiler and probably remove the hack above to let the compiler do its job. \$\endgroup\$ – Martin York May 29 at 23:47
  • 1
    \$\begingroup\$ The edit in question was the addition of #include <type_traits> after it was mentioned in the answer. Please don't make such modifications after an answer has been posted. \$\endgroup\$ – Jamal May 30 at 0:56
  • \$\begingroup\$ This question discussed on meta: codereview.meta.stackexchange.com/questions/9185/… \$\endgroup\$ – rolfl May 30 at 16:27
6
\$\begingroup\$

The code is missing #include <type_traits>; it would have been nice to have had the test cases too.

It would be nice to be able to check the argument restriction using assert. Unfortunately, this doesn't fit nicely with C++11 constexpr functions, which may contain only a single return statement. If you might also compile against a newer standard, we could perhaps conditionally test it:

#include <cassert>

template <typename I, typename P>
constexpr I div_by_power_of_2(I dividend, P power_of_2_divisor) noexcept
{
#if __cplusplus >= 201402L
    assert((power_of_2_divisor & power_of_2_divisor - 1) == 0);
#endif
    return dividend >> log2_of_power_of_2(power_of_2_divisor);
}

I don't see why we have a template and specializations, rather than simple overloading of log2_of_power_of_2, particularly as we don't widen signed types to preserve sign.

Contrary to your comment, the constexpr is valuable, as it allows this function to be called from within another constexpr function, whether or not that one is being called with constant arguments.


Modified code

static constexpr unsigned
log2_of_power_of_2(unsigned non_negative_power_of_2) noexcept
{ return __builtin_ctz  (non_negative_power_of_2); }

static constexpr unsigned long
log2_of_power_of_2(unsigned long non_negative_power_of_2)  noexcept
{ return __builtin_ctzl (non_negative_power_of_2); }

static constexpr unsigned long long
log2_of_power_of_2(unsigned long long non_negative_power_of_2) noexcept
{ return __builtin_ctzll(non_negative_power_of_2); }

static constexpr int
log2_of_power_of_2(int non_negative_power_of_2) noexcept
{ return __builtin_ctz  (non_negative_power_of_2); }

static constexpr long
log2_of_power_of_2(long non_negative_power_of_2)  noexcept
{ return __builtin_ctzl (non_negative_power_of_2); }

static constexpr long long
log2_of_power_of_2(long long non_negative_power_of_2) noexcept
{ return __builtin_ctzll(non_negative_power_of_2); }


#include <cassert>

template <typename I, typename P>
constexpr I div_by_power_of_2(I dividend, P power_of_2_divisor) noexcept
{
#if __cplusplus >= 201402L
    assert((power_of_2_divisor & power_of_2_divisor - 1) == 0);
#endif
    return dividend >> log2_of_power_of_2(power_of_2_divisor);
}
#include <iostream>
int main()
{
    std::cout << div_by_power_of_2(15ul, 4) << '\n';
}
\$\endgroup\$
  • \$\begingroup\$ Also, would I, in this case, not also need to have implementations for char, unsigned char, short etc? \$\endgroup\$ – einpoklum May 29 at 16:29
  • \$\begingroup\$ Why would you want different implementations for narrower types, unless there are different intrinsics to use in them? Remember that overloads work with best match (unlike templates, which take exact match). \$\endgroup\$ – Toby Speight May 29 at 16:39
  • \$\begingroup\$ @TobySpeight: To avoid the case of multiple overloads with the same priority \$\endgroup\$ – einpoklum May 29 at 16:43
  • \$\begingroup\$ I'm still not sure what you mean - changing 15ul to (short)15 in my test program has no ambiguity (it promotes to int). \$\endgroup\$ – Toby Speight May 29 at 17:01
  • \$\begingroup\$ @TobySpeight: Hmm. Maybe I'm wrong about that. Anyway, +1 for your suggestions. \$\endgroup\$ – einpoklum May 29 at 21:32
5
\$\begingroup\$

Moving to an answer:

My knowledge on compilers is 20 years old. So I could be wrong. But a compiler can do a lot of the maths on const values (and now contexpr) at compile time (which is when all template code is also evaluated).

I have seen compilers check to see if this was a division by 2 (or multiple of 2) and do shifts (if the shifts are actually faster on that platform (the compiler I worked on explicitly did this test as part of validation and did not plant the the shifts on the SOC chip we had)).

I believe I have read (so this is more speculative) that the chips were baking in this optimization into the hardware circuitry. OK. The old chips did not do it like the Z80 and x86 but chip optimizations have come along way (and it has been a long time since I kept up with the trades but this is a simple hardware optimization).

BUT that is not my main issue. My issue is with programmer micro optimization. You are unlikely to beat the compiler, but you can. The Problem is that your optimization just locked you into a technique that the compiler probably can't optimize around and thus you are pesimizing your code in the long run.

Over time compiler will improve (or your code will be moved to another architecture) because you have locked in one technique you are probably preventing the compiler from taking advantage of some new technique or hardware appropriate optimization.

Compilers are extremly good at micro (peephole) optimization. Trying to beat the compiler is counterproductive in the long run. Compilers are very bad at algorithmic optimizations (humans are very good at this. So concentrate your optimizations at the algorithm level).

\$\endgroup\$
  • \$\begingroup\$ Given that Z80 (and, I think, 6502) don't have hardware divide, it's unsurprising that they don't have the optimisation. ;-) \$\endgroup\$ – Toby Speight May 30 at 17:24
  • \$\begingroup\$ I'm only interested in non-const values. Now, it's true that a compiler could check whether a division is by a power-of-2 and do shifts in that case, but that check has its cost; and I think it's unlikely compilers would want to do this. Now, you're right that programmer micro-optimization is a problem... but sometimes you write code specifically intended specifically for the "tight-loop", where micro-optimization is reasonable. \$\endgroup\$ – einpoklum May 30 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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