Monday, September 26, 2011

Copy Semantics and the Rule of Three

Commonly referred to as "the three amigos", the
  • copy constructor,
  • copy assignment operator, and
  • destructor
are sometimes generated by the compiler, when not defined directly by the programmer. Given a class definition such as the one below, the compiler will provide its own, synthesized version of the copy constructor and assignment operator for us.
class Basic
{
public:
    Basic()
        : m_data(new char[1024])
    {
    }

    ~Basic()
    {
        if (m_data)
            delete[] m_data;
         m_data = 0;
     }

private:
     char *m_data;
};
Here is how these default, compiler adaptations deal with different member types when we copy, assign to, or delete an object:

Default copy constructor:
  • Primitive types: Value is copied
  • Pointer types: Pointer is copied (shallow copy)
  • Objects: Calls object's copy constructor

Default assignment operator:
  • Primitive types: Value is copied
  • Pointer types: Pointer is copied (shallow copy)
  • Objects: Calls object's assignment operator

Default destructor:
  • Primitive types: Does nothing
  • Pointer types: Does nothing
  • Objects: Calls object's destructor

With C++11 also comes two new amigos (more about these later), they are the:
  • move constructor, and
  • move assignment operator.

A shallow copy simply means that the value of the pointer is copied, i.e., the address of the data, not the data itself. In our class definition above, the compiler-generated copy constructor and assignment operator are implicit. Consequently, the two objects in the following statements will end up with m_data pointers pointing to the same data.
Basic obj1;
Basic obj2(obj1);

The problem with our compiler-generated copy constructor (or, the problem with the Basic class destructor, depending on how you look at it) manifests when the objects are destroyed.
int main(int argc, char **argv)
{
    Basic obj1;
    Basic obj2(obj1);
    return 0;
}
This program will crash, and here is why:

  • The first object falls out of scope, and the data pointed to by m_data is released (in the destructor). So far, so good.
  • The second object falls out of scope. Since this object's m_data pointer is still pointing to the address of the memory we just released, the program will attempt to release the same memory again, which will cause the program to crash.

Rule of three

Dr. Dobbs describes the problem in great detail, in an article by Andrew Koenig and Barbara E. Moo. The observations are summarized in the following two rules, collectively referred to as "the rule of three":
  • If a class has a nonempty destructor, it almost always needs a copy constructor and an assignment operator.
  • If a class has a nontrivial copy constructor or assignment operator, it usually needs both of these members and a destructor as well.

Simply put, the rule states that; if we define one of the three members, we should usually define all three of them. To do so, there are essentially four different approaches. Each will be described in more detail below.
  • No copying
  • Deep copy
  • Reference counting
  • Copy-on-write

    1. No copying

    In some cases, we can simply prohibit copying. This is usually done by declaring the copy constructor and assignment operator private, thereby disabling them:
    class Basic
    {
    public:
        Basic()
            : m_data(new char[1024])
        {
        }    
    
        ~Basic()
        {
            if (m_data)
                delete[] m_data;
            m_data = 0;
        }
    
    private:
        Basic(const Basic&);                // copy-constructor
        Basic &operator =(const Basic&);    // assignment operator    
    
        char *m_data;
    };
    Note that the copy constructor and assignment operator are never actually defined. Any attempt to make a copy of a Basic object or assign to an already existing object will be caught at compile-time and throw an error.
    int main(int argc, char **argv)
    {
        Basic obj1;
        Basic obj2(obj1);
        obj2 = obj1;
    }
    The program will now fail to compile, with the following errors:
    // error: ‘Basic::Basic(const Basic&)’ is private
    // error: ‘Basic& Basic::operator=(const Basic&)’ is private
    This will obviously impose restrictions on how we can use objects created from the Basic class. The following, for example, will not work:
    Basic b;
    std::vector<Basic> v;
    v.push_back(b);
    Instead, we can store a pointer:
    std::vector<Basic *> v;
    v.push_back(new Basic);
    Similarly, passing an object by value or returning an object from a function will not work either.
    void doStuff(const Basic &basic) { /* ... */ }
    void otherStuff(Basic basic) { /* ... */ }
    
    Basic makeStuff()
    {
        Basic b;
        return b;   // error: ‘Basic::Basic(const Basic&)’ is private
    }
    
    int main()
    {
        Basic obj;
        doStuff(obj);       // ok!
        otherStuff(obj);    // error: ‘Basic::Basic(const Basic&)’ ...
        return 0;
    }
    In the end, project requirements will usually determine if the trade-offs associated with this no-copy approach are acceptable.

    QObject
    The no-copy pattern is found in Qt, where objects of QObject-based classes are treated as identities, rather than values, and mustn't be copied. From the documentation:
    Identities are cloned, not copied or assigned, and cloning an identity is a more complex operation than copying or assigning a value. Therefore, QObject and all subclasses of QObject (direct or indirect) have their copy constructor and assignment operator disabled.
    For convenience, Qt also provides the Q_DISABLE_COPY macro that declares a private copy constructor and assignment operator for us.
    class MyClass
    {
    public:
        MyClass()
        {
            // ...
        }    
    
        ~MyClass()
        {
            // ...
        }
    
    private:
        Q_DISABLE_COPY(MyClass)
    }

    2. Deep copy

    Another straightforward, but not always so efficient approach, is to let each object allocate its own resources and simply copy all data from the original to the new object. Such a copy is referred to as a deep copy. This is perhaps the most intuitive solution.

    We need to examine the various data members of the class, implement the copy constructor and assignment operator, and pay extra attention to pointer types. Our Basic class only has the char array to deal with:
    class Basic
    {
    public:
        Basic()
            : m_data(new char[1024])
        {
            memset(m_data, '-', 1024);
        }    
    
        ~Basic()
        {
            if (m_data)
                delete[] m_data;
            m_data = 0;
        }    
    
        Basic(const Basic &other)
            : m_data(new char[1024])
        {
            std::copy(other.m_data, other.m_data + 1024, m_data);
        }    
    
        Basic &operator =(const Basic &other)
        {
            if (this != &other) {
                if (m_data)
                    delete[] m_data;
                m_data = new char[1024];
                std::copy(other.m_data, other.m_data + 1024, m_data);
            }
            return *this;
        }
    
    private:
        char *m_data;
    };
    Here, we do a bit more work than necessary in the assignment operator. Since the size of the array is fixed at 1024 chars, we could simply re-use the same chunk of memory when m_data != 0, however, to keep the example as generic as possible; the steps that are usually involved are shown.

    Of course, if large objects are involved, copying can be expensive – a simple loop such as this,
    Basic b1;
    std::vector<Basic> v;
    for (int i = 0; i < 1024; ++i)
    {
        v.push_back(b1);
    }
    results in a total of approx. 2 MiB being copied.

    3. Reference counting

    Reference counting is a technique to keep track of the number of references that exist to a specific resource. It can help us to address the issue of resource deallocation (double delete) mentioned earlier and, typically, involves the following steps: A new object allocates the resource and sets the reference count to one. When a (shallow) copy is made, the reference count is incremented. When an object is destroyed, the reference count is decremented and once it reaches zero, the resource is finally released.

    Intrusive vs. non-intrusive reference counting

    There are two different approaches to reference counting: We can either place the counter within the object being counted; or outside, separate from the object. These methods are referred to as intrusive and non-intrusive reference counting respectively.

    Here is an example of a class that makes use of non-intrusive reference counting:
    class Stuff
    {
    public:
        Stuff()
            : m_count(new long unsigned),
              m_data(new char[1024])
        {
            *m_count = 1;        
    
            // Fill data with '0' character
            memset(m_data, '0', 1024);
        }    
    
        ~Stuff()
        {
            decrement();
        }    
    
        Stuff(const Stuff &other)
            : m_count(other.m_count),
              m_data(other.m_data)
        {
            ++(*m_count);
        }    
    
        Stuff &operator =(const Stuff &other)
        {
            if (this != &other) {
                decrement();
                m_count = other.m_count;
                m_data = other.m_data;
                ++(*m_count);
            }
            return *this;
        }    
    
        void setData(int i, char value)
        {
            m_data[i] = value;            // crude implementation
        }                                 // for testing purposes only
    
        char data(int i) const
        {
            return m_data[i];             // crude implementation
        }                                 // for testing purposes only
    
    private:
        void decrement()
        {
            if (!m_count)
                return;
            --(*m_count);
            if (0 == *m_count) {
                delete m_count;
                if (m_data)
                    delete[] m_data;
                m_count = 0;
                m_data = 0;
                std::cout << "Deleting data!\n";   // debug info
            }
        }    
    
        unsigned long *m_count;
        char          *m_data;
    };
    Copying is inexpensive, but since the data is shared between the shallow copies, changing one of them will change the others as well:
    Stuff obj;
    Stuff obj2(obj);
    Stuff obj3;
    obj3 = obj2;
    
    std::cout << obj.data(5);       // '0'
    std::cout << obj2.data(5);      // '0'
    std::cout << obj3.data(5);      // '0'
    
    obj2.setData(5, 'x');
    
    std::cout << obj.data(5);       // 'x'
    std::cout << obj2.data(5);      // 'x'
    std::cout << obj3.data(5);      // 'x'
    Run this example from codepad: http://codepad.org/oKJOvKAF

    The actual data is only deleted once, which is when the reference count reaches zero:
    Stuff *obj1 = new Stuff;
    Stuff *obj2 = new Stuff(*obj);
    Stuff *obj3 = new Stuff(*obj);
    delete obj1;
    std::cout << "obj1 destroyed\n";
    delete obj2;
    std::cout << "obj2 destroyed\n";
    delete obj3;
    std::cout << "obj3 destroyed\n";
    This will produce the following output:
    obj1 destroyed
    obj2 destroyed
    Deleting data!
    obj3 destroyed
    Reference counting is used in various garbage collection algorithms and a number of different programming languages and libraries, including PHP, Apple's Cocoa framework and the glib GObject system.

    Shared pointers

    The above solution can be drastically simplified by using an existing reference counted smart pointer, such as shared_ptr, provided by the Boost library. As of C++11, shared_ptr is also part of the STL. In the following example, the Boost version is used:
    #include <boost/shared_ptr.hpp>
    
    class LargeObject
    {
    public:
        // ...
    };
    
    class SmartClass
    {
    public:
        SmartClass()
            : m_someLargeObject(new LargeObject)
        {
        }
    
    private:
        boost::shared_ptr<LargeObject> m_someLargeObject;
    };
    Most of the details are now taken care of by the smart pointer class and the default, compiler-synthesized version of the destructor, copy constructor and assignment operator are sufficient.

    QSharedPointer

    Qt also provides its own shared pointer. QSharedPointer is similar to its STL/Boost equivalent but also implements atomic reference counting and is safe to use in multi-threaded code without mutexes or other locking mechanisms.

    The Pimpl idiom

    The Pimpl (pointer to implementation) idiom, also known as a compiler firewall, opaque pointer, or a Cheshire Cat technique, can be seen as a more pure form of encapsulation. It enables an implementation to be changed without the need to recompile client code. Unrelated to reference counting, a Pimpl:
    • Makes it possible to maintain binary compatibility.
    • Can reduce compile times.

    One flavor of the Pimpl pattern is the so called d-pointer, invented by Arnt Gulbrandsen of Trolltech; the company that initially developed Qt.

    The following example uses the d-pointer technique to implement a form of intrusive reference counting:
    class PimplPrivate
    {
    public:
        PimplPrivate()
            : count(1)
        {
            memset(data, '0', 1024);
        }    
    
        ~PimplPrivate() {}    
    
        PimplPrivate(const PimplPrivate &other)
            : count(1)
        {
            std::copy(other.data, other.data + 1024, data);
        }    
    
        char data[1024];
        int  count;
    };
    
    class Pimpl
    {
    public:
        Pimpl()
            : d(new PimplPrivate)
        {
        }    
    
        ~Pimpl()
        {
            if (!d)
                return;
            --d->count;
            if (0 == d->count) {
                delete d;
                d = 0;
            }
        }    
    
        Pimpl(const Pimpl &other)
            : d(other.d)
        {
            ++d->count;
        }    
    
        Pimpl &operator =(const Pimpl &other)
        {
            if (this != &other) {
                --d->count;
                if (0 == d->count)
                    delete d;
                d = other.d;
                ++d->count;
             }
             return *this;
        }    
    
        void setData(int i, char value)
        {
            d->data[i] = value;            // crude implementation
        }                                  // for testing purposes only
    
        char data(int i) const
        {
            return d->data[i];             // crude implementation
        }                                  // for testing purposes only
    
    private:
        PimplPrivate *d;
    };
    All private data members are migrated to a separate class and access must now go through the d-pointer. By convention, the private class is named after its public counterpart with an added "Private" (e.g., MyClass → MyClassPrivate). The copy constructor in PimplPrivate isn't strictly required here, but it will be used when we further extend the functionality of the class.

    In a pure Pimpl, the header file should only contain a forward declaration for the private class. The actual class definition is contained in the source file:

    header file:
    class PimplPrivate;          // forward declaration
    
    class Pimpl
    {
        // declarations for member functions of the Pimpl class
    };
    source file:
    class PimplPrivate
    {
        // ...
    };
    
    Pimpl::Pimpl() {}
    
    // definitions for Pimpl member functions
    The reference count is placed in the Private class. Copying the d-pointer and incrementing the counter is now all that is required.

    The illustration shows how the d-pointer of the new object is copied to point to the same data. As a result, the copies share their private data members – they are shallow copies.
    int main(int argc, char **argv)
    {
        Pimpl p1;
        Pimpl p2(p1);
        std::cout << p1.data(0) << "\n";
        std::cout << p2.data(0) << "\n";
        p2.setData(0, 'x');
        std::cout << p1.data(0) << "\n";
        std::cout << p2.data(0) << "\n";
        return 0;
    }
    The program produces the following output:
    0
    0
    x
    x
    Run this example from codepad: http://codepad.org/Env61HMA

    Pimpl using a smart pointer

    Again, a shared_ptr can make things a whole lot easier:
    #include <boost/shared_ptr.hpp>
    
    class SmartPimplPrivate
    {
    public:
        SmartPimplPrivate()
        {
            memset(data, '0', 1024);
        }    
    
        ~SmartPimplPrivate() {}    
    
        SmartPimplPrivate(const SmartPimplPrivate &other)
        {
            std::copy(other.data, other.data + 1024, data);
        }    
    
        char data[1024];
    };
    
    class SmartPimpl
    {
    public:
        SmartPimpl()
            : d(new SmartPimplPrivate)
        {
        }    
    
        void setData(int i, char value)
        {
            d->data[i] = value;          // crude implementation
        }                                // for testing purposes only
    
        char data(int i) const
        {
            return d->data[i];           // crude implementation
        }                                // for testing purposes only
    
    private:
        boost::shared_ptr<SmartPimplPrivate> d;
    };
    The compiler-synthesized version of the destructor, copy constructor and assignment operator are sufficient for the SmartPimpl class.

    The Q_D macro

    D-pointers are used heavily in the Qt library. See this, and this article for more detailed explanations of d-pointers; as well as the Q_DECLARE_PRIVATE, and Q_D macros in Qt. Note, however, that since d-pointers and the Q_D macro is not part of the public API, or officially supported; forward compatibility cannot be guaranteed (although it is not likely that the macros will be removed, since a lot of code depends on their use).

    4. Copy-on-write

    Finally, copy-on-write can be seen as a, kind of, lazy evaluation technique, or more specifically, a lazy deep copy. Copies are shallow, but prior to any operation that modifies the data (when calling a non-const function), a deep copy is made. So, the actual copy is delayed, and only takes place when necessary – on write.

    The basic pattern of a copy-on-write operation is described by the following example program:
    Obj original;
    Obj copy(original);         // copy and original are now
                                // shallow copies, sharing the
                                // actual data
    
    copy.readSomeData();        // calling a const function
                                // does not trigger a copy
    
    original.modifySomeData(1); // This function is non-const,
                                // the data will be detached prior to
                                // modifying the object (copy on write)
    
    // We now have two separate objects
    First, the function to copy, or detach the data must be added. For our manually reference counted class, it could look like this:
    class Pimpl
    {
    public:
        // ...      
    
        void detach()
        {
            if (d->count > 1) {
                --d->count;
                d = new PimplPrivate(*d);
            }
        }    
    
        // ...
    };
    This is where the private class' copy constructor comes in. The smart pointer class requires even less work. Here are also the setter and getter functions.
    #include <boost/shared_ptr.hpp>
    
    class SmartPimplPrivate
    {
        // ...
    };
    
    class SmartPimpl
    {
    public:
        SmartPimpl()
            : d(new SmartPimplPrivate)
        {
        }    
    
        void setData(int i, char value)
        {
            detach();                       // Copy on write
            d->data[i] = value;
        }    
    
        char data(int i) const
        {
            return d->data[i];
        }    
    
        void detach()
        {
            if (d.use_count() > 1) {
                d = boost::shared_ptr<SmartPimplPrivate>(new SmartPimplPrivate(*d));
                std::cout << "---- detaching! ----\n";
            }
        }
    
    private:
        boost::shared_ptr<SmartPimplPrivate> d;
    };
    • setData() now calls detach() prior to changing the array.
    • A deep copy is created if more than one reference exists.
    int main(int argc, char **argv)
    {
        SmartPimpl p1;
        p1.setData(0, 'y');
        SmartPimpl p2(p1);
        SmartPimpl p3(p1);
        std::cout << p1.data(0) << "\n";
        std::cout << p2.data(0) << "\n";
        std::cout << p3.data(0) << "\n";
        p1.setData(0, 'x');
        std::cout << p1.data(0) << "\n";
        std::cout << p2.data(0) << "\n";
        std::cout << p3.data(0) << "\n";
        return 0;
    }
    This program will output the following:
    y
    y
    y
    ---- detaching! ----
    x
    y
    y
    Run this example from codepad: http://codepad.org/NUyL73z5

    Now, two different SmartPimplPrivate objects exist. One with a reference count of 2, the other with a reference count of 1.

    Explicit/Implicit Sharing

    This technique is sometimes referred to as explicit sharing. The private data is referenced and only copied when we (explicitly) call detach(). In addition to this, implicit sharing  involves having the data automatically detached as soon as any non-const function is called, thereby eliminating the need to call detach() manually.

    Qt provides the QSharedDataPointer and QSharedData classes for this purpose. Alternatively QExplicitlySharedDataPointer can be used when explicit sharing is more suitable.

    C++11 move semantics

    Move semantics enables us to write code that moves resources from one object to another. The distinction here is between copying, and moving; where moving means that the new object, rather, takes over the resources from the original. The original object becomes useless, and must be left in such a state that it can be destroyed or assigned to, without causing resource leaks or triggering any undefined behavior. To support this, we can let a class provide a
    • move constructor, and
    • move assignment operator (may not be required).
     
    By allowing the compiler choose to call the move constructor, we can avoid unnecessary copying and thereby gain performance improvements. Consider the following example:
    class A
    {
    public:
        A(const char *info)
            : m_info(new std::string(info))
        {
            std::cout << "allocating object resources\n";
        }
    
        ~A()
        {
            delete m_info;
            std::cout << "deallocating object resources\n";
        }
    
        A(const A &other)
            : m_info(new std::string(*other.m_info))
        {
            std::cout << "copying data\n";
        }
    
        A &operator =(const A &other)
        {
            if (this != &other) {
                delete m_info;
                m_info = new std::string(*other.m_info);
                std::cout << "allocating + copying data\n";
            }
            return *this;
        }
    
        inline std::string info() const { return *m_info; }
    
    private:
        std::string *m_info;
    };
    
    int main()
    {
        std::vector<A> v;
    
        A a("banana");
        v.push_back(a);
    
        A b("mayonnaise");
        v.push_back(b);
    
        A c("aardvark");
        v.push_back(c);
    
        std::cout << "------------\n";
    
        std::cout << v.at(0).info() << "\n";
        std::cout << v.at(1).info() << "\n";
        std::cout << v.at(2).info() << "\n";
    
        std::cout << "------------\n";
    
        return 0;
    }
    This program produces the following output:
    allocating object resources
    copying data
    allocating object resources
    copying data
    copying data
    deallocating object resources
    allocating object resources
    copying data
    copying data
    copying data
    deallocating object resources
    deallocating object resources
    ------------
    banana
    mayonnaise
    aardvark
    ------------
    ... etc
    Run this example from codepad: http://codepad.org/MCnrPwf9

    By adding a move constructor, and changing v.push_back(something) to v.push_back(std::move(something)),
    class A
    {
    public:
        // ...
    
        A(A &&other)
        {
            m_info = other.m_info;
            other.m_info = 0;
        }
    };
    
    int main()
    {
        std::vector<A> v;
    
        A a("banana");
        v.push_back(std::move(a));
    
        A b("mayonnaise");
        v.push_back(std::move(b));
    
        A c("aardvark");
        v.push_back(std::move(c));
    
        std::cout << "------------\n";
    
        std::cout << v.at(0).info() << "\n";
        std::cout << v.at(1).info() << "\n";
        std::cout << v.at(2).info() << "\n";
    
        std::cout << "------------\n";
    
        return 0;
    }
    we get, instead:
    allocating object resources
    allocating object resources
    deallocating object resources
    allocating object resources
    deallocating object resources
    deallocating object resources
    ------------
    banana
    mayonnaise
    aardvark
    ------------
    ... etc
    The data is now moved from the object to the vector, and if we try to access the original object, the program will crash:
    A a("banana");
    v.push_back(std::move(a));
    
    std::cout << a.info();          // undefined behavior
    The following illustration explains the role of a move constructor:

    The move assignment operator has similar objectives, with the difference that the object may already have resources allocated, and just as in the case of a normal (copy) assignment operator, these existing resources must be released before any data is moved to the new object.

    Rvalue references

    With the concept of move semantics, C++11 introduces a new kind of reference, the rvalue reference. For a detailed explanation of rvalue references, see the following articles:

        Implementation

        We can now add a move constructor and move assignment operator to the non-intrusive reference counting class described under section 3. The illustration shows how the data is "drained" from the original object, which after the move operation can no longer be used.

        Here is what they could look like:
        class Stuff
        {
        public:
            // ...    
        
            Stuff(Stuff &&other)
                : m_count(other.m_count),
                  m_data(other.m_data)
            {
                other.m_count = 0;
                other.m_data = 0;
            }    
        
            Stuff &operator =(Stuff &&other)
            {
                if (this != &other)
                {
                    decrement();
                    m_count = other.m_count;
                    m_data = other.m_data;
                    other.m_count = 0;
                    other.m_data = 0;
                }
                return *this;
            }    
        
            // ...
        };
        The double ampersand (&&) is the notation used for an rvalue reference (apparently pronounced as "ref-ref"). Note that we cannot use a const reference here since we need to leave the object with m_count and m_data as null pointers.

        More about move semantics and rvalue references in a later post.

        Please leave a comment if you found this post useful. Suggestions and corrections are also welcome.

          0 comments:

          Post a Comment