Software Assurance Reference Dataset

H. S. Teoh via Digitalmars-d digitalmars-d at puremagic.com
Tue Jul 22 12:10:51 PDT 2014


On Tue, Jul 22, 2014 at 11:34:20AM -0700, Walter Bright via Digitalmars-d wrote:
> On 7/20/2014 8:15 PM, Timon Gehr wrote:
> >So does Haskell.
> >
> >import Control.Monad
> >import Control.Monad.ST
> >import Data.STRef
> >
> >factorial :: Integer -> Integer
> >factorial n = runST $ do
> >   r <- newSTRef 1
> >   forM_ [1..n] $ \i->
> >     modifySTRef r (*i)
> >   readSTRef r
> 
> Would you rather write that or:
> 
>   int factorial(int i) pure {
>     auto r = 1;
>     foreach (i; 1..n + 1)
> 	r *= i;
>     return r;
>   }
> 
> And I'd love to see what native code is generated for the Haskell
> example.

I'd rather write:

	int factorial(int n) pure {
		return reduce!((a,b) => a*b)(1, iota(2, n));
	}

;-)

With gdc -O3, this produces almost the same code as your looped version.
But I can barely read the disassembly, because it appears that gdc -O3
triggers aggressive vectorization, so there are tons of instructions
manipulating xmm registers and the loop is unrolled by 8 iterations.

I have this lurking suspicion that this may actually perform more poorly
than the naïve version for small values of n. :-) DMD, with -release -O
-inline, was unable to inline the call to reduce, but was at least able
to optimize reduce+iota into the equivalent of a simple foreach loop. So
it looks quite promising.

We should push for more aggressive optimizations of functional-style
constructs in D; I think there's a lot of potential here.


T

-- 
My program has no bugs! Only unintentional features...


More information about the Digitalmars-d mailing list