Store abstract types in a container

General Usage Performance
1

What is the best way to store abstract types in an array let’s say:
I have array world geometry. Each world component is essentially an object. Each array element could be A or B type, but both A<:C, B<:C. So I need a Array{C} to store these objects. In case I do it this way I get compiler type inference warnings.

What is the best way to overcome this limitaion?

Suggestions I already got:

  1. Create dummy class D with integer coding that would distinguish the types.
  2. It should not cause a lot of trouble with regard to performance, but it does upon testing. Type stability gives around 20% performance which is important.
2

The first thing is to identify if there is actually a performance problem if you just put them in an abstractly typed container… because otherwise that’s what I would suggest too.

3

Without seeing any code or how your types are defined, it’s a bit hard to say. Perhaps you could create a type WorldComponentsCollection defined as

struct WorldComponentsCollection
    collection_A::Vector{A}
    collection_B::Vector{B}
end

function WorldComponentsCollection(components)
    collection_A = filter(c -> isa(c, A), components)
    collection_B = filter(c -> isa(c, B), components)
    WorldComponentsCollection(collection_A, collection_B)
end

Then you could pre-process your array of components by storing them in a WorldComponentsCollection instance, and operate on the WorldComponentsCollection instead of the array. That would eliminate any type inference issues.

4

Note that Array by itself is an abstract type - you haven’t defined the dimensions. A full specification would be Array{C, 1}, which is a container of one dimension holding objects that are (a subtype) of C.

Have you tried Vector{T} where T <: C or Vector{Union{A, B}}? This avoids the abstract type.

Moreover, what sort of compiler warning do you observe?

5

At this point I do not care of it is 2d or 1d array. I believe union A B is already ambigous and get type inference warnings

6

You have understood my problem very well, and I think your solution is very good. However, the reason why I store these 2 types in a single array is that, there would be a lot of WorldComponent changing.

That is, the order of the elements in collection_C:Vector{Union(A,B)} is crucial and that is why I want to store it in a contiguous array because in my case it is connected chain (like self connected linked list), and in the simulation I would run over all WorldComponents for many laps. The issue is that cost of simulating one WorldComponent is trivial, the real issue comes because of many laps.

I do not mind storing A,B separately, as long as I can note the initial order somehow (I really do not know how at this point, perhaps by integer coding again?) and guarantee good performance when using A, B containers separately (in terms of memory moving and stuff).

Let me know if I explained myself correctly and thanks for your response in advance

7

Union{A,B} is going to be faster because small unions are very well optimized.

What type does your actual array have? How do you construct it? What sort of errors or warnings do you get? I assumed, based on you writing Array{C}, that you left the dimension unspecified somewhere, which is going to lead to suboptimal performance, regardless of what C is precisely.

Moreover, are you certain this part of the code is your bottleneck? Maybe there’s some other part that’s taking up more time, some example code would go a long way to diagnosing the issue.

8

I suppose you could modify your definition to, perhaps,

struct WorldComponentsCollection
    collection_A::Vector{Tuple{Int64,A}}
    collection_B::Vector{Tuple{Int64,B}}
end

function WorldComponentsCollection(components)
    components = enumerate(components)
    collection_A = filter(c -> isa(c[2], A), components)
    collection_B = filter(c -> isa(c[2], B), components)
    WorldComponentsCollection(collection_A, collection_B)
end

Then collection_A[i] would store a 2-tuple whose first element is an index into the original components array and whose second element is an component of type A, and similar for collection_B. Then you could process your elements in order by doing something analogous to the merge step in a merge sort, e.g.

function process(c::WorldComponentsCollection)
    i = j = 1
    while i <= length(c.collection_A) && j <= length(c.collection_B)
        if c.collection_A[i][1] < c.collection_B[j][1]
            process(c.collection_A[i][2])
            i += 1
        else
            process(c.collection_B[j][2])
            j += 1
        end
    end

    while i <= length(c.collection_A)
        process(c.collection_A[i][2])
        i += 1
    end

    while j <= length(c.collection_B)
        process(c.collection_B[i][2])
        j += 1
    end
end