www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Detecting performance pitfall in array access

reply Adnan <relay.public.adnan outlook.com> writes:
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 16 2020
next sibling parent reply Johan <j j.nl> writes:
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
parent Adnan <relay.public.adnan outlook.com> writes:
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 17 2020
prev sibling parent reply kinke <noone nowhere.com> writes:
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
next sibling parent kinke <noone nowhere.com> writes:
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 17 2020
prev sibling parent Adnan <relay.public.adnan outlook.com> writes:
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?
May 17 2020