Julia：基本功能比类似功能快 10,000 倍

Question

我正在使用 Julia 中的十进制到二进制转换器 'bin()'，希望提高性能。我需要使用 BigInts 来解决这个问题，并从我的文件中使用 bigInt 调用 bin() 输出正确的二进制表示；然而，调用类似于 bin() 函数的函数需要一分钟的时间，而 bin() 需要大约 0.003 秒。为什么会有这么大的差异？

function binBase(x::Unsigned, pad::Int, neg::Bool)
    i = neg + max(pad,sizeof(x)<<3-leading_zeros(x))
    a = Array(Uint8,i)
    while i > neg
        a[i] = '0'+(x&0x1)
        x >>= 1
        i -= 1
    end
    if neg; a[1]='-'; end
    ASCIIString(a)
end



function bin1(x::BigInt, pad::Int)
    y = bin(x)
end



function bin2(x::BigInt, pad::Int,a::Array{Uint8,1}, neg::Bool)
    while pad > neg
        a[pad] = '0'+(x&0x1)
        x >>= 1
        pad -= 1
    end
    if neg; a[1]='-'; end
    ASCIIString(a)
end




function test()
    a = Array(Uint8,1000001)
    x::BigInt= 2
    x = (x^1000000)


    @time bin1(x,1000001)
    @time bin2(x,1000001,a,true)

end

test()

Answer 1

使用 julia's profiling tools I can see that Base.bin is calling a C function from libGMP, which has all sorts of machine specific optimizations (somewhere here is mpn_get_str that is being called).

@profile bin1(x,1000001)
Profile.print()
Profile.clear()
@profile bin2(x,1000001,a,true)
Profile.print()
Profile.clear()

我还可以看到分配的字节数存在巨大差异（bin1:1000106，bin2:62648125016），这需要进行更多的分析和调整，但我想前一段足以给出答案。

Answer 2

正如 Felipe Lema 所指出的，Base 将 BigInt 打印委托给 GMP，GMP 可以打印 BigInts 而无需对它们进行任何中间计算 - 使用 BigInts 进行大量计算以找出它们的数字非常慢并且最终分配了很多的记忆。底线：x >>= 1 对于 Int64 值之类的东西非常有效，但对于 BigInts 这样的东西效率不高。

Julia：基本功能比类似功能快 10,000 倍

Julia: Base function 10,000x quicker then similar function

binary

julia