# Memory allocations when performing operation on Tuple of structs

**URL:** <https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276>\
**Category:** Performance\
**Tags:** tuple, memory-allocation, struct\
**Created:** [October 14, 2024, 8:40am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276 "2024-10-14T08:40:12Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![albertomercurio](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albertomercurio/32/27051_2.png) [@albertomercurio](https://discourse.julialang.org/u/albertomercurio)\
**Post date:** [October 14, 2024, 8:40am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/1 "2024-10-14T08:40:12Z")

</div>

Hello,

I’m facing a memory allocation problem on an apparently simple case. I have the following struct

```julia
struct MyStruct{T1<:AbstractMatrix, T2}
    data::T1
    other::T2
end

```

where `data` is a matrix and `other` is something that will not be involved in the next operations, but we will see it will lead to memory allocations.

Now I show how I get memory allocations when performing operations on a `Tuple` of these objects, with different types for the `other` field.

```julia
using LinearAlgebra
using BenchmarkTools

struct MyStruct{T1<:AbstractMatrix, T2}
    data::T1
    other::T2
end

struct MyStructSum{T}
    ops::T
end

function LinearAlgebra.mul!(y::AbstractVector, a::MyStruct, x::AbstractVector)
    mul!(y, a.data, x)
    return y
end

function LinearAlgebra.mul!(y::AbstractVector, a::MyStructSum, x::AbstractVector)
    for op in a.ops
        mul!(y, op, x)
    end
    return y
end

T = Float64
N = 200
M = 10
ops = ntuple(i-> rand(T, N, N), Val(M))
vals = ntuple(i-> rand() > 0.5 ? rand(Int64) : rand(Float64), Val(M))

my_structs = ntuple(i-> MyStruct(ops[i], vals[i]), Val(M))
my_sum_struct = MyStructSum(my_structs)

typeof(my_sum_struct)

x = rand(T, N)
y = similar(x)

mul!(y, my_sum_struct, x);

@benchmark mul!($y, $my_sum_struct, $x)

```

```julia
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max): 37.297 μs … 135.552 μs ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 37.902 μs ┊ GC (median): 0.00%
 Time (mean ± σ): 38.379 μs ± 2.357 μs ┊ GC (mean ± σ): 0.00% ± 0.00%

   ▃▇██▆▄▃▁ ▁▂▂▃▂▁ ▂
  ▇████████▇▇▇▆▄▆▇▇███████▇█▇▇▆▇▅▇▇▆▆▆▇▇▆▆▆▅▄▅▅▅▄▄▃▃▄▄▁▁▄▄▄▁▃▄ █
  37.3 μs Histogram: log(frequency) by time 46.1 μs <

 Memory estimate: 1.86 KiB, allocs estimate: 19.

```

How course, if all the `other` fields have the same time, then I don’t have memory allocations. But in my complete implementation I need them, and in general they will be function types.

How can I solve this problem, knowing that the `mul!` operation is performed only in the `data` field, and it doesn’t use there `other` at all?

---

<div class="post-metadata">

**Author:** ![Albert\_de\_montserrat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_de_montserrat/32/9135_2.png) [@Albert\_de\_montserrat](https://discourse.julialang.org/u/Albert_de_montserrat)\
**Post date:** [October 14, 2024, 9:08am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/2 "2024-10-14T09:08:53Z")

</div>

`my_sum_struct.ops` is a heterogeneous tuple, as it contains elements of both `MyStruct{Matrix{Float64}, Float64}` and `MyStruct{Matrix{Float64}, Int64}`. Iterating over heterogeneous tuples is type unstable as the compiler can’t figure out the type of `my_sum_struct.ops[i]` if `i` is a runtime variable. The solution is to unroll the loop, however this will work only if the length of `my_sum_struct.ops` is not too large. One simple way to do it is with `ntuple`

```julia
@inline Val_length(::NTuple{N, Any}) where N = Val(N)

function mul2!(y::AbstractVector, a::MyStructSum, x::AbstractVector) 
    VN = Val_length(a.ops)
    ntuple(VN) do i
        @inline
        mul!(y, a.ops[i], x)
    end
    return y
end

```

```julia-repl
julia> @btime mul2!($y, $my_sum_struct, $x);
  35.600 μs (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![albertomercurio](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albertomercurio/32/27051_2.png) [@albertomercurio](https://discourse.julialang.org/u/albertomercurio)\
**Post date:** [October 14, 2024, 10:02am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/3 "2024-10-14T10:02:45Z")

</div>

> [@Albert\_de\_montserrat](#):
>
> however this will work only if the length of `my_sum_struct.ops` is not too large

Why are we constrained by this? What happens if we have large Tuples? Is it only a compilation issue, or also a run issue? What is the order of magnitude of the Tuple length to be considered ok?

BTW, thanks for the working example. But why do we need to define a dedicated function for returning the length of a tuple? Is that not known at compile time and thus just writing `VN = Val(length(a.ops))` would work?

---

<div class="post-metadata">

**Author:** ![Albert\_de\_montserrat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_de_montserrat/32/9135_2.png) [@Albert\_de\_montserrat](https://discourse.julialang.org/u/Albert_de_montserrat)\
**Post date:** [October 14, 2024, 10:23am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/4 "2024-10-14T10:23:23Z")

</div>

In your particular case looks like the compiler gives up at `N>10` with `ntuple`. But a `@generated` function seems to do the trick for much larger `N`:

```julia
@generated function mul3!(y::AbstractVector, a::MyStructSum, x::AbstractVector, ::Val{N}) where N
    quote 
        Base.@nexprs $N i -> begin
            @inline 
            mul!(y, a.ops[i], x)
        end
        return y
    end
end

T = Float64;
N = 200
M = 200
ops = ntuple(i-> rand(T, N, N), Val(M))
vals = ntuple(i-> rand() > 0.5 ? rand(Int64) : rand(Float64), Val(M))

my_structs = ntuple(i-> MyStruct(ops[i], vals[i]), Val(M))
my_sum_struct = MyStructSum(my_structs)

```

yields

```julia-repl
julia> using ChairMarks
julia> @b mul3!($(y, my_sum_struct, x, Val(length(my_sum_struct.ops)))...)
2.473 ms

```

And you are right, `Val(length(a.ops))` is enough as it is known at compile time.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 14, 2024, 11:05am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/5 "2024-10-14T11:05:40Z")

</div>

> [@Albert\_de\_montserrat](#):
>
> The solution if to unroll the loop

Another way to do this is with `foreach`

---

<div class="post-metadata">

**Author:** ![Albert\_de\_montserrat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_de_montserrat/32/9135_2.png) [@Albert\_de\_montserrat](https://discourse.julialang.org/u/Albert_de_montserrat)\
**Post date:** [October 14, 2024, 12:30pm UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/6 "2024-10-14T12:30:29Z")

</div>

`foreach` looks indeed a better option than `ntuple`, but it still gives up at `M>32` and it starts allocating. For `M=33`

```julia-repl
julia> mul4!(y::AbstractVector, a::MyStructSum, x::AbstractVector) = foreach(ops -> mul!(y, ops, x), a.ops)
mul4! (generic function with 1 method)

julia> @b mul4!($(y, my_sum_struct, x)...)
122.300 μs (64 allocs: 18.000 KiB)

```

---

<div class="post-metadata">

**Author:** ![mrufsvold](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrufsvold/32/31600_2.png) [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)\
**Post date:** [October 14, 2024, 1:56pm UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/7 "2024-10-14T13:56:48Z")

</div>

Would it be too much of an edge case for the compiler to consider small union splitting for looping over a heterogenous tuple? In this case, since there are only two types, it seems like it would be possible to say `my_sum_struct.ops[i]::Union{MyStruct{Matrix{Float64}, Float64}, MyStruct{Matrix{Float64}, Int64}}`.

---

<div class="post-metadata">

**Author:** ![albertomercurio](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albertomercurio/32/27051_2.png) [@albertomercurio](https://discourse.julialang.org/u/albertomercurio)\
**Post date:** [October 14, 2024, 8:57pm UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/8 "2024-10-14T20:57:52Z")

</div>

Thank you! It worked.

BTW, is the following code still good?

```julia
@generated function LinearAlgebra.mul!(y::AbstractVector, a::MyStructSum, x::AbstractVector)
    ops_types = a.parameters[1].parameters
    N = length(ops_types) # Get the length of the tuple
    quote
        for i = 1:$N
            mul!(y, a.ops[i], x)
        end
        return y
    end
end

```

I still have zero allocations and there is no need to pass the length of the tuple as an argument.

I have just few additional questions. What is the purpose of using `Base.@nexprs` here? Why does the `foreach` function perform better, up to a defined length of the tuple? Does the `@generated` case have a limit in the length of the tuple?

---

<div class="post-metadata">

**Author:** ![Albert\_de\_montserrat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albert_de_montserrat/32/9135_2.png) [@Albert\_de\_montserrat](https://discourse.julialang.org/u/Albert_de_montserrat)\
**Post date:** [October 15, 2024, 6:09am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/9 "2024-10-15T06:09:24Z")

</div>

That looks like a valid function to me, but you should test if it eventually gives up on unrolling the loop and ends up allocating. You could alternatively also do the following if you want to avoid explicitly passing `Val(length(a.ops))` :

```julia
LinearAlgebra.mul!(y::AbstractVector, a::MyStructSum, x::AbstractVector) = LinearAlgebra.mul!(y, a, x, Val(length(a.ops)))
@generated function LinearAlgebra.mul!(y::AbstractVector, a::MyStructSum, x::AbstractVector, ::Val{N}) where N
    quote 
        Base.@nexprs $N i -> begin
            @inline 
            mul!(y, a.ops[i], x)
        end
        return y
    end
end

```

whatever version you prefer. `Base.@nexprs` is in charge of the unrolling. For example, `Base.@nexprs 3 i -> mul!(y, a.ops[i], x)` will literally generate the following code:

```julia
mul!(y, a.ops[1], x)
mul!(y, a.ops[2], x)
mul!(y, a.ops[3], x)

```

So I don’t expect this version to allocate memory; however, how large do you expect the length of the tuple to be? I guess you will see large compilation times if it’s really long (I don’t have an intuition here, you should test it).

As for `foreach`, it looks like it has a hard-coded manual unrolling up to `N=31`, and then it loops over the remaining elements of the tuple. You can see it [here](https://github.com/JuliaLang/julia/blob/fe82988327183f90ddccb3f7e270a88c9e9c2021/base/operators.jl#L595).

---

<div class="post-metadata">

**Author:** ![albertomercurio](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/albertomercurio/32/27051_2.png) [@albertomercurio](https://discourse.julialang.org/u/albertomercurio)\
**Post date:** [October 15, 2024, 10:18am UTC](https://discourse.julialang.org/t/memory-allocations-when-performing-operation-on-tuple-of-structs/121276/10 "2024-10-15T10:18:31Z")

</div>

Thank you for the reply. My Tuple may have an arbitrary number of elements, but usually less the 20 I would say. But it is better to support an arbitrary number of elements.