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

Question

I'm playing around with the decimal to binary converter 'bin()' in Julia, wanting to improve performance. I need to use BigInts for this problem, and calling bin() with a bigInt from within my file outputs the correct binary representation; however, calling a function similar to the bin() function costs a minute in time, while bin() takes about .003 seconds. Why is there this huge difference?

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

As noted by Felipe Lema, Base delegates BigInt printing to GMP, which can print BigInts without doing any intermediate computations with them – doing lots of computations with BigInts to figure out their digits is quite slow and ends up allocating a lot of memory. The bottom line: doing x >>= 1 is extremely efficient for things like Int64 values but not that efficient for things like BigInts.

Answer 2

Using 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() 

I could also see a huge difference in bytes allocates (bin1:1000106, bin2:62648125016) which would require some more profiling and tunning, but I guess the previous paragraph is enough for an answer.