快速、无分支的无符号整数绝对差分
快速、无分支的无符号整数绝对差分
提问于 2014-03-17 08:27:28
我有一个程序，它大部分时间都在计算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，但是比较原始码需要使用Int。这导致了不必要的分配，因为我被迫存储64位Int而不是Word8.
我已经分析并确认，fromIntegral :: Word8 -> Int的使用占该计划总分配的42.4 %。
- 我的版本使用2个比较，2个乘法和2个减法。我想知道是否有更有效的方法，使用按位操作或单指令多数据指令，并利用我正在比较
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版本更快，但我决定使用标量版本。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22445019
复制相关文章
相似问题