Problem with creating view of vectors in vector of vectors (it keeps allocating)

I have a problem where Julai keeps allocating, causing something I think should be fast to be slow. Simple example:

vec_vec = [1:100 for i in 1:100]
@time vals = [vec for vec in vec_vec] # Fast, few allocations
@time vals = [vec[1:end] for vec in vec_vec] # Slow, many allocations.
@time vals = [(@view vec[1:end]) for vec in vec_vec] # Slow, many allocations.
@time vals = [[v for v in vec] for vec in vec_vec] # Slow, many allocations.

In practise I got a a vector of vectors, and I want to create a new vector where each value is a sub-vector of the vector at the corresponding index. In some cases I would also like to reshape this to a matrix. However, this turns out to be slow due to allocations, as in the example above. I was hoping using @view would solve it but that does not seem to be the case

The problem is that you are benchmarking with global variables. Put the code in a function. Use @btime from BenchmarkTools.jl to get more accurate timing statistics (and interpolate global variables). When I do this, the allocations disappear:

julia> using BenchmarkTools

julia> f1(vec_vec) = [vec[1:end] for vec in vec_vec]
f1 (generic function with 1 method)

julia> f2(vec_vec) = @views [vec[1:end] for vec in vec_vec]
f2 (generic function with 1 method)

julia> @btime f1($vec_vec);
  211.219 ns (1 allocation: 1.77 KiB)

julia> @btime f2($vec_vec);
  220.346 ns (1 allocation: 1.77 KiB)

Note that even f1 does not allocate here (except for a single allocation of the returned array), because a range 1:100 is a very special kind of vector that is not explicitly stored, and slices vec[1:end] of ranges also return ranges without allocating.

If you instead have a vector of regular heap-allocated vectors (Vector), e.g. returned by rand(100), then you will see a big difference in allocation from using @views:

julia> vec_vec2 = [rand(100) for i in 1:100];

julia> @btime f1($vec_vec2);
  6.208 μs (101 allocations: 88.38 KiB)

julia> @btime f2($vec_vec2);
  243.415 ns (1 allocation: 4.12 KiB)

1 Like

That is great, thanks a lot and for the explanation!