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

Question

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

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))]

哪个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 版本速度更快，但我决定使用标量版本。

Answer 1

嗯，我尝试了一下基准测试。我用Criterion对于基准，因为它做了适当的显着性测试。我也用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

输出:

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

我使用absolute integer value来自“Bit Twiddling Hacks here”的技巧。不幸的是我们需要强制转换，我认为单独在 Word8 领域不可能很好地解决问题，但无论如何使用 native 整数类型似乎是明智的(绝对没有必要)创建一个堆对象)。

它看起来并没有很大的差异，但我的测试设置也不完美:我将函数映射到大量随机值以排除分支预测，从而使分支版本看起来比实际更有效。这会导致 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-}
                                  {-]-}
         ]