Fast lookup into (almost) constant array


#1

I have this (simplified) code in a module.

const A = @SMatrix [1.0 2.0;
                    3.0 4.0]

f(r, x::Number) = x * Vector{Float64}(A[r,:])

f is a bottleneck function. This is already really quick and I’m happy with performance but wondering if I can do better. The multiplier x is pretty much a constant, defined on initialisation but also updated occasionally based on user interaction.

Is there a way to gain some more speed by pre-multiplying A by x and indexing into that array? I haven’t been able to work out a way to do it. The pre-calculation would be done from a different file in the same module, which seems to complicate things.


#2

The issue is that you are creating a vector which is heap allocated. You’re getting two allocations, the second because of the resulting *. It’s faster to just use the resulting SVector from indexing the SMatrix.


#3

It’s doubtful that you’d get any speed improvement. A multiply is basically free with a copy, which you’re probably gonna have to do anyway. Depends a bit on the surrounding code though. As @ChrisRackauckas said though, your biggest bottleneck in the above code will be the Vector allocation.


#4

OK good to know, thanks.

I was definitely allocating needlessly.

f(r, x::Number) = x * Vector{Float64}(cellcentres[r,:])
f2(r, x::Number) = Vector{Float64}(x * cellcentres[r,:])
f3(r, x::Number) = [(x*cellcentres[r,:]).data...]
julia> @btime f(2, 1000.0);
  46.041 ns (2 allocations: 192 bytes)

julia> @btime f2(2, 1000.0);
  21.496 ns (1 allocation: 96 bytes)

julia> @btime f3(2, 1000.0);
  32.493 ns (3 allocations: 128 bytes)

So f2 is the way to go. It would be nice to get this performance:

julia> f4(r, x::Number) = x * cellcentres[r,:];

julia> @btime f4(2, 1000.0);
  6.942 ns (0 allocations: 0 bytes)

but unfortunately I do need a vector. Thanks again.


#5

Why? No codes should rely on the underlying data structure, just the actions. If you just allow AbstractVector most codes should work just fine, unless you’re modifying this vector in the future, in which case you can just use setindex.


#6

Yeah, this assumption should definitely be questioned. You can also use an MVector if you need mutation.


#7

You’re right of course! I was over-restricting types in the downstream functions. This was a great lesson.