Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
My current best try uses the uvector package, has two 'vectors' of type (UArr Double) as input, and relies on the sumU and zipWithU functions which use streaming to compute the result: dist_fast :: UArr Double -> UArr Double -> Double dist_fast p1 p2 = sumDs `seq` sqrt sumDs where sumDs = sumU ds ds= zipWithU euclidean p1 p2 euclidean x y = d*d where d = x-y You'll probably want to make sure that 'euclidian' is specialized to the types you need (here 'Double'), not used overloaded for 'Num a=>a' (check -ddump-tc, or -ddump-simpl output). After that, unrolling the fused fold loop (uvector internal) might help a bit, but isn't there yet: http://hackage.haskell.org/trac/ghc/ticket/3123 http://hackage.haskell.org/trac/ghc/wiki/Inlining And even if that gets implemented, it doesn't apply directly to your case, where the loop is in a library, but you might want to control its unrolling in your client code. Having the loop unrolled by a default factor (8x or so) should help for loops like this, with little computation. Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
kenneth.hoste:
> Hello,
>
> For a while now, I've been trying to come up with a fast Haskell-only
> function which implements Euclidean distance in n-dimensional space.
>
> So far, I've been disappointed by the performance of my best effort
> in Haskell, compared to C. I'm hoping some of the Haskell experts
> and/or performance gurus on this list can help me out on resolving this,
> and also maybe shed some light on some strange (imho) things I've run
> into.
>
> My current best try uses the uvector package, has two 'vectors' of type
> (UArr Double) as input, and relies on the sumU and zipWithU functions
> which use streaming to compute the result:
>
> dist_fast :: UArr Double -> UArr Double -> Double
> dist_fast p1 p2 = sumDs `seq` sqrt sumDs
> where
> sumDs = sumU ds
> ds= zipWithU euclidean p1 p2
> euclidean x y = d*d
> where
> d = x-y
The problem in your uvector code is the use of lists, rather than uvector
generators. Replace [1..n] with enumFromTo:
import Control.Monad
import System.Environment
import System.IO
import Data.Array.Vector
dist :: UArr Double -> UArr Double -> Double
dist p1 p2 = sumU (zipWithU euclidean p1 p2)
where
euclidean x y = d*d where d = x-y
main = do
[dim] <- map read `fmap` getArgs
print $
dist
(enumFromToFracU 1.0 dim)
(enumFromToFracU 1.0 dim)
Now the entire thiing will fuse to a loop.
$s$wfold_s1RR :: Double# -> Double# -> Double# -> Double#
$s$wfold_s1RR =
\ (sc_s1RH :: Double#)
(sc1_s1RI :: Double#)
(sc2_s1RJ :: Double#) ->
case >## sc1_s1RI a5_s1QR of wild4_a1tn {
False ->
case >## sc_s1RH a5_s1QR of wild5_X1vx {
False ->
let {
x1_a1Jg [ALWAYS Just L] :: Double#
x1_a1Jg = -## sc1_s1RI sc_s1RH } in
$s$wfold_s1RR
(+## sc_s1RH 1.0)
(+## sc1_s1RI 1.0)
(+## sc2_s1RJ (*## x1_a1Jg x1_a1Jg));
True -> sc2_s1RJ
};
True -> sc2_s1RJ
}; } in
case $s$wfold_s1RR 1.0 1.0 0.0 of ww_s1QH { __DEFAULT ->
a19 (D# ww_s1QH)
and this assembly:
$ ghc -O2 -fvia-C -optc-O3
s1T9_info:
movsd 5(%rbx), %xmm7
ucomisd %xmm7, %xmm6
ja .L15
ucomisd %xmm7, %xmm5
jbe .L18
.L14:
.L15:
movsd (%rbp), %xmm5
leaq8(%rbp), %rbp
jmp *(%rbp)
.L18:
movapd %xmm6, %xmm7
subsd %xmm5, %xmm7
mulsd %xmm7, %xmm7
addsd (%rbp), %xmm7
movsd %xmm7, (%rbp)
movsd .LC0(%rip), %xmm7
addsd %xmm7, %xmm5
addsd %xmm7, %xmm6
jmp s1T9_info
Which I'd wager will match the C, which has to allocate the two arrays (GHC
essentially decides it doesn't need the arrays any more.
-- Don
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
dist_fast :: UArr Double -> UArr Double -> Double dist_fast p1 p2 = sumDs `seq` sqrt sumDs where sumDs = sumU ds ds= zipWithU euclidean p1 p2 euclidean x y = d*d where d = x-y You'll probably want to make sure that 'euclidian' is specialized to the types you need (here 'Double'), not used overloaded for 'Num a=>a' (check -ddump-tc, or -ddump-simpl output). Sorry about that misdirection - as it happened, I was looking at the tc output for 'dist_fast' (euclidean :: forall a. (Num a) => a -> a -> a), but the simpl output for 'dist_fast_inline' .., which uses things like __inline_me .. case Dist.sumU (Dist.$wzipWithU .. GHC.Num.- @ GHC.Types.Double GHC.Float.$f9 x_aLt y_aLv Once I actually add a 'dist_fast_inline_caller', that indirection disappears in the inlined code, just as it does for dist_fast itself. dist_fast_inlined_caller :: UArr Double -> UArr Double -> Bool dist_fast_inlined_caller p1 p2 = dist_fast_inlined p1 p2 > 2 However, in the simpl output for 'dist_fast_inline_caller', the 'sumU' and 'zipWithU' still don't seem to be fused - Don? Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
claus.reinke:
>>> dist_fast :: UArr Double -> UArr Double -> Double
>>> dist_fast p1 p2 = sumDs `seq` sqrt sumDs
>>> where
>>> sumDs = sumU ds
>>> ds= zipWithU euclidean p1 p2
>>> euclidean x y = d*d
>>> where
>>> d = x-y
>>
>> You'll probably want to make sure that 'euclidian' is specialized to
>> the types you need (here 'Double'), not used overloaded for 'Num a=>a'
>> (check -ddump-tc, or -ddump-simpl output).
>
> Sorry about that misdirection - as it happened, I was looking at the tc
> output for 'dist_fast' (euclidean :: forall a. (Num a) => a -> a -> a),
> but the simpl output for 'dist_fast_inline' .., which uses things like
>
>__inline_me ..
>case Dist.sumU (Dist.$wzipWithU ..
>GHC.Num.- @ GHC.Types.Double GHC.Float.$f9 x_aLt y_aLv
>
> Once I actually add a 'dist_fast_inline_caller', that indirection
> disappears in the inlined code, just as it does for dist_fast itself.
>
>dist_fast_inlined_caller :: UArr Double -> UArr Double -> Bool
>dist_fast_inlined_caller p1 p2 = dist_fast_inlined p1 p2 > 2
>
> However, in the simpl output for 'dist_fast_inline_caller', the
> 'sumU' and 'zipWithU' still don't seem to be fused - Don?
All the 'seq's and so on should be unnecessary, and even so, I still get
the expected fusion:
import Control.Monad
import System.Environment
import System.IO
import Data.Array.Vector
{-
dist :: UArr Double -> UArr Double -> Double
dist p1 p2 = sumU (zipWithU euclidean p1 p2)
where
euclidean x y = d*d where d = x-y
-}
main = do
[dim] <- map read `fmap` getArgs
print $
dist_fast_inlined
(enumFromToFracU 1.0 dim)
(enumFromToFracU 1.0 dim)
dist_fast_inlined :: UArr Double -> UArr Double -> Double
{-# INLINE dist_fast_inlined #-}
dist_fast_inlined p1 p2 = sumDs `seq` sqrt sumDs
where
sumDs = sumU ds
ds= zipWithU euclidean p1 p2
euclidean x y = d*d
where
d = x-y
{-
19 RuleFired
2 /##
3 SC:$wfold0
5 int2Double#
1 map
1 mapList
3 streamU/unstreamU
2 truncate/Double->Int
1 unpack
1 unpack-list
$s$wfold_s1TB :: Double# -> Double# -> Double# -> Double#
-}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
Once I actually add a 'dist_fast_inline_caller', that indirection
disappears in the inlined code, just as it does for dist_fast itself.
dist_fast_inlined_caller :: UArr Double -> UArr Double -> Bool
dist_fast_inlined_caller p1 p2 = dist_fast_inlined p1 p2 > 2
However, in the simpl output for 'dist_fast_inline_caller', the
'sumU' and 'zipWithU' still don't seem to be fused - Don?
All the 'seq's and so on should be unnecessary, and even so, I still get
the expected fusion:
As I said, I don't get the fusion if I just add the function above to the
original Dist.hs, export it and compile the module with '-c -O2 -ddump-simpl':
Dist.dist_fast_inlined_caller =
\ (w1_s1nb :: Data.Array.Vector.UArr.UArr GHC.Types.Double)
(w2_s1nc :: Data.Array.Vector.UArr.UArr GHC.Types.Double) ->
case (Dist.$wzipWithU Dist.lvl2 w1_s1nb w2_s1nc)
`cast` (trans
Data.Array.Vector.UArr.TFCo:R56:UArr
Data.Array.Vector.UArr.NTCo:R56:UArr
:: Data.Array.Vector.UArr.UArr GHC.Types.Double
~
Data.Array.Vector.Prim.BUArr.BUArr GHC.Types.Double)
of _
{ Data.Array.Vector.Prim.BUArr.BUArr ipv_s1lb
ipv1_s1lc
ipv2_s1ld ->
letrec {
$wfold_s1nN :: GHC.Prim.Double#
-> GHC.Prim.Int#
-> GHC.Prim.Double#
LclId
[Arity 2
Str: DmdType LL]
$wfold_s1nN =
\ (ww_s1mZ :: GHC.Prim.Double#) (ww1_s1n3 :: GHC.Prim.Int#) ->
case GHC.Prim.==# ww1_s1n3 ipv1_s1lc of _ {
GHC.Bool.False ->
$wfold_s1nN
(GHC.Prim.+##
ww_s1mZ
(GHC.Prim.indexDoubleArray#
ipv2_s1ld (GHC.Prim.+# ipv_s1lb ww1_s1n3)))
(GHC.Prim.+# ww1_s1n3 1);
GHC.Bool.True -> ww_s1mZ
}; } in
case $wfold_s1nN 0.0 0 of ww_s1n7 { __DEFAULT ->
GHC.Prim.>## (GHC.Prim.sqrtDouble# ww_s1n7) 2.0
}
}
Claus
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
claus.reinke: >>> Once I actually add a 'dist_fast_inline_caller', that indirection >>> disappears in the inlined code, just as it does for dist_fast itself. >>> >>>dist_fast_inlined_caller :: UArr Double -> UArr Double -> Bool >>>dist_fast_inlined_caller p1 p2 = dist_fast_inlined p1 p2 > 2 >>> >>> However, in the simpl output for 'dist_fast_inline_caller', the >>> 'sumU' and 'zipWithU' still don't seem to be fused - Don? >> >> All the 'seq's and so on should be unnecessary, and even so, I still get >> the expected fusion: > > As I said, I don't get the fusion if I just add the function above to the > original Dist.hs, export it and compile the module with '-c -O2 > -ddump-simpl': I can't reproduce this. Does the complete program fragment I posted earlier yield the desired result? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
As I said, I don't get the fusion if I just add the function above to the original Dist.hs, export it and compile the module with '-c -O2 -ddump-simpl': I can't reproduce this. Interesting. I'm using ghc 6.11.20090320 (windows), uvector-0.1.0.3. I attach the modified Dist.hs and its simpl output, created via: ghc -c Dist.hs -O2 -ddump-tc -ddump-simpl-stats -ddump-simpl > Dist.dumps Perhaps others can confirm the effect? Note that the 'dist_fast' in the same module does get fused, so it is not likely an options issue. I still suspect that the inlining of the 'Dist.zipWith' wrapper in the 'dist_fast_inlined' '__inline_me' has some significance - it is odd to see inlined code in an '__inline_me' and the fusion rule won't trigger on 'Dist.sumU . Dist.$wzipWithU', right? Does the complete program fragment I posted earlier yield the desired result? Yes. Note that the original poster also reported slowdown from use of 'dist_fast_inlined'. Claus Dist.dumps Description: Binary data Dist.hs Description: Binary data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
On May 18, 2009, at 15:28 , Claus Reinke wrote: My current best try uses the uvector package, has two 'vectors' of type (UArr Double) as input, and relies on the sumU and zipWithU functions which use streaming to compute the result: dist_fast :: UArr Double -> UArr Double -> Double dist_fast p1 p2 = sumDs `seq` sqrt sumDs where sumDs = sumU ds ds= zipWithU euclidean p1 p2 euclidean x y = d*d where d = x-y You'll probably want to make sure that 'euclidian' is specialized to the types you need (here 'Double'), not used overloaded for 'Num a=>a' (check -ddump-tc, or -ddump-simpl output). I understand from your later post that is was in fact specialized, but how do I make sure it _is_ specialized? Can I just add a type signature in the dist_fast definition for euclidean, or should I define euclidean outside of dist_fast, with an explicit type signature? If the latter, won't that hurt performance? Or should marking it INLINE take care of that? After that, unrolling the fused fold loop (uvector internal) might help a bit, but isn't there yet: http://hackage.haskell.org/trac/ghc/ticket/3123 http://hackage.haskell.org/trac/ghc/wiki/Inlining And even if that gets implemented, it doesn't apply directly to your case, where the loop is in a library, but you might want to control its unrolling in your client code. Having the loop unrolled by a default factor (8x or so) should help for loops like this, with little computation. This seems rather serious, and might be one of the bigger reasons why I'm getting nowhere close to C in terms of performance... The loop body is ridiculously small, so it would make sense to unroll it somewhat to help avoid the loop overhead. However, it seems like GHC isn't able to do that now. Is there any way to unroll the loop myself, to speed things up? Seems hard, because I'm using uvector... K. -- Kenneth Hoste Paris research group - ELIS - Ghent University, Belgium email: kenneth.ho...@elis.ugent.be website: http://www.elis.ugent.be/~kehoste blog: http://boegel.kejo.be ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
On May 18, 2009, at 20:54 , Claus Reinke wrote: As I said, I don't get the fusion if I just add the function above to the original Dist.hs, export it and compile the module with '-c -O2 -ddump-simpl': I can't reproduce this. Interesting. I'm using ghc 6.11.20090320 (windows), uvector-0.1.0.3. I attach the modified Dist.hs and its simpl output, created via: ghc -c Dist.hs -O2 -ddump-tc -ddump-simpl-stats -ddump-simpl > Dist.dumps Perhaps others can confirm the effect? Note that the 'dist_fast' in the same module does get fused, so it is not likely an options issue. I still suspect that the inlining of the 'Dist.zipWith' wrapper in the 'dist_fast_inlined' '__inline_me' has some significance - it is odd to see inlined code in an '__inline_me' and the fusion rule won't trigger on 'Dist.sumU . Dist. $wzipWithU', right? As far as I can tell, the dist_fast_inlined doesn't get fused, i.e. I'm seeing zipWithU and sumU being used in it, which is not the case in dist_fast. This is on OS X/PowerPC, using GHC 6.10.1. Does the complete program fragment I posted earlier yield the desired result? Yes. Note that the original poster also reported slowdown from use of 'dist_fast_inlined'. Don, you were defining dist inside the main module, while in our case the dist functions are defined in a seperate Dist.hs module... Would that matter? K. -- Kenneth Hoste Paris research group - ELIS - Ghent University, Belgium email: kenneth.ho...@elis.ugent.be website: http://www.elis.ugent.be/~kehoste blog: http://boegel.kejo.be ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
Hello!
On Monday 18 May 2009 14:37:51 Kenneth Hoste wrote:
> I'm mostly interested in the range 10D to 100D
is the dimension known at compile-time? Then you could consider Template
Haskell. I wrote up some code for generating the vector types and vector
subtraction/inner product below, HTH. One problem is that I'm using a
typeclass and apparently you can't make {-# SPECIALISE #-} pragmas with TH,
so let's hope it is automatically specialised by GHC.
Greetings,
Daniel
TH.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}
module TH where
import Language.Haskell.TH
import Control.Monad
-- Non-TH stuff
class InnerProductSpace v r | v -> r where
innerProduct :: v -> v -> r
class AbGroup v where
minus :: v -> v -> v
euclidean x y = case minus x y of
z -> sqrt $! innerProduct z z
-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)
makeVectors :: Int -- ^ Dimension
-> Q Type -- ^ Component type, assumed to be a 'Num'
-> String -- ^ Name for the generated type
-> Q [Dec]
makeVectors n ctyp name0 = do
-- let's assume ctyp = Double, name = Vector for the comments
-- generate names for the variables we will need
xs <- replicateM n (newName "x")
ys <- replicateM n (newName "y")
let
name = mkName name0
-- shorthands for arithmetic expressions; the first takes expressions,
-- the others take variable names
sumE e1 e2 = infixE (Just e1) [|(+)|] (Just e2)
varDiffE e1 e2 = infixE (Just (varE e1)) [|(-)|] (Just (varE e2))
varProdE e1 e2 = infixE (Just (varE e1)) [|(*)|] (Just (varE e2))
conPat vars = conP name (fmap varP vars)
-- > data Vector = Vector !Double ... !Double
theDataD =
dataD noContext name [] -- no context, no params
[normalC name (replicate n (strict ctyp))]
[''Eq,''Ord,''Show] -- 'deriving' clause
innerProdD =
-- > instance InnerProductSpace Vector Double where ...
instanceD noContext ( conT ''InnerProductSpace
`appT` conT name
`appT` ctyp)
-- > innerProduct = ...
[valD
(varP 'innerProduct)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
(lamE [conPat xs, conPat ys]
-- x1*y1 + + xn*yn + 0
(foldl sumE [|0|] $
zipWith varProdE xs ys)
))
[] -- no 'where' clause
]
abGroupD =
instanceD noContext ( conT ''AbGroup
`appT` conT name)
-- > minus = ...
[valD
(varP 'minus)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
(lamE [conPat xs, conPat ys]
-- Vector (x1-y1) ... (xn-yn)
(foldl appE (conE name) $
zipWith varDiffE xs ys)
))
[] -- no 'where' clause
]
sequence [theDataD,innerProdD,abGroupD]
Main.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module Main where
import TH
$(makeVectors 3 [t|Double|] "Vec3")
main = print $ euclidean (Vec3 1 1 1) (Vec3 0 0 0)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
I understand from your later post that is was in fact specialized, but how do I make sure it _is_ specialized? -ddump-tc seems to give the generalized type, so it seems you'd need to look at the -ddump-simpl output if you want to know whether a local function is specialized. http://www.haskell.org/haskellwiki/Performance/GHC#Looking_at_the_Core Can I just add a type signature in the dist_fast definition for euclidean, If you need it at exactly one type, that is the simplest way. There's also the SPECIALIZE pragma http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html#specialize-pragma and for local and non-exported functions '-O' should enable auto-specialization http://www.haskell.org/ghc/docs/latest/html/users_guide/faster.html After that, unrolling the fused fold loop (uvector internal) might help a bit, but isn't there yet: http://hackage.haskell.org/trac/ghc/ticket/3123 http://hackage.haskell.org/trac/ghc/wiki/Inlining And even if that gets implemented, it doesn't apply directly to your case, where the loop is in a library, but you might want to control its unrolling in your client code. Having the loop unrolled by a default factor (8x or so) should help for loops like this, with little computation. This seems rather serious, and might be one of the bigger reasons why I'm getting nowhere close to C in terms of performance... You should be able to get near (a small factor) without it, but not having it leaves a substantial gap in performance, especially for simple loop bodies (there is also the case of enabling fusion over multiple loop iterations, but that may call for proper fix-point fusion). The loop body is ridiculously small, so it would make sense to unroll it somewhat to help avoid the loop overhead. However, it seems like GHC isn't able to do that now. Apart from the links above, the new backend also has relevant TODO items: http://hackage.haskell.org/trac/ghc/wiki/BackEndNotes Is there any way to unroll the loop myself, to speed things up? Seems hard, because I'm using uvector... You could 'cabal unpack' uvector, hand-unroll the core loop all its operations get fused into, then reinstall the modified package.. (perhaps that should be a package configuration option, at least until GHC gets loop or recursion unrolling - since this would be a temporary workaround, it would probably not be worth it to have multiple package versions with different unroll factors; if this actually helps uvector users with performance in practice, they could suggest it as a patch). Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
Hi,
meh, I just realised that there is no sensible way to actually
introduce/eliminate the generated types. I'm attaching a revised version with
fromList/toList functions. Maybe the vector type should be polymorphic and be
an instance of Functor, Monad and Foldable? But then we really depend on
specialisation.
Greetings,
Daniel
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}
module TH where
import Language.Haskell.TH
import Control.Monad
-- Non-TH stuff
class InnerProductSpace v r | v -> r where
innerProduct :: v -> v -> r
class AbGroup v where
minus :: v -> v -> v
class FromToList v r | v -> r where
fromList :: [r] -> Maybe v
toList :: v -> [r]
euclidean x y = case minus x y of
z -> sqrt $! innerProduct z z
-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)
makeVectors :: Int -- ^ Dimension
-> Q Type -- ^ Component type, assumed to be a 'Num'
-> String -- ^ Name for the generated type
-> Q [Dec]
makeVectors n ctyp name0 = do
-- let's assume ctyp = Double, name = Vector for the comments
-- generate names for the variables we will need
xs <- replicateM n (newName "x")
ys <- replicateM n (newName "y")
lst <- newName "list"
let
name = mkName name0
-- shorthands for arithmetic expressions; the first takes expressions,
-- the others take variable names
sumE e1 e2 = infixE (Just e1) [|(+)|] (Just e2)
varDiffE e1 e2 = infixE (Just (varE e1)) [|(-)|] (Just (varE e2))
varProdE e1 e2 = infixE (Just (varE e1)) [|(*)|] (Just (varE e2))
conPat vars = conP name (fmap varP vars)
-- > data Vector = Vector !Double ... !Double
theDataD =
dataD noContext name [] -- no context, no params
[normalC name (replicate n (strict ctyp))]
[''Eq,''Ord,''Show] -- 'deriving' clause
innerProdD =
-- > instance InnerProductSpace Vector Double where ...
instanceD noContext ( conT ''InnerProductSpace
`appT` conT name
`appT` ctyp)
-- > innerProduct = ...
[valD
(varP 'innerProduct)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
(lamE [conPat xs, conPat ys]
-- x1*y1 + + xn*yn + 0
(foldl sumE [|0|] $
zipWith varProdE xs ys)
))
[] -- no 'where' clause
]
abGroupD =
instanceD noContext ( conT ''AbGroup
`appT` conT name)
-- > minus = ...
[valD
(varP 'minus)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn) ->
(lamE [conPat xs, conPat ys]
-- Vector (x1-y1) ... (xn-yn)
(foldl appE (conE name) $
zipWith varDiffE xs ys)
))
[] -- no 'where' clause
]
fromToListD =
instanceD noContext ( conT ''FromToList
`appT` conT name
`appT` ctyp)
[ funD 'fromList
[ clause [listP $ fmap varP xs]
(normalB
([|Just|] `appE`
(foldl appE (conE name) $ fmap varE xs)))
[]
, clause [wildP] (normalB [|Nothing|]) [] -- wrong number
of elements
]
, funD 'toList
[ clause [conPat xs]
(normalB
(listE (fmap varE xs)))
[]]
]
sequence [theDataD,innerProdD,abGroupD,fromToListD]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fast Eucl. dist. - Haskell vs C
On May 19, 2009, at 13:24 , Daniel Schüssler wrote:
Hello!
On Monday 18 May 2009 14:37:51 Kenneth Hoste wrote:
I'm mostly interested in the range 10D to 100D
is the dimension known at compile-time? Then you could consider
Template
Haskell.
In general, no. :-)
It will be known for some applications, but not for others.
I'm more and more amazed what comes into play just to implement
something simple like n-dim. Euclidean distance relatively fast using
Haskell.
It seems to me that GHC is missing several critical optimizations
(yes, I know, patches welcome) to enable it to emit fast code
for HPC applications.
I'm still a big fan of Haskell, for a variety of reasons, but it seems
like it's not ready yet for the task I had in mind, which is a shame.
Just to be clear, this isn't a flame bait post or anything, just my 2
cents.
K.
I wrote up some code for generating the vector types and vector
subtraction/inner product below, HTH. One problem is that I'm using a
typeclass and apparently you can't make {-# SPECIALISE #-} pragmas
with TH,
so let's hope it is automatically specialised by GHC.
Greetings,
Daniel
TH.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS -fglasgow-exts #-}
module TH where
import Language.Haskell.TH
import Control.Monad
-- Non-TH stuff
class InnerProductSpace v r | v -> r where
innerProduct :: v -> v -> r
class AbGroup v where
minus :: v -> v -> v
euclidean x y = case minus x y of
z -> sqrt $! innerProduct z z
-- TH
noContext :: Q Cxt
noContext = return []
strict :: Q Type -> StrictTypeQ
strict = liftM ((,) IsStrict)
makeVectors :: Int -- ^ Dimension
-> Q Type -- ^ Component type, assumed to be a 'Num'
-> String -- ^ Name for the generated type
-> Q [Dec]
makeVectors n ctyp name0 = do
-- let's assume ctyp = Double, name = Vector for the comments
-- generate names for the variables we will need
xs <- replicateM n (newName "x")
ys <- replicateM n (newName "y")
let
name = mkName name0
-- shorthands for arithmetic expressions; the first takes
expressions,
-- the others take variable names
sumE e1 e2 = infixE (Just e1) [|(+)|] (Just e2)
varDiffE e1 e2 = infixE (Just (varE e1)) [|(-)|] (Just (varE
e2))
varProdE e1 e2 = infixE (Just (varE e1)) [|(*)|] (Just (varE
e2))
conPat vars = conP name (fmap varP vars)
-- > data Vector = Vector !Double ... !Double
theDataD =
dataD noContext name [] -- no context, no params
[normalC name (replicate n (strict ctyp))]
[''Eq,''Ord,''Show] -- 'deriving' clause
innerProdD =
-- > instance InnerProductSpace Vector Double where ...
instanceD noContext ( conT ''InnerProductSpace
`appT` conT name
`appT` ctyp)
-- > innerProduct = ...
[valD
(varP 'innerProduct)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn)
->
(lamE [conPat xs, conPat ys]
-- x1*y1 + + xn*yn + 0
(foldl sumE [|0|] $
zipWith varProdE xs ys)
))
[] -- no 'where' clause
]
abGroupD =
instanceD noContext ( conT ''AbGroup
`appT` conT name)
-- > minus = ...
[valD
(varP 'minus)
(normalB
-- \(Vector x1 x2 ... xn) (Vector y1 y2 ... yn)
->
(lamE [conPat xs, conPat ys]
-- Vector (x1-y1) ... (xn-yn)
(foldl appE (conE name) $
zipWith varDiffE xs ys)
))
[] -- no 'where' clause
]
sequence [theDataD,innerProdD,abGroupD]
Main.hs
--
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE MultiParamTypeClasses #-}
module Main where
import TH
$(makeVectors 3 [t|Double|] "Vec3")
main = print $ euclidean (Vec3 1 1 1) (Vec3 0 0 0)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Kenneth Hoste
Paris research group - ELIS - Ghent University, Belgium
email: kenneth.ho...@elis.ugent.be
website: http://www.elis.ugent.be/~kehoste
blog: http://boegel.kejo.be
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
