Drop element from tuple

[jw3126]

I have a Tuple and I want to drop its ith element (e.g. construct a new tuple with the same elements, except the ith is missing). For example

(1,2,3,4) , 1 --> (2,3,4)
(1,2,3,4) , 3 --> (1,2,4)
(1,2,3,4) , 4 --> (1,2,3)

How to do this?

[STAR0SS]

You can do something like that:

t = tuple(1,2,3,4)

function subtuple(t::Tuple,i::Integer)

    idx = 1:length(t)

    idx = setdiff(idx,i)

    t[idx]

end

subtuple(t,3)

(1,2,4)

[jw3126]

Okay thanks, it works! However it has extremely poor performance. I would love to do this stack allocated.

```
using BenchmarkTools

function subtuple(t::Tuple,i::Integer)
    idx = 1:length(t)
    idx = setdiff(idx,i)
    t[idx]
end

@benchmark subtuple($(1,2,3,4), $1)
```

BenchmarkTools.Trial: 
  samples:          10000
  evals/sample:     10
  time tolerance:   5.00%
  memory tolerance: 1.00%
  memory estimate:  1.33 kb
  allocs estimate:  22
  minimum time:     1.52 μs (0.00% GC)
  median time:      1.69 μs (0.00% GC)
  mean time:        1.96 μs (9.07% GC)
  maximum time:     323.58 μs (98.21% GC)

[jw3126]

The following is faster, though it does not scale very well for large indices because of ridiculous if chains...

```
@generated function droptup{N,T,i}(x::NTuple{N,T}, ::Type{Val{i}})
    @assert 1 <= i <= N
    args = [:(x[$j]) for j in deleteat!([1:N...], i)]
    Expr(:tuple, args...)
end

@generated function droptup{N,T}(x::NTuple{N,T}, i::Int)
    quote
        @nif $N d->(i==d) d-> droptup(x, Val{d})
    end
end

using BenchmarkTools
x = (10,20,30,40)

@benchmark droptup($x, 4)
```

BenchmarkTools.Trial: 
  samples:          10000
  evals/sample:     1000
  time tolerance:   5.00%
  memory tolerance: 1.00%
  memory estimate:  0.00 bytes
  allocs estimate:  0
  minimum time:     6.00 ns (0.00% GC)
  median time:      6.00 ns (0.00% GC)
  mean time:        6.11 ns (0.00% GC)
  maximum time:     70.00 ns (0.00% GC)

[Tim Holy]

It might scale just fine, because LLVM might discover the pattern of your
"giant switch statement" and essentially compute a jump location. Even if not,
if you're calling this repeatedly with a tuple of consistent length, the
branches become predictable and then they kind of don't count. So in most
cases I doubt it's possible to beat the performance of the solution you
posted.

For small tuples, you can essentially match the performance of your generated
function using "lispy" recursion. This is more friendly for the compiler,
which you may or may not care about. (It's something we care about in Base,
but there's no reason you necessarily have to worry about it in your own
code.)

First, a couple of convenience functions:

@inline push(t::Tuple, item) = (t..., item)
@inline unshift(t::Tuple, item) = (item, t...)
# we'll also need something like shift!, but that's already present
# and called Base.tail

Now let's implement your function:

drop_ith(t, i) = 1 <= i <= length(t) ?
_drop_ith((), t, i) :
throw(ArgumentError("need 1 <= $i <= $(length(t))"))
@inline function _drop_ith(out, t, i)
h, t1 = t[1], Base.tail(t)
_drop_ith(length(out)+1 == i ? unshift(out, h) : push(out, h), t1, i)
end
_drop_ith(out, ::Tuple{}, i) = Base.tail(out)

This uses the sneaky trick of preserving type-stability by putting the element
you want to drop into the first position, thus ensuring that the tuple always
grows by 1 on each level of recursion. (For tuples, the length is part of the
type, so making the length predictable is critical for type-stability.) At the
end, you strip off the first element.

This works well up to tuples of size 14; any bigger, and a variable called
MAX_TUPLETYPE_LEN ends up kicking in and hurting performance. However, it has
the advantage of not needing Val tricks or @generated functions. In cases
where there's less run-time checking, this approach can usually match
@generated solutions, so the general technique is worth knowing.

Best,
--Tim

[Sisyphuss]

Why not use `vector`?

[jw3126]

@Sisyphuss: The problem with vectors is that they are always heap allocated. If you do stuff involving lots of small size vectors things become slow. What I need to do is projecting points onto simplexes in 1-4 dimensions, so this a task base arrays are bad at. I tried to do it only allocating the arrays once and mutating them. But this makes the code very quickly very ugly... Now I use the FixedSizeArrays package instead, which is based on Tuples.

@Tim: Thanks for the insights! On my machine slowness starts to kick in at size 9 already. I tried to read the llvm code, but did not really understand it. It seems however that the machine will not go through N (out, t) pairs for a tuple of length N?

Also is it possible in Julia, to implement this function in a low level way, like directly shifting bits in the tuple?

[Kristoffer Carlsson]

You cannot hack around the fact that a tuple is immutable so you need to construct a new one from scratch.

[jw3126]

I did not mean to mutate the tuple. Just implement the index dropping by some code which directly specifies the bits of the new tuple as a function of the bits of the old tuple.

[Tim Holy]

On Saturday, June 25, 2016 6:45:05 AM CDT jw3126 wrote:
> @Tim: Thanks for the insights! On my machine slowness starts to kick in at
> size 9 already.

Depends on which version of julia you're running (I'm running a recent
julia-0.5-dev).

> I tried to read the llvm code, but did not really
> understand it. It seems however that the machine will not go through N
> (out, t) pairs for a tuple of length N?

The @inline gives LLVM the chance to elide the apparent intermediates:
essentially you're describing the computation you want to perform in a way the
compiler can understand, but which may or may not reflect the final operations
performed by the CPU. Coaching it into taking the opportunity to fully
optimize this operation takes a little practice, and unfortunately sometimes
involves a little magic (e.g., https://github.com/JuliaLang/julia/issues/
17126).

Best,
--Tim

[jw3126]

Thanks again Tim!