Julia/LLVM 整数结果的高效整数除法

Question

我运行是一个基本类型稳定性问题，其中将两个 Integer 分开会产生一些具体类型 AbstractFloat.

typeof(60 * 5 / 60)
> Float64

现在这是安全的做法，但它会导致转换为浮点数的运行时开销。

如果我们知道除法总是得到一个余数为 0 的数，那会怎样呢？一个 Integer？

我们可以使用：

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

这给了我们一些具体的类型Integer，但是这种方法仍然有开销，我们可以从 LLVM IR 中看到：

@code_llvm  div(60 * 5 , 60)

那么，当我们知道结果不会有余数时，是否有什么魔法可以消除运行时开销？

可能的解决路径：

我更希望使用 Julia 构造来解决这个问题，即使我们需要创建它，而不是注入 LLVM IR...但是话又说回来，我们可以将该注入包装到 Julia 函数中...

或者我们可能需要像 @inbounds 这样的宏来进行安全的整数除法。

或者也许有一些适用于任何语言的纯数学方法来执行此操作？

Answer 1

整数除法是 CPU 上最慢的 cache-independent 运算之一；事实上，floating-point 除法在大多数 CPU 上更快（自己测试看看）。如果您事先知道要除以什么（并且想多次除以它），那么预先计算允许您将 integer-division 替换为 multiplication/shift/add 的因子可能是值得的。有很多网站描述了这个基本思想，here's one。

有关 julia 的实现，请参阅 https://gist.github.com/simonster/a3b691e71cc2b3826e39

Answer 2

你是对的 - div 函数中有一点开销，但这不是因为可能还有剩余部分。这是因为 div(typemin(Int),-1) 和 div(x, 0) 一样是一个错误。因此，您在 @code_llvm 中看到的开销只是对这些情况的检查。在这些错误条件下，您想要的 LLVM 指令只是 sdiv i64 %0, %1… and the processor will even throw a SIGFPE。我们可以使用 llvmcall 创建我们自己的 "overhead-free" 版本：

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 可以通过静态分析证明它会出错，它 更改其输出 以完全跳过 division（和随后的异常）！这个自定义 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%，所以相对于整数 division。正如 @tholy 指出的那样，与几乎所有其他 CPU 操作相比，它仍然非常慢，因此如果您经常 dividing 相同的数字，您可能需要调查他的替代方案回答。

Julia/LLVM 整数结果的高效整数除法

Julia/LLVM Efficient Division of Integer Numbers with Integer Result

mathematical-optimization

llvm

julia