I want to implement a function conforming to the following interface and contract:

void move_towards(float& value, float target, float step) 
    // Moves `value` towards `target` by `step`. 
    // `value` will never go beyond `target`, but can match it.
    // If `step == 0.0f`, `value` is unchanged.
    // If `step > 0.0f`, `std::abs(target - value)` decreases.
    // If `step < 0.0f`, the behavior is undefined.

The idea is to use this function to gradually move an existing floating point value towards another, without ever exceeding the target. This is useful -- for example -- to perform linear transitions between values as part of the execution of a game loop.

Here's an example test case:

float value = 5.0f;
move_towards(value,  10.f,  1.f); assert(value ==  6.0f);
move_towards(value,  10.f,  1.f); assert(value ==  7.0f);
move_towards(value, -5.f,   5.f); assert(value ==  2.0f);
move_towards(value, -5.f,   5.f); assert(value == -3.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value, -5.f,   5.f); assert(value == -5.0f);
move_towards(value,  0.f,  15.f); assert(value ==  0.0f);

I tried a few branchless ideas using a combination of std::copysign and std::clamp, but they always failed in some edge cases. In the end, I resorted to using a branchy version:

void move_towards(float& value, float target, float step) 
{
    if (value < target)
    {
        value  = step;
        if (value > target)
        {
            value = target;
        }
    }
    else if (value > target)
    {
        value -= step;
        if (value < target)
        {
            value = target;
        }
    }
}

live on godbolt.org

• Is it possible to implement move_towards in order to produce branchless instructions?
• If not, is it possible to at least minimize the number of branches?
• Regardless, what version provides the best run-time performance?

CodePudding user response：

I think this is the approach that Francois Andrieux was hinting at. Have you tried this? It's just one branch.

void move_towards(float& value, float target, float step) {
    value = target < value 
        ? std::max(value - step, target)
        : std::min(value   step, target);
}

https://godbolt.org/z/jxKP6oT1h

CodePudding user response：

You can do this completely branch-free, if you have a reasonably modern processor target (with branch-free selection from two floating-point values).

The approach would be to formulate the problem as follows:

Compute a "signed step" value that is either step or -step, depending on whether target > value or target < value. Find the median of target, value and value signed step. Finding the median can be done by sorting, but for three elements you can also just combine the elements with an invertible operation and apply the inverted operation on the combination with the maximum and minimum of the three values. For float, invertible operations are a bit of a problem, because addition/subtraction are not associative. However, in your comments you said that you do not care about the case where the target and value have extremely different magnitudes, so addition and subtraction work decently well. A better solution would bitwise convert to an unsigned integer type of the same width, then use xor as the invertible operation, then convert the median bit pattern back to float.

Here's the solution on godbolt, and in the answer:

void move_towards(float& value, float target, float step) {
    auto sstep = (target > value ? step : -step);
    auto nval = value   sstep;
    value = value   target   nval -
        std::min(std::min(value, target), nval) -
        std::max(std::max(value, target), nval);
}