Attack of the clones

Time and space considerations in four different approaches to implementing deep clone() methods

January 24, 2003

Q: What are the advantages and disadvantages of implementing deep cloning via Java serialization and a built-in Object.clone() method from a performance point of view?

A: Equipping classes in your application with correct clone() implementation is essential to many defensive programming patterns. Common examples include defensive copying of method parameters, cloning internal fields before returning them in getters, implementing immutability patterns, implementing containers with deep cloning semantics, and so on.

Even though the question mentions just two possibilities, there are at least four distinct approaches to clone() implementation. In this Java Q&A installment, I consider design and performance tradeoffs involved in all of them.

Because cloning is so customizable, this article's examples will not necessarily translate directly to your own code; however, the general conclusions we will reach should provide useful guidelines in any application design.

Note the following disclaimer: What exactly constitutes a deep clone is debatable. Even though two objects can safely share the same String reference viewed as data, they cannot if the same field is used as an instance-scoped object monitor (such as when calling Object.wait()/notify() on it) or if field instance identity (such as when using the == operator) is significant to the design. In the end, whether or not a field is shareable depends on the class design. For simplicity, I assume below that all fields are used as pure data.

Performance measurements setup

Let's jump right into some code. I use the following simple hierarchy of classes as my cloning guinea pig:

public class TestBaseClass
             implements Cloneable, Serializable
{
    public TestBaseClass (String dummy)
    {
        m_byte = (byte) 1;
        m_short = (short) 2;
        m_long = 3L;
        m_float = 4.0F;
        m_double = 5.0;
        m_char = '6';
        m_boolean = true;
        m_int = 16;
        m_string = "some string in TestBaseClass";
        
        m_ints = new int [m_int];
        for (int i = 0; i < m_ints.length; ++ i) m_ints [i] = m_int;
        
        m_strings = new String [m_int];
        m_strings [0] = m_string; // invariant: m_strings [0] == m_string
        for (int i = 1; i < m_strings.length; ++ i)
            m_strings [i] = new String (m_string);
    }
    public TestBaseClass (final TestBaseClass obj)
    {
        if (obj == null) throw new IllegalArgumentException ("null input: obj");
        
        // Copy all fields:
        
        m_byte = obj.m_byte;
        m_short = obj.m_short;
        m_long = obj.m_long;
        m_float = obj.m_float;
        m_double = obj.m_double;
        m_char = obj.m_char;
        m_boolean = obj.m_boolean;
        
        m_int = obj.m_int;
        m_string = obj.m_string;
        
        if (obj.m_ints != null) m_ints = (int []) obj.m_ints.clone ();
        if (obj.m_strings != null) m_strings = (String []) obj.m_strings.clone ();
    }
    
    // Cloneable:
    public Object clone ()
    {
        if (Main.OBJECT_CLONE)
        {
            try
            {
                // Chain shallow field work to Object.clone(): 
                final TestBaseClass clone = (TestBaseClass) super.clone ();
                
                // Set deep fields:
                if (m_ints != null)
                    clone.m_ints = (int []) m_ints.clone ();
                if (m_strings != null)
                    clone.m_strings = (String []) m_strings.clone ();
                
                return clone;
            }
            catch (CloneNotSupportedException e)
            {
                throw new InternalError (e.toString ());
            }
        }
        else if (Main.COPY_CONSTRUCTOR)
            return new TestBaseClass (this);
        else if (Main.SERIALIZATION)
            return SerializableClone.clone (this);
        else if (Main.REFLECTION)
            return ReflectiveClone.clone (this);
        else
            throw new RuntimeException ("select cloning method");
    }
    
    protected TestBaseClass () {} // accessible to subclasses only
    
    private byte m_byte;
    private short m_short;
    private long m_long;
    private float m_float;
    private double m_double;
    private char m_char;
    private boolean m_boolean;
    private int m_int;
    private int [] m_ints;
    private String m_string;
    private String [] m_strings; // invariant: m_strings [0] == m_string    
} // end of class
public final class TestClass extends TestBaseClass
             implements Cloneable, Serializable
{
    public TestClass (String dummy)
    {
        super (dummy);
        
        m_int = 4;
        
        m_object1 = new TestBaseClass (dummy);
        m_object2 = m_object1; // invariant: m_object1 == m_object2
    
        m_objects = new Object [m_int];
        for (int i = 0; i < m_objects.length; ++ i)
            m_objects [i] = new TestBaseClass (dummy);
    }
    public TestClass (final TestClass obj)
    {
        // Chain to super copy constructor:
        super (obj);
        
        // Copy all fields declared by this class:
        
        m_int = obj.m_int;
        
        if (obj.m_object1 != null)
            m_object1 = ((TestBaseClass) obj.m_object1).clone ();
        m_object2 = m_object1; // preserve the invariant
        
        if (obj.m_objects != null)
        {
            m_objects = new Object [obj.m_objects.length];
            for (int i = 0; i < m_objects.length; ++ i)
                m_objects [i] = ((TestBaseClass) obj.m_objects [i]).clone ();
        }
    }
    
    // Cloneable:
    public Object clone ()
    {
        if (Main.OBJECT_CLONE)
        {
            // Chain shallow field work to Object.clone():
            final TestClass clone = (TestClass) super.clone ();
            
            // Set only deep fields declared by this class:
            
            if (m_object1 != null)
                clone.m_object1 = ((TestBaseClass) m_object1).clone ();
            clone.m_object2 = clone.m_object1; // preserve the invariant
            
            if (m_objects != null)
            {
                clone.m_objects = (Object []) m_objects.clone ();
                for (int i = 0; i < m_objects.length; ++ i)
                    clone.m_objects [i] = ((TestBaseClass) m_objects [i]).clone ();
            }
            return clone;
        }
        else if (Main.COPY_CONSTRUCTOR)
            return new TestClass (this);
        else if (Main.SERIALIZATION)
            return SerializableClone.clone (this);
        else if (Main.REFLECTION)
            return ReflectiveClone.clone (this);
        else
            throw new RuntimeException ("select cloning method");
    }
        
    protected TestClass () {} // accessible to subclasses only
    private int m_int;        
    private Object m_object1, m_object2; // invariant: m_object1 == m_object2
    private Object [] m_objects;
} // End of class

TestBaseClass has several fields of primitive types as well as a String and a couple of array fields. TestClass both extends TestBaseClass and aggregates several instances of it. This setup allows us to see how inheritance, member object ownership, and data types can affect cloning design and performance.

In a previous Java Q&A article, I developed a simple timing library that comes in handy now. This code in class Main measures the cost of TestClass.clone():

        // Create an ITimer:
        final ITimer timer = TimerFactory.newTimer ();
        
        // JIT/hotspot warmup:
        // ...
        TestClass obj = new TestClass ();
        
        // Warm up clone():
        // ...
        final int repeats = 1000;
        
        timer.start ();
        // Note: the loop is unrolled 10 times
        for (int i = 0; i < repeats / 10; ++ i)
        {
            obj = (TestClass) obj.clone ();
            ... repeated 10 times ...
        }
        timer.stop ();
        
        final DecimalFormat format = new DecimalFormat ();
        format.setMinimumFractionDigits (3);
        format.setMaximumFractionDigits (3);
        
        System.out.println ("method duration: " +
            format.format (timer.getDuration () / repeats) + " ms");

I use the high-resolution timer supplied by TimerFactory with a loop that creates a moderate number of cloned objects. The elapsed time reading is reliable, and there is little interference from the garbage collector. Note how the obj variable continuously updates to avoid memory caching effects.

Also note how clone() is implemented in both classes. The implementation in each class is in fact four, selected one at a time using four conditional compilation constants in Main: OBJECT_CLONE, COPY_CONSTRUCTOR, SERIALIZATION, and REFLECTION. Recompile the entire object when changing the cloning approach.

Let's now examine each approach in detail.

Approach 1: Cloning by chaining to Object.clone()

This is perhaps the most classical approach. The steps involved are:

  • Declare your class to implement the Cloneable marker interface.
  • Provide a public clone override that always begins with a call to super.clone() followed by manual copying of all deep fields (i.e., mutable fields that are object references and cannot be shared between several instances of the parent class).
  • Declare your clone override not to throw any exceptions, including CloneNotSupportedException. To this effect, the clone() method in your hierarchy's first class that subclasses a non-Cloneable class will catch CloneNotSupportedException and wrap it into an InternalError.

Correct implementation of Cloneable easily deserves a separate article. Because my focus is on measuring performance, I will repeat the relevant points here and direct readers to existing references for further details (see Resources).

This traditional approach is particularly well suited to the presence of inheritance because the chain of super.clone() eventually calls the native java.lang.Object.clone() implementation. This is good for two reasons. First, this native method has the magic ability to always create an instance of the most derived class for the current object. That is, the result of super.clone() in TestBaseClass is an instance of TestClass when TestBaseClass.clone() is part of the chain of methods originating from TestClass.clone(). This makes it easy to implement the desirable x.clone().getClass() == x.getClass() invariant even in the presence of inheritance.

Second, if you examine the JVM sources, you will see that at the heart of java.lang.Object.clone() is the memcpy C function, usually implemented in very efficient assembly on a given platform; so I expect the method to act as a fast "bit-blasting" shallow clone implementation, replicating all shallow fields in one fell swoop. In many cases, the only remaining manual coding is done to deeply clone object reference fields that point to unshareable mutable objects.

Running the test with the OBJECT_CLONE variable set to true on a Windows 550-MHz machine with Sun Microsystems' JDK 1.4.1 produces:

clone implementation: Object.clone()
method duration: 0.033 ms

This is not bad for a class with multiple primitive and object reference fields. But for better insight, I must compare the result with other approaches below.

Despite its advantages, this approach is plagued with problems due to poor java.lang.Object.clone() design. It cannot be used for cloning final fields unless they can be copied shallowly. Creating smart, deeply cloning container classes is complicated by the fact that Cloneable is just a marker interface, and java.lang.Object.clone() is not public. Finally, cloning inner classes does not work due to problems with outer references. See articles by Mark Davis and Steve Ball in Resources for some of the earliest discussions about this topic.

Approach 2: Cloning via copy construction

This approach complements Approach 1. It involves these steps:

  • For every class X, provide a copy constructor with signature X(X x).

  • Chain to the base class's copy constructor in all but the first class in your hierarchy. You can chain to clone() or directly to the base copy constructor. The former choice is more polymorphic and works when the base copy constructor is private, and the latter sometimes avoids the small cost of casting clone()'s return value to a specific type.

  • Following the chaining call, set all class fields by copying them from the input parameter. For every object reference field, you decide individually whether to clone it deeply.

Setting COPY_CONSTRUCTOR to true and rerunning the test produces:

clone implementation: copy construction
method duration: 0.024 ms

This beats Approach 1. The result might not be surprising because the overhead of native method calls has increased and the cost of new object creation has decreased with increasing JDK versions. If you rerun the same tests in Sun's JDK 1.2.2, the situation favors Approach 1. Of course, performance depends on the relative mix of shallow and deep fields in the class hierarchy. Classes with many primitive type fields benefit more from Approach 1. Classes with a few mostly immutable fields work very efficiently with Approach 2, with a speed advantage at least 10 times greater than Approach 1.

Approach 2 is more error prone than Approach 1 because it is easy to forget to override clone() and accidentally inherit a superclass's version that will return an object of the wrong type. If you make the same mistake in Approach 1, the result will be less disastrous. Additionally, it is harder to maintain the implementation in Approach 2 when fields are added and removed (compare the OBJECT_CLONE branch in TestBaseClass.clone() with similar code in the copy constructor). Also, Approach 1 requires less class cooperation in some cases: for a base class with only shallow fields, you don't need to implement Cloneable or even provide a clone() override if you do not intend to clone at the base class level.

However, an undeniable advantage of cloning via copy construction is that it can handle both final fields and inner classes. But due to dangers present when inheritance is involved, I recommend using this sparingly and preferably simultaneously with making the relevant classes final.

Approach 3: Cloning via Java serialization

Java serialization is convenient. Many classes are made serializable by simply declaring them to implement java.io.Serializable. Thus, a whole hierarchy of classes can be made cloneable by deriving them from a base Serializable class whose clone() is implemented as a simple, yet extremely generic method:

    public Object clone (Object obj)
    {
        try
        {
            ByteArrayOutputStream out = new ByteArrayOutputStream ();
            ObjectOutputStream oout = new ObjectOutputStream (out);
            oout.writeObject (obj);
            
            ObjectInputStream in = new ObjectInputStream (
                new ByteArrayInputStream (out.toByteArray ()));
            return in.readObject ();
        }
        catch (Exception e)
        {
            throw new RuntimeException ("cannot clone class [" +
                obj.getClass ().getName () + "] via serialization: " +
                e.toString ());
        }
    }

This is so generic it can be used for cloning classes that can be written and added to your application by someone else long after you provide the base classes. But this convenience comes at a price. After switching TestBaseClass.clone() and TestClass.clone() to the SERIALIZATION branch I get:

clone implementation: serialization
method duration: 2.724 ms

This is roughly 100 times slower than Approaches 1 and 2. You probably would not want this option for defensive cloning of parameters of otherwise fast intra-JVM methods. Even though this method can be used for generic containers with deep cloning semantics, cloning a few hundred objects would make you see times in the one-second range: a doubtful prospect.

There are several reasons why this approach is so slow. Serialization depends on reflective discovery of class metadata, known to be much slower than normal method calls. Furthermore, because a temporary input/output (I/0) stream is used to flatten the entire object, the process involves UTF (Universal Transformation Format) 8-encoding and writing out every character of, say, TestBaseClass.m_string. Compared to that, Approaches 1 and 2 only copy String references; each copy step has the same small fixed cost.

What's even worse, ObjectOutputStream and ObjectInputStream perform a lot of unnecessary work. For example, writing out class metadata (class name, field names, metadata checksum, etc.) that may need to be reconciled with a different class version on the receiving end is pure overhead when you serialize a class within the same ClassLoader namespace.

On the plus side, serialization imposes fairly light constructor requirements (the first non-Serializable superclass must have an accessible no-arg constructor) and correctly handles final fields and inner classes. This is because native code constructs the clone and populates its fields without using any constructors (something that can't be done in pure Java).

One more interesting advantage of Approach 3 is that it can preserve the structure of object graph rooted at the source object. Examine the dummy TestBaseClass constructor. It fills the entire m_strings array with the same m_string reference. Without any special effort on our part, the invariant m_strings[0] == m_string is preserved in the cloned object. In Approaches 1 and 2, the same effect is either purely incidental (such as when immutable objects remain shared by reference) or requires explicit coding (as with m_object1 and m_object2 in TestClass). The latter could be hard to get right in general, especially when object identities are established at runtime and not compile time (as is the case with TestClass).

Approach 4: Cloning via Java reflection

Approach 4 draws inspiration from Approach 3. Anything that uses reflection can work on a variety of classes in a generic way. If I require the class in question to have a (not necessarily public) no-arg constructor, I can easily create an empty instance using reflection. It is especially efficient when the no-arg constructor doesn't do anything. Then it is a straightforward matter to walk the class's inheritance chain all the way to Object.class and set all (not just public) declared instance fields for each superclass in the chain. For each field, I check whether it contains a primitive value, an immutable object reference, or an object reference that needs to be cloned recursively. The idea is straightforward but getting it to work well requires handling a few details. My full demo implementation is in class ReflectiveClone, available as a separate download. Here is the pseudo-code of the full implementation, with some details and all error handling omitted for simplicity:

public abstract class ReflectiveClone
{
    /**
     * Makes a  reflection-based deep clone of 'obj'. This method is mutually
     * recursive with {@link #setFields}.
     * 
     * @param obj current source object being cloned
     * @return obj's deep clone [never null; can be == to 'obj']
     */
    public static Object clone (final Object obj)
    {        
        final Class objClass = obj.getClass ();
        final Object result;
                
        if (objClass.isArray ())
        {           
            final int arrayLength = Array.getLength (obj);
            
            if (arrayLength == 0) // empty arrays are immutable
                return obj;
            else
            {                      
                final Class componentType = objClass.getComponentType ();
                
                // Even though arrays implicitly have a public clone(), it
                // cannot be invoked reflectively, so need to do copy construction:
                
                result = Array.newInstance (componentType, arrayLength);
                
                if (componentType.isPrimitive () ||
                    FINAL_IMMUTABLE_CLASSES.contains (componentType))
                {
                    System.arraycopy (obj, 0, result, 0, arrayLength);
                }
                else
                {
                    for (int i = 0; i < arrayLength; ++ i)
                    {
                        // Recursively clone each array slot:
                        final Object slot = Array.get (obj, i);
                        if (slot != null)
                        {
                            final Object slotClone = clone (slot);
                            Array.set (result, i, slotClone);
                        }
                    }
                }
                
                return result;
            }
        }
        else if (FINAL_IMMUTABLE_CLASSES.contains (objClass))
        {
            return obj;
        }
        
        // Fall through to reflectively populating an instance created
        // via a no-arg constructor:
        // clone = objClass.newInstance () can't handle private constructors:
            
        Constructor noarg = objClass.getDeclaredConstructor (EMPTY_CLASS_ARRAY);
        if ((Modifier.PUBLIC & noarg.getModifiers ()) == 0)
        {
            noarg.setAccessible (true);
        }
        result = noarg.newInstance (EMPTY_OBJECT_ARRAY);
        
        for (Class c = objClass; c != Object.class; c = c.getSuperclass ())
        {
            setFields (obj, result, c.getDeclaredFields ());
        }
        
        return result;
    }    
    /**
     * This method copies all declared 'fields' from 'src' to 'dest'.
     * 
     * @param src source object
     * @param dest src's clone [not fully populated yet]
     * @param fields fields to be populated
     */
    private static void setFields (final Object src, final Object dest,
                                   final Field [] fields)
    {
        for (int f = 0, fieldsLength = fields.length; f < fieldsLength; ++ f)
        {            
            final Field field = fields [f];
            final int modifiers = field.getModifiers ();
            
            if ((Modifier.STATIC & modifiers) != 0) continue;
            
            // Can also skip transient fields here if you want reflective
            // cloning to be more like serialization.
            
            if ((Modifier.FINAL & modifiers) != 0)
                throw new RuntimeException ("cannot set final field" +
                field.getName () + " of class " + src.getClass ().getName ());
            
            if ((Modifier.PUBLIC & modifiers) == 0) field.setAccessible (true);
            
            Object value = field.get (src);
            
            if (value == null)
                field.set (dest, null);
            else
            {
                final Class valueType = value.getClass ();
                
                if (! valueType.isPrimitive () &&
                    ! FINAL_IMMUTABLE_CLASSES.contains (valueType))
                {
                    // Value is an object reference, and it could be either an
                    // array or of some mutable type: try to clone it deeply
                    // to be on the safe side.
                        
                    value = clone (value);
                }
                
                field.set (dest, value);
            }
        }
    }
 
    private static final Set FINAL_IMMUTABLE_CLASSES; // Set in 
    private static final Object [] EMPTY_OBJECT_ARRAY = new Object [0];
    private static final Class [] EMPTY_CLASS_ARRAY = new Class [0];
    
    static
    {
        FINAL_IMMUTABLE_CLASSES = new HashSet (17);
        
        // Add some common final/immutable classes:
        FINAL_IMMUTABLE_CLASSES.add (String.class);
        FINAL_IMMUTABLE_CLASSES.add (Byte.class);
        ...
        FINAL_IMMUTABLE_CLASSES.add (Boolean.class);
    }
} // End of class

Note the use of java.lang.reflect.AccessibleObject.setAccessible() to gain access to nonpublic fields. Of course, this requires sufficient security privileges.

Since the introduction of JDK 1.3, setting final fields via reflection is no longer possible (see Note 1 in Resources); so, this approach resembles Approach 1 because it can't handle final fields. Note also that inner classes cannot have no-arg constructors by definition (see Note 2 in Resources), so this approach will not work for them either.

Coupled with the no-arg constructor requirement, this approach restricts the type of classes it can handle. But you would be surprised how far it can go. The full implementation adds a few useful features. While traversing the object graph rooted at the source object, it keeps an internal objMap parameter that maps values in source object graphs to their respective clones in the cloned graphs. This restores the ability to preserve object graphs that I had in Approach 3. Also, the metadataMap parameter caches class metadata for all classes that it encounters while cloning an object and improves performance by avoiding slow reflection. The relevant data structures are scoped to a single call to clone(), and the overall idea is very similar to Java serialization revamped to just do object cloning. Similar to the previous section, a whole hierarchy of suitable classes can be made cloneable by equipping the base class with one generic method:

    public Object clone ()
    {
        return ReflectiveClone.clone (this);
    }

What is this method's performance? Rerunning the test with the REFLECTION branch selected produces:

clone implementation: reflection
method duration: 0.537 ms

This is roughly five times faster than straightforward serialization—not too bad for another generic approach. In terms of its performance and capabilities, it represents a compromise between the other three solutions. It can work very well for JavaBean-like classes and other types that usually do not have final fields.

Resource considerations

Measuring memory overhead is more difficult than measuring performance. It should be obvious that the first two approaches shine in this area, as they instantiate only the data that will populate the cloned fields.

Cloning via serialization has an extra drawback that may have escaped your attention above. Even though serializing an object preserves the structure of the object graph rooted at that instance, immutable values will get duplicated across disjoint calls to clone(). As an example, you can verify for yourself that

    TestClass obj = new TestClass ("dummy");
    System.out.println (obj.m_string == ((TestClass) obj.clone ()).m_string);

will print false for Approach 3

only

. Thus, cloning via serialization will have a tendency to pollute heap with redundant copies of immutable objects like

String

s. Approaches 1 and 2 are completely free from this problem, and Approach 3 is mostly free from it.

A quick and dirty proof of these observations can be seen by changing the body of Main.main() to keep the clones in memory and track the object count when a given heap size is reached:

        int count = 0;
        List list = new LinkedList ();
        try
        {
            while (true)
            {
                list.add (obj.clone ());
                ++ count;
            }
        }
        catch (Throwable t)
        {
            System.out.println ("count = " + count);
        }

Run this in a JVM with a -Xmx8m setting and you will see something similar to this:

>java -Xmx8m Main
clone implementation: Object.clone()
count = 5978 Exception in thread "main" java.lang.OutOfMemoryError
...
clone implementation: copy construction
count = 5978
...
clone implementation: serialization
count = 747
...
clone implementation: reflection
count = 5952

Approach 3's overhead increases with the number of immutable fields in a class. Removing this overhead is nontrivial.

The recap

The following table recaps the properties of all cloning approaches in this article from several perspectives: speed, resource utilization, class design constraints, object graph handling.

Object.clone()
Speed High
Resource utilization Low
Class design constraints Does not work with deep final fields; does not work with inner classes; must implement Cloneable; medium amount of manual class maintenance
Object graphs Does not handle object graphs transparently
Copy construction
Speed High
Resource utilization Low
Class design constraints Superclasses and subclasses must cooperate; copy constructor required; a lot of manual class maintenance
Object graphs Does not handle object graphs transparently
Serialization
Speed Low
Resource utilization High; creates redundant immutable fields
Class design constraints Must implement Serializable; first non-Serializable class needs an accessible no-arg constuctor
Object graphs Handles object graphs
Reflection
Speed Medium
Resource utilization Medium
Class design constraints Does not work with final fields; does not work with inner classes; each class must provide no-arg constructor
Object graphs Handles object graphs

This article discussed implementing a single method, Object.clone(). It is amazing that a single method can have so many implementation choices and subtle points. I hope this article provided you with some food for thought and useful guidelines for your application class design.

Vladimir Roubtsov has programmed in a variety of languages for more than 12 years, including Java since 1995. Currently, he develops enterprise software as a senior developer for Trilogy in Austin, Texas.

Learn more about this topic

Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more