[haiku-gsoc] Re: Bitwise manipulations
- From: Adrien Destugues <pulkomandy@xxxxxxxxxxxxx>
- To: haiku-gsoc@xxxxxxxxxxxxx
- Date: Sat, 24 Jun 2017 09:05:07 +0200
On Sat, Jun 24, 2017 at 03:22:00AM +0530, Ayush Agrawal wrote:
Going through the source code of TCP, I came across instances where using
small bit hacks could have helped avoid branching.
Example: use of min_c at lines 2031, 2038 etc in TCPEndpoint.cpp.
min_c is defined as: #define min_c(a,b) ((a)>(b)?(b):(a)) in SupportDefs.h
and also in fssh_defs.h.
An alternate to minimum of two number is: min = b ^ ((a^b) & -(a<b)) .
The advantage of using the latter is that it avoids any branching howsoever
which in turn is good for instruction level pipelining at the hardware
level since the risk of flushing the pipeline due to speculative branching
is eliminated.
Have you actually benchmarked this?
While these bit hacks look like a good idea at first glance, quite often
it turns out the compiler is already able to remove branching from the
plain readable version.
In general, such micro-optimizations should be done only if:
- A benchmark shows they are actually useful
- The involved code is "hot", ie. executed a lot and in performance
critical paths
- Higher level optimizations have already been tried (using better
algorithms, etc)
Only in these cases, we can make the tradeoff and lose a bit of
readability for a bit of performance. Otherwise, readable code is more
important.
In particular, from GCC documentation I see this:
-fif-conversion
Attempt to transform conditional jumps into branch-less equivalents.
This include use of conditional moves, min, max, set flags and abs
instructions, and some tricks doable by standard arithmetics. The use of
conditional execution on chips where it is available is controlled by
if-conversion2.
Enabled at levels -O, -O2, -O3, -Os.
Most of our code is already compiled at -O2, so I expect your change
will have no impact, or at worst, a negative impact because gcc will not
"recognize" the unusual way to write a min() and will not be able to
optimize as well.
This option is not available in gcc2, but if you are interested in
performance, you should be using gcc5 versions of Haiku anyway.
and, from the bit twiddling hacks page:
"On some rare machines where branching is very expensive and no
condition move instructions exist, the above expression might be faster
than the obvious approach, r = (x < y) ? x : y, even though it involves
two more instructions. (Typically, the obvious approach is best,
though.)"
TL,DR: you can let the compiler handle this. It knows better.
--
Adrien.
Other related posts:
