Hiho,
wow, first of all: this community is awesome - so many kind and
interesting answers. =)
With your help I was able to achieve a performance boost for
several different operations.
Some benchmarks:
Allocation of 5 10.000 x 10.000 matrices in a row:
Before: ~8,2 seconds
After: ~2,3 seconds (with the minimallyInitializedArray!)
Multiplication of two 1000x1000 matrices:
Before: ~14,8 seconds
After: ~4,3 seconds
However, I think there is still much potential in order to
further optimize this code. Let me tell you what changes I have
mainly performed on the code so far ...
Matrix is still a class but I changed it to a final class
preventing matrix methods to be virtual. Dimension is now a final
struct (don't know if 'final' is affecting structs in any way
tough ...). This mainly gave the multiplication a huge
performance boost.
When converting the Matrix to a struct from class the
multiplication even lowered from ~4.3 seconds to about 3.6
seconds. However, I am currently not sure if I want matrices to
be structs (value types).
Besides that I tried to add nothrow and pure as attribute to
every possible method. However, as it turned out I wasn't able to
add the pure modifier to any method as I always called an impure
method with it (as stated by the compiler). This actually made
sense most of the times and I think the only pure methods now are
the constructor methods of the Dimension struct.
What may still speed up things?
In my tests it turned out that the simple code:
auto m1 = Matrix!double.random(1000, 1000, -10, 10, 0.25);
auto m2 = Matrix!double.random(1000, 1000, -10, 10, 0.25);
auto m3 = m1 * m2;
Called the normal copy-constructor. This is sad as it would be a
huge performance boost if it would make use of the move
semantics. (In the C++ matrix codes this scenario would actually
call move assignment operator for matrix m3 which is much much
faster than copying.)
But I haven't figured out yet how to use move semantics in D with
class objects. Or is that just possible with struct value types?
I have also tried the LDC compiler. However, it gave me some
strange bugs. E.g. it didn't like the following line:
ref Matrix transpose() const {
return new Matrix(this).transposeAssign();
}
And it forced me to change it to:
ref Matrix transpose() const {
auto m = new Matrix(this);
m.transposeAssign();
return m;
}
Which is kind of ugly ...
I hope that this is getting fixed soon, as I imply it as correct
D code because the DMD is capable to compile this correctly.
Some of you came up with the thing that transposing the matrix
before multiplication of both takes place must be much slower
than without the transposition. In my former Java and C++
programs I have already tested what strategy is faster and it
turned out that cache efficiency DOES matter of course. There are
also papers explaining why a transpose matrix multiplication may
be faster than without transposing.
In the end this is just a test suite and there is already an even
faster approach of a matrix multiplication which runs in O(n^2.8)
instead of O(n^3) as my current simple solution. And with the
power of OpenCL (or similar) one could even lift a matrix
multiplication to the GPU and boom.^^ But the current task is to
find general optimized code for the D language - this thread
already helped me much!
I wasn't aware that D is actually capable of lazy evaluations
other than the if-pseude-lazy-evaluation which is kind of cool.
However, I still have to look that up in order to maybe find a
use for it in these codes.
SIMD instructions also sound extremely cool but a little bit too
complex regarding the fact that I am fairly new to D and still
learning basics of this language.
In the end I wanted to state something which I found very
iritating. Bearophile stated correctly that my pre-conditions for
the index operators are all wrong and corrected my code with some
smooth additions:
T opIndex(in size_t row, in size_t col) const nothrow
in {
assert(row < nRows);
assert(col < nCols);
} body {
return data[dim.offset(row, col)];
}
The in and body statements are cool as far as I realize what they
are for. However, in the benchmarks they had a clear and
noticable negative impact on the matrix multiplication which
raised to ~8 seconds from ~4 seconds with his code compared to
mine. When leaving out the in and body statement block and using
only one normal block as follows, it stayed at the 4 seconds
duration for that task and so I think that the compiler won't
optimize things in an 'in' code block - is that right?
T opIndex(in size_t row, in size_t col) const nothrow {
assert(row < nRows);
assert(col < nCols);
return data[dim.offset(row, col)];
}
Thanks again for all your helpful comments and thanks in advance
- I am eagerly looking forward for your future comments! =)
Robin
