Re: [boost] non-branching min()

Subject: Re: [boost] non-branching min()
From: DE (satan66613_at_[hidden])
Date: 2009-09-11 11:18:34

on 11.09.2009 at 4:39
 Topher Cooper wrote :
> You might find some sections of Sean Aaron Anderson's "Bit-Twiddling
> Hacks" of interest, though perhaps not of practical use.  Check out:
> Compute the minimum (min) or maximum (max) of two integers without
> branching 
> <http://graphics.stanford.edu/%7Eseander/bithacks.html#IntegerMinOrMax>
> Conditionally set or clear bits without branching
> <http://graphics.stanford.edu/%7Eseander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching>
> Conditionally negate a value without branching 
> <http://graphics.stanford.edu/%7Eseander/bithacks.html#ConditionalNegate>
i'll check it out

> Its worth noting that the better optimization your compiler has the 
> better the loop in your test case will do on your branchless method.  
> But a good optimizing compiler would probably avoid the branch in the 
> first place.
> To use the technique to its fullest you or the optimizer should
> translate your loop into something like (untested):
>       type a[2] = {BIG_VALUE, ANY_VALUE};
>       type* vp[2] = {--&v1[0], --&v2[0]};  // I know, but I'm
> expressing some possibly low level optimization.
>       for (size_t i = 0; i<n; ++i)
>       {
>         a[1] = *vp[*++vp[1]<*++vp[0]];
>         a[0] = a[a[1]<a[0]];
>       }
i thought about it but didn't try although

> A good optimizing compiler should be able to do most or all of this
> from the inlined method, though the "relaxation" of the transfer of
> the move to "c[]" into an indirection as vp is pretty sophisticated.
> Binding the local a and the temporary containing the min of the v's
> to the vector they would otherwise be transfered to is routine.
> Of course, if this were code you really wanted to optimize, rather
> than a test loop, you would improve locality by processing each
> vector separately by making c[] a reference
my intention was just to heavily load min() implementation
alternatively one can compute 'res[i] = min(v1[i], v2[i])' in a loop
the timing would be very similar

on 11.09.2009 at 13:10
 Thorsten Ottosen wrote :
> If you are going to benchmark over several platforms, please include the
> technique described here:
> http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
thanks for the link
by the way msvc abs() does just that thing like in this paper

-- 
Pavel