Well, I tried to benchmark a bit. I use Criterion for the benchmarks, because it does proper significance tests. I also use QuickCheck here to ensure that all methods return the same results.
I compiled with GHC 7.6.3 (so I couldn't include your primops function, unfortunately) and with -O3
:
ghc -O3 AbsDiff.hs -o AbsDiff && ./AbsDiff
Primarily we can see the difference between a naive implementation and a bit of fiddeling:
absdiff1_w8 :: Word8 -> Word8 -> Word8
absdiff1_w8 a b = max a b - min a b
absdiff2_w8 :: Word8 -> Word8 -> Word8
absdiff2_w8 a b = unsafeCoerce $ xor (v + mask) mask
where v = (unsafeCoerce a::Int64) - (unsafeCoerce b::Int64)
mask = unsafeShiftR v 63
Output:
benchmarking absdiff_Word8/1
mean: 249.8591 us, lb 248.1229 us, ub 252.4321 us, ci 0.950
....
benchmarking absdiff_Word8/2
mean: 202.5095 us, lb 200.8041 us, ub 206.7602 us, ci 0.950
...
I use the absolute integer value trick from "Bit Twiddling Hacks here". Unfortunately we need casts, I don't think that it is possible to solve the problem well in the domain of Word8
alone, but it seems sensible to use the native integer type anyway (there's definitely no need to create a heap object though ).
It doesn't really look like a large difference, but my test setup is also not perfect: I am mapping the function over a large list of random values to rule out branch prediction making the branching version seem more efficient than it is. This causes thunks to build up in memory, which could influence the timings a lot. When we subtract the constant overhead for maintaining the list, we could well see a lot more than the 20% speedup.
The generated assembly is actually pretty good (this is an inlined version of the function):
.Lc4BB:
leaq 7(%rbx),%rax
movq 8(%rbp),%rbx
subq (%rax),%rbx
movq %rbx,%rax
sarq $63,%rax
movq $base_GHCziInt_I64zh_con_info,-8(%r12)
addq %rax,%rbx
xorq %rax,%rbx
movq %rbx,0(%r12)
leaq -7(%r12),%rbx
movq $s4z0_info,8(%rbp)
1 subtraction, 1 addition, 1 right-shift, 1 xor and no branch, as expected. Using the LLVM backend doesn't improve the runtime noticably.
Hope this is useful if you want to try out more stuff.
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Main where
import Data.Word
import Data.Int
import Data.Bits
import Control.Arrow ((***))
import Control.DeepSeq (force)
import Control.Exception (evaluate)
import Control.Monad
import System.Random
import Unsafe.Coerce
import Test.QuickCheck hiding ((.&.))
import Criterion.Main
absdiff1_w8 :: Word8 -> Word8 -> Word8
absdiff1_w8 !a !b = max a b - min a b
absdiff1_int16 :: Int16 -> Int16 -> Int16
absdiff1_int16 a b = max a b - min a b
absdiff1_int :: Int -> Int -> Int
absdiff1_int a b = max a b - min a b
absdiff2_int16 :: Int16 -> Int16 -> Int16
absdiff2_int16 a b = xor (v + mask) mask
where v = a - b
mask = unsafeShiftR v 15
absdiff2_w8 :: Word8 -> Word8 -> Word8
absdiff2_w8 !a !b = unsafeCoerce $ xor (v + mask) mask
where !v = (unsafeCoerce a::Int64) - (unsafeCoerce b::Int64)
!mask = unsafeShiftR v 63
absdiff3_w8 :: Word8 -> Word8 -> Word8
absdiff3_w8 a b = if a > b then a - b else b - a
{-absdiff4_int :: Int -> Int -> Int-}
{-absdiff4_int (I# a) (I# b) =-}
{-I# ((a <# b) *# (b -# a) +# (a ># b) *# (a -# b))-}
e2e :: (Enum a, Enum b) => a -> b
e2e = toEnum . fromEnum
prop_same1 x y = absdiff1_w8 x y == absdiff2_w8 x y
prop_same2 (x::Word8) (y::Word8) = absdiff1_int16 x' y' == absdiff2_int16 x' y'
where x' = e2e x
y' = e2e y
check = quickCheck prop_same1
>> quickCheck prop_same2
instance (Random x, Random y) => Random (x, y) where
random gen1 =
let (x, gen2) = random gen1
(y, gen3) = random gen2
in ((x,y),gen3)
main =
do check
!pairs_w8 <- fmap force $ replicateM 10000 (randomIO :: IO (Word8,Word8))
let !pairs_int16 = force $ map (e2e *** e2e) pairs_w8
defaultMain
[ bgroup "absdiff_Word8" [ bench "1" $ nf (map (uncurry absdiff1_w8)) pairs_w8
, bench "2" $ nf (map (uncurry absdiff2_w8)) pairs_w8
, bench "3" $ nf (map (uncurry absdiff3_w8)) pairs_w8
]
, bgroup "absdiff_Int16" [ bench "1" $ nf (map (uncurry absdiff1_int16)) pairs_int16
, bench "2" $ nf (map (uncurry absdiff2_int16)) pairs_int16
]
{-, bgroup "absdiff_Int" [ bench "1" $ whnf (absdiff1_int 13) 14-}
{-, bench "2" $ whnf (absdiff3_int 13) 14-}
{-]-}
]