Hello, I am trying to examine what causes my similar D solution
to lag behind performance.
In the link, they don't have ldc or gdc but according to my
machine, the dmd generated code isn't really far behind ldc
generated code.
So here is the actual code:
ulong levenshteinEditDistance(T)(in ref T a, in ref T b) if
(isSomeString!T) {
import std.array : uninitializedArray;
auto matrix = uninitializedArray!(ulong[][])(a.length + 1,
b.length + 1);
foreach (i; 0 .. a.length + 1)
matrix[i][0] = i;
foreach (j; 0 .. b.length + 1)
matrix[0][j] = j;
import std.algorithm : min;
for (int i = 1; i < a.length + 1; ++i)
for (int j = 1; j < b.length + 1; ++j) {
const ulong substitutionCost = a[i - 1] == b[j - 1] ? 0
: 1;
matrix[i][j] = min(matrix[i - 1][j - 1] +
substitutionCost,
matrix[i][j - 1] + 1, matrix[i - 1][j]
+ 1);
}
return matrix[a.length][b.length];
}
In my machine, if you feed "aa" and "bbc" to the function, ldc
generated code takes around 400 microseconds. I don't have an
access to gdc in my machine.
https://imgshare.io/image/NN8Xmp
Full code:
D : https://run.dlang.io/is/vLj7BC
Nim : https://play.nim-lang.org/#ix=2mhH (for reference)
Compiler flags:
dub : build -b release-nobounds
nimble : --d:danger