Happy Thanksgiving Week!

[Arthur Chan]

Hey Everyone,

Hope you are all warm and comfortable, and off to a grateful and cozy week.

Would there be much interest, amongst those of you remaining in-town, in a hack-in of any sort? I'm having performance problems with my code, and I'd love to have some company while I bang my head at it.

Cheers,
.arthur

[Johan Tibell]

Hi Arthur,

I won't be able to meet in person, but if you have some specific piece of code that is performing badly, send it my way and I'll have a look.

-- Johan

--
You received this message because you are subscribed to the Google Groups "Bay Area Haskell Users Group" group.
To post to this group, send email to baha...@googlegroups.com.
To unsubscribe from this group, send email to bahaskell+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Arthur Chan]

Hey Johan,

If you could look at it, I'd be ecstatic, because I've thrown everything I know at it. The code is at http://github.com/baguasquirrel/Stats-Clustering

The offending code is the ziggurat algorithm (in Statistics.Distribution.Gaussian), which I've correctly implemented (you can test it with the histogram function), but it is strangely less performant than Box-Muller.

There's two scripts, Statistics.TestZiggurat and Statistics.TestBoxMuller, which you can use as entry points into the code.

Cheers,

Arthur

[Arthur Chan]

I guess a little background would be useful too.

The Ziggurat code may look a lot more conplicated than the Box-Muller in normaldistribution, but it should run faster because in most cases (97% of the time with a table size of 128), it just needs a few bit masks and multiplies, vs the sin, cos, sqrt and log of Box-Muller.

Arthur :: LittleBrick

On Nov 18, 2012, at 9:30 AM, Johan Tibell <johan....@gmail.com> wrote:

[Bryce Verdier]

What day are you thinking? I migrant be able to join in depending on that and location.

Happy turkey day!

Bryce

[Johan Tibell]

Hi Arthur,

I think the amount of polymorphism is killing performance (e.g. all those overloaded functions). It is definitely possible to get such code to go fast, but it requires a bit more expertise. The main things I got from looking at ziggurat is:

• You're using boxed Vectors. Even with the SPECIALIZE pragma, those Vectors won't become unboxed. If you want the code to stay polymorphic you can use add an Unbox type class constraint on ziggurat and switch to unboxed Vectors.
• RandomGen is not specialized, so there will be some overhead each time a random number is required.

I took a quick look at the Core. You can find the core for ziggurat here at https://gist.github.com/4106836 . There are two interesting things to note. First, lets look at the type:

$fUniformGaussianValuesDoubleDouble_ziggurat
  :: forall g_a2D9.
     RandomGen g_a2D9 =>
     (Vector Double, Vector Double, Vector Word)
     -> g_a2D9 -> (Double, g_a2D9)

Here we see that:

• RandomGen hasn't been specialized away.
• We're using boxed Vectors of boxed Doubles.

There's a lot of Core in the body, but note that this happens a lot:

case $wrandomIvalInteger
       @ g_a2D9
       @ Word
       $dRandomGen_a2Da
       $fNumWord
       $fRandomCSize4
       $fRandomCSize3
       g1_X1UE

This is the call to the unspecialized RandomGen. Note how we're passing a number of dictionary parameters here.

I also recommend that you look at Bryan's statistics package, which tackles a similar domain and has good performance from what I understand.

[Johan Tibell]

Hi Arthur,

I added the Unbox constraint and also added RandomGem to the SPECIALISE pragma:

{-# SPECIALISE INLINE ziggurat :: (VU.Vector Float, VU.Vector Float, VU.Vector Word) -> PureMT -> (Float,PureMT) #-}
{-# SPECIALISE INLINE ziggurat :: (VU.Vector Double, VU.Vector Double, VU.Vector Word) -> PureMT -> (Double,PureMT) #-}
{-# INLINE ziggurat #-}
ziggurat :: (Floating p, Ord p, R.Random p, Show p, VU.Unbox p, R.RandomGen g)
         => (VU.Vector p, VU.Vector p, VU.Vector Word)
         -> g
         -> (p,g)

(I also had to change some calls to V.foo to VU.foo and change some other type signatures.)

The code is now using unboxed vectors, which is good. From looking at the core, it's still not specializing correctly on the RandomGen correctly. That might be due to a performance bug in the random package or due to missing type signatures in ziggurat (causing some values to be treated as Integers). I suggest you add type signatures to the local function definitions in ziggurat (you might need the ScopedTypeVariables extension).

FYI, this is the command I used to generate the Core:

ghc -O2 Statistics/Distributions/Gaussian.hs -ddump-simpl -dsuppress-coercions -dsuppress-idinfo -dsuppress-module-prefixes -fforce-recomp > /tmp/Gaussian.hcr

-- Johan

[Arthur Chan]

Hey Bryce

I'm in Pali Alto but I've no problem going up to SF. I'm busy Friday but no other obligations yet. I'd prefer a time in the morning if that's ok with you.

Arthur

[Arthur Chan]

Hey Johan

Much gratitude for your suggestions. I think I'm going to need to play with it this week, so I'll have something interesting to tell.

Arthur :: LittleBrick