# Help with reducing allocations when indexing into custom Array

**URL:** <https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732>\
**Category:** Performance\
**Tags:** array, memory-allocation, speed-optimization\
**Created:** [January 13, 2025, 3:48pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732 "2025-01-13T15:48:09Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![thomasc791](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thomasc791/32/214650_2.png) [@thomasc791](https://discourse.julialang.org/u/thomasc791)\
**Post date:** [January 13, 2025, 3:48pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/1 "2025-01-13T15:48:09Z")

</div>

Hi everyone,  
I am quite new to the language, and was wondering if people could help me optimising my piece of code. The idea for this array type is to reduce the total Base.summarysize for a vector of vector as much as possible. I did this by creating a type that has a “pointer” to the actual vector, like StridedArrays, but more minimal. The size of the array in StridedArrays does not really change.

```julia
struct FMat{N} <: AbstractArray{Int,1}
  data::Vector{<:Integer}
  @inline function FMat(vals::Vector{Vector{T}}) where {T}
    N = size(vals, 1)
    flattened = reduce(vcat, vals)
    A = Array{T,1}(undef, N + 1 + size(flattened, 1))
    A[1] = 1
    A[N+2:end] = flattened
    A[2:N+1] = accumulate(+, size(i, 1) for i in vals) .+ 1
    new{N}(A)
  end

  @inline function FMat{N}(vals::Vector{<:Int}) where {N}
    new{N}(vals)
  end
end

Base.length(::FMat{N}) where {N} = N

Base.size(::FMat{N}) where {N} = (N,)

@inline function Base.getindex(A::FMat{N}, i::Int) where {N}
  return A.data[A.data[i]+N+1:A.data[i+1]+N]
end

@inline function Base.getindex(A::FMat{N}, u::UnitRange) where {N}
  i_start = u.start
  i_stop = u.stop
  @views indices = A.data[i_start:i_stop+1] .- A.data[i_start] .+ 1
  a = vcat(indices, A.data[N+A.data[i_start]+1:N+A.data[i_stop+1]])
  return FMat{length(u)}(a)
end

Base.setindex!(A::FMat{N}, ::Int, ::Int) where {N} = A

IndexStyle(::Type{<:FMat}) = IndexLinear()

```

The code is able to halve the total memory size of the vector of vectors, which I was quite happy with. But then I started to check the actual performance of the indexing, it turned out the indexing is ~5x slower.

running

```julia
elements = Vector{Vector{Int}}()
for i in 1:7
  nrows = rand(UInt16) + 1
  for _ in 1:nrows
    push!(elements, abs.(rand(Int16, i)))
  end
end
fm = FMat(elements)

julia> @btime fm[end]
  190.954 ns (9 allocations: 240 bytes)
julia> @btime elements[end]
  30.271 ns (1 allocation: 16 bytes)

```

if i instead change it to

```julia
julia> @btime @view fm[end]
  28.810 ns (1 allocation: 48 bytes)

```

This of course is a big improvement, but I don’t want to keep writing @view everytime I want to get the element.

```julia
julia> @btime fm[end-5:end]
  2.708 μs (29 allocations: 1.77 KiB)
julia> @btime elements[end-5:end]
  118.097 ns (6 allocations: 192 bytes)

```

```julia
julia> @btime @view fm[end-5:end]
  80.627 ns (3 allocations: 96 bytes)
julia> @btime @view elements[end-5:end]
  94.805 ns (5 allocations: 128 bytes)

```

which in fact is a lot better. Any help would be greatly appreciated!

---

<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:** [January 13, 2025, 5:16pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/2 "2025-01-13T17:16:22Z")

</div>

> [@thomasc791](#):
>
> ```julia
> struct FMat{N} <: AbstractArray{Int,1}
> data::Vector{<:Integer}
> 
> ```

I don’t have the time to look into the details of this right now, but the type signature of the `data` field is abstract. There is no way for the compiler to determine the memory layout of `FMat` based on the type tag itself. You should make the element type of `data` into a type parameter, like this:

```julia
struct FMat{N, T}
   data::Vector{T}

```

---

<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:** [January 14, 2025, 10:12am UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/3 "2025-01-14T10:12:22Z")

</div>

The first thing you should do is improve the benchmarking. Observe

```julia
julia> @btime elements[end]
  38.625 ns (1 allocation: 16 bytes)

julia> @btime $elements[end]
  2.000 ns (0 allocations: 0 bytes)

```

The variable `elements` is a global, which can significantly mess up benchmarking, so when using BenchmarkTools, interpolate global variables with `$`.

Secondly, I suggest _not_ using the length `N` as a type parameter, but instead use the element type of the inner vectors, so this, instead:

```julia
struct FMat2{T} <: AbstractVector{T}
    data::Vector{T}
    len::Int
end

```

Using a type parameter for length means your code will almost always be type unstable, for example when doing slices. The compiler cannot predict the output type, and that is bad.

Or perhaps you don’t need any type parameter at all, if you always want `Int`.

Here’s a simple implementation. Two notes: I personally never use `@inline`, the compiler decides better than I do, and I strongly advise you _not_ to use `u.start` or `u.stop` for ranges, those are internal implementation details, and not part of the API. use `first(u)` and `last(u)`.

```julia
struct FMat2{T} <: AbstractVector{T}
    data::Vector{T}
    len::Int
    FMat2{T}(vals::Vector{T}, n=1) where {T<:Integer} = new{T}(vals, n)
end
function FMat2(vals::Vector{Vector{T}}) where {T<:Integer}
    N = length(vals)
    M = sum(length, vals)
    A = Vector{T}(undef, N + 1 + M)
    A[1] = 1
    len = 0
    i, j = 1, N+1
    for vv in vals
        A[i+=1] = (len += length(vv)) + 1
    end
    for vv in vals
        for v in vv
            A[j+=1] = v
        end
    end
    return FMat2{T}(A, N)
end
Base.length(fm::FMat2) = fm.len
Base.size(fm::FMat2) = (length(fm),)

function Base.getindex(A::FMat2, i::Int)
    N = length(A)
    return A.data[A.data[i]+N+1:A.data[i+1]+N]
end

function Base.getindex(A::FMat2{T}, u::UnitRange) where {T}
    i_start = first(u)
    i_stop = last(u)
    N = length(A)
    indices = @views A.data[i_start:i_stop+1] .- A.data[i_start] .+ 1
    a = vcat(indices, @view A.data[N+A.data[i_start]+1:N+A.data[i_stop+1]])
    return FMat2{T}(a, length(u))
end

Base.setindex!(A::FMat2{N}, ::Int, ::Int) where {N} = A

IndexStyle(::Type{<:FMat2}) = IndexLinear()

```

Try benchmarking, but remember the `$`.

I have not put `@views` on `getindex`, I’m not sure what you are actually looking for, but if you do that, scalar `getindex` is almost as fast as it is directly on `elements`.

---

<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:** [January 14, 2025, 11:36am UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/4 "2025-01-14T11:36:47Z")

</div>

Have you considered creating two vectors? One for the indices, and one for the data?

---

<div class="post-metadata">

**Author:** ![thomasc791](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thomasc791/32/214650_2.png) [@thomasc791](https://discourse.julialang.org/u/thomasc791)\
**Post date:** [January 14, 2025, 12:42pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/5 "2025-01-14T12:42:51Z")

</div>

Wow, this was incredibly helpful. Thank you very much. I did notice that your way of constructing the FMat is exactly the same speed, and amount and size of allocations as mine, which is nice to see. The method is now quite close to the `elements[index]`:

```julia
julia> @btime last($fm)
  3.443 ns (0 allocations: 0 bytes)

```

```julia
julia> @btime last($elements)
  2.218 ns(0 allocations: 0 bytes)

```

Still the time it take is ~1.5x longer, but that is already way better. Especially the parametric type that transfers the type information made a big difference.

I will check if splitting vector into a separate vector for the indices and one for elements makes a big difference in performance.

---

<div class="post-metadata">

**Author:** ![thomasc791](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thomasc791/32/214650_2.png) [@thomasc791](https://discourse.julialang.org/u/thomasc791)\
**Post date:** [January 14, 2025, 12:55pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/6 "2025-01-14T12:55:08Z")

</div>

Yeah, this was the initial idea.  
So the FMat will be used to represent elements in a finite element mesh. In the end I will create one for every dimension, so 0D, 1D, 2D, and 3D. All of which eventually will be stored in a struct, or vector. However, I recently watched a video on data-oriented design, which indicated that a vector of structs could increase the size of the data by a lot because of padding and alignment. I didn’t know whether this was an issue here, so I ended up choosing a single vector. I am going to make the other structure now, and compare the two.

---

<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:** [January 14, 2025, 1:09pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/7 "2025-01-14T13:09:30Z")

</div>

> [@thomasc791](#):
>
> I did notice that your way of constructing the FMat is exactly the same speed, and amount and size of allocations as mine,

Oh, on my computer my constructor is approximately twice as fast, and with half as much allocation.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 14, 2025, 2:08pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/8 "2025-01-14T14:08:05Z")

</div>

> [@DNF](#):
>
> Have you considered creating two vectors? One for the indices, and one for the data?

> [@thomasc791](#):
>
> However, I recently watched a video on data-oriented design, which indicated that a vector of structs could increase the size of the data by a lot because of padding and alignment.

Depends on the data types, and which format is better depends on how you are accessing it. In any case, you could use StructArrays.jl to make the API look like an array of structs when internally it is stored as a struct of arrays.

> [@thomasc791](#):
>
> So the FMat will be used to represent elements in a finite element mesh.

There are quite a few finite-element libraries in Julia already; I would look at how they store their meshes and data even if you want to want to write your own.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 14, 2025, 2:45pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/9 "2025-01-14T14:45:41Z")

</div>

> [@thomasc791](#):
>
> So the FMat will be used to represent elements in a finite element mesh. In the end I will create one for every dimension, so 0D, 1D, 2D, and 3D.

~~Consider using StaticArrays and just having a Vector{SVector{…}}.~~ (edit: bad idea, mea culpa)

> [@thomasc791](#):
>
> However, I recently watched a video on data-oriented design, which indicated that a vector of structs could increase the size of the data by a lot because of padding and alignment. I didn’t know whether this was an issue here, so I ended up choosing a single vector.

That is the wrong response!

You now learned that there is something something alignment padding that affects vectors of structs.

Nice! Now you know that there is something that you could learn, and what keywords to google, and once you do, you are empowered to worry about the issue.

Since you have not learned the details yet, you cannot take any other action to mitigate alignment padding. Using half-knowledge to maybe avoid a maybe-issue that you don’t understand at all is super counter-productive!

(I personally think that you should learn the details. But reasonable opinions on that may differ – do you learn programming with assembly or with lisp / julia? Matter of taste. If you knew any details, you’d know that alignment is not an issue for your constructions)

---

<div class="post-metadata">

**Author:** ![thomasc791](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thomasc791/32/214650_2.png) [@thomasc791](https://discourse.julialang.org/u/thomasc791)\
**Post date:** [January 14, 2025, 6:57pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/10 "2025-01-14T18:57:47Z")

</div>

> [@foobar\_lv2](#):
>
> Since you have not learned the details yet, you cannot take any other action to mitigate alignment padding. Using half-knowledge to maybe avoid a maybe-issue that you don’t understand at all is super counter-productive!
> 
> (I personally think that you should learn the details. But reasonable opinions on that may differ – do you learn programming with assembly or with lisp / julia? Matter of taste. If you knew any details, you’d know that alignment is not an issue for your constructions)

I agree with you on this. However, I don’t have enough time to figure out all the details to completely understand it. So I thought it wasn’t a bad idea to choose the approach, which I knew has a small footprint, but is a little bit harder to implement.

> [@foobar\_lv2](#):
>
> Consider using StaticArrays and just having a Vector{SVector{…}}.

This on the other hand I do not agree with. The README.md clearly states that for larger arrays a regular array results in better performance:

> Note that in the current implementation, working with large `StaticArray`s puts a lot of stress on the compiler, and becomes slower than `Base.Array` as the size increases. A very rough rule of thumb is that you should consider using a normal `Array` for arrays larger than 100 elements.

Or do you mean that the FMat should instead use with a Vector{SVector{Int}}. Where the inner SVector{Int} contains the node numbers? If so, would that really improve performance? I am not doing linear algebra operations with the vectors, but instead using them as indices for the node matrix.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 14, 2025, 10:21pm UTC](https://discourse.julialang.org/t/help-with-reducing-allocations-when-indexing-into-custom-array/124732/11 "2025-01-14T22:21:09Z")

</div>

> [@thomasc791](#):
>
> Or do you mean that the FMat should instead use with a Vector{SVector{Int}}. Where the inner SVector{Int} contains the node numbers?

I think I misunderstood what you’re doing here. Sorry! Disregard my ill-considered advice on that.

Having read your code more, I think I would probably go with two backing arrays?

```julia
struct FMat{T}
ptr::Vector{Int}
payload::Vector{T}
end
Base.getindex(f::FMat, idx) = view(f.payload, f.ptr[i]:f.ptr[i+1])

```

One of the big weirdnesses of your design is that the length of your `FMat` is part of the type. Is that really appropriate?