deepcopy as the default copying mechanism is inefficient

[rfourquet]

deepcopy is supposed to recreate the exact structure of the passed object, including aliasing. For example:

julia> x = big(1); a = [x, x]; b = deepcopy(a)
 2-element Array{BigInt,1}:
 1
 1
julia> b[1] === b[2]
true

To provide this feature, deepcopy creates a dictionary, which is passed to deepcopy_internal, to keep track of the identity of objects which "have been seen so far".

We have some problems with that:

1. we often (always?) ignore the dictionary in our implementations of deepcopy_internal, which makes it non-conformant with the definition;
2. I believe we sometimes use deepcopy to not only take ownership of an object, but also, for a matrix (maybe other objects), we assume all the entries are independant after deepcopy; this is consistent with 1) for what we control, but this is wrong for user-provided matrices which implement deepcopy in a conformant way;
3. this is inneficient: we pay for a feature we don't need (and even need to not have) and ignore; for example:

julia> x = FlintZZ(1);

julia> @btime deepcopy($x);
 83.200 ns (3 allocations: 384 bytes)

julia> function fmpz_set(a::fmpz)
           # creates directly a copy with a ccall to the flint library
           x = fmpz()
           ccall((:fmpz_set, :libflint), Nothing, (Ref{fmpz}, Ref{fmpz}), x, a)
           x
       end

julia> @btime fmpz_set($x);  
  18.568 ns (1 allocation: 16 bytes)

But currently no API is exposed to make a copy of an fmpz besides deepcopy.

In other words, deepcopy doesn't have the needed semantics, which have been shoehorned into this function for convenience, but I think we should move away from it. I propose to introduce a new function, which provides the guaranties we need (point 2. above) and is efficient. We could call it dealias or dealias_copy, or whatever better name. To make the transition easier, it could temporarily default to deepcopy as a first approximation.

As a bonus, I'm pretty sure we could come up with an API which allows to define automatically this recursive dealias_copy for many recursive types, based on 1) copy (which copies the outer structure) and 2) an API to get and set "entries" of an object together with with the information of what constitutes the indices/coefficients of the objects. Then only leave types would have to define dealias_copy, which can then safely (but innefficiently) default to deepcopy.

[fieker]

FlintZZ(a) should make a copy
copy(a) might make a copy
copy_into!(a,b) (in Hecke) will do this...

[rfourquet]

FlintZZ(a) should make a copy

Currently it does not, and it looks like a feature. It allows get an FlintZZ from a without making an unnecessary copy if you don't need.

copy(a) might make a copy

Currently it does not. But I thought a bit more about the problem here, and we actually might be able get away with it (in many cases) by simply requiring defining copy, which has to copy the outer structure of the object. But I will need to understand better the exact semantics of the the mutating functions (addeq! etc.) before coming up with a proposal.

[wbhart]

FlintZZ(a) should make a copy

Fortunately, it does not.

copy(a) might make a copy

I don't think we rely on copy anywhere. And I think it is not a good idea. We once considered it, and we could in fact speed some things up. But because we have inconsistent semantics for mutation due to the crossover from Flint to Julia conventions above basic arithmetic, this would be incredibly hard to do. I think we should just forget about copy.

copy_into!(a,b) (in Hecke) will do this...

I agree that if Hecke already uses copy_into! for this, we should do the same in AbstractAlgebra/Nemo, i.e. exactly the fast version of "deepcopy" that @rfourquet is proposing here.

But it is only a meaningful change if done for all our types, and if it is then used across all our packages. So this is a big job that should not be half done then left. It's also not a high priority, as it isn't currently broken for us, even if it doesn't respect the Julia conventions on deepcopy. Let's focus on closing tickets in order of importance.

I would also consider this change to be breaking, as it means all our packages would need to be updated to use it, and implementing the correct semantics of deepcopy on top of copy_into! would slow things down, so everyone would really want to change their code to avoid the regression.

One other thing: I really don't like fmpz_set(a) returning a copy of a. The name should be something universal. Of course, copy would be ideal, but that has different semantics in Julia. Perhaps full_copy or recursive_copy. I think dealias_copy is too specific, as it refers to one specific reason why you would want to do a full copy, instead of just saying full copy. Something short and memorable would be best. And I don't have any good ideas at the moment. Perhaps clone or duplicate?

[wbhart]

Ah, except that @fieker pointed out that you can't use the new "deepcopy" proposed here because you have to check that more complex types don't refer to themselves recursively, for which the dictionary is needed. So perhaps we must use deepcopy everywhere in generic code after all!

Clearly this needs more thought.

[rfourquet]

Let's focus on closing tickets in order of importance.

This is a pretty serious issue for developers wanting to extend AbstractAlgebra with their types, as for example we request that the parent object is not copied in deepcopy, which is incompatible with the real definition of deepcopy. But indeed this should not affect the regular user too much, which is the target audience for the release of Oscar, so I appreciate this is not top priority.

implementing the correct semantics of deepcopy on top of copy_into! would slow things down

Actually, I believe there is a default implementation of deepcopy_internal for user defined types ((mutable) struct), so typically users don't need to define it themselves.

One other thing: I really don't like fmpz_set(a) returning a copy of a. The name should be something universal.

Of course. My use here of this function (before I removed it) was just a local performant solution to the problem, for the specific need here, without having to overhaul the whole system.

you can't use the new "deepcopy" proposed here because you have to check that more complex types don't refer to themselves recursively, for which the dictionary is needed

Yes I saw this in the documentation, but didn't find yet an example of this, to help me understand more precisely the problem. Would you happen to have the name of such a recursive type off the top of your head?

So perhaps we must use deepcopy everywhere in generic code after all!

If this turns out to be the case (I really hope not!), then we need to settle on a name for the cheaper one, like was needed in this PR (in a non-generic code).

[wbhart]

Let's focus on closing tickets in order of importance.

This is a pretty serious issue for developers wanting to extend AbstractAlgebra with their types, as for example we request that the parent object is not copied in deepcopy, which is incompatible with the real definition of deepcopy. But indeed this should not affect the regular user too much, which is the target audience for the release of Oscar, so I appreciate this is not top priority.

Yes, I didn't say it wasn't worth doing. I said that it isn't anything like the most important open ticket in our project. And as we said today, Oscar is that project. Extending AbstractAlgebra with one's own types is not at all a priority for Oscar. Us Oscar developers understand this well enough, so it isn't affecting us.

implementing the correct semantics of deepcopy on top of copy_into! would slow things down

Actually, I believe there is a default implementation of deepcopy_internal for user defined types ((mutable) struct), so typically users don't need to define it themselves.

Maybe, but it won't work for types corresponding to those in a C library.

you can't use the new "deepcopy" proposed here because you have to check that more complex types don't refer to themselves recursively, for which the dictionary is needed

Yes I saw this in the documentation, but didn't find yet an example of this, to help me understand more precisely the problem. Would you happen to have the name of such a recursive type off the top of your head?

No, but it occurs in Hecke, I believe. And in any event, we certainly need to support this (according to @fieker).

So perhaps we must use deepcopy everywhere in generic code after all!

If this turns out to be the case (I really hope not!), then we need to settle on a name for the cheaper one, like was needed in this PR (in a non-generic code).

We can discuss it at our weekly Oscar meeting.

[fieker]

we require a+deepcopy(a) to work. Since a copy of a parent in general would be a new parent we don't deepcopy them. Julia does not have parents, hence no conventions for them. I could argue that technically deepcopy, fully and completely recursive, should create a new type...
We regard parents as extended types...

[fieker]

The generic needs a (some) functions that one can rely to create new elements - before mutatin is happening. Thus the need for a (shallow) copy.
I can easily construct examples where a copy of levels up to any desired depth would be fine, but in reality one supports copy (as top level) and deepcopy (all the way down)
l = [1,2,:a]
push!(l, l)
will give a (silly) recursive objects.
Since any(?) parnt can accumulate any(?) data in the auxiliary array, I can create it there easily.
Wether this is currently used: don't know, but it is legal

[rfourquet]

a+deepcopy(a) to work. Since a copy of a parent in general would be a new parent we don't deepcopy them.

If deepcopy also deepcopies the parent, it would work.

Julia does not have parents, hence no conventions for them.

As a side note, I argued hard in a Julia PR to implement deepcopy not in a dumb mechanical way, but with some possible performance improvements depending on the semantics. For example, I argued deepcopy(::BigInt) should be a no-op, as a BigInt is semantically immutable (BTW Tommy was not happy with this PR). But it was argued that sometimes you want a "fully independant object" (for example for cache locality), so deepcopy kept it's meaning of "make a fully independant object". If I remember correctly, we kindof of settled on the idea that another function (could be named recursive_copy, or deepcopy with a kwarg switch) could do the more semantic stuff. So deepcopy is, by the current rules, required to create a fully independant object, which respects the subobjects aliasing-relations of the input.

[wbhart]

a+deepcopy(a) to work. Since a copy of a parent in general would be a new parent we don't deepcopy them.

If deepcopy also deepcopies the parent, it would work.

@fieker is saying that it will not work. It's also my understanding. The parents need to be === equal. The deepcopy function does not preserve this, which is why deepcopy does not make copies of the parents.

Julia does not have parents, hence no conventions for them.

As a side note, I argued hard in a Julia PR to implement deepcopy not in a dumb mechanical way, but with some possible performance improvements depending on the semantics. For example, I argued deepcopy(::BigInt) should be a no-op, as a BigInt is semantically immutable (BTW Tommy was not happy with this PR).

Yes, we argued against this. It changes the order of complexity of certain important algorithms if you make BigInt immutable. I also strongly opposed this.

But it was argued that sometimes you want a "fully independant object" (for example for cache locality), so deepcopy kept it's meaning of "make a fully independant object". If I remember correctly, we kindof of settled on the idea that another function (could be named recursive_copy, or deepcopy with a kwarg switch) could do the more semantic stuff. So deepcopy is, by the current rules, required to create a fully independant object, which respects the subobjects aliasing-relations of the input.

As we view the parents as quasi-types, they should retain === equality.

julia> deepcopy(Int) === Int
true

[fieker]

OK, summary and TERMINATING this discussion for now:

• All arguments have merit.
• This does NOT address any of our current problems
• At this point in time, we do not have the resources to change foundations, in particular in such a sensitive area. The Julia semantics of deepcopy changed over the time - at least the documentation and explanations. Some of our decisions were made in the dawn of time. We would do things differently now, BUT CANNOT afford to change this now, nor can we afford to discuss our decisions NOW. They were made, for good or bad. And they had to be made. Now we live by and with them.
  Curently, we have to
• add features
• remove bugs
• document and test
• do NOT worry about improving the code base/ runtime UNLESS there is a supported need case

[rfourquet]

it will not work. It's also my understanding. The parents need to be === equal.

Right, sorry, I forgot temporarily that the == test in some check_parent functions fall back to ===.

It changes the order of complexity of certain important algorithms if you make BigInt immutable.

Sometimes for the better (when you don't intend to mutate the BigInt), that's why I was pushing for this change. But anyway, this belong to another (Julia) issue :)

@fieker I aknowledged above that this is not a priority issue, so I'm not pushing to move away from deepcopy now. However, I was asked to use inefficiently deepcopy in a function, because my solution of using an internal function which does copy an fmpz was not accepted. So I believe it might be possible to come with a good name/API for this function, generic or not, which allows people to do this basic task of duplicating an fmpz efficiently.