Re: [eigen] Should I care about col major vs. row major for dense matrices

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2009/7/3 Jens Mueller <jens.k.mueller@xxxxxx>:
> Hi all,
>
> I'm missing some implications for the storage order of dense matrices. I
> know that for sparse matrices you can only use let's say row(), if the
> matrix is row major.
> But for dense matrices you can use both (independent of the storage
> order). Are there any performance implications by doing so? I'm assuming
> yes, since I doubt that the compiler can optimize this.
> But I'm very unsure. In essence, I want to speed up my code but I'm not
> sure whether this is a real issue.

First of all, yes, all of the dense matrix API is independent of the
storage order. So it's only a question of performance.

Matrix decompositions (like LU, etc...) are themselves agnostic in
that respect, but when choosing an algorithm to compute them, and when
implementing that algorithm, we sometimes make decisions that favor a
storage order. Of course this isn't anything fundamental, ideally we'd
write all our code either in a storage-order-agnostic way or write 2
paths, one for each order, but in practice, for lack of coding time,
we have some code that runs faster with column-major order than with
row-major order. That's the case of LU, for instance. Indeed,
column-major being the default in eigen, given the choice (the
dilemma!) we optimize for it.

Reasons for a performance difference include memory locality, and the
possibility of vectorization. Consider the implementation of adding
two column-major matrices. Obviously it's best to proceed column-wise.
If we proceeded row-wise, we'd be doing very non-local memory accesses
and it would be impossible to vectorize. Likewise, many algorithms
need to be implemented either rowwise or colwise, with the same
implications for performance. Fixing this can be done either
abstracting the notion of rows and cols, talking instead of "inner
slices", or writing two separate code paths.

Benoit