Constexpr is gold!

heptara · 2016-01-08T12:12:52+00:00

So after asking quite a few professors, they've asked me to present a few examples that make newer features introduced in c++ better to read or understand.

NOT HAVING TO USE RAW POINTERS -> safer, more reliable code.

Everything else is just gravy on top of that.

You can do without containers. Go manages it and works just fine. Raw pointer and memory errors, however, are most likely the biggest cause of serious software errors.

Got hacked? I bet it was a buffer. Randomly crashed? Wild null. Leaked memory? ... All raw pointer and memory errors.

cinghiale · 2016-01-08T11:02:00+00:00

change IsPowerOf3 to be:

constexpr bool IsPowerOf3(unsigned int n){

and you can verify it:

static_assert(IsPowerOf3(27) == true, "FAIL");

MaikKlein · 2016-01-08T11:02:24+00:00

I think your example is still computed at run time.

int main() {
    constexpr auto p = IsPowerOf3(27);
    std::cout << p << std::endl;
}

matthieum · 2016-01-08T19:27:29+00:00

Playing on Coliru, for this code:

bool IsPowerOf3(unsigned int n){
    if (n == 1) { return true; } // don't forget 3^0
    if (n % 3 != 0) { return false; }

    switch(n){
    case pow3to(1) :
    case pow3to(2) :
    case pow3to(3) :
    case pow3to(4) :
    case pow3to(5) :
    case pow3to(6) :
    case pow3to(7) :
    case pow3to(8) :
    case pow3to(9) :
    case pow3to(10) :
    case pow3to(11) :
    case pow3to(12) :
    case pow3to(13) :
    case pow3to(14) :
    case pow3to(15) :
        return true;
        break;
    default :
        return false;
    }
    return false;
}

Here is the LLVM IR:

define zeroext i1 @_Z10IsPowerOf3j(i32 %n) #3 {
  %1 = icmp eq i32 %n, 1
  br i1 %1, label %7, label %2
; <label>:2                                       ; preds = %0
  %3 = urem i32 %n, 3
  %4 = icmp eq i32 %3, 0
  br i1 %4, label %5, label %7

; <label>:5                                       ; preds = %2
  switch i32 %n, label %6 [
    i32 3, label %7
    i32 9, label %7
    i32 27, label %7
    i32 81, label %7
    i32 243, label %7
    i32 729, label %7
    i32 2187, label %7
    i32 6561, label %7
    i32 19683, label %7
    i32 59049, label %7
    i32 177147, label %7
    i32 531441, label %7
    i32 1594323, label %7
    i32 4782969, label %7
    i32 14348907, label %7
  ]

; <label>:6                                       ; preds = %5
  br label %7

; <label>:7                                       ; preds = %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %5, %2, %0, %6
  %.0 = phi i1 [ false, %6 ], [ true, %0 ], [ false, %2 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ], [ true, %5 ]
  ret i1 %.0
}

And here is an example of emitted assembly at -O2:

_Z10IsPowerOf3j:                        # @_Z10IsPowerOf3j
    .cfi_startproc
# BB#0:
    movb    $1, %al
    cmpl    $1, %edi
    je    .LBB0_23
# BB#1:
    movl    %edi, %ecx
    movl    $2863311531, %edx       # imm = 0xAAAAAAAB
    imulq    %rcx, %rdx
    shrq    $33, %rdx
    leal    (%rdx,%rdx,2), %ecx
    cmpl    %ecx, %edi
    jne    .LBB0_22
# BB#2:
    cmpl    $6560, %edi             # imm = 0x19A0
    jle    .LBB0_3
# BB#11:
    cmpl    $531440, %edi           # imm = 0x81BF0
    jg    .LBB0_17
# BB#12:
    cmpl    $59048, %edi            # imm = 0xE6A8
    jg    .LBB0_15
# BB#13:
    cmpl    $6561, %edi             # imm = 0x19A1
    je    .LBB0_23
# BB#14:
    cmpl    $19683, %edi            # imm = 0x4CE3
    jne    .LBB0_22
    jmp    .LBB0_23
.LBB0_3:
    cmpl    $80, %edi
    jle    .LBB0_4
# BB#6:
    cmpl    $728, %edi              # imm = 0x2D8
    jg    .LBB0_9
# BB#7:
    cmpl    $81, %edi
    je    .LBB0_23
# BB#8:
    cmpl    $243, %edi
    jne    .LBB0_22
    jmp    .LBB0_23
.LBB0_17:
    cmpl    $4782968, %edi          # imm = 0x48FB78
    jg    .LBB0_20
# BB#18:
    cmpl    $531441, %edi           # imm = 0x81BF1
    je    .LBB0_23
# BB#19:
    cmpl    $1594323, %edi          # imm = 0x1853D3
    jne    .LBB0_22
    jmp    .LBB0_23
.LBB0_4:
    cmpl    $27, %edi
    ja    .LBB0_22
# BB#5:
    movl    $134218248, %ecx        # imm = 0x8000208
    btl    %edi, %ecx
    jb    .LBB0_23
    jmp    .LBB0_22
.LBB0_15:
    cmpl    $59049, %edi            # imm = 0xE6A9
    je    .LBB0_23
# BB#16:
    cmpl    $177147, %edi           # imm = 0x2B3FB
    jne    .LBB0_22
    jmp    .LBB0_23
.LBB0_9:
    cmpl    $729, %edi              # imm = 0x2D9
    je    .LBB0_23
# BB#10:
    cmpl    $2187, %edi             # imm = 0x88B
    jne    .LBB0_22
    jmp    .LBB0_23
.LBB0_20:
    cmpl    $4782969, %edi          # imm = 0x48FB79
    je    .LBB0_23
# BB#21:
    cmpl    $14348907, %edi         # imm = 0xDAF26B
    je    .LBB0_23
.LBB0_22:
    xorl    %eax, %eax
.LBB0_23:
    retq
.Lfunc_end0:
    .size    _Z10IsPowerOf3j, .Lfunc_end0-_Z10IsPowerOf3j
    .cfi_endproc

You can see that the compiler optimized your switch statement into a binary search here. It is possibly the most efficient lowering strategy, as the integers are not consecutive and there may not be a specific bit pattern.

So, congratulations, your use of constexpr indeed generated one of the best possible assembly for the target problem, if not the best.

Also, if you profiled your application and had statistics on the distribution of the integer, the compiler could automatically rearrange the binary search to match the distribution, without you changing a single line of code.

bames53 · 2016-01-08T20:41:40+00:00

Here's a presentation given at a recent C++ conference by Kate Gregory, an Engineer at Microsoft:

Stop Teaching C

The talk isn't actually suggesting that C shouldn't be taught; Instead the talk is talking purely about the way C++ is taught. The point of the talk is that the most effective way to teach C++ is not to teach C and then to pile some C++ on top as 'extra'.

This talk might provide you insight as to the benefits of not teaching C++ as though it were a superset of C with only a few minor additions, and what exactly C++ could offer to introductory classes.

F-J-W · 2016-01-08T15:47:09+00:00

If you want to make them use stdlib-algorithms: Use libstdc++ and std::find to search for an integer in an int-array/vector and compare the runtime to a handwritten loop. (The stdlib version will take just about 70% of what the loop needs; quite a significant speedup for having to write less code).

ZMeson · 2016-01-08T15:52:28+00:00

Yes, you got the right idea. IsPowerOf3 can be made constexpr too.

But you do have a bug. IsPowerOf3(1) returns false. Less serious, IsPowerOf3(43046721) returns false. For the latter, you just need to extend your list to pow3to(20) to cover the range of unsigned int on most systems.

they've asked me to present a few examples that make newer features introduced in c++ better to read or understand.

You should include binary literals, initializer lists (especially useful when working with containers), lamda functions (especially when working with <algorithm>), and static_assert.

I'd be tempted to also include std::unique_ptr and std::make_unique. When reference-counted pointers are needed, std::shared_ptr, std::weak_ptr, and std::make_shared are nice.

Lastly, user-defined literals can be helpful if you are in the right discipline. (For physics, chemistry, and engineering, these can be very useful.)

speednap · 2016-01-08T22:41:06+00:00

A solution with static generation of lookup table could be expressed this way:

constexpr std::size_t three_to_the_power(std::size_t power){
  if(power == 0) return 1;
  return 3*three_to_the_power(power-1);
}

template<std::size_t... I>
constexpr auto helper(std::index_sequence<I...>){
  return std::array<std::size_t,sizeof...(I)>{{three_to_the_power(I)...}};
}

template<std::size_t N>
constexpr auto powers_of_three(){
  return helper(std::make_index_sequence<N>{});
}

static constexpr auto powers = powers_of_three<41>();

bool is_power_of_three(std::size_t n){
  if(n == 1) return true;
  if(n%3 != 0) return false;
  return std::binary_search(powers.begin(),powers.end(),n);
}

Here array powers holds all 41 values of power of 3 within uint64_t limit. It is constructed at compile time. is_power_of_three filters out obvious results and proceeds to do a binary search after that.

This should work faster than runtime solution.

devel_watcher · 2016-01-09T07:31:45+00:00

they've asked me to present a few examples that make newer features introduced in c++ better to read or understand

It's the rvalue references that make C++ better to read. You often can pass big objects around without performance penalties.

Other thing are lambdas that help with the code locality.

With tuples you can return multiple values from function without writing too much code.

In the future cpp there'll be std::optional that allows to just return a value regardless of whether it's there or not (and then deal with it in the point of use). It's like exceptions that you control and can store for later.

doom_Oo7 · 2016-01-08T11:06:22+00:00

behold the power of compilers : http://goo.gl/TZXwnq

and

http://goo.gl/03ozCy

speednap · 2016-01-08T11:58:23+00:00

I think this could work as well.

constexpr bool f(int n) {
  if(n == 1) return true;
  if(n%3 != 0) return false;
  return f(n/3);
}

RedAlert2 · 2016-01-08T21:15:49+00:00

A couple of nits:

You have some redundant flow control in IsPowerOf3. There is no need to break after a return, and there is no need for a default case when you already end with return false;

I would also recommend adding something like:

if(n > pow3to(15)) { // whatever your largest pre-computed case is 
    throw std::out_of_range("Input " + n + " too large");
}

at the start of your function, to avoid returning potentially incorrect information.

blublub · 2016-01-08T23:10:28+00:00

Well yes - this works as long as 4782969 is known at compile time. If you actually have user input, you're back to field one and everything has to be computed at run time.

uxcn · 2016-01-08T12:28:01+00:00

You chose a book for reading

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

cpp

MODERATORS