# Type stable difference of tuples
**URL:** https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933
**Category:** General Usage
**Tags:** question
**Created:** [May 25, 2017, 7:59pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933 "2017-05-25T19:59:37Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@jebej](https://discourse.julialang.org/u/jebej)
#### Post date: [May 25, 2017, 7:59pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/1 "2017-05-25T19:59:37Z")
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.
---
### Author:  [@cstjean](https://discourse.julialang.org/u/cstjean)
#### Post date: [May 25, 2017, 9:49pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/2 "2017-05-25T21:49:35Z")
If I’m understanding you correctly…
```julia
# 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?
---
### Author:  [@jebej](https://discourse.julialang.org/u/jebej)
#### Post date: [May 25, 2017, 10:13pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/3 "2017-05-25T22:13:25Z")
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.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [May 25, 2017, 10:33pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/4 "2017-05-25T22:33:54Z")
Are both your tuples already sorted and have no duplicate elements? If so:
```julia
import Base: tail
@inline function sorted_setdiff(t1::Tuple, t2::Tuple)
if t1[1] == t2[1]
sorted_setdiff(tail(t1), tail(t2))
else
(t1[1], sorted_setdiff(tail(t1), t2)...)
end
end
@noinline sorted_setdiff(t1::Tuple{}, t2::Tuple) = error("did not find $(t2[1])")
sorted_setdiff(t1::Tuple, ::Tuple{}) = t1
sorted_setdiff(::Tuple{}, ::Tuple{}) = ()
```
Benchmarks are left to the reader…
---
### Author:  [@jebej](https://discourse.julialang.org/u/jebej)
#### Post date: [May 25, 2017, 10:44pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/5 "2017-05-25T22:44:54Z")
Wow that’s really neat! The `@code_warntype` output of this is pretty crazy but it works perfectly well! Thanks all for your help.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [May 25, 2017, 10:51pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/6 "2017-05-25T22:51:46Z")
Yeah, don’t call it on large tuples — it creates exponentially large functions. 🙂
---
### Author:  [@e3c6](https://discourse.julialang.org/u/e3c6)
#### Post date: [June 6, 2020, 2:06pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/7 "2020-06-06T14:06:08Z")
> [@mbauman](#):
>
> ```julia
> @noinline sorted_setdiff(t1::Tuple{}, t2::Tuple) = error("did not find $(t2[1])")
>
> ```
Sorry to revive a very old topic. But why is this marked `@noinline`?
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [June 8, 2020, 2:29pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/8 "2020-06-08T14:29:00Z")
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.~~
---
### Author:  [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)
#### Post date: [June 8, 2020, 3:11pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/9 "2020-06-08T15:11:12Z")
> [@mbauman](#):
>
> and error messages could create a GC frame. I’m sure it’s no longer necessary.
The string interpolation probably requires a GC frame?
```julia
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[7]: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
...
```
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [June 8, 2020, 3:19pm UTC](https://discourse.julialang.org/t/type-stable-difference-of-tuples/3933/10 "2020-06-08T15:19:05Z")
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
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
%reass.add = add i64 %0, 3
%reass.add1 = add i64 %reass.add, %3
%reass.mul = mul i64 %reass.add1, %0
ret i64 %reass.mul
}
```