Type stable difference of tuples

General Usage
1

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.

2

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?

3

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.

4

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[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…

5 Likes
5

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

6

Yeah, don’t call it on large tuples — it creates exponentially large functions. :slight_smile:

7

Sorry to revive a very old topic. But why is this marked @noinline?

8

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
9

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[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
...
1 Like
10

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
  %reass.add = add i64 %0, 3
  %reass.add1 = add i64 %reass.add, %3
  %reass.mul = mul i64 %reass.add1, %0
  ret i64 %reass.mul
}