Tuple reverse is not type-stable enough

General Usage
1

I just start with an MWE:

# julia 1.4
# ]add AxisKeys
using AxisKeys
using Test

# "more" type-stable version of reverse
reverse_tuple(x) = ntuple(i -> x[length(x) + 1 - i], length(x))

f1(nt) = NamedDimsArray(zeros(1,1,1), keys(nt) |> reverse)
f2(nt) = NamedDimsArray(zeros(1,1,1), keys(nt) |> reverse_tuple)

@inferred f1((a=1,b=1,c=1))  # fails: keys not inferred
@inferred f2((a=1,b=1,c=1))  # passes

Basically, function f1 does not infer correctly, but f2 does - and the only thing that differs is the tuple reversal function.
Note that Base.reverse is type-stable if used by itself, and the example above reproduces only when reverse is put inside something else.

Any idea why this happens and what’s going on?

2

You’re putting the (:c, :b, :a) tuple into a type parameter, so you’re not really fighting type-stability… you’re fighting constant propagation. Not only does Julia need to get the type of reverse correct, it needs to deduce (and mark) the fact that it’s going to return that particular value ahead of time. That in turn is affecting the downstream type-stability once you put the (hopefully) constant value into a type parameter.

1 Like
3

Note for sufficiently long tuples, reverse will become a gigantic runtime performance problem:

julia> @generated function myreverse(t::NTuple{N, Any}) where {N}
           Expr(:tuple, (:(t[$i]) for i in N:-1:1)...)
       end
myreverse (generic function with 1 method)

julia> for n ∈ 1:5:50
           tt = Ref(Tuple(1:n))
           println("n = $n")
           print("  "); 
           @btime reverse($tt[])
           print("  ");
           @btime myreverse($tt[])
           println(" ")
       end
n = 1
    1.289 ns (0 allocations: 0 bytes)
    1.290 ns (0 allocations: 0 bytes)
 
n = 6
    2.839 ns (0 allocations: 0 bytes)
    2.909 ns (0 allocations: 0 bytes)
 
n = 11
    3.439 ns (0 allocations: 0 bytes)
    3.349 ns (0 allocations: 0 bytes)
 
n = 16
    4.369 ns (0 allocations: 0 bytes)
    4.489 ns (0 allocations: 0 bytes)
 
n = 21
    4.229 ns (0 allocations: 0 bytes)
    4.229 ns (0 allocations: 0 bytes)
 
n = 26
    7.116 ns (0 allocations: 0 bytes)
    6.939 ns (0 allocations: 0 bytes)
 
n = 31
    5.819 ns (0 allocations: 0 bytes)
    5.669 ns (0 allocations: 0 bytes)
 
n = 36
    25.239 μs (72 allocations: 6.47 KiB)
    9.749 ns (0 allocations: 0 bytes)
 
n = 41
    31.559 μs (82 allocations: 8.19 KiB)
    7.657 ns (0 allocations: 0 bytes)
 
n = 46
    38.580 μs (92 allocations: 10.16 KiB)
    12.381 ns (0 allocations: 0 bytes)

but this is a separate issue from type stability.

4

Indeed, you are right - I didn’t notice that. It means AxisKeys interface is not type-stable, and nothing is suboptimal about Base.reverse implementation, right?
Then my reverse_tuple is somehow easier for the julia constant propagation, but it has nothing to do with type stability?

5

Some reverse(::Tuple) performance discussion references:

1 Like