Hiho,
I am fairly new to the D programming and still reading throught
the awesome online book at http://ddili.org/ders/d.en/index.html.
However, I think it is missing some things or I am missing
glasses and overlooked these parts in the book.^^
Currently I am trying to write a very simple Matrix library for
some minor linear algebra operations such as calculating
determine, some simple compositions etc. I am aware that this
probably has been done already and I am mainly focusing learning
D with this project. =)
I already wrote a similar Matrix library for Java and C++ with
more or less the same algorithms in order to benchmark these
languages.
As I am very new to D I instantly ran into certain optimizing
issues. E.g. the simple matrix multiplication based in my java
implementation requires about 1.5 secs for multiplying two
1000x1000 matrices, however my D implementation requires 39
seconds without compiler optimizations and about 14 seconds with
-inline, -O, -noboundscheck and -release. So I am sure that I
just missed some possible optimization routines for D and that I
could miss entire patters used in D to write more optimized code
- especially when looking at the const and immutability concepts.
I won't paste the whole code, just the important parts.
class Matrix(T = double) {
private T[] data;
private Dimension dim;
}
This is my class with its templated data as a one dimensional
array (as I don't like jagged-arrays) and a dimension (which is a
struct). The dimension object has some util functionality such as
getting the total size or mapping (row, col) to a one-dimensional
index besides the getter for rows and columns.
this(size_t rows, size_t cols) {
this.dim = Dimension(rows, cols);
this.data = new T[this.dim.size];
enum nil = to!T(0);
foreach(ref T element; this.data) element = nil;
}
This is one of the constructor. Its task is just to create a new
Matrix instance filled with what is 0 for the templated value -
don't know if there is a better approach for this. I experienced
that floating point values are sadly initialized with nan which
isn't what I wanted -> double.init = nan.
I am using opIndex and opIndexAssign in order to access and
assign the matrix values:
T opIndex(size_t row, size_t col) const {
immutable size_t i = this.dim.offset(row, col);
if (i >= this.dim.size) {
// TODO - have to learn exception handling in D first. :P
}
return this.data[i];
}
Which calls:
size_t size() @property const {
return this.rows * this.cols;
}
I think and hope that this is getting optimized via inlining. =)
This works similar for opIndexAssign.
The function I am mainly benchmarking is the simple matrix
multiplication where one of the multiplied matrices is tranposed
first in order to improve cache hit ratio.
Matrix opMul(ref const(Matrix) other) {
if (this.dim.rows != other.dim.cols || this.dim.cols !=
ther.dim.rows) {
// TODO - still have to learn exception handling first ...
}
auto m = new Matrix(this.dim.rows, other.dim.cols);
auto s = new Matrix(other).transposeAssign();
size_t r1, r2, c;
T sum;
for (r1 = 0; r1 < this.dim.rows; ++r1) {
for (r2 = 0; r2 < other.dim.rows; ++r2) {
sum = to!T(0);
for (c = 0; c < this.dim.cols; ++c) {
sum += this[r1, c] * other[r2, c];
}
m[r1, r2] = sum;
}
}
return m;
}
I am aware that there are faster algorithms for matrix
multiplication but I am mainly learning how to write efficient D
code in general and not based on any algorithm.
This is more or less the same algorithm I am using with java and
c++. Both require about 1.5 secs (after java warm-up) to perform
this task for two 1000x1000 matrices. D compiled with DMD takes
about 14 seconds with all (known-to-me) optimize flag activated.
(listed above)
I wanted to make s an immutable matrix in order to hopefully
improve performance via this change, however I wasn't technically
able to do this to be honest.
Besides that I can't find a way how to make a use of move
semantics like in C++. For example a rvalue-move-constructor or a
move-assign would be a very nice thing for many tasks.
I am not quite sure also if it is normal in D to make an idup
function as slices have which creates an immutable copy of your
object. And are there important things I have to do while
implementing an idup method for this matrix class?
Another nice thing to know would be if it is possible to
initialize an array before it is default initialized with T.init
where T is the type of the array's fields. In C++ e.g. there is
no default initialization which is nice if you have to initialize
every single field anyway. E.g. in a Matrix.random() method which
creates a matrix with random values. There it is unnecessary that
the (sometimes huge) array is completely initialized with the
type's init value.
Thanks in advance!
Robin
