# Type stable difference of tuples

Hello everyone, I am trying to figure out how to take the difference between two tuples of integers in a type-stable way, assuming that, if tuple `a` has length `n`, and tuple `b` has length `m`, then tuple `c = setdiff(a,b)` will have length `n-m`.

With that condition, it seems like it should be possible.

If I’m understanding you correctly…

``````# Should work, but unfortunately doesn't
overlapping_setdiff{N, M}(a::NTuple{N, Int}, b::NTuple{M, Int})::NTuple{N-M, Int} =
tuple(setdiff(a, b)...)

# Type-stable
@generated overlapping_setdiff2{N, M}(a::NTuple{N, Int}, b::NTuple{M, Int}) =
:(tuple(setdiff(a, b)...)::NTuple{\$(N-M), Int})

overlapping_setdiff2((3,4,5), (4,5))
``````

It’s type-stable but not terribly efficient, since it builds an intermediate array. Is that a problem?

Thanks, I didn’t know about the generated trick! Yeah, I do want it to be efficient. I was also using `setdiff`, and it is quite slow. I managed to make it faster by using a bitarray, but that still is pretty slow.

Are both your tuples already sorted and have no duplicate elements? If so:

``````import Base: tail
@inline function sorted_setdiff(t1::Tuple, t2::Tuple)
if t1 == t2
sorted_setdiff(tail(t1), tail(t2))
else
(t1, sorted_setdiff(tail(t1), t2)...)
end
end
@noinline sorted_setdiff(t1::Tuple{}, t2::Tuple) = error("did not find \$(t2)")
sorted_setdiff(t1::Tuple, ::Tuple{}) = t1
sorted_setdiff(::Tuple{}, ::Tuple{}) = ()
``````

Benchmarks are left to the reader…

4 Likes

Wow that’s really neat! The `@code_warntype` output of this is pretty crazy but it works perfectly well! Thanks all for your help.

Yeah, don’t call it on large tuples — it creates exponentially large functions. Sorry to revive a very old topic. But why is this marked `@noinline`?

Old versions of Julia weren’t nearly as smart about their inlining behaviors, and error messages could create a GC frame. I’m sure it’s no longer necessary.

1 Like

The string interpolation probably requires a GC frame?

``````julia> function f(x)
x < 10 && error("x not allowed to be less than zero, got \$x")
return x
end
f (generic function with 1 method)

julia> @code_llvm f(2)

;  @ REPL:1 within `f'
define i64 @julia_f_198(i64) {
top:
%1 = alloca %jl_value_t*, i32 2
%gcframe = alloca %jl_value_t*, i32 3, align 16
...
``````
1 Like

Yes, I figured that’d still require a GC frame, but I just assumed that the inliner had gotten smart enough to prevent such a thing. But that part isn’t true — I should have tested it first:

``````julia> function g(x)
f(x)
6x^3 + x^2 + 3x
end
g (generic function with 1 method)

julia> @code_llvm g(2)'
# long with GC preamble, etc.

julia> @noinline function f_noinline(x)
x < 10 && error("x not allowed to be less than zero, got \$x")
return x
end
f_noinline (generic function with 1 method)

julia> function g2(x)
f_noinline(x)
6x^3 + x^2 + 3x
end

julia> @code_llvm debuginfo=:none g2(22)

define i64 @julia_g2_308(i64) {
top:
%1 = call i64 @j_f_noinline_309(i64 %0)
%2 = mul i64 %0, %0
%3 = mul i64 %2, 6