我有一个程序,它大部分时间都在计算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 %。
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版本更快,但我决定使用标量版本。
https://stackoverflow.com/questions/22445019
复制相似问题