Julia/LLVM高效实现整数除法并返回整数结果

Question

Julia/LLVM高效实现整数除法并返回整数结果

5

我遇到了一个基本的类型稳定性问题，在这个问题中，两个 Integer 的除法会产生某些具体类型的 AbstractFloat。

typeof(60 * 5 / 60)
> Float64

现在这样做是安全的，但会产生运行时开销，因为需要将其转换为浮点数。

如果我们知道除法总是会得到一个余数为0的数字，即一个整数，我们可以使用以下任一方法：

div(60 * 5 , 60) 
fld(60 * 5 , 60)

这样我们得到了一些具体类型的 整数(Integer)，但是这种方法仍然有一些额外开销，可以从LLVM IR中看出：

@code_llvm  div(60 * 5 , 60)

那么，在我们知道结果不会有余数时，有没有什么魔法可以去除运行时开销呢？

可能的解决方案：

我更喜欢使用Julia的构造来解决这个问题，即使我们需要创建它，而不是注入LLVM IR... 但是，我们也可以将该注入封装到一个Julia函数中...

或者，我们需要一个类似于@inbounds的宏，用于安全地进行整数除法并产生整数。

或者，也许有一些纯数学方法可以在任何语言中执行此操作？

- BAR

注意：可以使用“\div<tab>”来减少视觉开销，它会产生“÷”。 “a÷b”等同于“div(a,b)”。 - Dan Getz

2个回答

10

整数除法是CPU上最慢的缓存无关操作之一；实际上，在大多数CPU上，浮点除法更快（您可以自己测试并查看）。如果您事先知道要除以什么（并且想多次除以它），则可以预先计算因子，从而允许您用乘法/移位/加法替换整数除法。有许多网站描述了这个基本思想，这里有一个。

对于julia的实现，请参见https://gist.github.com/simonster/a3b691e71cc2b3826e39

- tholy

1

更新：Julia现在有非导出的SignedMultiplicativeInverse和UnsignedMultiplicativeInverse类型，允许您使用此技巧而无需自行编写代码。 - tholy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mbauman · Accepted Answer

你是对的 - div 函数确实有一定的开销，但这并不是因为它可能存在余数。而是因为 div(typemin(Int),-1) 和 div(x, 0) 都会导致错误。所以你在 @code_llvm 中看到的开销只是为了检查这些情况。你需要的 LLVM 指令只是 sdiv i64 %0, %1... 并且处理器甚至会在这些错误条件下抛出 SIGFPE。我们可以使用 llvmcall 创建自己的“无开销”版本：

julia> unsafe_div(x::Int64,y::Int64) = Base.llvmcall("""
           %3 = sdiv i64 %0, %1
           ret i64 %3""", Int64, Tuple{Int64, Int64}, x, y)
unsafe_div (generic function with 1 method)

julia> unsafe_div(8,3)
2

julia> @code_llvm unsafe_div(8,3)

define i64 @julia_unsafe_div_21585(i64, i64) {
top:
  %2 = sdiv i64 %0, %1
  ret i64 %2
}

julia> unsafe_div(8,0)
ERROR: DivideError: integer division error
 in unsafe_div at none:1

那么，如果这样有效，为什么Julia坚持要将这些检查插入到LLVM IR中呢？这是因为LLVM认为这些错误情况在其优化过程中属于未定义行为。因此，如果LLVM能够通过静态分析证明它会出错，它就会更改其输出以跳过整个除法（和随后的异常）！这个自定义的div函数确实是不安全的：

julia> f() = unsafe_div(8,0)
f (generic function with 2 methods)

julia> f()
13315560704

julia> @code_llvm f()

define i64 @julia_f_21626() {
top:
  ret i64 undef
}

在我的机器上（一台旧的 Nehalem i5），这个不安全的版本可以将 div 的速度提高约 5-10%，因此相对于整数除法的固有成本，这里的开销并不是非常可怕。正如@tholy所指出的那样，与几乎所有其他 CPU 操作相比，它仍然非常慢，因此如果您经常使用相同的数字进行除法运算，则可能需要查看他的答案中提供的替代方案。