Is there a way to "forward" getindex for Tuples in a type-stable way?

General Usage
21

One other option is to add a layer of indirection so that all the bt[i]'s of a particular type are indexed by subarrays of another array; each subarray is parameterized by this type. Then the code can run through the bt[i] entries ordered by type rather than by i, so that the inner loops are all type-stable. I think that DifferentialEquations.jl uses a related technique for specifying boundary conditions. (The situation with boundary conditions is more complicated because these are functions rather than quantities, and each function is its own type in Julia.)

22

As far as I understand, that’s what TypeSortedCollections.jl does for you automatically.

1 Like
23

Yeah I was looking at TypeSortedCollections.jl but something from their README scared me a bit:

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.

What I will soon-ish do is simply make my container a tuple and benchmark everything, versus it being a simple tuple or a TypeSortedCollection. I will definitely post my results here!

1 Like
24

Awesome, would be interesting to see.

I added that comment on account of the fact that if the number of types is close to the number of elements, you’re just going to have a bunch of extra for loops over 1-element Vectors stored in the TypeSortedCollection. So in this case, using a TypeSortedCollection instead of a Tuple will just add a bit of overhead without getting any payback in terms of reduced compilation time.

25

FYI, I just added broadcast! (with AbstractVector destination) to TypeSortedCollections (requires TypeSortedCollections master for now):

julia> using TypeSortedCollections, BenchmarkTools

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> @benchmark $results .= $x .* $sortedys # with julia -O3 --check-bounds=no

BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     10.196 ns (0.00% GC)
  median time:      10.836 ns (0.00% GC)
  mean time:        11.453 ns (0.00% GC)
  maximum time:     1.048 μs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     999
1 Like
26

Fyi, the exact example I gave in my original question is now type-stable thanks to the magic of https://github.com/JuliaLang/julia/pull/24362 which just recently got merged into master :slight_smile:

2 Likes