Reviewer patch for #16803

[jdemeyer]

Various fixes/improvements/clean-ups after #16803.

CC: @vbraun @mmasdeu @williamstein @simon-king-jena

Component: linear algebra

Author: Volker Braun, Jeroen Demeyer

Branch/Commit: c46a4d5

Reviewer: Volker Braun, Jeroen Demeyer

Issue created by migration from https://trac.sagemath.org/ticket/17090

[vbraun]

comment:3

Flint has a --enable-assert configure switch to turn on assertions which should be handy for debugging.

[simon-king-jena]

comment:4

Replying to @vbraun:

Flint has a --enable-assert configure switch to turn on assertions which should be handy for debugging.

... which should become part of #16938, right?

[vbraun]

comment:5

I'd prefer to add it here, there is already too much going on at #16938

[vbraun]

Branch: u/vbraun/add_missing_fmpz_init

[vbraun]

Commit: df10459

[vbraun]

comment:7

Turns out assertions aren't used that much in flint, I still can't reproduce the crash.

---

New commits:

6f2750e	Never build static library
df10459	Enable flint assertions

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1 +1,27 @@
-The code from #16803 is missing `fmpz_init()`/`fmpz_clear()` in several places. This can cause random segfaults, as witnessed for example in #16938.
+The code from #16803 is missing `fmpz_init()`/`fmpz_clear()` in `_lmul_` (and perhaps other places too). This can cause random segfaults and memory leaks, as witnessed for example in #16938.
+
+The code in question:
+
+```
+    cpdef ModuleElement _lmul_(self, RingElement right):
+        """
+        EXAMPLES::
+
+            sage: a = matrix(QQ,2,range(6))
+            sage: (3/4) * a
+            [   0  3/4  3/2]
+            [ 9/4    3 15/4]
+        """
+        cdef Py_ssize_t i
+        cdef Integer _x
+        cdef fmpz_t z
+        _x = Integer(right)
+        cdef Matrix_integer_dense M
+        M = self._new_uninitialized_matrix(self._nrows,self._ncols)
+        sig_on()
+        fmpz_set_mpz(z,_x.value)
+        fmpz_mat_scalar_mul_fmpz(M._matrix,self._matrix,z)
+        sig_off()
+        M._initialized = True
+        return M
+```

[jdemeyer]

comment:9

The problem is that an assertion won't help against uninitialized variables.

[simon-king-jena]

comment:10

Replying to @jdemeyer:

The problem is that an assertion won't help against uninitialized variables.

And I thought a debug version would have a paranoid memory management, so that the use of uninitialised variables would result in an immediate abort.

[simon-king-jena]

comment:11

Why not building a static library, by the way?

[vbraun]

comment:12

Because static libraries suck. If you rebuild flint with debugging, is Sage going to use the new shared library or have the old static library compiled in?

[vbraun]

comment:13

And yes, I had hoped that flint had some mechanism to ensure that *_init is called, but no such luck.

[jdemeyer]

Changed branch from u/vbraun/add_missing_fmpz_init to u/jdemeyer/ticket/17090

[jdemeyer]

comment:15

This should fix the problem, but I haven't tested it wth #16938.

---

New commits:

7b38491

Fix initialization of fmpz_t

[jdemeyer]

Changed commit from df10459 to 7b38491

[simon-king-jena]

comment:16

Concerning

+ fmpz_init(z)
+ fmpz_set_mpz(z, x.value)

Is there no fmpz_init_set? I know that there is a combined init-set function for mpz, but I don't know about fmpz.

[vbraun]

comment:17

There is:

$ grep fmpz_init_set flint-2.4.3/fmpz.h 
void fmpz_init_set(fmpz_t f, const fmpz_t g)
void fmpz_init_set_ui(fmpz_t f, ulong g)
void fmpz_init_set_readonly(fmpz_t f, const mpz_t z);

[simon-king-jena]

comment:18

Replying to @vbraun:

There is:

$ grep fmpz_init_set flint-2.4.3/fmpz.h 
void fmpz_init_set(fmpz_t f, const fmpz_t g)
void fmpz_init_set_ui(fmpz_t f, ulong g)
void fmpz_init_set_readonly(fmpz_t f, const mpz_t z);

I think it should be used.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1,27 +1 @@
-The code from #16803 is missing `fmpz_init()`/`fmpz_clear()` in `_lmul_` (and perhaps other places too). This can cause random segfaults and memory leaks, as witnessed for example in #16938.
-
-The code in question:
-
-```
-    cpdef ModuleElement _lmul_(self, RingElement right):
-        """
-        EXAMPLES::
-
-            sage: a = matrix(QQ,2,range(6))
-            sage: (3/4) * a
-            [   0  3/4  3/2]
-            [ 9/4    3 15/4]
-        """
-        cdef Py_ssize_t i
-        cdef Integer _x
-        cdef fmpz_t z
-        _x = Integer(right)
-        cdef Matrix_integer_dense M
-        M = self._new_uninitialized_matrix(self._nrows,self._ncols)
-        sig_on()
-        fmpz_set_mpz(z,_x.value)
-        fmpz_mat_scalar_mul_fmpz(M._matrix,self._matrix,z)
-        sig_off()
-        M._initialized = True
-        return M
-```
+Various fixes/improvements/clean-ups after #16803.

[vbraun]

comment:20

This branch fixes all valgrind warnings from matrix_integer_dense (when running benchmark_hnf)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

8a16a8e

Further clean-up

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7b38491 to 8a16a8e

[jdemeyer]

comment:22

Replying to @simon-king-jena:

I think it should be used.

Done

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e5f684b

Remove unused code

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8a16a8e to e5f684b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9b31003

Check 'implementation' argument

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e5f684b to 9b31003

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

a2860d8

Undo changes to padics from #16803

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9b31003 to a2860d8

[jdemeyer]

Author: Volker Braun, Jeroen Demeyer

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

342d152

Remove unneeded imports

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a2860d8 to 342d152

[williamstein]

comment:29

Why did you delete the following functions:

_multiply_linbox
_multiply_multi_modular
_det_pari

[jdemeyer]

comment:30

Replying to @williamstein:

Why did you delete the following functions:

_multiply_linbox
_multiply_multi_modular

These were simply unused. If you think we should keep them "for reference", there is always the git log.

And _det_pari was copied in #16803, I just deleted one of the two copies.

[williamstein]

comment:31

Replying to @jdemeyer:

Replying to @williamstein:

Why did you delete the following functions:

_multiply_linbox
_multiply_multi_modular

These were simply unused. If you think we should keep them "for reference", there is always the git log.

I'm against removing them. Just because they aren't explicitly used elsewhere in Sage, doesn't mean they aren't useful to have. For example,

• I used them in testing the original patch (having multiple ways of computing products in order to compare) that this is following up on.

• At one time Linbox was the fastest for multiplying matrices (at least in 2007, when Clement Pernet was my postdoc at UW). Now it's terrible, at least as it is built in Sage. Having the function _multiply_linbox makes it easier to test the speed of linbox versus flint (or multimodular) at any point. If you remove it, then suddenly this becomes more difficult. It's entirely plausible that linbox could again become faster than FLINT, and it would be more difficult to know without this function.

• I personally don't trust FLINT, and having an easy alternative to test (or swap out for) matrix multiplication makes me happier. I remember clearly times in the past when FLINT gave flat out wrong answers when multiplying large polynomials (burried deep in some p-adic cohomology calculations), and -- when tracking this down -- being able to instrument things so we could easily run the whole big computation with either FLINT or PARI was critical.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 342d152 to 5b77c78

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

95b431d	Put back old multiplication code (as requested by William Stein)
5b77c78	Restore doctest

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5b77c78 to 7843e3f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

7843e3f

Fix fmpz_mat_t declaration

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7843e3f to c46a4d5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

192c8e6	Missing comma between command-line arguments
9604069	Merge commit '192c8e6f5c6e5f0bd0dd02d51b5f103924a408ef' into ticket/17090
c46a4d5	Some reformatting

[jdemeyer]

comment:35

I am going to leave this branch alone for now, please review! There is another follow-up at #17094.

[jdemeyer]

comment:36

Replying to @williamstein:

Why did you delete the following functions:

_multiply_linbox

Here's a better reason: it's broken!

sage: A = identity_matrix(ZZ,3)
sage: A._multiply_linbox(A)
[0 0 0]
[0 0 0]
[0 0 0]

Fixing this at #17094...

[jdemeyer]

comment:37

Replying to @vbraun:

And yes, I had hoped that flint had some mechanism to ensure that *_init is called, but no such luck.

In C, this simply cannot be done. A variable on the stack starts out in a totally unpredictable state.

[vbraun]

comment:38

Replying to @jdemeyer:

In C, this simply cannot be done. A variable on the stack starts out in a totally unpredictable state.

Thats of course, strictly speaking, true. But I would be happy to take my chances with a padding int being initialized to 0xdeadbeef and having a random, but usually different, value if it was not initialized.

[jdemeyer]

comment:39

Replying to @vbraun:

But I would be happy to take my chances with a padding int being initialized to 0xdeadbeef

...if you take care to clear out that 0xdeadbeef after use and assume that the compiler doesn't optimize that clearing away, I guess it would work.

[vbraun]

comment:40

Looks good to me!

[vbraun]

Reviewer: Volker Braun, Jeroen Demeyer

[vbraun]

Changed branch from u/jdemeyer/ticket/17090 to c46a4d5