#15104: Special case modn_dense matrix operations to improve performance
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.2
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Nils Bruin | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/nbruin/ticket/15104 | a908e28159a544ca33f03dcbf0e8def3cfe9a60e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by nbruin):
Replying to [comment:13 SimonKing]:
> In the ticket description, you say: "taking a transpose of a modn_dense
matrix of smallish size is much more expensive than constructing the right
kernel, '''because the method is just a generic implementation.'''"
>
> In contrast, I believe that there ''should'' be a generic implementation
of the transpose, or at least there should be some generic helper methods
for creating the transposed matrix.
I'm not arguing with that. I'm just saying that we should override it on
something like matrices over small finite prime fields because the call
overhead of the `getunsafe` and `setunsafe` functions is really noticeable
relative to the straight C-level reshuffling of data one can do in this
specific case.
> For example, it should make sense to have a method of a matrix space
returning the transposed matrix space, and this method should perhaps even
be a cached method. When using this helper in all custom implementations
of `.transpose()`, then the time to create the transposed matrix' parent
could be reduced.
That might very well be a good idea. It doesn't quite solve the problem
for stack/submatrix operations, though.
> Moreover, all matrices are supposed to provide fast `set/get_unsafe()`
methods. Are you really sure that a generic implementation relying on
these fast "unsafe" methods would be slower than a custom implementation
such as the one of `Matrix_modn_dense` that uses the underlying data
structure directly, rather than using `set/get_unsafe`
Yes, for modndense it definitely is, because it boils down to reshuffling
a C-array of floats/doubles. I'm pretty sure the compiler isn't capable of
inlining `getunsafe` and `setunsafe`.
>{{{
> M._entries[j+i*nrows] = self._entries[i+j*ncols]
> }}}
And of course, in this line we could even save some multiplications, but I
wasn't sure whether that makes a proper difference on modern CPUs.
> And is this really the correct thing to do? Namely, in the unsafe
set/get method of `Matrix_modn_dense_float`, the operations are done on
the attribute `._matrix`, not `._entries`. If I understand correctly,
`._matrix` is arranged in rows,
`._matrix` is an array of pointers into `._entries` (and yes, in my code I
assumed that `Matrix_modn_dense_template` always has its entries laid out
in the same way. That assumption is made elsewhere in the file too).
Looking up via `._matrix` might save a multiplication at the expense of an
extra memory access. My gut feeling was that the memory access was going
to be worse, but I didn't extensively check. My guess would be that if the
multiplications are costly, it's better to avoid them through repeated
additions (we need the intermediate results) than by extra memory
indirection. Perhaps replace everything by straight pointer arithmetic on
a pointer starting at `M._entries`?
> We need to address the following custom `.transpose()` methods:
We can reevaluate them with what we learn here, but I'm not sure that the
same tradeoffs will apply. For instance, for an integer matrix we cannot
expect the entries to be contiguously stored and of the same size, so the
memory management just for the entries is already much more expensive.
--
Ticket URL: <http://trac.sagemath.org/ticket/15104#comment:14>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
