Quadratic memory usage with ExEdge/ExVertex

[iraikov]

Hello,

The following program exhibits quadratic memory usage: for n = 1050, memory allocated is 71510184 bytes, for n = 2050 memory allocated is 266372872 bytes, for n = 3050 memory allocated is 595032344 bytes, and so on. These graphs are not very big, so it would be good to fix this issue, if possible.

using Graphs

n = 2050
p = 0.1

function build(n,p)
gEx = graph([ ExVertex(x,string(x)) for x = 1:n ], ExEdge{ExVertex}[])
V = vertices(gEx)
eind = 1
for i = 1 : n
println ("i = ", i)
for j = 1 : n
if rand() < p
d = AttributeDict ()
d[utf8("weight")] = 0.1
add_edge! (gEx, ExEdge (eind, V[i], V[j], d))
eind = eind + 1
end
end
end
println (gEx)
gEx
end

@time build(n,p)

[gaborcsardi]

Well, the number of edges also increases quadratically, as far as I can tell from your code, so this is not a big surprise. :)

[iraikov]

Ok, you do have a good point :-) But why is the memory usage so high? Using Standard ML (mlton) and a sparse weight matrix representation, a graph with 1e7 edges takes about 200MB of memory. With Graphs.jl, a graph of the same size with ExEdge takes 8GB. Is there some way to figure out what is using all this memory?

[jakebolewski]

@iraikov we don't currently have a good way to traverse the live object graph and get memory usage information. You could use julia's --track-allocation flag which can tell you what source lines are allocating a lot of memory in Graphs.jl which might help.