Thread overview
Detecting performance pitfall in array access
May 17, 2020
Adnan
May 17, 2020
Johan
May 18, 2020
Adnan
May 17, 2020
kinke
May 17, 2020
kinke
May 18, 2020
Adnan
May 17, 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
May 17, 2020
On Sunday, 17 May 2020 at 03:30:57 UTC, Adnan wrote:
> 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.
>
> https://imgshare.io/image/NN8Xmp

Can you add `--force` to the dub commandline to make sure it is rebuilding the executable?

-Johan

May 17, 2020
On Sunday, 17 May 2020 at 03:30:57 UTC, Adnan wrote:
> 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

My timings are very different, using LDC v1.21 on Win64:

* ldc2 -O -release -run bla.d aa bbc: 8-9 μs
* ldc2 -O -release -boundscheck=off -run bla.d aa bbc: 8-9 μs
* ldc2 -O -release -boundscheck=off -flto=full -defaultlib=phobos2-ldc-lto,druntime-ldc-lto -run bla.d aa bbc: 4 μs

DMD v2.091:
* dmd -m64 -O -release -boundscheck=off -run ..\speed.d aa bbc: ~11 μs

As a side note, using jagged arrays for multiple dimensions should probably be avoided whenever you can.
May 17, 2020
On Sunday, 17 May 2020 at 11:39:30 UTC, kinke wrote:
> DMD v2.091:
> * dmd -m64 -O -release -boundscheck=off -run ..\speed.d aa bbc: ~11 μs

I forgot `-inline` for DMD; that reduces the speed, yielding ~16 μs.
May 18, 2020
On Sunday, 17 May 2020 at 09:41:55 UTC, Johan wrote:
> On Sunday, 17 May 2020 at 03:30:57 UTC, Adnan wrote:
>> 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.
>>
>> https://imgshare.io/image/NN8Xmp
>
> Can you add `--force` to the dub commandline to make sure it is rebuilding the executable?
>
> -Johan

The results stay the same. Probably some weird bug in my system.
May 18, 2020
On Sunday, 17 May 2020 at 11:39:30 UTC, kinke wrote:
> As a side note, using jagged arrays for multiple dimensions should probably be avoided whenever you can.
By jagged array, do you mean vector of vectors? What would be an alternative?