Vcat taking up all the memory


#1

VERSION = v"0.6.2"

I have a triangle/jagged array of a data structure that contains a vector d and a coefficient. I want to find the elementwise minimum and maximum of all the ds of the datastructures in the jagged array. I am comparing three methods. I realized that the more verbose the code, the faster it runs. Also the most succint one uses all the memory on my machine (16GB) even for a small array.

# minmax.jl
mutable struct Data{F}
    d::Vector{F}
    coef::F
end

function mmcat(triarr)
    dds = [[d.d for d in dd] for dd in triarr]
    lo = min.(vcat(dds...)...)
    hi = max.(vcat(dds...)...)
    lo, hi
end

function mmfor(triarr)
    itr = Iterators.flatten(triarr)
    lo = first(itr).d
    hi = first(itr).d
    for i in itr
        lo = min.(lo, i.d)
        hi = max.(hi, i.d)
    end
    lo, hi
end

function mmitr(triarr)
    itr = Iterators.flatten(triarr)
    lo = mapreduce(d->d.d, (d1, d2)->min.(d1, d2), first(itr).d, itr)
    hi = mapreduce(d->d.d, (d1, d2)->max.(d1, d2), first(itr).d, itr)
    lo, hi
end

tridata(n) = [[Data(rand(0:9999, 3), 1) for i in 1:j] for j in 1:n]

td3 = tridata(3)
@show mmfor(td3) mmitr(td3) mmcat(td3)

N = 100
tdN = tridata(N)
@show sizeof(tdN)
@show (N*(N+1)/2) * 4 * 8

@show @time mmfor(tdN)
@show @time mmitr(tdN)
@show @time mmcat(tdN)

When I run I get the following output.

$ julia minmax.jl 
mmfor(td3) = ([3028, 148, 657], [9595, 8595, 9345])
mmitr(td3) = ([3028, 148, 657], [9595, 8595, 9345])
mmcat(td3) = ([3028, 148, 657], [9595, 8595, 9345])

sizeof(tdN) = 800
((N * (N + 1)) / 2) * 4 * 8 = 161600.0

  0.000699 seconds (15.24 k allocations: 1.239 MiB)
@time(mmfor(tdN)) = ([2, 4, 1], [9999, 9998, 9993])

  0.000742 seconds (20.21 k allocations: 1.387 MiB)
@time(mmitr(tdN)) = ([2, 4, 1], [9999, 9998, 9993])

^C

I have to cancel because all the 16GB are taken up by mmcat, not to mention the time it takes even for N=30!
What’s happening with mmcat? What is the julian way of doing this?


#2

Well vcat is eager, so with mmcat you’re forcing julia to concatenate many tiny length-3 vectors into a big array, only to reduce it down again. vcat may be using excess memory, but the iterator based solution is always going to perform much better. For what it’s worth, I personally found mmfor to be much easier to read than the others!

I think the underlying problem you’re having here is that your data structure is nested several layers deep, which makes expressing operations on it clumsy. The memory layout will also be very inefficient compared to a flatter data structure because your inner arrays are so short. Having said that, here’s a variation of mmitr which I think is more readable:

mmitr2(triarr) = extrema(d.d for d in Iterators.flatten(triarr))

To improve your memory layout and access patterns (avoiding allocating many independent small objects), I’d suggest changing Data to

using StaticArrays

struct Data2{F}
    d::SVector{3,F}
    coef::F
end

if that’s compatible with the way you want to use it.

Ideally there’d be a julia package I could recommend for storing jagged arrays efficiently, but I can’t seem to find one with a quick search.


#3

Ha ha. Thanks. May be vcat is better in 1.0.