Efficient UArray dot-product?

Jon Fairbairn Jon.Fairbairn@cl.cam.ac.uk
Mon, 03 Jun 2002 11:15:09 +0100

> =

> =

> Is it possible to write an dot-product function that GHC will compile
> to efficient code without using unsafeAt?  I've tried and can't.  I'm
> looking at generic IArray functions pragma-specialized to UArray Int
> Double.  With unsafeAt the -ddump-simpl output looks optimal to me
> (aside from not unrolling or pipelining**):
> =

>   loop i s | i > ubSI =3D s
>            | otherwise =3D let s' =3D s + (small `unsafeAt` i) * (big `=
unsafeAt` =

> (off + i))
>                          in seq s' $ loop (i + 1) s'

Isn't that rather the wrong question?  I'd be more
interested in "How do I get ghc to generate efficient code
for dotprod?"

   dotprod a b =3D sum (map e (indices a))
		 where e ix =3D a!ix * b!ix

Especially since ghc does a pretty damn good job for this version


       dotprod :: UArray Int Double -> UArray Int Double -> Double

   dotprod a b =3D foldr (+) 0 (map e (indices a))
		 where e ix =3D a!ix * b!ix

(It's a pity that it can only eliminate the list for foldr,
not the foldl used in sum).

I'm not at all familiar with the intermediate code, so I
don't know what in the output from the above is particularly
inefficient. It does seem to do a lot of deconstructing and
I've no idea how to get round that, but I'd much prefer to
see a definition like dotprod in the Haskell code and all
the mysteries and contortions done in ghc.


PS It's a national holiday in the UK, so you might not hear
anything from the ghc guys for a bit.

-- =

J=F3n Fairbairn                                 Jon.Fairbairn@cl.cam.ac.u=
31 Chalmers Road                                         jf@cl.cam.ac.uk
Cambridge CB1 3SZ            +44 1223 570179 (after 14:00 only, please!)