快速、无分支的 unsigned int 绝对差

我有一个程序，它花费大部分时间计算 RGB 值之间的欧几里德距离（无符号 8 位的 3 元组）Word8）。我需要一个快速、无分支的 unsigned int 绝对差函数，这样

unsigned_difference :: Word8 -> Word8 -> Word8
unsigned_difference a b = max a b - min a b

尤其，

unsigned_difference a b == unsigned_difference b a

我使用 GHC 7.8 中的新 primops 得出了以下结论：

-- (a < b) * (b - a) + (a > b) * (a - b)
unsigned_difference (I# a) (I# b) =
    I# ((a <# b) *# (b -# a) +# (a ># b) *# (a -# b))]

which ghc -O2 -S编译为

.Lc42U:
    movq 7(%rbx),%rax
    movq $ghczmprim_GHCziTypes_Izh_con_info,-8(%r12)
    movq 8(%rbp),%rbx
    movq %rbx,%rcx
    subq %rax,%rcx
    cmpq %rax,%rbx
    setg %dl
    movzbl %dl,%edx
    imulq %rcx,%rdx
    movq %rax,%rcx
    subq %rbx,%rcx
    cmpq %rax,%rbx
    setl %al
    movzbl %al,%eax
    imulq %rcx,%rax
    addq %rdx,%rax
    movq %rax,(%r12)
    leaq -7(%r12),%rbx
    addq $16,%rbp
    jmp *(%rbp)

编译用ghc -O2 -fllvm -optlo -O3 -S生成以下 asm：

.LBB6_1:
    movq    7(%rbx), %rsi
    movq    $ghczmprim_GHCziTypes_Izh_con_info, 8(%rax)
    movq    8(%rbp), %rcx
    movq    %rsi, %rdx
    subq    %rcx, %rdx
    xorl    %edi, %edi
    subq    %rsi, %rcx
    cmovleq %rdi, %rcx
    cmovgeq %rdi, %rdx
    addq    %rcx, %rdx
    movq    %rdx, 16(%rax)
    movq    16(%rbp), %rax
    addq    $16, %rbp
    leaq    -7(%r12), %rbx
    jmpq    *%rax  # TAILCALL

因此，LLVM 设法用（更有效？）条件移动指令代替比较。不幸的是编译时使用-fllvm对我的程序的运行时间影响不大。

然而，这个功能有两个问题。

• 我想比较Word8，但是比较 primops 需要使用Int。这会导致不必要的分配，因为我被迫存储 64 位Int而不是一个Word8.

我已经分析并确认了使用fromIntegral :: Word8 -> Int占该计划总拨款的 42.4%。

• 我的版本使用 2 次比较、2 次乘法和 2 次减法。我想知道是否有更有效的方法，使用按位运算或 SIMD 指令并利用我正在比较的事实Word8.

我之前已经标记过这个问题C/C++以吸引那些更倾向于位操作的人的注意。我的问题使用 Haskell，但我会接受以任何语言实现正确方法的答案。

结论：

我决定使用

w8_sad :: Word8 -> Word8 -> Int16
w8_sad a b = xor (diff + mask) mask
    where diff = fromIntegral a - fromIntegral b
          mask = unsafeShiftR diff 15

因为它比我原来的要快unsigned_difference功能齐全，实现简单。 Haskell 中的 SIMD 内在函数尚未成熟。因此，虽然 SIMD 版本速度更快，但我决定使用标量版本。

好吧，我试着进行了一些基准测试。我用标准 http://hackage.haskell.org/package/criterion-0.8.0.1对于基准，因为它做了适当的显着性测试。我也用快速检查 http://hackage.haskell.org/package/QuickCheck这里确保所有方法返回相同的结果。

我使用 GHC 7.6.3 进行编译（不幸的是，我无法包含您的 primops 函数）并使用-O3:

ghc -O3 AbsDiff.hs -o AbsDiff && ./AbsDiff

首先，我们可以看到简单的实现和一些小改动之间的区别：

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
...

我用绝对整数值 http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs来自“Bit Twiddling Hacks here”的技巧。不幸的是我们需要强制转换，我认为不可能在以下领域很好地解决问题Word8单独使用，但无论如何使用本机整数类型似乎都是明智的（但绝对不需要创建堆对象）。

它看起来并不是很大的差异，但我的测试设置也不完美：我将函数映射到大量随机值上，以排除分支预测，从而使分支版本看起来比实际更有效。这会导致 thunk 在内存中积累，这可能会极大地影响时间。当我们减去维护列表的恒定开销时，我们很可能会看到比 20% 的加速要多得多的结果。

生成的程序集实际上非常好（这是该函数的内联版本）：

.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 次减法、1 次加法、1 次右移、1 次异或且无分支。使用 LLVM 后端并不会显着改善运行时间。

如果您想尝试更多东西，希望这对您有用。

{-# 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-}
                                  {-]-}
         ]