Julia/LLVM使用整数结果对整数进行有效划分

Question

我遇到了一个基本类型稳定性问题,其中划分两个Integers将产生一些具体类型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上与缓存无关的最慢操作之一; 实际上,大多数CPU上的浮点除法速度更快(自己测试一下).如果您事先知道要分割的内容(并希望将其除以多次),则可以使用预先计算因子来进行乘法/移位/加法替换整数除法.有许多网站描述了这个基本想法,这里是一个.

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

Answer 2

你是对的 - 函数中有一点开销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操作相比,它仍然非常慢,所以如果你经常除以相同的数字,你可能想要在他的答案中研究替代方案.