In a previous blog, we saw that we have options for which version of core we examine. We saw that we had a significant dictionary creation attributed cost, beneath unvector2D.
unvector2D :: (Data.LinearMap.LMapDom a s,VectorSpace s s) => (a :> (s,s)) -> (a :> s,a :> s)
unvector2D d = ( (\ (x,_) -> x) <$>> d
, (\ (_,y) -> y) <$>> d
)
With the call tree
6961
6962
6963
6964
6965
6966
6967
6968
6969
6970
6971
6972
6973
6974
6975
6976
6977
| unvector2D Main 529 0 0.1 0.0 5.8 5.5 1 3080460
$f4 Data.VectorSpace 722 0 0.0 0.0 0.3 0.6 0 0
$f3 Data.AdditiveGroup 723 0 0.3 0.6 0.3 0.6 2 53396224
<$>> Data.Derivative 565 0 0.0 0.0 5.4 4.9 0 0
fmapD Data.Derivative 566 0 0.4 0.3 5.4 4.9 3 23903816
fmapD Data.Maclaurin 662 0 0.0 0.0 5.0 4.6 0 0
$f4 Data.Maclaurin 670 0 0.7 2.5 2.4 3.5 5 218451520
$f5 Data.Maclaurin 671 0 0.0 0.0 1.8 1.0 0 0
liftD2 Data.Maclaurin 672 0 0.3 0.5 1.8 1.0 2 47378016
liftL2 Data.LinearMap 1342 0 0.1 0.1 1.5 0.4 1 9246272
inL2 Data.LinearMap 1343 56596 0.8 0.1 1.4 0.3 6 10413664
inL Data.LinearMap 1344 56596 0.4 0.1 0.5 0.2 3 9960896
$f12 Data.LinearMap 1345 0 0.1 0.1 0.1 0.1 1 7923440
fmapL Data.LinearMap 663 0 0.5 0.2 2.6 1.1 4 15831680
inL Data.LinearMap 664 247370 1.8 0.5 2.0 0.9 13 43537120
$f12 Data.LinearMap 665 0 0.3 0.4 0.3 0.4 2 34631800
inT Data.Derivative 567 0 0.0 0.1 0.0 0.1 0 4928736 |
So, lets try make this tree dictioary-free, to see what happens.
We give the following functions the following types, by changing the code to add prime(’) and dollar($) versions, and making the auxiliary versions call other auxiliary versions.
type R = Double
type R2 = (Double,Double)
unvector2D :: (Data.LinearMap.LMapDom a s,VectorSpace s s) => (a :> (s,s)) -> (a :> s,a :> s)
unvector2D' :: ((R,R) :> (R,R)) -> ((R,R) :> R,(R,R) :> R)
(<$>>) :: (LMapDom a s, VectorSpace b s) => (b -> c) -> (a :> b) -> (a :> c)
(<$>>$) :: ((R,R) -> R) -> ((R,R) :> (R,R)) -> ((R,R) :> R)
fmapD :: (LMapDom a s, VectorSpace b s) => (b -> c) -> (a :> b) -> (a :> c)
fmapD' :: (D2 -> Double) -> (D2 :> D2) -> (D2 :> Double)
fmapL :: (LMapDom a s, VectorSpace b s) => (b -> c) -> (a :-* b) -> (a :-* c)
fmapL' :: ((D2 :> D2) -> (D2 :> Double)) -> (D2 :-* (D2 :> D2)) -> (D2 :-* (D2 :> Double))
There were some small refactors to get the types to be visiable correctly.
The tree now looks like this.
unvector2D' Main 230 51342 0.0 0.0 3.5 5.4 0 2669784
<$>>$ Data.Derivative 271 102684 0.1 0.0 3.5 5.3 1 1232208
fmapD' Data.Maclaurin 273 371028 0.1 0.2 3.2 5.3 1 18471984
fmapL' Data.Maclaurin 419 134172 0.5 0.3 3.1 5.1 4 24150960
$f4 Data.Maclaurin 430 0 0.6 1.5 2.6 4.6 5 127732736
$f5 Data.Maclaurin 435 0 0.0 0.0 1.2 1.6 0 0
liftD2 Data.Maclaurin 436 0 0.1 0.5 1.2 1.6 1 47381616
liftL2 Data.LinearMap 1401 0 0.1 0.1 0.6 0.5 1 9247392
$f12 Data.LinearMap 1699 0 0.0 0.0 0.1 0.0 0 0
$f4 Data.VectorSpace 1700 0 0.0 0.0 0.1 0.0 0 0
$f3 Data.AdditiveGroup 1701 0 0.1 0.0 0.1 0.0 1 3783360
inL2 Data.LinearMap 1402 56603 0.3 0.1 0.4 0.3 2 10414952
inL Data.LinearMap 1403 56603 0.1 0.1 0.1 0.2 1 9962128
$f12 Data.LinearMap 1404 0 0.0 0.1 0.0 0.1 0 7924420
$f12 Data.LinearMap 537 0 0.0 0.0 0.4 0.6 0 0
$f4 Data.VectorSpace 538 0 0.0 0.0 0.4 0.6 0 0
$f3 Data.AdditiveGroup 539 0 0.4 0.6 0.4 0.6 3 49616384
fmapD Data.Maclaurin 434 0 0.1 1.0 0.8 1.5 1 88587860
fmapL Data.LinearMap 1396 0 0.1 0.1 0.6 0.5 1 7245504
inL Data.LinearMap 1397 113211 0.3 0.2 0.5 0.4 2 19925136
$f12 Data.LinearMap 1398 0 0.3 0.2 0.3 0.2 2 15849540
$f12 Data.LinearMap 421 0 0.0 0.2 0.0 0.2 0 18784080
inT Data.Derivative 272 0 0.1 0.1 0.1 0.1 1 4928832
So we have fmapL' just before $f4 on the call graph. fmapL' in Haskell and Core looks like
fmapL' :: ((D2 :> D2) -> (D2 :> Double)) -> (D2 :-* (D2 :> D2)) -> (D2 :-* (D2 :> Double))
fmapL' = \ fn a -> linear (fmap fn (lapply a))
fmapL'_rfEg :: ((Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
-> Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
-> (Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2))
-> Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
[GlobalId]
[Arity 2]
fmapL'_rfEg =
\ (fn_afH5 :: (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
-> Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
(a_afH6 :: Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)) ->
__scc {fmapLzq main:Data.Maclaurin}
case $dLMapDom_rgnq
of tpl_B1 { Data.LinearMap.:DLMapDom tpl1_B2 tpl2_B3 tpl3_B4 ->
tpl3_B4
@ (Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
(((Control.Monad.Instances.$f4 @ (GHC.Float.Double, GHC.Float.Double))
`cast` ((GHC.Base.:Co:TFunctor) ((->) Data.Maclaurin.D2)
:: (GHC.Base.:TFunctor) ((->) Data.Maclaurin.D2)
~
forall a_a16n b_a16o.
(a_a16n -> b_a16o)
-> (Data.Maclaurin.D2 -> a_a16n)
-> Data.Maclaurin.D2
-> b_a16o))
@ (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
@ (Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
fn_afH5
(tpl2_B3
@ (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
$dVectorSpace1_rgnW
a_afH6))
}
The $f4 is a different $f4 than the one we are looking for (this one is from Control.Monad.Instances.$f4). So how does this end in invoking (our) $f4? We replace fmap with (.), the instance for fmap at the ((->) t) type, to avoid this needless dictionary.
fmapL' :: ((D2 :> D2) -> (D2 :> Double)) -> (D2 :-* (D2 :> D2)) -> (D2 :-* (D2 :> Double))
fmapL' = \ fn a -> linear (\ x -> fn (lapply a x))
fmapL'_rfwI :: ((Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
-> Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
-> (Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2))
-> Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
[GlobalId]
[Arity 2]
fmapL'_rfwI =
\ (fn_afzx :: (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
-> Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
(a_afzy :: Data.Maclaurin.D2
Data.LinearMap.:-* (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)) ->
__scc {fmapLzq main:Data.Maclaurin}
case $dLMapDom_rgfW
of tpl_B1 { Data.LinearMap.:DLMapDom tpl1_B2 tpl2_B3 tpl3_B4 ->
tpl3_B4
@ (Data.Maclaurin.D2 Data.Maclaurin.:> GHC.Float.Double)
(\ (x_afzA :: Data.Maclaurin.D2) ->
fn_afzx
(tpl2_B3
@ (Data.Maclaurin.D2 Data.Maclaurin.:> Data.Maclaurin.D2)
$dVectorSpace1_rggs
a_afzy
x_afzA))
}
<code>
Our profiling listing gives:
<command>
unvector2D' Main 230 51099 0.1 0.0 4.9 5.4 1 2657148
<$>>$ Data.Derivative 271 102198 0.3 0.0 4.7 5.3 2 1226376
fmapD' Data.Maclaurin 273 363738 0.4 0.2 4.2 5.3 3 18096792
fmapL' Data.Maclaurin 419 130770 0.1 0.1 3.8 5.0 1 7323120
$f12 Data.LinearMap 421 0 0.5 0.7 3.7 4.9 4 49328560
$f4 Data.VectorSpace 537 0 0.0 0.0 0.5 0.6 0 0
$f2 Data.AdditiveGroup 538 0 0.5 0.6 0.5 0.6 4 44877248
$f4 Data.Maclaurin 430 0 1.2 1.5 2.6 3.6 9 107289632
$f5 Data.Maclaurin 435 0 0.0 0.0 0.8 0.9 0 0
liftD2 Data.Maclaurin 436 0 0.3 0.5 0.8 0.9 2 40021632
liftL2 Data.LinearMap 1399 0 0.3 0.1 0.5 0.3 2 7151760
inL2 Data.LinearMap 1400 43967 0.3 0.1 0.3 0.2 2 8089928
inL Data.LinearMap 1401 43967 0.0 0.1 0.0 0.1 0 7738192
fmapD Data.Maclaurin 434 0 0.3 1.0 0.7 1.3 2 74334452
fmapL Data.LinearMap 1395 0 0.1 0.1 0.4 0.3 1 5628096
inL Data.LinearMap 1396 87939 0.3 0.2 0.3 0.2 2 15477264
inT Data.Derivative 272 0 0.3 0.1 0.3 0.1 2 4905504
Strange, we have a call to $f12 before the call to $f4. But we *know* fmapL' does not call dictionaries. Time to add explicit annotations.
fmapL' :: ((D2 :> D2) -> (D2 :> Double)) -> (D2 :-* (D2 :> D2)) -> (D2 :-* (D2 :> Double))
fmapL' = \ fn a -> {-# SCC "fmapL'_body" #-} linear ({-# SCC "fmapL'_linear_arg" #-} (\ x -> {-# SCC "fmapL'_0" #-} fn ({-# SCC "fmapL'_1" #-} (lapply a x))))
These annotations give this profile
unvector2D' Main 230 51018 0.1 0.0 5.2 5.4 1 2652936
<$>>$ Data.Derivative 271 102036 0.3 0.0 5.1 5.4 2 1224432
fmapD' Data.Maclaurin 273 361308 0.1 0.3 4.8 5.3 1 17971728
fmapL' Data.Maclaurin 419 129636 0.0 0.0 4.6 5.0 0 0
fmapL'_body Data.Maclaurin 420 129636 0.0 0.0 4.6 5.0 0 0
$f12 Data.LinearMap 424 0 0.6 0.3 0.6 0.3 4 18149040
fmapL'_linear_arg Data.Maclaurin 422 0 0.0 0.0 4.1 4.7 0 0
fmapL'_0 Data.Maclaurin 423 261680 0.0 0.0 4.1 4.7 0 2074176
fmapL'_1 Data.Maclaurin 429 259272 0.0 0.1 4.1 4.7 0 5185440
$f12 Data.LinearMap 430 0 0.3 0.4 4.1 4.6 2 29142856
$f4 Data.VectorSpace 542 0 0.0 0.0 0.4 0.6 0 0
$f2 Data.AdditiveGroup 543 0 0.4 0.6 0.4 0.6 3 42036416
$f4 Data.Maclaurin 435 0 1.0 1.5 3.4 3.6 7 100475264
$f5 Data.Maclaurin 440 0 0.0 0.0 1.5 0.8 0 0
liftD2 Data.Maclaurin 441 0 0.6 0.5 1.5 0.8 4 37568304
liftL2 Data.LinearMap 1404 0 0.4 0.1 1.0 0.3 3 6453216
inL2 Data.LinearMap 1405 39755 0.3 0.1 0.6 0.2 2 7314920
inL Data.LinearMap 1406 39755 0.3 0.1 0.3 0.1 2 6996880
fmapD Data.Maclaurin 439 0 0.6 1.0 0.8 1.3 4 69583316
fmapL Data.LinearMap 1400 0 0.0 0.1 0.3 0.3 0 5088960
inL Data.LinearMap 1401 79515 0.3 0.2 0.3 0.2 2 13994640
inT Data.Derivative 272 0 0.0 0.1 0.0 0.1 0 4897728
We crank the handle again, with more annotations determining that it is the call to lapply that is the sub-expression that triggers the call to $12, then $4. This one is turning out to be tricky! The cost of $4 is inside a call lapply, between the application and the arrival at the destination. Something is missing here.
Stuck for ideas, , we looked hard at lapply. What arguments is it getting called with?
-- | Domain of a linear map.
class VectorSpace a s => LMapDom a s | a -> s where
-- | Linear map type
data (:-*) a :: * -> *
-- | Linear map as function
lapply :: VectorSpace b s => (a :-* b) -> (a -> b)
-- | Function (assumed linear) as linear map.
linear :: (a -> b) -> (a :-* b)
instance (LMapDom a s, LMapDom b s) => LMapDom (a,b) s where
data (a,b) :-* o = PairL (a :-* o) (b :-* o)
PairL ao bo `lapply` (a,b) = ao `lapply` a ^+^ bo `lapply` b
linear f = PairL (linear (\ a -> f (a,zeroV)))
(linear (\ b -> f (zeroV,b)))
After inserting a trace in lapply, it turns out that the lapply argument is *always* (0.0,1.0) or (1.0,0.0). Scope for a good, generic memoization mechanism. No sign of our call to $f4 yet, but at least we have a way of speeding things up, then repeating the safari.
If this seems like we are jumping around all over the place, we yes, we are! Record what you have measured, be careful what you change, and test your assumptions are the meta-rules here. The next blog will try add some memoization.