Should we use a polyalg for `permute!`?

[araujoms]

permute!(v, p) is strictly worse than v[p]. It is slower, allocates more memory, and doesn't work for multidimensional arrays. It shouldn't exist. I think the following alternatives are reasonable:

1. Deprecate it.
2. Write instead something like

function permute!(v::AbstractArray, p::AbstractArray)
    for i in 1:length(p)-1
        ind = p[i]
        while (ind < i)
            ind = p[ind]
        end
        if i != ind
            temp = v[i]
            v[i] = v[ind]
            v[ind] = temp
        end
    end
    return v
end

This is much slower but at least it doesn't allocate. EDIT: Copied correct in-place algorithm from StackOverflow.
3. Define permute!(dest, src, p) = @views dest .= src[p], which is faster and doesn't allocate.

I'm happy to do a PR for any of the alternatives if there's agreement. Not also that invpermute! suffers from similar problems.

[mbauman]

Sure, it seems useful to optimize this. It's currently a very naive one-liner, with some of your suggestions already documented.

julia/base/combinatorics.jl

Line 215 in 3ed13ea

permute!(v, p::AbstractVector) = (v .= v[p])

[araujoms]

A little searching reveals that permute! and invpermute! used to be defined in terms of the in-place functions permute!! and invpermute!!, until #44941 introduced the current implementation because it was faster. There @stevengj also pointed out that it made these functions pointless.

If there is some poor soul using those functions they'll benefit from a deprecation warning.

[mbauman]

Ah, yeah, I see that @LilithHafner considered deprecating it there and discussed it with triage, but found far too many uses for such a prominently documented function to go away.

Seems a good 2.0 candidate, though.

I do agree that it's unfortunate that the faster allocating alternative is so easy to write, while the actual in-place version has a (definitionally) worse computational complexity but skips allocations and is harder to write.

[araujoms]

Deprecation is not breaking, it can be done any time. Actual removal can wait for a century for all I care, I just don't want users to fall into this trap.

I do agree that alternative 2 is bad, that's why I'm proposing permute!(dest, src, p) = @views dest .= src[p], which is not only fast and non-allocating, but also trivial to write.

[LilithHafner]

Feel free to make a PR adding @views and share the benchmarks.

[stevengj]

Deprecation is not breaking, it can be done any time.

Really? It degrades existing code by adding a deprecation warning.

[araujoms]

julia> using Random, BenchmarkTools

julia> function goodpermute!(c, v, p)
           for i in eachindex(p)
               c[i] = v[p[i]]
           end
           return c
       end
goodpermute! (generic function with 1 method)

julia> function benchmark(n)
           Random.seed!(1)
           p = randperm(n)
           v = randn(n)
           c = similar(v)
           @btime permute!($v, $p)
           @btime goodpermute!($c, $v, $p)    
           return nothing
       end
benchmark (generic function with 1 method)

julia> benchmark(10)
  20.230 ns (2 allocations: 144 bytes)
  6.422 ns (0 allocations: 0 bytes)

julia> benchmark(100)
  60.655 ns (2 allocations: 928 bytes)
  37.831 ns (0 allocations: 0 bytes)

julia> benchmark(1000)
  643.357 ns (3 allocations: 7.88 KiB)
  385.386 ns (0 allocations: 0 bytes)

[LilithHafner]

permute! throws if p contains out of bounds elements whereas goodpermute! is UB in that case.

[araujoms]

Fair enough, I've edited the benchmarks.

[mbauman]

It also doesn't solve the problem of the 2-arg "trap"... and (with bounds checking) it's also roughly the same as the documented and straightforward c .= @view v[p]. Broadcasting will even get v .= @view v[p] right with the exact same defensive copy. We don't define or export the non-bang permute — that's just getindex, too.

If we want to get rid of permute! in any case, I'd say let's not expand its surface area.

It's wild just how hard an in-place permutation is. I don't think there exists a (edit:) non-quadratic 0-allocation algorithm, in fact. Your naive version in the OP is not correct.

Here's the most recent work I can find in the literature with a quick scan. It's a surprisingly hard problem — so hard, in fact, that "strictly in-place" (edit: for non-quadratic algorithms) is defined to still use $O(\log{} n)$ extra storage... and it looks like that's been proven to be optimal!

Dudek, Bartłomiej, Paweł Gawrychowski, and Karol Pokorski. "Strictly in-place algorithms for permuting and inverting permutations." Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings 17. Springer International Publishing, 2021. https://arxiv.org/pdf/2101.03978

[adienes]

I believe there do exist 0-allocation algorithms, but they are Θ(n^2) ...

[araujoms]

Shit, you're right, the thing I wrote only works for a single cycle. Sorry about that.

The only thing I care about is getting rid of the trap. I think including goodpermute! would be the least painful way of doing it. With it one could simply do @deprecate permute!(v, p) permute!(v, copy(v), p). Otherwise there will be no place to document c .= @view v[p] or whatever implementation of goodpermute! you prefer, and the users will have to come up with it themselves.