3 ms·

These are cool, but how much is automatically done for you by the compiler? For example, if I changed all of my calls to min(x,y) with r = y + ((x - y) & ((x -

by rgarcia 15y ago

These are cool, but how much is automatically done for you by the compiler? For example, if I changed all of my calls to min(x,y) with r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y) my code would quickly become unreadable. I could define a macro, but those are supposedly evil[1]. [1] http://www.parashift.com/c++-faq-lite/inline-functions.html#faq-9.5 http://www.parashift.com/c++-faq-lite/inline-functions.html#...

jandrewrogers 15y ago
Many of the very simple algorithms are done by a good compiler, more complex ones generally are not. It is pretty easy to turn these into clean, generalized functions using templates in C++ and std::numeric_limits. I have a substantial library of generalized algorithms constructed from bit-twiddling primitives that does not use any macros. The value of these examples is that if you understand the underlying mechanisms behind them you can use those building blocks to construct even more complex (and extremely fast) algorithms than demonstrated at the link. Complex, high-level algorithms can be implemented using these bit hacks once you wrap your head around what they are actually doing. The caveat is that the code will be opaque for programmers that are not fluent in bit-hacking. For most applications you won't see much performance benefit because these are micro-optimizations. If you have a small kernel that is being executed a hundred thousand or million times per second then algorithms constructed this way can be a substantial performance optimization (easily integer factor speedup, I frequently see 10x for components). Algorithms built on bit-twiddling primitives tend to have two properties that make them particularly efficient on modern processors. First, they make very good use of superscalar CPUs, putting the parallel ALUs to work. Second, they often take branching algorithms (e.g. small tight loops, ?: operator, if statements) and convert them into branchless algorithms. If you are doing performance and latency sensitive code, this method of building algorithms is worth learning. For everyone else, it is a neat bit of computer science arcana that really delves into the nature of integers.
oakenshield 15y ago
The FAQ mainly complains about multi-statement macros that use conditionals or loops (among some sillier criticism). For a one-statement expression such as the above, I would use a macro because it's so much easier to define than a (potentially templatized) inline function. Also, to answer your "how much is done for you by the compiler" question, gcc has a few builtins: __builtin_clz (count leading 0 bits), __builtin_popcount (number of 1 bits), etc. but it's not nearly enough for most common bit twiddling use-cases. http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
rcfox 15y ago
When in doubt: compare the resulting assembly for the two versions. gcc -S foo.c
anonymoushn 15y ago
I've had a good result using this macro instead of calling min. I wouldn't do it in something serious, but the code was <400LOC to crunch numbers and calculate a certain integer sequence.
Jach 15y ago
Just use the damn macro, evil or not. I'm pretty sure they're not evil. [1] [1] http://yosefk.com/c++fqa/inline.html#fqa-9.5 http://yosefk.com/c++fqa/inline.html#fqa-9.5
DarkShikari 15y ago
min() is a special case: on most modern architectures (x86, ARM, etc), the naive code will compile optimally. Example on x86: cmp eax, ebx cmovg eax, ebx The compiler will likely not understand the insane bit-hack method, which is much more complicated, and thus not parse it into a simple cmov sequence.

by rgarcia 15y ago

jandrewrogers 15y ago

Many of the very simple algorithms are done by a good compiler, more complex ones generally are not. It is pretty easy to turn these into clean, generalized functions using templates in C++ and std::numeric_limits. I have a substantial library of generalized algorithms constructed from bit-twiddling primitives that does not use any macros. The value of these examples is that if you understand the underlying mechanisms behind them you can use those building blocks to construct even more complex (and extremely fast) algorithms than demonstrated at the link. Complex, high-level algorithms can be implemented using these bit hacks once you wrap your head around what they are actually doing. The caveat is that the code will be opaque for programmers that are not fluent in bit-hacking. For most applications you won't see much performance benefit because these are micro-optimizations. If you have a small kernel that is being executed a hundred thousand or million times per second then algorithms constructed this way can be a substantial performance optimization (easily integer factor speedup, I frequently see 10x for components). Algorithms built on bit-twiddling primitives tend to have two properties that make them particularly efficient on modern processors. First, they make very good use of superscalar CPUs, putting the parallel ALUs to work. Second, they often take branching algorithms (e.g. small tight loops, ?: operator, if statements) and convert them into branchless algorithms. If you are doing performance and latency sensitive code, this method of building algorithms is worth learning. For everyone else, it is a neat bit of computer science arcana that really delves into the nature of integers.

oakenshield 15y ago

The FAQ mainly complains about multi-statement macros that use conditionals or loops (among some sillier criticism). For a one-statement expression such as the above, I would use a macro because it's so much easier to define than a (potentially templatized) inline function. Also, to answer your "how much is done for you by the compiler" question, gcc has a few builtins: __builtin_clz (count leading 0 bits), __builtin_popcount (number of 1 bits), etc. but it's not nearly enough for most common bit twiddling use-cases. http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

rcfox 15y ago

When in doubt: compare the resulting assembly for the two versions. gcc -S foo.c

anonymoushn 15y ago

I've had a good result using this macro instead of calling min. I wouldn't do it in something serious, but the code was <400LOC to crunch numbers and calculate a certain integer sequence.

Jach 15y ago

Just use the damn macro, evil or not. I'm pretty sure they're not evil. [1] [1] http://yosefk.com/c++fqa/inline.html#fqa-9.5 http://yosefk.com/c++fqa/inline.html#fqa-9.5

DarkShikari 15y ago

min() is a special case: on most modern architectures (x86, ARM, etc), the naive code will compile optimally. Example on x86: cmp eax, ebx cmovg eax, ebx The compiler will likely not understand the insane bit-hack method, which is much more complicated, and thus not parse it into a simple cmov sequence.