CODEWITHSUNDEEP
memoryjulia
Pigna
Pigna

Reputation: 2924

Julia: efficient memory allocation

My program is memory-hungry, so I need to save as much memory as I can. When you assign an integer value to a variable, the type of the value will always be Int64, whether it's 0 or +2^63-1 or -2^63. I couldn't find a smart way to efficiently allocate memory, so I wrote a function that looks like this (in this case for integers):

function right_int(n)
    types = [Int8,Int16,Int32, Int64, Int128]
    for t in reverse(types)
        try
            n = t(n)
        catch InexactError
            break
        end
    end
    n
end

a = right_int(parse(Int,eval(readline(STDIN))))

But I don't think this is a good way to do it.

I also have a related problem: what's an efficient way of operating with numbers without worrying about typemins and typemaxs? Convert each operand to BigInt and then apply right_int?

Upvotes: 3

Views: 1018

Answers (1)

mbauman
mbauman

Reputation: 31342

You're missing the forest for the trees. right_int is type unstable. Type stability is a key concept in reducing allocations and making Julia fast. By trying to "right-size" your integers to save space, you're actually causing more allocations and higher memory use. As a simple example, let's try making a "right-sized" array of 100 integers from 1-100. They're all small enough to fit in Int8, so that's just 100 bytes plus the array header, right?

julia> @allocated [right_int(i) for i=1:100]
26496

Whoa, 26,496 bytes! Why didn't that work? And why is there so much overhead? The key is that Julia cannot infer what the type of right_int might be, so it has to support any type being returned:

julia> typeof([right_int(i) for i=1:100])
Array{Any,1}

This means that Julia can't pack the integers densely into the array, and instead represents them as pointers to 100 individually "boxed" integers. These boxes tell Julia how to interpret the data that they contain, and that takes quite a bit of overhead. This doesn't just affect arrays, either — any time you use the result of right_int in any function, Julia can no longer optimize that function and ends up making lots of allocations. I highly recommend you read more about type stability in this very good blog post and in the manual's performance tips.

As far as which integer type to use: just use Int unless you know you'll be going over 2 billion. In the cases where you know you need to support huge numbers, use BigInt. It's notable that creating a similar array of BigInt uses significantly less memory than the "right-sized" array above:

julia> @allocated [big(i) for i=1:100]
6496

Upvotes: 9

Related Questions