Re: [boost] non-branching min()

Subject: Re: [boost] non-branching min()
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-09-10 18:01:35

DE wrote:
>     template<typename type> inline
>     type min(type a, type b)
>     {
>       const type c[2] = {a, b};
>       return c[b<a];
>     }

How well this performs compared to the conventional ?: implementation
will depend on how the arguments are distributed.  If the outcome is
skewed, then branch prediction will make the conventional
implementation faster.  If the outcome is 50/50 (and not correlated
with some other branch), then your code may do better.

> here's a test code:
>
>     #include <vector>
>     int main()
>     {
>       typedef int type;
>       const int n = 1000000;
>       std::vector<type> v1(n), v2(n);
>       //filling v1 and v2 somehow
>       type min = BIG_VALUE;
>       for (size_t i = 0; i<n; ++i)
>         a = min(a, min(v1[i], v2[i]));  //searching minima of v1 and v2
>       return 0;
>     }

So the min(v1[i],v2[i]) is 50/50 (assuming that you fill the arrays
with random values), while min(a,...) will be skewed to normally prefer
the second arg after the first few cycles.  Perhaps you can confirm
that your code does better for the former and worse for the latter by
testing e.g.

      a = std::min(a, my::min(v1[i], v2[i]));

Is there some reason why a compiler cannot do your optimisation
automatically when you write ?: expressions?

Regards,  Phil.