# Help to reduce memory allocations in a function

**URL:** <https://discourse.julialang.org/t/help-to-reduce-memory-allocations-in-a-function/101422>\
**Category:** Performance\
**Created:** [July 10, 2023, 8:05am UTC](https://discourse.julialang.org/t/help-to-reduce-memory-allocations-in-a-function/101422 "2023-07-10T08:05:57Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lian\_Yunlong](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lian_yunlong/32/14437_2.png) [@Lian\_Yunlong](https://discourse.julialang.org/u/Lian_Yunlong)\
**Post date:** [July 10, 2023, 8:05am UTC](https://discourse.julialang.org/t/help-to-reduce-memory-allocations-in-a-function/101422/1 "2023-07-10T08:05:57Z")

</div>

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.

```julia

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:

```julia

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

```julia
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.

```

---

<div class="post-metadata">

**Author:** ![Sevi](https://avatars.discourse-cdn.com/v4/letter/s/c67d28/32.png) [@Sevi](https://discourse.julialang.org/u/Sevi)\
**Post date:** [July 10, 2023, 8:30am UTC](https://discourse.julialang.org/t/help-to-reduce-memory-allocations-in-a-function/101422/2 "2023-07-10T08:30:23Z")

</div>

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)`

---

<div class="post-metadata">

**Author:** ![Lian\_Yunlong](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lian_yunlong/32/14437_2.png) [@Lian\_Yunlong](https://discourse.julialang.org/u/Lian_Yunlong)\
**Post date:** [July 10, 2023, 8:44am UTC](https://discourse.julialang.org/t/help-to-reduce-memory-allocations-in-a-function/101422/3 "2023-07-10T08:44:54Z")

</div>

```julia
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 !