TypeSortedCollections

TypeSortedCollections provides the TypeSortedCollection type, which can be used to store type-heterogeneous data in a way that allows operations on the data to be performed in a type-stable manner. It does so by sorting a type-heterogeneous input collection by type upon construction, and storing these elements in a Tuple of concretely typed Vectors, one for each type. TypeSortedCollections provides type stable methods for map!, foreach, broadcast!, and mapreduce that take at least one TypeSortedCollection.

An example:

julia> using TypeSortedCollections

julia> f(x::Int64, y::Float64) = x * y
f (generic function with 2 methods)

julia> f(x::Float64, y::Float64) = round(Int64, -x * y)
f (generic function with 2 methods)

julia> xs = Number[1.; 2; 3];

julia> sortedxs = TypeSortedCollection(xs);

julia> ys = [1.; 2.; 3.];

julia> results = Vector{Int64}(length(xs));

julia> map!(f, results, sortedxs, ys)
3-element Array{Int64,1}:
 -1
  4
  9

julia> @allocated map!(f, results, sortedxs, ys)
0

Use cases

TypeSortedCollections are appropriate when the number of different types in a heterogeneous collection is (much) smaller than the number of elements of the collection. If the number of types is approximately the same as the number of elements, a plain Tuple may be a better choice.

Note that construction of a TypeSortedCollection is of course not type stable, so the intended usage is not to construct TypeSortedCollections in tight loops.

See also FunctionWrappers.jl for a solution to the related problem of storing and calling multiple callables in a type-stable manner, and Unrolled.jl for a macro-based solution.

Iteration order

By default, TypeSortedCollections do not preserve iteration order, in the sense that the order in which elements are processed in map!, foreach, broadcast!, and mapreduce will not be the same as if these functions were called on the original type-heterogeneous vector:

julia> xs = Number[1.; 2; 3.];

julia> sortedxs = TypeSortedCollection(xs);

julia> foreach(println, sortedxs)
1.0
3.0
2

If this is not desired, a TypeSortedCollection that does preserve iteration order can be constructed by passing in an additional constructor argument:

julia> xs = Number[1.; 2; 3.];

julia> sortedxs = TypeSortedCollection(xs, true);

julia> foreach(println, sortedxs)
1.0
2
3.0

The cost of preserving iteration order is that the number of Vectors stored in the TypeSortedCollection becomes equal to the number of contiguous subsequences of the input collection that have the same type, as opposed to simply the number of different types in the input collection. Note that calls to map! and foreach with both TypeSortedCollection and AbstractVector arguments are correctly indexed, regardless of whether iteration order is preserved:

julia> xs = Number[1.; 2; 3.];

julia> sortedxs = TypeSortedCollection(xs); # doesn't preserve iteration order

julia> results = similar(xs);

julia> map!(identity, results, sortedxs) # results of applying `identity` end up in the right location
3-element Array{Number,1}:
 1.0
 2
 3.0

Working with multiple TypeSortedCollections

Consider the following example:

julia> xs = Number[Float32(1); 2; 3.; 4.];

julia> ys = Number[1.; 2.; 3; 4];

julia> results = Vector{Float64}(length(xs));

julia> sortedxs = TypeSortedCollection(xs);

julia> sortedys = TypeSortedCollection(ys);

julia> map!(*, results, sortedxs, sortedys) # Error!

The error happens because xs and ys don't have the same number of different element types. This problem can be solved by aligning the indices of sortedys with those of sortedxs:

julia> sortedys = TypeSortedCollection(ys, TypeSortedCollections.indices(sortedxs));

julia> map!(*, results, sortedxs, sortedys)
4-element Array{Float64,1}:
  1.0
  4.0
  9.0
 16.0

Broadcasting

Broadcasting (in place) is implemented for AbstractVector return types:

julia> x = 4;

julia> ys = Number[1.; 2; 3];

julia> sortedys = TypeSortedCollection(ys);

julia> results = similar(ys, Float64);

julia> results .= x .* sortedys
3-element Array{Float64,1}:
  4.0
  8.0
 12.0

julia> @allocated results .= x .* sortedys
0