Detecting performance pitfall in array access

Adnan relay.public.adnan at outlook.com
Sun May 17 03:30:57 UTC 2020


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


More information about the Digitalmars-d-learn mailing list