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.

$\endgroup$
2
$\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.

$\endgroup$
  • $\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 Jun 14 '12 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 Jun 14 '12 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 Feb 15 '14 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).

$\endgroup$
  • $\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 Jun 14 '12 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 Jun 14 '12 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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