How does C++ return value optimization (RVO) work when the function get's called with the variable that the return value gets assigned to?

Question

Originally, I had a problem like this: I have a vector with data and want to perform an operation n times. Doing it in place is impossible, so a new vector gets constructed in every loop cycle, the operation gets done and memory gets to freed. What kind of operation is not important for my question, but mathematically it squares a permutation (I just wanted to come up with an operation that cannot be done in-place). It applies result[i] = in[in[i]] for all Elements.

vector<int> *sqarePermutationNTimesUnsafe(vector<int> *in, int n)
{
    if (n <= 0) { throw; }
    
    vector<int> *result = in;
    vector<int> *shuffled;
    for (int i = 0; i < n; i++)
    {
        shuffled = new vector<int>(in->size(), 0);
        for (int j = 0; j < in->size(); j++)
        {
            (*shuffled)[j] = (*result)[(*result)[j]];
        }

        if (result != in) { delete result; }
        result = shuffled;
    }
    return result;
}

The main thing for speed up is, that the new data is written to shuffled, and then there is just a pointer swap required to do the next shuffling. It works, but it's ugly and error-prone. So I figured a better way of doing this is to use modern c++. Passing references should be faster than passing the vectors<...>, so I did that. As the swapping of references is not directly possible, I split it up into two functions and relied on return value optimization to swap the references.

// do the permutation
vector<int> sqarePermutation(const vector<int> &in)
{
    vector<int> result(in.size(), 0);
    for (int i = 0; i < in.size(); i++)
    {
        result[i] = in[in[i]];
    }
    return result;
}

// do the permutation n times
vector<int> sqarePermutationNTimes(const vector<int> &in, const int n)
{
    vector<int> result(in); // Copying here is ok and required
    for (int i = 0; i < n; i++)
    {
        result = sqarePermutation(result); // Return value optimization should be used so "swap" the references
    }
    return result;
}

I wanted to make sure, that RVO works so I wrote a little program to test it.

#include <iostream>

using namespace std;

class RegisteredObject
{
private:
    int index;
public:
    RegisteredObject(int index);
    ~RegisteredObject();
    int getIndex() const;
};

RegisteredObject::RegisteredObject(int index): index(index)
{
    cout << "- Register Object " << index << endl;
}

RegisteredObject::~RegisteredObject()
{
    cout << "- Deregister Object " << index << endl;
}

int RegisteredObject::getIndex() const
{
    return index;
}

RegisteredObject objectWithIncreasedIndex(const RegisteredObject &object)
{
    return RegisteredObject(object.getIndex() + 1);
}


int main() {
    cout << "Init a(0)" << endl;
    RegisteredObject a(0); 
    cout << "RVO from a to a" << endl;
    a = objectWithIncreasedIndex(a); // Seems to be buggy
    cout << "RVO from a to b" << endl;
    RegisteredObject b = objectWithIncreasedIndex(a); // Why does a get destructed here?
    cout << "End" << endl;
    return 0;
}

Don't hesitate to try it out on your machine, results may vary. The program has a simple data object that shows when the constructor and destructor are called. I am using Mac OS Clang 11.0.3 targeted for x86_64-apple-darwin19.6.0. It produces the following result:

Init a(0)
- Register Object 0
RVO from a to a
- Register Object 1
- Deregister Object 1 //EDIT: <--- this should be Object 0
RVO from a to b
- Register Object 2
End
- Deregister Object 2
- Deregister Object 1

As you see, Object 1 never gets destructed. I think it happens because of RVO. RVO constructs the new Object 1 into the place of Object 0. But because it forgot to make a temporary copy of Object 0, the destructor get's called with index 1 instead.

Declaring the index as const helps to prevent this bug, as the compiler throws an error.

object of type 'RegisteredObject' cannot be assigned because its copy
      assignment operator is implicitly deleted

But I don't think it is the solution. For me, it seems like C++'s (or at least clang's) RVO is broken. This means, that the above implementation of the Permutation might try to double-free memory, or not use RVO at all.

So first of all, what do you think causes the Bug with not freeing Object 1?

And how would you implement an efficient and beautiful version of the sqarePermutationNTimes Method?

Answer 1

When monitoring constructor/destructor don't forget copy(/move) constructor and assignment, then you got something similar to:

Init a(0)
- Register Object {0x7ffc74c7ae08: 0}
RVO from a to a
- Register Object {0x7ffc74c7ae0c: 1}
assign {0x7ffc74c7ae08: 0} <- {0x7ffc74c7ae0c: 1}
- Deregister Object {0x7ffc74c7ae0c: 1}
RVO from a to b
- Register Object {0x7ffc74c7ae0c: 2}
End
- Deregister Object {0x7ffc74c7ae0c: 2}
- Deregister Object {0x7ffc74c7ae08: 1}

Demo

RVO is applied as you don't have copy constructor call.

but assignment does still exist.

a = objectWithIncreasedIndex(a);

is equivalent to

a = RegisteredObject(a.getIndex() + 1);

instead of

a = RegisteredObject(RegisteredObject(a.getIndex() + 1));

thanks to RVO.

For your first snippet, you have so n (move-)assignments and n temporaries created.

You might reduce temporaries by using the (old) output variable way.

// do the permutation
void squarePermutation(const std::vector<int> &in, std::vector<int>& result)
{
    result.resize(in.size());
    for (int i = 0; i != in.size(); ++i) {
        result[i] = in[in[i]];
    }
}
// Convenient call
std::vector<int> squarePermutation(const std::vector<int> &in)
{
    std::vector<int> result;
    squarePermutation(in, result);
    return result;
}

// do the permutation n times
vector<int> sqarePermutationNTimes(const vector<int> &in, const int n)
{
    std::vector<int> result(in); // Copying here is ok and required
    std::vector<int> tmp; // outside of loop so build only once

    for (int i = 0; i != n; i++)
    {
        squarePermutation(result, tmp);
        std::swap(result, tmp); // Modify internal pointers
    }
    return result;
}