D slower ~1s from C ?!

[Marco Leise]

Am Thu, 05 Apr 2012 19:22:37 +0200
schrieb "Minas" <minas_mina1990 at hotmail.co.uk>:

> Many of you should know the website "projecteuler.net", where 
> there are mathematical problems to solve with computers.
> 
> I am doing those in D, and after I finished one today, I decided 
> to compile it in C as well to compare the results.

The first rule or PE: You don't talk about PE in the public. You accidentally posted a solution to a problem in the public. Now people can solve the task, using a search engine. And after solving the problem, get access to other language implementations. Some employers even use problems from there to assess new programmers. And believe me, you wouldn't want a co-worker that cheated on PE to get the job ;).

Anyway like others suggested, I use GDC to get the most out of D and I actually like the challenge of staying under 50ms for every problem I solve. (My Friend Key is 58749952297599_fa95cc8e61e8df1206f1144436ac050f)
Admittedly my first solutions aren't always fast. Often I just solve the problem and then look into the forum for how to make it _fast_. After a while I think, I should have a nice library of very fast helper functions.

My personal favorite is a small struct that can be used to iterate along rows or diagonals of Pascal's triangle:

---------------------

alias size_t ℕ;

/**
 * The ultimate tool to move around in Pascal's triangle. Pascal(0, 0) is the
 * top of the triangle with the value of 1.
 */
struct Pascal
{
	this(ℕ n, ℕ k) {
		// internally we offset these by +1, to simplify the math
		++n; ++k;
		_n = n;
		if (k > n / 2) {
			_k = _n;
			left(_n - k);
		} else {
			right(k - 1);
		}
	}
	
	ℕ left(ℕ amount) {
		while (amount--) {
			_value *= --_k;
			_value /= _n - _k;
		}
		return _value;
	}
	
	ℕ right(ℕ amount) {
		while (amount--) {
			_value *= _n - _k;
			_value /= _k++;
		}
		return _value;
	}
	
	ℕ rightDown(ℕ amount) {
		while (amount--) {
			_value *= _n++;
			_value /= _k++;
		}
		return _value;
	}

	ℕ leftDown(ℕ amount) {
		while (amount--) {
			_value *= _n++;
			_value /= _n - _k;
		}
		return _value;
	}

	ℕ leftUp(ℕ amount) {
		while (amount--) {
			_value *= --_k;
			_value /= --_n;
		}
		return _value;
	}

	ℕ rightUp(ℕ amount) {
		while (amount--) {
			_value *= _n - _k;
			_value /= --_n;
		}
		return _value;
	}
	
	@property
	ℕ value() { return _value; }
	
	alias value this;
	
	private:
	
	ℕ _n = 1, _k = 1;
	ℕ _value = 1;
}

-------------------------

I use it like this for combinatorics calculations (n over k), where a naive approach would recalculate that Pascal's triangle value at the required position over and over again:

	ℕ[] permut_per_variation = new ℕ[variations];
	Pascal pascal = Pascal(_2 + _3, _3);
	foreach (v; 0..variations)
	{
		permut += permut_per_variation[v] = pascal;
		pascal.leftDown(1);
		pascal.left(2);
	}

Still some functional programmers keep mocking me for my lines of code count. And I tend to agree now and then (some FP solutions are _really_ short). With these fun tasks it is more a matter of personality though. I prefer fast over concise code. Some participants even use ASM... maybe they like it really close to the metal. In any case it is good to know how C/D code maps to machine code, e.g. what is efficient and what not, so you don't misuse real instead of int.

Looking at your code I noticed the following:

*)	writeln() is ok, but doesn't flush (e.g. missing output when a program is halted in a debugger or crashes)
	You can use stdout.writeln() when you need the output on the screen as soon as the line is executed

*)	n = abs(n); // <- don't need this, you already declared n as unsigned

*)	if( n % 2 ...)
	Just in case someone wonders, GCC/GDC replaces the modulo with faster	
	code. There is no need to write n & 1, which is a bit more cryptic.

*)	for(ulong i = 2; i <= cast (ulong)sqrt(cast(double)n+1); ++i)
	can be written as:
	foreach (i; 2 .. cast(ulong)sqrt(n)+1)

	Foreach only computes start and end once and 'i' will be ulong thanks to the cast!

*)	ulong power = cast(ulong)pow(10, cast(ulong)log10(n));
	can alternatively be written as:
	ulong power = 10 ^^ cast(ulong)log10(n);

*)	In the following while loop, you can replace
	power = cast(ulong)pow(10, cast(ulong)log10(n));
	with
	power /= 10;

But really, only the isPrime() function is taking up time in this code. This is a short and fast version with GDC 64bit, but a different algorithm would help more:

bool isPrime(ulong n)
{
	// 0 and 1 aren't primes
	if( n < 2 ) return false;

	for( ulong i = 2; n / i >= i; ++i )
		if( n % i == 0 )
			return false;

	return true;
}

When / and % are used close to each other, they are handled in one CPU instruction. So you can avoid floating point math altogether.

-- 
Marco