slowness in copy of integer sparse matrices

[Frédéric Chapoton]

Hello,

With sage 8.9.b7 under py3, I get

sage: P = posets.TamariLattice(8)
sage: H = P._hasse_diagram
sage: L = H.lequal_matrix()
sage: %time copy(L)
CPU times: user 2.71 s, sys: 4.01 ms, total: 2.71 s
Wall time: 2.71 s
1430 x 1430 sparse matrix over Integer Ring (use the '.str()' method to see the entries)

And this seems to me to be a bit too much. But maybe I am wrong ? This comes from here:

sage: ms = L.parent()
sage: ec = ms.element_class
sage: d = L.dict()
sage: %timeit ec(ms, entries=d, coerce=False, copy=False)
1 loop, best of 5: 2.63 s per loop

Any idea on what is happening ? on how to improve the situation ?

cheers,

Frédéric

[Nils Bruin]

It seems to be spending a lot of time in cython code, so "%crun" might give the best idea. This is part of the profile obtained by running the "copy" command 20 times:

       0   0.0%   1.3%     2575  98.2% __pyx_pw_4sage_6matrix_21matrix_integer_sparse_21Matrix_integer_sparse_5__init__
      27   1.0%   2.4%     2271  86.6% __pyx_f_4sage_7modules_21vector_integer_sparse_mpz_vector_set_entry
       0   0.0%   2.4%     1719  65.6% PyRun_FileExFlags
      24   0.9%   3.3%     1290  49.2% __pyx_f_4sage_7modules_21vector_integer_sparse_allocate_mpz_vector
     213   8.1%  11.4%     1201  45.8% sig_malloc (inline)
       0   0.0%  11.4%     1193  45.5% PyRun_SimpleFileExFlags
      27   1.0%  12.4%      957  36.5% __gmpz_init
      38   1.4%  13.9%      930  35.5% __pyx_f_4sage_3ext_6memory_sage_sig_malloc
     316  12.1%  25.9%      828  31.6% __GI___libc_malloc
     163   6.2%  32.2%      751  28.7% sig_free (inline)
       5   0.2%  32.4%      733  28.0% __pyx_f_4sage_3ext_6memory_sage_sig_free
       0   0.0%  32.4%      705  26.9% Py_Main
     323  12.3%  44.7%      512  19.5% _int_malloc
     336  12.8%  57.5%      340  13.0% _int_free
     334  12.7%  70.2%      334  12.7% sig_unblock (inline)

 There's no obvious culprit to my eye. It looks like a lot of time is spent in memory allocation and in setting of entries. Using a boolean matrix could be much more efficient.

[Simon King]

Hi all,

did someone open a ticket for that issue?

Best regards,
Simon

[Frédéric Chapoton]

I can create a ticket, but I would like first to be sure that is a real issue.

Frédéric

[E. Madison Bray]

On Tue, Aug 27, 2019 at 3:19 PM Frédéric Chapoton <fchap...@gmail.com> wrote:
>
> I can create a ticket, but I would like first to be sure that is a real issue.

Do you have any previous benchmarks to compare it to? Even if you
think, for some reason (?) that it's "too slow" I don't know that it's
that meaningful a statement without something to compare to...

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/76162260-12ec-44a7-b0da-14d61e1ce552%40googlegroups.com.

[Nils Bruin]

On Tuesday, August 27, 2019 at 9:29:31 AM UTC-7, E. Madison Bray wrote:

On Tue, Aug 27, 2019 at 3:19 PM Frédéric Chapoton <fchap...@gmail.com> wrote:
>
> I can create a ticket, but I would like first to be sure that is a real issue.

Do you have any previous benchmarks to compare it to?  Even if you
think, for some reason (?) that it's "too slow" I don't know that it's
that meaningful a statement without something to compare to...

It seems to me that copying a sparse matrix of this size can be done WAY faster. It can definitely be done by implementing a special-purpose copying routine for this class of sparse matrices, but it might be worth seeing if the generic code can be sped up already.

Basis for my claim that this can be done is based on the amount of data involved. It is a 1430x1430 sparse matrix, with entries from {0,1} (yet represented by a matrix over the integers), with on average 83 nonzero entries per row. So the matrix has a fill ratio of about 5%. Not supersparse, but definitely deserves the name.

One thing is that creating a dense matrix out of it is already faster and then copying that is WAY faster:

sage: %time Lc=copy(L)
CPU times: user 1.36 s, sys: 7.55 ms, total: 1.37 s
Wall time: 1.37 s
sage: %time M=L.dense_matrix()
CPU times: user 420 ms, sys: 5.9 ms, total: 426 ms
Wall time: 427 ms
sage: %time Mc=copy(M)
CPU times: user 14.5 ms, sys: 0 ns, total: 14.5 ms
Wall time: 14.7 ms

Creating similar data in a non-optimized way is also way faster. The following makes a location-value type list representation of the matrix (also as a dict):

sage: %time v=[(i,j,1) for i in [0..1429] for j in [0..82]]
CPU times: user 96.9 ms, sys: 13.2 ms, total: 110 ms
Wall time: 105 ms
sage: %time v={(i,j):1 for i in [0..1429] for j in [0..82]}
CPU times: user 125 ms, sys: 25.6 ms, total: 150 ms
Wall time: 132 ms

and as a row-sparse list presentation:

sage: %time v=[(i,j,1) for i in [0..1429] for j in [0..82]]
CPU times: user 96.9 ms, sys: 13.2 ms, total: 110 ms
Wall time: 105 ms
sage: %time v={(i,j):1 for i in [0..1429] for j in [0..82]}
CPU times: user 125 ms, sys: 25.6 ms, total: 150 ms
Wall time: 132 ms

Based on this, I'm convinced a factor 10 speed-up is very easily attained. Based on the copying of the dense one, possibly a factor 100.

[Nils Bruin]

On Tuesday, August 27, 2019 at 10:40:53 AM UTC-7, Nils Bruin wrote:

and as a row-sparse list presentation:

sage: %time v=[(i,j,1) for i in [0..1429] for j in [0..82]]
CPU times: user 96.9 ms, sys: 13.2 ms, total: 110 ms
Wall time: 105 ms
sage: %time v={(i,j):1 for i in [0..1429] for j in [0..82]}
CPU times: user 125 ms, sys: 25.6 ms, total: 150 ms
Wall time: 132 ms

Sorry; copy-paste problem. This was supposed to be:

sage: %time v=[[(j,1) for j in [0..82]] for i in [0..1429]]
CPU times: user 169 ms, sys: 7.19 ms, total: 176 ms
Wall time: 170 ms