2
$\begingroup$

Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them.

  • Reflection-based (Python)
  • Auto-generated shallow-copy-based (Java)
  • Compiler-generated polymorphic deep copy (anybody?)

The last one seems to be the most efficient one, but I do not know if it is implemented anywhere.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

You have to be very careful of what you mean when you say "deep-copying". This came up in a thread at StackOverflow in relation to C++. The first question you need to address is can an automatic "deep-copy" even be done? Consider just a few basic quesetions:

  1. If the type of a data element is a referential type can you determine whether a deep copy implies copying the reference or the referred to type? That is, can you identify the ownership of these items?
  2. Does the presence of a singleton, or external resource, prevent a deep copy, or does the copy refer to the same resource?
  3. Given that data relations often form graphs with cycles. Could such a relationship automatically be detected? Even if yes, what would if mean to start the deep copy at an inner-node of such a structure?

This is likely why you only find references which are very language specific. Each language has its own notion of copying. This default copy is not likely to match the expected notion of a deep-copy in all situations.

I would say it is not possible to even specify what deep-copy is without explicitly enumerating the types available in a given language. This would essentially require that all research about deep-copying is specific to a particular language (even if that language is theoretical).

If you are looking for efficiency comparisons you would then also be stuck in the domain of a very particular language. You could possible define a reduced compound data type common to several languages and evaluate the efficiency of copying such structures. Such results however would not be applicable to any language with more complex data types.

Improve this answer
$\endgroup$
3
  • $\begingroup$ For Java, C#, etc the automatic deep-copy is usually implemented via deserialize(serialize(original)). For some objects (Singleton, Lock, FileHandle, ...) this just fails with an exception. Cycle-detection is of course necessary, just like serialize does it. I don't understand what the problem with references is. $\endgroup$
    – qznc
    Commented Jun 14, 2012 at 12:09
  • $\begingroup$ Reference example: You have a master container of objects and then create sub-containers with references to the original objects. If you clone these sub-containers you'd expect to get references to the master and not clones of the elements. That is, sometimes the data reference is the data itself. $\endgroup$
    – edA-qa mort-ora-y
    Commented Jun 14, 2012 at 13:31
  • $\begingroup$ I don't think automated deep copying of types that don't contain cyclic references would be a problem if there were a way of marking which references encapsulate identity, unshared mutable state, both or neither. Unfortunately, Java uses one type of "reference" for everything, and references which encapsulate unshared mutable state must be treated differently from those which identify shared entities. $\endgroup$
    – supercat
    Commented Feb 15, 2014 at 5:26
1
$\begingroup$

Partial answer for functional languages:

In Ocaml, I believe this could be done even at runtime, because even if types are removed, we know if a word is a pointer or some data. However, it is not that good of an idea, because in the pure part of Ocaml (which is often well-understood) you don't need deep copy: the data structures are not mutable, thus deep copy will have no other effect than occupying more memory. It is all the more true for pure functional programming languages like Haskell.

About the types:

Note that despite the fact that it is useless for functional languages, the typing information there is in those would be enough to provide a compile-time-generated deep copy generic functions. (But not polymorphic, the copy function needs to be aware of types).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I never really used Ocaml, but I assume it is capable of mutable data. Otherwise it would be impossible to implement algorithms like Quicksort, which works in-place. In Java you would specialize the deep copy for immutable objects to simply return the identical object. $\endgroup$
    – qznc
    Commented Jun 14, 2012 at 12:14
  • $\begingroup$ @qznc: Sure there are but you know you have to be careful with them. (For example, the in-place version of quicksort is with an array. But in Ocaml you prefer the not in-place version). This was just to say it was not necessary.* $\endgroup$
    – jmad
    Commented Jun 14, 2012 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.