SOA transform

General Usage Performance
1

I’m playing with a SOA transform (AoS and SoA - Wikipedia) via StructArrays.jl. My code:

using StructArrays

function test1()
    n = 10
    v = Vector{Tuple{Int, Int}}(undef, n)
    s = 0
    for i in 1:n
        v[i] = Base.setindex(v[i], 2 * i - 1, 1)
        v[i] = Base.setindex(v[i], 2 * i, 2)
        v1 = v[i][1]
        v2 = v[i][2]
        # v1, v2 = v[i]
        s += v1 + v2
    end
    @assert s == n * (2 * n + 1)
end

function test2()
    n = 100000
    v = StructArray{Tuple{Int, Int}}(undef, n)
    s = 0
    for i in 1:n
        v[i] = Base.setindex(v[i], 2 * i - 1, 1)
        v[i] = Base.setindex(v[i], 2 * i, 2)
        v1 = v[i][1]
        v2 = v[i][2]
        # v1, v2 = v[i]
        s += v1 + v2
    end
    @assert s == n * (2 * n + 1)
end

@btime test1()
@btime test2()

Result:

 33.132 ns (1 allocation: 240 bytes)
  134.200 ΞΌs (4 allocations: 1.53 MiB)

What am I missing?

2

Stupid mistake on my side. Correcting the n in test1 results in

266.100 ΞΌs (2 allocations: 1.53 MiB)
  134.600 ΞΌs (4 allocations: 1.53 MiB)

Back to the drawing board, trying to isolate the problem in my real program and sorry for the noise.

3

Interesting: I code_warntyped the critical part of my program and saw red. Now the critical part seem to be the functions

Base.getindex(alloc::Allocator{T, I}, i::I) where {T, I} =
    @inbounds alloc.store[i]

with store a Vector{T} and

function Base.getindex(alloc::SOAllocator{T, I}, i::I)::T where {T, I}
    @inbounds alloc.store[i]
end

with store a StructArray{T}. @code_warntype gives me

Variables
  #self#::Core.Const(getindex)
  alloc::Allocator{Tuple{Int64, Int64}, Int64}
  i::Int64
  val::Tuple{Int64, Int64}

Body::Tuple{Int64, Int64}
1 ─      $(Expr(:inbounds, true))
β”‚   %2 = Base.getproperty(alloc, :store)::Vector{Tuple{Int64, Int64}}
β”‚        (val = Base.getindex(%2, i))
β”‚        $(Expr(:inbounds, :pop))
└──      return val

for the first and

Variables
  #self#::Core.Const(getindex)
  alloc::SOAllocator{Tuple{Int64, Int64}, Int64}
  i::Int64
  val::Any

Body::Tuple{Int64, Int64}
1 ─ %1 = $(Expr(:static_parameter, 1))::Core.Const(Tuple{Int64, Int64})
β”‚        $(Expr(:inbounds, true))
β”‚   %3 = Base.getproperty(alloc, :store)::StructArray{Tuple{Int64, Int64}, N, C, I} where {N, C<:Union{Tuple, NamedTuple}, I}
β”‚        (val = Base.getindex(%3, i))
β”‚        $(Expr(:inbounds, :pop))
β”‚   %6 = Base.convert(%1, val)::Tuple{Vararg{Any, _A}} where _A
β”‚   %7 = Core.typeassert(%6, %1)::Tuple{Int64, Int64}
└──      return %7

for the second. Has someone any idea what is going wrong here?

4

just a side note, you can write this simply as

               v[i] = (2 * i - 1, 2 * i)

I would guess that you have some abstract type in your struct, but hard to tell only with this.

1 Like
5

I have:

mutable struct SOAllocator{T, I} <: AbstractAllocator{T, I}
    n::I
    resizable::Bool
    store::StructArray{T}
    first::I
    last::I
end

whereas StructArray’s definition is

struct StructArray{T, N, C<:Tup, I} <: AbstractArray{T, N}
    components::C
end

But I have no idea, if and how I have to specify the other type parameters.

6

At least N=1 seems now obvious. Investigating further…

7

You can try this, to see if it is the parameters of the struct array that are missing:

1 Like
8

Here is the only way I found to specify the C type parameter

v = StructArray{Tuple{Int, Int}, 1}(undef, 1)
println(typeof(v))
v = StructArray{Tuple{Int, Int}, 1, Tuple{Vector{Int}, Vector{Int}}}((Vector{Int}(undef, 1), Vector{Int}(undef, 1)))
println(typeof(v))

Unfortunately the second constructor requires an instance of the components. Is there any way around this?

9

Something like this and external construction of the store seems to do the job:

mutable struct SOAllocator{T <: Tuple, I, S <: StructVector{T}} <: AbstractAllocator{T, I}
    n::I
    resizable::Bool
    store::S
    first::I
    last::I
end

@code_warntype now shows

Variables
  #self#::Core.Const(getindex)
  alloc::SOAllocator{Tuple{Int64, Int64}, Int64, StructVector{Tuple{Int64, Int64}, Tuple{Vector{Int64}, Vector{Int64}}, Int64}}
  i::Int64
  val::Tuple{Int64, Int64}

Body::Tuple{Int64, Int64}
1 ─ %1 = $(Expr(:static_parameter, 1))::Core.Const(Tuple{Int64, Int64})
β”‚        $(Expr(:inbounds, true))
β”‚   %3 = Base.getproperty(alloc, :store)::StructVector{Tuple{Int64, Int64}, Tuple{Vector{Int64}, Vector{Int64}}, Int64}
β”‚        (val = Base.getindex(%3, i))
β”‚        $(Expr(:inbounds, :pop))
β”‚   %6 = Base.convert(%1, val)::Tuple{Int64, Int64}
β”‚   %7 = Core.typeassert(%6, %1)::Tuple{Int64, Int64}
└──      return %7

Excellent advice as usual!

1 Like