`setcoeff!` should not take ownership of coefficient arg

[felix-roehrich]

Currently, setcoeff! for Generic.Poly, Generic.MPoly, Generic.NCPoly and Generic.RelSeries takes ownership of coefficient passed as argument. However, this is not documented as parted of the corresponding interfaces and neither does FLINT behave in this way. Additionally, the behaviour changes implicitly depending on whether the argument is immutable or not, making it hard to reason and may lead to unexpected results. Finally, some of the current code is already broken with respect to this issue; for example the generic shift_left and shift_right for univariate polys has setcoeff!(r, i + n - 1, coeff(f, i - 1)).

For these reasons I believe that setcoeff! should not take ownership of the argument.

[lgoettgens]

my two cents: this is currently completely broken and I fully agree with @felix-roehrich here.

MWE:

julia> R, _ = residue_ring(ZZ, 5)
(Residue ring of integers modulo 5, Map: integers -> R)

julia> Rx, x = polynomial_ring(R)
(Univariate polynomial ring in x over R, x)

julia> f = x^2 + x + 1
x^2 + x + 1

julia> g = shift_left(f, 1)
x^3 + x^2 + x

julia> g = add!(g, x)
x^3 + x^2 + 2*x

julia> f
x^2 + x + 2

Doing mutable arithmetic on the result g of shift_left (without exclamation mark) should not modify f!

[lgoettgens]

ping @thofma @fingolfin for their opinion

[thofma]

this (the MWE of @lgoettgens) is expected, see https://nemocas.github.io/Nemo.jl/stable/developer/topics/#Aliasing-rules

[lgoettgens]

this (the MWE of @lgoettgens) is expected, see nemocas.github.io/Nemo.jl/stable/developer/topics#Aliasing-rules

I would say that the following except from the aliasing rules is not fulfilled by the standard implementation of shift_left/right

Note that this implies that setcoeff! should not be passed an element that aliases another somewhere else, even in part

[felix-roehrich]

this (the MWE of @lgoettgens) is expected, see https://nemocas.github.io/Nemo.jl/stable/developer/topics/#Aliasing-rules

This is part of the Nemo documentation, but the AA documentation has no mention of this, so I would not say this is expected. Furthermore the FLINT set_coeff variants do not have aliasing issues and handle this properly, so the warning for Nemo in particular is completely pointless.

[thofma]

This was added in https://github.com/Nemocas/Nemo.jl/issues/278, a time when there was no AA, but everything was part of Nemo. The documentation has not made it through the split very well.

The shift_left implementations are wrong as you and @lgoettgens noticed and should be fixed.

[felix-roehrich]

After skimming through abouth 20% of setcoeff! uses (in AA alone) I found this non exhaustive list, having the same bug. This is such a common mistake and I repeat that FLINT deals with this properly. Furthermore, to be on the safe side you always need to make a deepcopy, which in many cases causes unnecessary allocations.

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/AbsSeries.jl#L95-L101

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L984-L997

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1129-L1138

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1277-L1283

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1299-L1305

[fieker]

Flint does not deal with this at all, it follows from other parts of the design. But why is setcoeff at fault and not getcoeff? I am happy to discuss things next week, but we're not going to rewrite oscar, we cannot afford to. Mutating operations are all unsafe if you do not precisely know what you are doing. And even then... But they are essential to speed

On Wed, 19 Mar 2025, 17:02 Felix Röhrich, @.***> wrote:

After skimming through abouth 10% of setcoeff! uses I found this non exhaustive list, having the same bug. This is such a common mistake and I repeat that FLINT deals with this properly. Furthermore, to be on the safe side you always need to make a deepcopy, which in many cases causes unnecessary allocations.

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/AbsSeries.jl#L95-L101

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L984-L997

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1129-L1138

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1277-L1283

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1299-L1305

— Reply to this email directly, view it on GitHub https://github.com/Nemocas/AbstractAlgebra.jl/issues/2041#issuecomment-2737204464, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA36CV56MTWK6N3W2G2NVM32VGIKBAVCNFSM6AAAAABZLBNYGKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMZXGIYDINBWGQ . You are receiving this because you are subscribed to this thread.Message ID: @.***> [image: felix-roehrich]felix-roehrich left a comment (Nemocas/AbstractAlgebra.jl#2041) https://github.com/Nemocas/AbstractAlgebra.jl/issues/2041#issuecomment-2737204464

After skimming through abouth 10% of setcoeff! uses I found this non exhaustive list, having the same bug. This is such a common mistake and I repeat that FLINT deals with this properly. Furthermore, to be on the safe side you always need to make a deepcopy, which in many cases causes unnecessary allocations.

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/AbsSeries.jl#L95-L101

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L984-L997

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1129-L1138

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1277-L1283

https://github.com/Nemocas/AbstractAlgebra.jl/blob/1b1f18d39601515635e8cd3c2ff38eff14753a2b/src/Poly.jl#L1299-L1305

— Reply to this email directly, view it on GitHub https://github.com/Nemocas/AbstractAlgebra.jl/issues/2041#issuecomment-2737204464, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA36CV56MTWK6N3W2G2NVM32VGIKBAVCNFSM6AAAAABZLBNYGKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMZXGIYDINBWGQ . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[felix-roehrich]

but we're not going to rewrite oscar, we cannot afford to

setcoeff! is used a total of 4 times in OSCAR and OSCAR also mainly relies on FLINT that is reason this remained undiscovered until now.

But they are essential to speed

The current setcoeff! does not reuse allocated memory, which means it is generally slower than the behaviour I imagine/want.

[thofma]

setcoeff! is used a total of 4 times in OSCAR and OSCAR also mainly relies on FLINT that is reason this remained undiscovered until now.

By OSCAR we mean the OSCAR ecosystem. There are > 100 occurrences in Hecke.

But they are essential to speed

The current setcoeff! does not reuse allocated memory, which means it is generally slower than the behaviour I imagine/want.

The current setcoeff! does not allocate anything. It is basically just setting a pointer.

Regarding the FLINT interface: The interface with FLINT is very inefficient and unergonomic. Trying to use it efficiently in the current form is prone to memory leaks or corruption. (And writing "generic" code is awkward.) I think it should not be an inspiration.

@lgoettgens I am trying to wrap my head around aliasing & mutation rules. Small thought experiment: Let's for a moment suppose that the aliasing rule is that no coefficients within one polynomial alias each other. From looking at the code, it seems that no functions creates illegal polynomials given legal polynomials. Would agree? Then your MWE would be caused by calling a mutating function on something that the caller does not own (i.e., something not created by R(), zero, +, *, /, -). Would that make sense in this hypothetical world?

[lgoettgens]

@lgoettgens I am trying to wrap my head around aliasing & mutation rules. Small thought experiment: Let's for a moment suppose that the aliasing rule is that no coefficients within one polynomial alias each other.

That is part of the rules (Other objects, e.g. polynomials, series, etc., are constructed from objects that do not alias one another, even in part)

From looking at the code, it seems that no functions creates illegal polynomials given legal polynomials. Would agree? Then your MWE would be caused by calling a mutating function on something that the caller does not own (i.e., something not created by R(), zero, +, *, /, -). Would that make sense in this hypothetical world?

Yes, that is exactly my reasoning above. setcoeff! takes ownership of the passed coeff, but shift_left uses a coefficient it does not have ownership over. So with the current formulation of the aliasing rules, shift_left should make a copy of the coefficient to pass to setcoeff!.

(This is different from the original motivation of this issue to change aliasing rules/ownership handling, but fixes the MWE.)

[felix-roehrich]

The current setcoeff! does not allocate anything. It is basically just setting a pointer.

Let's look at reverse!(z, x, length(x)) as example. To fix this function I would have to write setcoeff!(z, i-1, deepcopy(coeff(x, len-i))). The deepcopy does allocate, regardless if coeff(z, i-1) is allocated or not. In the case where z has the same length as x the current version needs to allocate length(x) times the number of allocations needed for a coefficient, where instead the coefficients of z could just be "set" to the passed value, causing no allocations.

Also I want to point out that this change is backward compatible. The alternative is to look at every setcoeff! use and check if this need a deepcopy or not.

[thofma]

That is part of the rules (Other objects, e.g. polynomials, series, etc., are constructed from objects that do not alias one another, even in part)

No, the written down rule is much stricter. I was trying to argue that the current implementations satisfy the mentioned weaker rule.

From looking at the code, it seems that no functions creates illegal polynomials given legal polynomials. Would agree? Then your MWE would be caused by calling a mutating function on something that the caller does not own (i.e., something not created by R(), zero, +, *, /, -). Would that make sense in this hypothetical world?

Yes, that is exactly my reasoning above. setcoeff! takes ownership of the passed coeff, but shift_left uses a coefficient it does not have ownership over. So with the current formulation of the aliasing rules, shift_left should make a copy of the coefficient to pass to setcoeff!.

OK. Do you agree that your example is still a non-example, since you are calling a mutating function on a thing you do not own? There is no guarantee that shift(f, ...) returns something that you are allowed to mutate, right?

[lgoettgens]

From looking at the code, it seems that no functions creates illegal polynomials given legal polynomials. Would agree? Then your MWE would be caused by calling a mutating function on something that the caller does not own (i.e., something not created by R(), zero, +, *, /, -). Would that make sense in this hypothetical world?

Yes, that is exactly my reasoning above. setcoeff! takes ownership of the passed coeff, but shift_left uses a coefficient it does not have ownership over. So with the current formulation of the aliasing rules, shift_left should make a copy of the coefficient to pass to setcoeff!.

OK. Do you agree that your example is still a non-example, since you are calling a mutating function on a thing you do not own? There is no guarantee that shift(f, ...) returns something that you are allowed to mutate, right?

IMO there is not enough documentation to decide that. Is shift_left an arithmetic operation, even though it is not listed explicitly in https://nemocas.github.io/Nemo.jl/stable/developer/topics/#Arithmetic-operations-return-a-new-object ?

All other functions may also return the input object if they wish.

This does not apply here, as it returns a different object that aliases the input.

In other words, the return value of all other functions is not suitable for use in an unsafe function.

This explains the current behaviour. However, it is not a reformulation nor an implication of the previous sentence. Other objects, e.g. polynomials, series, etc., are constructed from objects that do not alias one another, even in part contradicts the existence of polys that partially alias each other, but are not identical.

Iiuc, this is also how it is in FLINT: Two objects may be identical, or don't alias at all. Such a kind of partial aliasing is not supported there. This is also the reason why e.g. fmpz_poly_set_coeff_fmpz does not use the input directly, but instead calls fmpz_set which copies the input.

And our users (neither AA nor Oscar users) will ever find that in the deepness of Nemo dev docs.

[thofma]

IMO there is not enough documentation to decide that. Is shift_left an arithmetic operation, even though it is not listed explicitly in https://nemocas.github.io/Nemo.jl/stable/developer/topics/#Arithmetic-operations-return-a-new-object ?

I think there is enough documentation to conclude that shift_left is not an arithmetic operation. There is an exhaustive list of arithmetic operations and shift_left is not part of it.

Let me quote from the creator of FLINT and AbstractAlgebra and Nemo (https://nemocas.github.io/Nemo.jl/stable/developer/topics/#Aliasing-rules-and-mutation):

We have developed over a period of many years a set of rules that maximise the performance benefit we get from our unsafe operators, whilst keeping the burden imposed on the programmer to a minimum. It has been a very difficult task to arrive at the set of rules we have whilst respecting correctness of our code, and it would be extremely hard to change any of them.

[lgoettgens]

There is an exhaustive list of arithmetic operations and shift_left is not part of it.

There are a lot of uses of mutating arithmetic downstream that mutate things that come not from one of these few functions. All of these would need to be revisited and changed, thus hurting performance there. Just mentioning a few from different areas:

• https://github.com/oscar-system/Oscar.jl/blob/7775a3af4c3cca531bbad5f44f93ef0458f6ca0e/examples/PerfectPowers.jl#L75
• https://github.com/oscar-system/Oscar.jl/blob/4be79ac7aad5038afc8c5dce96010ad5f5ca010a/experimental/GModule/src/Misc.jl#L323
• https://github.com/oscar-system/Oscar.jl/blob/edbdb5fb682443235f08564c79d9b40dfee99cb5/experimental/QuadFormAndIsom/src/embeddings.jl#L135
• https://github.com/oscar-system/Oscar.jl/blob/1fd761305abfff8630c9ce0e6a8b41a07d5389dc/src/AlgebraicGeometry/Surfaces/K3Auto.jl#L1052
• https://github.com/oscar-system/Oscar.jl/blob/e827584db3c5e46edc29d20d5404abbfc19f2608/src/Rings/oscar_singular.jl#L100

I don't want to blame anyone for these code snippets, I also tripped in this (but could not find an example this fast). The list of functions that guarantee to return a new object IMO at least misses zero, one, zero_matrix, just to name a few.

[thofma]

I think there is a difference between writing generic code for RingElement and examples of the form

my_function(x::ZZRingElem) = x^2

function my_other_function(x::ZZRingElem)
  y = my_other_function(x)
  mul!(y, y, y)
return y

I guess the unwritten rule is that if I know more about the input, I can assume more about what is allowed? I know that this is not ideal, but it is part of the aforementioned compromise.