I need to code a function that computes the L1 distance between the two vectors. It doesn’t need to be super precise — it serves as the estimate for some error as part of the stopping criterion of an algorithm—, but it needs to be fast since it will be invoked quite frequently. I guess the most straightforward way to write this in julia would be:
function L1_vec(a, b) sum(abs.(a .- b)) end
But of course this allocates a vector. The results of a simple benchmark are:
julia> N = 1000; a = rand(N); b = rand(N); @benchmark L1_vec($a, $b) BenchmarkTools.Trial: memory estimate: 7.94 KiB allocs estimate: 1 -------------- minimum time: 856.400 ns (0.00% GC) median time: 1.004 μs (0.00% GC) mean time: 1.412 μs (18.29% GC) maximum time: 62.230 μs (91.36% GC) -------------- samples: 10000 evals/sample: 35
My second try was to just iterate over the vectors, adding the difference to a counter and applying vectorization. All in all I ended up with the following function:
function L1_non_alloc(a, b) s = 0.0 @simd for i in eachindex(a) @inbounds s += abs(a[i] - b[i]) end return s end
This version gets rid of the unwanted allocations and is around x10 faster than the previous in the same simple benchmark:
julia> @benchmark L1_non_alloc($a, $b) BenchmarkTools.Trial: memory estimate: 0 bytes allocs estimate: 0 -------------- minimum time: 103.950 ns (0.00% GC) median time: 120.109 ns (0.00% GC) mean time: 127.151 ns (0.00% GC) maximum time: 301.482 ns (0.00% GC) -------------- samples: 10000 evals/sample: 900
My questions now are:
- Is there a more concise/julian way to write something similar to
L1_non_alloc? I am thinking of something similar to
mapbut that only saves the sum of applying some function
f(in this case
(x,y) -> abs(x-y)) to the input arrays.
- Is there any obvious improvement to be done in
L1_non_allocto make it more performant?
Thanks a lot!