Make this Tuple code faster

General Usage Performance
1

I have a Tuple and want to replace its starting segment:

function switch_front(new_front, t)
    n = length(t)
    k = length(new_front)
    @assert k <= n
    (new_front..., t[k+1:n]...)
end

using Test
@test switch_front((10,), (1, 2, 3, 4))        === (10, 2, 3, 4)
@test switch_front((10, 20), (1, 2, 3, 4))     === (10, 20, 3, 4)
@test switch_front((10, 20, 30), (1, 2, 3, 4)) === (10, 20, 30, 4)

For very small tuples this works fine. However already for length 4 tuple inference breaks down:

function funny_numbers(n)
    types = [
        Int128, Int16, Int32, Int64, Int8,
        UInt128, UInt16, UInt32, UInt64, UInt8,
        Float16, Float32, Float64,
    ]
    tuple([T(true) for T in rand(types, n)]...)
end

@inferred switch_front(funny_numbers(3), funny_numbers(3)) # works
@inferred switch_front(funny_numbers(2), funny_numbers(4)) # works
@inferred switch_front(funny_numbers(3), funny_numbers(4)) # fails

Is there a way to make this infer much better? I would like this to work for length 30 tuples. Can it be done without using @generated?

1 Like
2

This really doesn’t sound like a job for tuples, which are immutable. If you use arrays, you could do

function switch_front!(a, b)
    a[1:length(b)] .= b
end

function switch_front(a, b)
    c = copy(a)
    switch_front!(c, b)
    return c
end
3

Have you tried it with different function? funny_numbers is type unstable, I am surprised that there was any inference at all.

1 Like
4

The following seems to work:

function back(xs::Tuple, ::Val{N}) where {N}
    back(Base.tail(xs), Val{N-1}())
end
function back(x::Tuple, ::Val{0})
    x
end
function switch_front(new_front::NTuple{K,Any}, x) where {K}
    (new_front..., back(x, Val{K}())...)
end

using Test
function funny_numbers(n)
    types = [
        Int128, Int16, Int32, Int64, Int8,
        UInt128, UInt16, UInt32, UInt64, UInt8,
        Float16, Float32, Float64,
    ]
    tuple([T(true) for T in rand(types, n)]...)
end

@inferred back((1,2,3,4,5,5), Val(3)) # works
@inferred switch_front(funny_numbers(30), funny_numbers(40)) # works
@inferred switch_front(funny_numbers(1000), funny_numbers(1000)) # works
@inferred switch_front(funny_numbers(2000), funny_numbers(2000)) # fail, don't try this at home
1 Like
5

AFAICT it does not matter whether funny_numbers is type stable:

julia> @macroexpand @inferred f(g(x))
...
            var"#2#args" = (g(x),)
            var"#4#inftypes" = (Test.Base).return_types(f, (Test.Base).typesof(var"#2#args"...))
...

All arguments are evaluated before inference starts.

6

The strength of tuples relies on the fact that all element types are part of the tuples type. funny_numbers can’t guarantee that, since you’re picking types at random. If it’s type stable, it should be faster for more than just 4 elements.

1 Like
7

To clarify funny_numbers is a quick and dirty way to generate some tricky test tuples. I do not care about its performance or type stability. I only care about switch_front.

8

Try it on nightly. Tuple indexing should infer more reliably there.

2 Likes
9

Thanks! Your solution looks good, though here I am really interested in Tuples.

10

You can try to use ntuple

function switch_front2(new_front, t)
    n = length(t)
    k = length(new_front)
    @assert k <= n
    ntuple(i -> i <= k ? new_front[i] : t[i], n)
end

julia> @code_warntype switch_front2(funny_numbers(3), funny_numbers(4))
MethodInstance for switch_front2(::Tuple{UInt16, UInt128, Int8}, ::Tuple{UInt64, Int64, Int
8, Float32})
  from switch_front2(new_front, t) in Main at REPL[14]:1
Arguments
  #self#::Core.Const(switch_front2)
  new_front::Tuple{UInt16, UInt128, Int8}
  t::Tuple{UInt64, Int64, Int8, Float32}
Locals
  #11::var"#11#12"{Tuple{UInt16, UInt128, Int8}, Tuple{UInt64, Int64, Int8, Float32}, Int64
}
  k::Int64
  n::Int64
Body::Tuple{UInt16, UInt128, Int8, Float32}
1 ─       Core.NewvarNode(:(#11))
│         (n = Main.length(t))
│         (k = Main.length(new_front))
│   %4  = (k::Core.Const(3) <= n::Core.Const(4))::Core.Const(true)
│         %4
└──       goto #3
2 ─       Core.Const(:(Base.AssertionError("k <= n")))
└──       Core.Const(:(Base.throw(%7)))
3 ┄ %9  = Main.:(var"#11#12")::Core.Const(var"#11#12")
│   %10 = Core.typeof(new_front)::Core.Const(Tuple{UInt16, UInt128, Int8})
│   %11 = Core.typeof(t)::Core.Const(Tuple{UInt64, Int64, Int8, Float32})
│   %12 = Core.typeof(k::Core.Const(3))::Core.Const(Int64)
│   %13 = Core.apply_type(%9, %10, %11, %12)::Core.Const(var"#11#12"{Tuple{UInt16, UInt128,
 Int8}, Tuple{UInt64, Int64, Int8, Float32}, Int64})
│         (#11 = %new(%13, new_front, t, k::Core.Const(3)))
│   %15 = #11::Core.PartialStruct(var"#11#12"{Tuple{UInt16, UInt128, Int8}, Tuple{UInt64, I
nt64, Int8, Float32}, Int64}, Any[Tuple{UInt16, UInt128, Int8}, Tuple{UInt64, Int64, Int8,
Float32}, Core.Const(3)])
│   %16 = Main.ntuple(%15, n::Core.Const(4))::Tuple{UInt16, UInt128, Int8, Float32}
└──       return %16
2 Likes
11

On nightly this infers for tuples of size 1024. For 2048 I get some crazy crash.

12

Interesting, this works better then the variant in the opening post, but breaks down for Tuples of size 11.