# Fastest way to permute Array, given some permutation
**URL:** https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687
**Category:** Performance
**Tags:** sortperm, arrays
**Created:** [November 6, 2020, 3:42pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687 "2020-11-06T15:42:14Z")
**Posts on this page:** 14
**Page:** 1
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 6, 2020, 3:42pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/1 "2020-11-06T15:42:14Z")
I wonder what the fastest way is to apply a permutation to an array. Three approaches that I checked are:
```julia
julia> A = rand(10000);
julia> permutation = sortperm(A);
julia> @btime $A[$permutation];
11.700 μs (3 allocations: 78.22 KiB)
julia> @btime $A .= $A[$permutation];
13.200 μs (3 allocations: 78.22 KiB)
julia> @btime permute!($A,$permutation);
42.000 μs (2 allocations: 78.20 KiB)
```
None of these methods seem to be inplace (for the first one it is not surprising), I did however not expect the first approach to be the fastest. Any ideas what is causing this?
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [November 6, 2020, 3:54pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/2 "2020-11-06T15:54:10Z")
> [@DavidBerghaus](#):
>
> None of these methods seem to be inplace
The `permute!` function acts in-place in `A`, but requires the allocation of an auxiliary index array. You can do it fully in-place with the undocumented `Base.permute!!` function, which _also_ overwrites the `permutation` array (so that you can only call it once).
```julia
@btime Base.permute!!($A,p) setup=(p = copy($permutation)) evals=1;
```
However, it only saves about 15% on my machine.
> [@DavidBerghaus](#):
>
> I did however not expect the first approach to be the fastest. Any ideas what is causing this?
The basic issue here, I think, is that permuting an array in-place is generally a tricky problem, involving chasing the cycles of the permutation, that takes a bunch of bookkeeping and has poor memory-access patterns for cache-line utilization. Simply making an out-of-place copy via `A[permutation]` is much more straightforward (and involves more consecutive memory access) and hence faster.
---
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 6, 2020, 3:58pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/3 "2020-11-06T15:58:21Z")
Okay thank you, then I will not feel too bad for allocating this extra memory 😀
---
### Author:  [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)
#### Post date: [November 8, 2020, 1:33pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/4 "2020-11-08T13:33:32Z")
Note that you gain another 20% by doing
```julia
julia> @btime @inbounds $A[$permutation];
9.356 μs (2 allocations: 78.20 KiB)
```
---
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 8, 2020, 9:05pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/5 "2020-11-08T21:05:39Z")
Good point, that’s true!
---
### Author:  [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)
#### Post date: [November 8, 2020, 9:59pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/6 "2020-11-08T21:59:51Z")
Note that over-optimizing permutations may cause damage to your sanity, I know because I had to do it for maximum efficiency to replicate a literature heuristic.
The optimized heuristic code is [here](https://github.com/henriquebecker91/GuillotineModels.jl/blob/master/src/ppg2kp/Heuristic.jl#L280--L373). Basically, for each `Vector` that needs to be permuted frequently, I allocate a copy a single time, and then in the literal million iterations following, I copy-permute the original vector to the copy, and then swap who is the copy and who is the original in the loop scope.
I also had to gut the `sort` internals, it was not pretty. But I got rid of any allocations and my final code was six times faster. I just had to keep the old code to be able to check if the results were the same, or I introduced any bugs.
---
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 9, 2020, 2:08pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/7 "2020-11-09T14:08:42Z")
This indeed looks a bit tedious 😃
But for a 6x speed-up it might be worth it ^^
---
### Author:  [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)
#### Post date: [November 9, 2020, 3:38pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/8 "2020-11-09T15:38:42Z")
It become so much faster only because the code stopped allocating anything this way, and it is a code that literally runs at least one million iterations before stopping, so even one allocation inside the loop caused considerable slowdown, as the rest of the loop is just permutation of small vectors.
---
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 9, 2020, 4:50pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/9 "2020-11-09T16:50:34Z")
Yes, fortunately for me, this permutation line is only called a few times, so I don’t have to optimize too much. The reason for creating this thread was more out of curiosity and because I was suprised that `Base.permute!` is slower 🙂
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [November 9, 2020, 5:04pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/10 "2020-11-09T17:04:03Z")
> [@DavidBerghaus](#):
>
> ```julia
> julia> @btime $A[$permutation];
> 11.700 μs (3 allocations: 78.22 KiB)
>
> ```
Note that you can do this in-place on preallocated output using `B .= getindex.(Ref(A), permutation)`. For example:
```julia
julia> @btime $A[$permutation];
18.972 μs (2 allocations: 78.20 KiB)
julia> B = similar(A);
julia> @btime $B .= getindex.(Ref($A), $permutation);
7.601 μs (0 allocations: 0 bytes)
```
It’s a good thought exercise to make sure you understand why `A .= getindex.(Ref(A), permutation)` would **not** work (it executes, but produces the wrong `A` in general).
---
### Author:  [@DavidBerghaus](https://discourse.julialang.org/u/DavidBerghaus)
#### Post date: [November 9, 2020, 5:58pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/11 "2020-11-09T17:58:10Z")
> [@stevengj](#):
>
> It’s a good thought exercise to make sure you understand why `A .= getindex.(Ref(A), permutation)` would **not** work (it executes, but produces the wrong `A` in general).
Yes indeed, I originally thought that this is what
> [@DavidBerghaus](#):
>
> `$A .= $A[$permutation];`
would be doing (similar to `x, y = y, x`) until I realized that this line just creates a permuted copy of A and then replaces the array element-by element (which in hindsight seems obvious).
Also interesting that
> [@stevengj](#):
>
> `@btime $B .= getindex.(Ref($A), $permutation);`
does not seem to benefit from `@inbounds` 🙂
---
### Author:  [@orenbenkiki](https://discourse.julialang.org/u/orenbenkiki)
#### Post date: [September 12, 2021, 8:46am UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/12 "2021-09-12T08:46:24Z")
Would have been nice if `permute!` took an optional additional array to use instead of always allocating it (or overwriting the original in the case of `permute!!`). I’ve a case where I repeatedly permute not-too-long arrays and this de/allocation each time can be a performance issue. Is this something that might be considered as a feature for the `permute!` function?
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [September 12, 2021, 12:54pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/13 "2021-09-12T12:54:47Z")
> [@orenbenkiki](#):
>
> Would have been nice if `permute!` took an optional additional array to use instead of always allocating it (or overwriting the original in the case of `permute!!` ).
You could pass `copyto!(pcopy, p)` to `permute!!` if you want to preserve the original permutation array while using a preallocated buffer.
---
### Author:  [@orenbenkiki](https://discourse.julialang.org/u/orenbenkiki)
#### Post date: [September 12, 2021, 1:06pm UTC](https://discourse.julialang.org/t/fastest-way-to-permute-array-given-some-permutation/49687/14 "2021-09-12T13:06:19Z")
@stevengj - right, I should have though of that. This way I’d be able to apply the permutation as many times as I want w/o any allocations. Thanks!