Hi Rahul,

The reason I thought that maybe GHC didn't call the CPU instruction was due to my benchmarking, which showed that the built-in popCount was slower than the pure Haskell Broadword implementation:

main = defaultMain
  [ env setupEnv (\bv -> bgroup "Rank"
    [ bench "PopCnt1 Broadword - Once" (nf   (map (\n -> getCount (PC1BW.popCount1  (DVS.take n bv)))) [0, 1000..100000])
    , bench "PopCnt1 GHC       - Once" (nf   (map (\n -> getCount (PC1GHC.popCount1 (DVS.take n bv)))) [0, 1000..100000])
    ] )
  ]

Benchmarking results follow:

benchmarking Rank/PopCnt1 Broadword - Once
time                 18.49 ms   (17.89 ms .. 19.08 ms)
                     0.994 R²   (0.989 R² .. 0.998 R²)
mean                 19.62 ms   (19.22 ms .. 20.04 ms)
std dev              1.026 ms   (846.2 μs .. 1.315 ms)
variance introduced by outliers: 21% (moderately inflated)

benchmarking Rank/PopCnt1 GHC       - Once
time                 36.80 ms   (36.25 ms .. 37.57 ms)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 37.14 ms   (36.72 ms .. 37.97 ms)
std dev              1.100 ms   (650.6 μs .. 1.680 ms)

This makes the built-in nearly two times slower than the pure Haskell.  That's how I got into the ghc-prim code.

This is the broadword implementation I was using:

  popCount1 x0 = ((x3 * 0x0101010101010101) .>. 56)
    where
      x1 = x0 - ((x0 .&. 0xaaaaaaaaaaaaaaaa) .>. 1)
      x2 = (x1 .&. 0x3333333333333333) + ((x1 .>. 2) .&. 0x3333333333333333)
      x3 = (x2 + (x2 .>. 4)) .&. 0x0f0f0f0f0f0f0f0f

Maybe all I need to do is compile with some flags or switch the backend or something?  Any ideas?

Cheers,

-John


On Thu, 24 Mar 2016 at 08:28 John Ky <newhoggy@gmail.com> wrote:
Hi Rahul,

I see mention of the popcount instruction in nativeGen/X86/CodeGen.hs.  In particular it looks like it only activates if sse4_2 is activated?  Maybe all I need to do is activate this somehow?

Cheers,

-John

On Wed, 23 Mar 2016 at 12:07 <rahulmutt@gmail.com> wrote:
Hi John,

ghc-prim is just a stub package generated for the purpose of documentation. All primops are defined in a low level language called Cmm in GHC. If you want to make it even faster, you'll need to learn Cmm and update the definition in GHC. If you want to a specialized implementation for x86 systems, you may need to modify the NCG (Native Code Generator) which requires a knowledge of assembly language.

Hope that helps!
Rahul Muttineni

Sent from my BlackBerry 10 smartphone.
From: John Ky
Sent: Wednesday 23 March 2016 4:40 AM
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell
Reply To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell
Subject: [Haskell-beginners] let x = x in x (GHC.Prim)

Hello Haskellers,

I'm trying to write a faster popCount function for x86 systems.

I tried cloning the ghc-prim package and repurposing it for my own needs, but it isn't working as hoped.

In particular, popCnt64# was implemented in GHC.Prim as:

popCnt64# = let x = x in x

Which shouldn't terminate.  Yet when I call it, it magically finds the C implementation in hs_popcnt64 and returns the correct value.

My cloned project doesn't behave that way.  Instead it doesn't terminate as I would expect.

Anyone know what's happening here, if there is a way to make this work or tell me if I'm going about this completely the wrong way?

Cheers,

-John


_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners