I’ve written a decent amount of C++, but never really took the time to understand its internals. In the first of what will hopefully become a series of articles, we will look at lvalues, rvalues, and move semantics. This turns out to be a crucial part of the language and understanding it will greatly help you reason about the performance of your program.

Lvalues and rvalues

C++ has a distinction between lvalues and rvalues. A lvalue is something that has a long-term memory location, i.e. it is stored somewhere on the stack or the heap. You can expect that others will try to access and modify it.

int i = 0; // i is a lvalue

An rvalue, on the other hand, is a temporary value stored in a register and used for intermediate calculations. These don’t have a long-term memory location.

int add_one(int num) {
    return num + 1;
}
add_one(1); // 1 here is a rvalue

As such, lvalues are usually on the left side of an expression, and rvalues are usually on the right, hence their naming.

You can take the address of a lvalue, since again, it has a long-term memory location.

int num = 20;
int *ptr = #

Conversely, you cannot take the address of a rvalue.

int *ptr = &20; // error

Similarly, you can take a reference to a lvalue, but not a rvalue.

int num = 20;
int &ref = num; // ok
int &ref = 20;  // error

It sort of makes sense if you think about it. It’s a bit weird to take a reference to a temporary variable stored in some register. It’s meant to be used once and then discarded, and the content of that register is expected to change anytime, invalidating your reference.

Another way to think about it is that when you take a reference to a rvalue, you are trying to convert a rvalue into a lvalue, and then taking a reference to it, a practice that C++ forbids. On the other hand, you can convert a lvalue into a rvalue. When you do something like int j = i + 2, i, a lvalue, is implicitly converted into a rvalue, since the + operation takes two rvalues and returns a rvalue. An easy way to remember this is that it’s easy to move something in a permanent location to a temporary location (lvalue to rvalue conversion), but much harder to move a temporary object into a permanent location (rvalue to lvalue conversion).

Actually I may have lied a bit - the whole distinction between how lvalues and rvalues are stored (register vs stack/heap) isn’t totally true. The C++ spec doesn’t make any such restrictions on how variables are stored in memory; if the compiler sees that a variable is only used temporarily, it is free to move it to a register, so long as it doesn’t change the observable behavior of the program. Nonetheless, I think it’s helpful to differentiate between “short-term” temporaries and “long-term” memory locations.

However, what if you wanted to pass in temporary values to functions that won’t modify the underlying values? It would be annoying to have to convert the rvalue into a lvalue everytime you need to pass some read-only object into a function. As a result, C++ does allow you to take a const reference to a rvalue. Under the hood, the compiler will create a implicit temporary lvalue from your rvalue before passing it into your function, but it saves the programmer a headache each time.

// error
void do_nothing1(int &num) {
    return;
}
do_nothing1(1);

// ok
void do_nothing2(const int &num) {
    return;
}
do_nothing2(1);

One important thing to note about const lvalue references to rvalues is that their lifetime extends past the underlying rvalue they point to. Below is an example to illustrate this point.

const int &ref = 20;                      // 1
std::cout << "ref: " << ref << std::endl; // 2

Usually, a reference is valid only as long as the object it points to, so the example would introduce a dangling pointer. In this case, the lifetime of the rvalue 20 is the length of the expression it is in, i.e. the right hand side of line 1. However, since we have a const lvalue reference to it, its lifetime is now extended to when that reference expires.

So to summarize:

  • You can take a non-const lvalue reference to a lvalue but not a rvalue
  • However, you can take a const lvalue reference to a rvalue
  • (You can also take a const lvalue reference to a lvalue)
  • When you take a const lvalue reference to a temporary rvalue, the rvalue’s lifetime is extended to match that of the reference

Rvalue references

Turns out you can take references to temporaries (rvalues) as well. Let’s motivate this with an example. Suppose we want to implement a dynamic array of integers, one that automatically resizes when it reaches capacity. Since its size is not known at compile-time, we will need to allocate it on the heap via the new keyword in the constructor. We will also initialize the elements to 0 by default, with an optional argument init to change it. In the destructor, we will call delete on the memory.

class DynamicArray {
    public:
        // constructor
        DynamicArray(int init=0, size_t sz=10) {
            m_nums = new int[sz];
            for (int i = 0; i < sz; ++i) {
                m_nums[i] = init;
            }
            m_sz = sz;
        }
        // destructor
        ~DynamicArray() {
            delete[] m_nums;
        }
    private:
        int *m_nums;
        int init;
        size_t m_sz;
}

What should happen when we want to copy an existing DynamicArray object to an uninitialized object? For example:

DynamicArray d1(1, 10);
DynamicArray d2 = d1;

We need to 1. dynamically allocate memory for the new object and 2. copy the data from the old object to the new object, which is what we will do in our copy constructor.

// copy constructor
DynamicArray(const DynamicArray &that) {
    m_nums = new int[that.m_sz];
    std::memcpy(m_nums, that.m_nums, that.m_sz * sizeof(int));
    m_sz = that.m_sz;
}

On the other hand, what if we have an initialized object and we want to replace its contents with another initialized object?

DynamicArray d3(3, 10);
DynamicArray d4(4, 10);
d3 = d4;

This is what the assignment operator does: it needs to 1. delete the old object’s memory 2. re-allocate it with new, then 3. copy the new object’s data into the old object’s memory. As a slight optimization, note that we only need to delete and re-allocate if the new object and old object’s arrays are of different sizes. If they are the same, we can reuse the same memory and avoid an additional allocation.

// assignment
DynamicArray &operator=(const DynamicArray &that) {
    // prevent self-assignment
    if (this == &that) return *this;

    // if same size, then reuse memory
    if (m_sz == that.m_sz) {
        std::memcpy(m_nums, that.m_nums, that.m_sz * sizeof(int));
    } else {
        delete[] m_nums;
        m_nums = new int[that.m_sz];
        std::memcpy(m_nums, that.m_nums, that.m_sz * sizeof(int));
        m_sz = that.m_sz;
    }
    return *this;
}

Everything so far works as expected, but observe that the right-hand side of both our copy and assignment calls are lvalues.

// copy
DynamicArray d1(1, 10);
DynamicArray d2 = d1;

// assignment
DynamicArray d3(3, 10);
DynamicArray d4(4, 10);
d3 = d4;

Hence it makes sense that we need to make separate copies of memory - the lvalue is stored in a long-term memory location on the stack or heap and may be used by other entities. But what happens when the right hand side of our expressions consists of rvalues?

// copy
DynamicArray d2 = DynamicArray(1, 10);

// assignment
DynamicArray d3(3, 10);
d3 =  DynamicArray(4, 10);

The exact same thing happens! For the copy call, we allocate memory for d2 and copy the rvalue’s data into it. For the assignment call, we delete d3’s memory, re-allocate it with a new size, and copy the rvalue’s data into it. In other words, we aren’t taking advantage of the fact that the thing we’re copying from is a temporary, and thus will not be around beyond the expression it’s contained in.

This is where rvalue references come into play. An rvalue reference is denoted with two amperands (&&). Instead of having the compiler implicitly convert the rvalue into a lvalue and invoke the expensive copy/assignment operators, we take in references to the rvalues and simply change our internal structures to point to them. This idea allows us to implement what’s called move semantics - we’re moving objects around as opposed to copying them.

// move constructor
DynamicArray(DynamicArray &&that) {
    // just change a couple pointers!
    m_nums = that.m_nums;
    m_sz = that.m_sz;

    // invalidate the rvalue
    that.m_nums = nullptr;
    that.m_sz = 0;
}

// move assignment
DynamicArray &operator=(DynamicArray &&that) {
    if (this == &that) return *this;
    delete[] m_nums;
    // same thing here: no deep copying; just a couple assignments
    m_nums = that.m_nums;
    m_sz = that.m_sz;

    // invalidate rvalue
    that.m_nums = nullptr;
    that.m_sz = 0;
    return *this;
}

Now, whenever we invoke the copy or assignment operators, we no longer make a separate allocation and do a copy; we simply reuse the existing allocation.

This seems like a lot of complication for what seems like a trivial issue. But in general, you can assume the new and delete functions always come with extreme overhead. If you think about it, whenever you call new, the allocator has to search through the entire heap space to find a contiguous chunk of memory large enough to fit your data. When blocks are freed, it also has to perform coalescing between adjacent free blocks and compaction to avoid external fragmentation.

Recap

To recap what we learned so far:

  • Lvalues are usually on the left-hand side of an expression, and have a long-term memory location
  • Rvalues are usually on the right-hand side of an expression, and are stored temporarily in a register
  • You can take the address of a lvalue, but not of a rvalue, since it does not have a long-term memory location
  • You cannot bind a non-const lvalue reference to a rvalue
  • You can, however, take a rvalue reference to a rvalue, which allows us to implement move semantics and avoid additional memory allocations and copies, which you should assume are slow

References