# Can I decrease allocations here?

**URL:** <https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021>\
**Category:** New to Julia\
**Tags:** allocations\
**Created:** [March 17, 2022, 10:54am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021 "2022-03-17T10:54:59Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 17, 2022, 10:54am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/1 "2022-03-17T10:54:59Z")

</div>

I’m trying to further optimize [performance-critical function](https://discourse.julialang.org/t/weights-and-indices-for-linear-interpolation-extrapolation/77580) that locates values on a grid. Here I have tried using that the values will be sorted. And the bulk of the code is fast and has only 3 allocations, but then the final statement hits me with 2131 allocations 🤯 Could you help me minimize them?

```julia
function locate_vector(
    values::AbstractVector{<:Real},
    gridpoints;
    locate_below::Bool=false,
    locate_above::Bool=false,
)
    function incrementalsearch(low, value, gridpoints)
        while value >= gridpoints[low + 1]
            low += 1
        end

        return low
    end

    indices = ones(Integer, size(values))
    weights = Vector{Tuple}(undef, size(values))

    low = 1
    high = length(gridpoints) - 1

    for ix in eachindex(values)
        if values[ix] <= gridpoints[1]
            # indices[ix] = low = 1 # No need as indices and low are initialized to 1

            if !locate_below
                weights[ix] = (1.0, 0.0)
            end
        elseif values[ix] >= gridpoints[end]
            indices[ix:end] .= length(gridpoints) - 1

            if !locate_above
                weights[ix:end] .= repeat((0.0, 1.0), length(weights[ix:end]))
            end

            break
        elseif low == high
            indices[ix] = high
        else
            indices[ix] = low = incrementalsearch(low, values[ix], gridpoints)
        end
    end

    no_weights = filter(ix -> !isassigned(weights, ix), 1:length(weights))
    weights[no_weights] .= map( # Crazy number of allocations
        ix -> (
            gridpoints[indices[ix] .+ 1] .- values[ix],
            values[ix] .- gridpoints[indices[ix]]
        ) ./ (
            gridpoints[indices[ix] .+ 1]
            .- gridpoints[indices[ix]]
        ),
        no_weights,
    )

    return indices, weights
end

using BenchmarkTools
gridpoints = collect(range(0.1, 0.9, 100));
values = sort(rand(101));
@btime locate_vector(values, gridpoints; locate_above=true);
# 256.400 μs (2134 allocations: 63.00 KiB)

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 11:04am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/2 "2022-03-17T11:04:16Z")

</div>

You could use a comprehension (lazy) instead of `map` (eager constructing a vector) like so

```julia
    weights[no_weights] .= ((
            gridpoints[indices[ix] .+ 1] .- values[ix],
            values[ix] .- gridpoints[indices[ix]]
        ) ./ (
            gridpoints[indices[ix] .+ 1]
            .- gridpoints[indices[ix]]
        ) for ix in no_weights)

```

---

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 17, 2022, 11:12am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/3 "2022-03-17T11:12:44Z")

</div>

That helped, but only by very, very little—allocations dropped by 6 🤔

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 11:25am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/4 "2022-03-17T11:25:58Z")

</div>

Confirmed (checked that with profiler). Go back to ‘map’ and try

```julia
    weights = Vector{Tuple{Float64, Float64}}(undef, size(values))

```

This looks slightly better here. (`Vector{Tuple}` means implicitly `Vector{Tuple{Any...}}` and this is no good).

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 11:31am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/5 "2022-03-17T11:31:39Z")

</div>

Afterwards this

```julia
    for ix in no_weights
        weights[ix] =
            (
                gridpoints[indices[ix] .+ 1] .- values[ix],
                values[ix] .- gridpoints[indices[ix]]
            ) ./ (
                gridpoints[indices[ix] .+ 1]
                .- gridpoints[indices[ix]]
            )
    end

```

eliminates the last dynamic dispatch yielding

```julia
  770.635 ns (5 allocations: 3.61 KiB)

```

---

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 17, 2022, 11:53am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/6 "2022-03-17T11:53:45Z")

</div>

Great! Thank you!

---

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 17, 2022, 11:54am UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/7 "2022-03-17T11:54:29Z")

</div>

Noob question but how did you check that with the profiler?

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 12:01pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/8 "2022-03-17T12:01:46Z")

</div>

I’m still using Atom/Juno for this with a script like

```julia
using Profile
Profile.clear()
gridpoints = collect(range(0.1, 0.9, 100));
values = sort(rand(101));
locate_vector(values, gridpoints; locate_above=true);
@profile for i in 1:1000; locate_vector(values, gridpoints; locate_above=true); end
# Profile.print()
Juno.profiler() 

```

Here is before

 ![image](https://global.discourse-cdn.com/julialang/original/3X/9/7/973832d60573142a402d2866d269790fa1029443.png)

and here is after

 ![image](https://global.discourse-cdn.com/julialang/original/3X/1/f/1fba486354e93e12da880ad323de71a75afe9ea3.png)

Color coding: yellow is dynamic dispatch, red is allocation…

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 1:29pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/9 "2022-03-17T13:29:59Z")

</div>

> [@fredrikpaues](#):
>
> ```julia
> indices = ones(Integer, size(values))
> weights = Vector{Tuple}(undef, size(values))
> 
> ```

I understand that you fixed `Vector{Tuple}` to get a concrete element type, right? But did you also fix `indices`? `Integer` is an abstract type, you should use

```julia
indices = ones(Int, size(values))

```

instead.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 2:01pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/10 "2022-03-17T14:01:22Z")

</div>

Wait a minute! Did you check the correctness of the results?

Changing from this:

```julia
weights = Vector{Tuple}(undef, size(values))

```

to

```julia
weights = Vector{Tuple{Float64, Float64}}(undef, size(values))

```

may have some unintended consequences. Later in the code @fredrikpaues uses `!isassigned(weights, ix)`, but that makes no sense for the latter, because of this:

```julia
1.7.2> v1 = Vector{Tuple}(undef, 3)
3-element Vector{Tuple}:
 #undef
 #undef
 #undef

1.7.2> isassigned(v1, 1)
false

1.7.2> v2 = Vector{NTuple{2,Float64}}(undef, 3)
3-element Vector{Tuple{Float64, Float64}}:
 (2.5e-323, 3.5e-323)
 (4.0e-323, 4.4e-323)
 (5.0e-323, 5.4e-323)

1.7.2> isassigned(v2, 1)
true

```

There is no `#undef` value for bitsvalues like these, and `isassigned` is _always_ true.

I’m not 100% sure if the last code version still has `isassigned` because the image was _very_ small and blurry, but if so, the algorithm should be redesigned, without relying on `isassigned`, which is not a great idea.

One way is to initialize like this:

```julia
weights = fill((NaN, NaN), size(values))

```

and check for `isnan` instead of `isassigned`. Also, I wouldn’t create `no_weights` first, and then iterate over them. Just loop over `weights` and check for `NaN` in each iteration.

After doing this, there are only 2 allocations, one for `indices` and one for `weights`, as expected.

(Also, what’s up with all the broadcasting dots in that loop, are they needed?)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 2:45pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/11 "2022-03-17T14:45:03Z")

</div>

Oh, and this one:

> [@fredrikpaues](#):
>
> `weights[ix:end] .= repeat((0.0, 1.0), length(weights[ix:end]))`

This needlessly creates, not just one, but _two_ arrays on the right side. Firstly, `length(weights[ix:end])` allocates a whole array, just to measure its length. And then `repeat` creates _another_ one.

But there’s no reason to do this. Just assign the same value to all elements on the left. You’ll have to wrap the right hand side in a `Ref` though, to avoid broadcasting:

```julia
weights[ix:end] .= Ref((0.0, 1.0))

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 2:56pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/12 "2022-03-17T14:56:59Z")

</div>

@DNF: thanks for the code review. You are right on all counts, especially the unintended change in results! @tbeason : thanks!

For future reference and @fredrikpaues : here are the missing pieces

```julia
function locate_vector1(
    values::AbstractVector{<:Real},
    gridpoints;
    locate_below::Bool=false,
    locate_above::Bool=false,
)
    function incrementalsearch(low, value, gridpoints)
        while value >= gridpoints[low + 1]
            low += 1
        end

        return low
    end

    indices = ones(Integer, size(values))
    weights = Vector{Tuple}(undef, size(values))

    low = 1
    high = length(gridpoints) - 1

    for ix in eachindex(values)
        if values[ix] <= gridpoints[1]
            # indices[ix] = low = 1 # No need as indices and low are initialized to 1

            if !locate_below
                weights[ix] = (1.0, 0.0)
            end
        elseif values[ix] >= gridpoints[end]
            indices[ix:end] .= length(gridpoints) - 1

            if !locate_above
                weights[ix:end] .= Ref((0.0, 1.0))
            end

            break
        elseif low == high
            indices[ix] = high
        else
            indices[ix] = low = incrementalsearch(low, values[ix], gridpoints)
        end
    end

    no_weights = filter(ix -> !isassigned(weights, ix), 1:length(weights))
    weights[no_weights] .= map( # Crazy number of allocations
        ix -> (
            gridpoints[indices[ix] .+ 1] .- values[ix],
            values[ix] .- gridpoints[indices[ix]]
        ) ./ (
            gridpoints[indices[ix] .+ 1]
            .- gridpoints[indices[ix]]
        ),
        no_weights,
    )

    return indices, weights
end

function locate_vector2(
    values::AbstractVector{<:Real},
    gridpoints;
    locate_below::Bool=false,
    locate_above::Bool=false,
)
    function incrementalsearch(low, value, gridpoints)
        while value >= gridpoints[low + 1]
            low += 1
        end

        return low
    end

    indices = ones(Int, size(values))
    weights = Vector{Union{Nothing, Tuple{Float64, Float64}}}(nothing, size(values))

    low = 1
    high = length(gridpoints) - 1

    for ix in eachindex(values)
        if values[ix] <= gridpoints[1]
            # indices[ix] = low = 1 # No need as indices and low are initialized to 1

            if !locate_below
                weights[ix] = (1.0, 0.0)
            end
        elseif values[ix] >= gridpoints[end]
            indices[ix:end] .= length(gridpoints) - 1

            if !locate_above
                weights[ix:end] .= Ref((0.0, 1.0))
            end

            break
        elseif low == high
            indices[ix] = high
        else
            indices[ix] = low = incrementalsearch(low, values[ix], gridpoints)
        end
    end

    no_weights = filter(ix -> weights[ix] === nothing, 1:length(weights))
    for ix in no_weights
        weights[ix] =
            (
                gridpoints[indices[ix] .+ 1] .- values[ix],
                values[ix] .- gridpoints[indices[ix]]
            ) ./ (
                gridpoints[indices[ix] .+ 1]
                .- gridpoints[indices[ix]]
            )
    end

    return indices, weights
end

gridpoints = collect(range(0.1, 0.9, 100));
values = sort(rand(101));
result1 = locate_vector1(values, gridpoints; locate_above=false);
result2 = locate_vector2(values, gridpoints; locate_above=false);
@assert(result1 == result2)
result1 = locate_vector1(values, gridpoints; locate_above=true);
result2 = locate_vector2(values, gridpoints; locate_above=true);
@assert(result1 == result2)

using BenchmarkTools
gridpoints = collect(range(0.1, 0.9, 100));
values = sort(rand(101));
@btime locate_vector1($values, $gridpoints; locate_above=false); 
@btime locate_vector1($values, $gridpoints; locate_above=true); 
@btime locate_vector2($values, $gridpoints; locate_above=false); 
@btime locate_vector2($values, $gridpoints; locate_above=true); 

```

yielding

```julia
  110.000 μs (1429 allocations: 44.39 KiB)
  144.400 μs (1627 allocations: 50.19 KiB)
  873.077 ns (4 allocations: 4.17 KiB)
  892.000 ns (4 allocations: 4.23 KiB)

```

---

<div class="post-metadata">

**Author:** ![tbeason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tbeason/32/15898_2.png) [@tbeason](https://discourse.julialang.org/u/tbeason)\
**Post date:** [March 17, 2022, 3:05pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/13 "2022-03-17T15:05:23Z")

</div>

Don’t forget to interpolate values in `@btime`

```julia
julia> @btime locate_vector2(values, gridpoints; locate_above=true);
  677.914 ns (5 allocations: 4.34 KiB)

julia> @btime locate_vector2($values, $gridpoints; locate_above=$true);
  633.136 ns (4 allocations: 4.31 KiB)

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 3:10pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/14 "2022-03-17T15:10:12Z")

</div>

Actually, here’s a version with just 2 allocations:

```julia
function locate_vector3(
    values::AbstractVector{<:Real},
    gridpoints;
    locate_below::Bool=false,
    locate_above::Bool=false,
)
    function incrementalsearch(low, value, gridpoints)
        while value >= gridpoints[low + 1]
            low += 1
        end
        return low
    end

    indices = fill(1, size(values))
    weights = fill((NaN, NaN), size(values))

    low = 1
    high = length(gridpoints) - 1

    for ix in eachindex(values)
        if values[ix] <= gridpoints[1]
            if !locate_below
                weights[ix] = (1.0, 0.0)
            end
        elseif values[ix] >= gridpoints[end]
            indices[ix:end] .= length(gridpoints) - 1

            if !locate_above
                weights[ix:end] .= Ref((0.0, 1.0))
            end

            break
        elseif low == high
            indices[ix] = high
        else
            indices[ix] = low = incrementalsearch(low, values[ix], gridpoints)
        end
    end

    for i in eachindex(weights)
        w = weights[i]
        if isnan(w[1])
            grid1 = gridpoints[indices[i]]
            grid2 = gridpoints[indices[i]+1]
            val = values[i]
            weights[i] = ((grid2 - val) / (grid2 - grid1),
                          (val - grid1) / (grid2 - grid1))
        end
    end
    return indices, weights
end

```

```julia
1.7.2> @btime locate_vector3($values, $gridpoints; locate_above=true);
  575.275 ns (2 allocations: 2.64 KiB)

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 3:18pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/15 "2022-03-17T15:18:09Z")

</div>

By the way:

> [@fredrikpaues](#):
>
> ```julia
> gridpoints = collect(range(0.1, 0.9, 100));
> values = sort(rand(101));
> 
> ```

Are both `gridpoints` and `values` expected to be sorted, and even possibly regularly spaced? You don’t seem to exploit that. Your search function is woefully suboptimal.

---

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 17, 2022, 3:27pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/16 "2022-03-17T15:27:21Z")

</div>

Thank you! Both are sorted. None regularly spaced. How is the search function suboptimal? (I have another search function which uses binary search, but I just included one of them here.)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [March 17, 2022, 3:38pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/17 "2022-03-17T15:38:45Z")

</div>

I would have thought that binary search was better, but looking closer, it seems the current version might not be too bad.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [March 17, 2022, 4:08pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/18 "2022-03-17T16:08:41Z")

</div>

I imagine some kind of [merge](https://en.wikipedia.org/wiki/Merge_algorithm) variation could help?

Along the lines of

```julia
    iv = 1
    ig = 1
    while iv <= length(values) && ig <= length(gridpoints) 
        if values[iv] < gridpoints[ig]
            # do something
            iv += 1
        else if values[iv] == gridpoints[ig]
            # do something
            iv += 1
            ig += 1
        else
            # do something
            ig += 1
        end
    end
    while iv <= length(values)
        # do something
        iv += 1
    end

```

---

<div class="post-metadata">

**Author:** ![fredrikpaues](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fredrikpaues/32/34080_2.png) [@fredrikpaues](https://discourse.julialang.org/u/fredrikpaues)\
**Post date:** [March 25, 2022, 2:40pm UTC](https://discourse.julialang.org/t/can-i-decrease-allocations-here/78021/19 "2022-03-25T14:40:53Z")

</div>

> [@DNF](#):
>
> ```julia
> for ix in eachindex(values)
> 
> ```

By the way, I just learned that `eachindex` can take multiple inputs. Is there a good reason (not) to write `èachindex(values, indices, weights)` here? I’m thinking that it might be a good idea, just in case `values` [isn’t 1-based](https://docs.julialang.org/en/v1/devdocs/offset-arrays/).