Help to reduce memory allocations in a function

Hello Julia experts,

I have been working on the function `shortest_distance2_t` for quite a while, trying to optimise its performance. I do not have very advanced perf tools. Currently I use `BenchmarkTools` and `PProf`. I realize that there are too many memory allocations in this function. But I just donβt know how to reduce them.

The function and related definitions are listed below.

``````
import GeometricalPredicates: AbstractPolygon2D, AbstractPoint2D, AbstractLine2D, Line2D, Point2D, getx, gety, geta, getb

struct ExtLine2D{T<:AbstractPoint2D} <: AbstractLine2D
_a::T
_b::T
_bx::Float64
_by::Float64
_l2::Float64
end

function ExtLine2D(a::T, b::T) where {T<:AbstractPoint2D}
bx = getx(b) - getx(a)
by = gety(b) - gety(a)
ExtLine2D(a, b, bx, by, bx*bx+by*by)
end

geta(l::ExtLine2D) = l._a
getb(l::ExtLine2D) = l._b
length2(l::ExtLine2D) = l._l2

unpack(l::ExtLine2D) = (l._a._x, l._a._y, l._b._x, l._b._y, l._bx, l._by, l._l2)

struct PolygonInRegion2D{T<:AbstractPoint2D} <: AbstractPolygon2D
_p::Vector{T}
_l::Vector{ExtLine2D}
_i::Vector{Bool}
function PolygonInRegion2D{T}(p::T...) where {T<:AbstractPoint2D}
l = Vector{ExtLine2D}(undef, length(p) - 1)
for i in range(1, stop=length(p) - 1)
l[i] = ExtLine2D(p[i], p[i+1])
end
push!(l, ExtLine2D(p[end], p[1]))
new([p...;], l, [false for i = 1:length(l)])  # all edges are not inner edge
end
end

getpoints(polygon::PolygonInRegion2D) = polygon._p
getlines(polygon::PolygonInRegion2D) = polygon._l
getlabels(plg::PolygonInRegion2D) = plg._i

function shortest_distance2_t(px::Float64, py::Float64, plg::PolygonInRegion2D)::Tuple{Float64,Float64,Int}
d2min  = 1e20
d2     = 0.
tmin   = 0.0
imin   = 0
dx_10  = 0.
dy_10  = 0.
proj   = 0.
t      = 0.
i      = 0
for (ll,ii) in zip(plg._l, plg._i)
i += 1
if !ii  # not inner edge
#(d2,t) = _shortest_distance2_t(px, py, plg, i)
dx_10 = px - ll._a._x
dy_10 = py - ll._a._y
proj  = ll._bx * dx_10 + ll._by * dy_10
t     = proj / ll._l2
if t > 1
d2 = (ll._b._x-px)^2 + (ll._b._y-py)^2
t  = 1.
else
d2 = dx_10 * dx_10 + dy_10 * dy_10
if t < 0
t = 0.
else
d2 = max(0, d2 - t * proj)
end
end
if d2 < d2min
d2min = d2
tmin  = t
imin  = i
end
end
end
if d2min > 9.9e19
return (1e20, 0.0, -1)
else
return (d2min, tmin, imin)
end
end

``````

Below is an example:

``````
plg = PolygonInRegion2D{Point2D}(Point2D(0.,0.), Point2D(1.,0.1), Point2D(2.,0.2), Point2D(2.,1.), Point2D(1.,1.1), Point2D(0.,1.2))

using BenchmarkTools

@benchmark shortest_distance2_t(3.3, 0.3, plg)

``````

On my laptop, the benchmark result is

``````BenchmarkTools.Trial: 10000 samples with 10 evaluations.
Range (min β¦ max):  1.617 ΞΌs β¦ 482.226 ΞΌs  β GC (min β¦ max): 0.00% β¦ 98.34%
Time  (median):     1.818 ΞΌs               β GC (median):    0.00%
Time  (mean Β± Ο):   2.132 ΞΌs Β±   6.826 ΞΌs  β GC (mean Β± Ο):  5.70% Β±  1.96%

βββ
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
1.62 ΞΌs         Histogram: frequency by time        3.92 ΞΌs <

Memory estimate: 2.34 KiB, allocs estimate: 132.
``````

Not a Julia expert here but there is a type instability in your `PolygonInRegion2D` struct. The vector `_p` is parametrized, so `PolygonInRegion2D{Point2D}` will have a vector of the concrete point type in `_p`, but the vector of lines `_l` will still be a vector of the abstract type `ExtLine2D`.

Using `_l::Vector{ExtLine2D{T}}` in the struct definition (note the additional `T`) will get rid of the allocations.

Two more things:

• In general, a good first approach to spot type instabilities (which are often the cause for unnecessary allocations) is to run `@code_warntype shortest_distance2_t(3.3, 0.3, plg)`. This helps find the types that could not be inferred.
• `@benchmark shortest_distance2_t(3.3, 0.3, plg)` will still show a single allocation if it is used with out the dollar sign, as in `@benchmark shortest_distance2_t(3.3, 0.3, \$plg)`
4 Likes
``````BenchmarkTools.Trial: 10000 samples with 999 evaluations.
Range (min β¦ max):  12.292 ns β¦ 25.960 ns  β GC (min β¦ max): 0.00% β¦ 0.00%
Time  (median):     12.721 ns              β GC (median):    0.00%
Time  (mean Β± Ο):   13.588 ns Β±  1.339 ns  β GC (mean Β± Ο):  0.00% Β± 0.00%

β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ β
12.3 ns         Histogram: frequency by time        16.3 ns <

Memory estimate: 0 bytes, allocs estimate: 0.
``````

Awesome! I think the type-instability causes much of the mem-allocs I have observed with PProf (I havenβt shown the result). Thank you @Sevi !

1 Like