Three Optimization Tips for C++

Re:Three Optimization Tips for C++ by pbsd on Thursday May 08, 2014 @11:22AM (#7715752)

There is one oft-forgotten case that neither compilers nor (seemingly) libdivide seem to handle: when we know that an integer is a multiple of some constant, and we just want to get the result of the exact division.

This case allows for a simpler method, exemplified here (it also works for signed integers, but more care is needed with the shifting): http://goo.gl/D5q9IO

EDIT: On second thought, compilers are also not doing their best job on that example. f1 could be simplified to

    mov  rax, 4865095698
    add  edi, 1
    imul rdi
    shrd rax, rdx, 39
    ret

which has a shorter critical path.

[ Parent | on HN ]

Re:Three Optimization Tips for C++ by kazagistar on Thursday May 08, 2014 @12:48PM (#7716239)

> when we know that an integer is a multiple of some constant

How is a compiler supposed to track that information? That requires some serious dependent typing.

[ Parent | on HN ]

Re:Three Optimization Tips for C++ by pbsd on Thursday May 08, 2014 @12:56PM (#7716285)

It's not (by itself, at least). But you can give it hints, as in my example above (with __builtin_unreachable; other compilers have similar facilities, like __assume in MSVC). The compiler should, in theory, be able to deduce that x % 113 is always 0, and therefore must be a multiple of 113.

[ Parent | on HN ]