Minimizing stack allocation by way of temporaries in arithmetic operator overloads : Safe return method

user_14720556 0
Viewed 59

I am working on an implementation of EDDSA digital signatures and as the values used in the calculations can be up to 521 bits in size (scalers) and points have three scalers (projective coordinates), passing values by copy are expensive in terms of stack space and argument copy. To eliminate as many copies as possible, I pass the arguments as 'const &', create a local variable, perform the computation and place the result in the local variable, and then return the local variable. Note: Code is C++17 (clang).

struct Point { /* ... */ } ;

friend Point operator + (Point const & lhs , Point const & rhs)
{
  Point  res ; 

  /* Do addition and place result into 'res' */

  return res ;
}

This works fine for all possible argument types (& , const & , &&) but always requires additional stack space for the result. If a temporary is passed (Point &&), it can be used to hold the result and save stack space. The question here is how to correctly return the result?

friend Point operator + (Point && lhs , Point const & rhs)
{
  /* Do addition and place result into 'lhs' */

  return lhs ; // Not sure what is exactly returned here : Danger of dangling reference or ok?
}

/* OR */

friend Point && operator + (Point && lhs , Point const & rhs)
{
  /* Do addition and place result into 'lhs' */

  return std::move (lhs) ; // Danger of dangling reference to caller if not used correctly
}

I understand that the second case (return Point &&) can lead to a dangling reference if not handled correctly by the caller.

I have read similar questions and answers on returning && values, but I did not find anything specific to returning a && argument as a value (first case above).

How exactly does C++ define the return value behavior for the first case (return Point when the argument was Point &&)?

Is there a better (ie: efficient and safe) method for eliminating copies and reusing temporary argument memory?

Additionaly, if the overloaded operator is declared as a template, I understand the '&&' argument is treated differently to support perfect forwarding.

template <class Point> friend Point operator + (Point && lhs , Point const & rhs)
{
  /* Do addition and place result into 'lhs' */

  return lhs ;
}

How exactly does the '&& argument get treated differently (if so) than in the non-template definition and what is the correct way to return the result?

rvalue overloading c++
2 Answers

If you're returning by value from a function you don't have to worry about dangling references, as you're dealing with values and copies are made when necessary. So unless you're returning a reference, you don't have to worry. References passed as a parameter are invalidated at the end of the caller expression, so it could be safe to return one of the parameters by reference.

In your case you could do

Point &&operator + (Point &&lhs, Point const &rhs)
{
    // calculations modifying lhs
    // ...
    return lhs;
}

but in my opinion that would be much more error prone due to a possibility of dangling references than necessary, so I'm going to focus on returning by value. I encourage you to measure the performance difference none the less, to see if there's any difference.

When passed by value large structs are usually passed on the stack (>8 bytes on windows x64, >16 bytes on linux x64) for both function parameters and return values. For both, the caller allocates the necessary stack space. This is important to understand what's happening under the hood.

In the first case when you declare a res value that you later return, you can probably rely on compiler optimizations that no stack space is allocated for res, but the space allocated by the caller for the return value is used. This is similar to NRVO. Clang does this even with -O0 (look for (the lack of) allocas in the LLVM-IR).

With this in mind there's no need to provide an overload which can take an rvalue reference, as using a res variable wouldn't take up any addittional stack space.

Note that this optimization is usually only guaranteed if all of the return statements in the function are return ret;.

For parameters the best you can do to avoid stack allocations is not passing by value, so redundant copies don't have to be made when calling functions. Using const & is ideal in this case, as it can accept both rvalues and lvalues.

To expand further on the "NRVO-like" behaviour of using a res variable, let's take this example:

Point create_point()
{
    Point res;
    // fill res with values
    return res;
}

int main()
{
    Point p;
    p = create_point();
}

In this example using clang with -O1, only one stack allocation occurs, for p, and the rest are elided (see demo).

user_114884570

I would provide 2 overloads:

Point operator + (Point lhs , Point const & rhs){
    return lhs+=rhs;
};

Point&& operator + (Point const & lhs , Point&& rhs){
    return std::move(rhs+=lhs);
};

auto x=p1+p2;

and rely on copy elision(RVO, NRVO).

regards, FM.

user_63856400
Related