# Fast permutation vector: code needed
**URL:** https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357
**Category:** Performance
**Tags:** sorting
**Created:** [March 20, 2023, 5:53pm UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357 "2023-03-20T17:53:36Z")
**Posts on this page:** 19
**Page:** 2
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:14am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/22 "2023-03-21T02:14:55Z")
Sorry, I don’t follow: there are no allocations in 1.8.5 for `@btime begin $p .= 1:length($v); end`.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:16am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/23 "2023-03-21T02:16:15Z")
Yeah, and there shouldn’t be. `p .= 1:length(v)` calls for no allocation. Why 1.9 seems to do it, is a mystery. But test 1.9 with the `for` loop initialization.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:17am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/24 "2023-03-21T02:17:05Z")
And there are none in 1.9.0-rc1 either .
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:17am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/25 "2023-03-21T02:17:55Z")
> [@PetrKryslUCSD](#):
>
> with 1.9.0-rc1
>
> ```julia
> 4.945 ms (2 allocations: 781.30 KiB)
> 4.924 ms (2 allocations: 781.30 KiB)
>
> ```
These are allocations of the whole vector in 1.9
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:22am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/26 "2023-03-21T02:22:33Z")
Well, I did:
```julia
julia> module mt001
using BenchmarkTools
const v = rand(100_000);
const p = zeros(Int, 100_000);
@btime sortperm!($p, $v);
# @show p
@btime begin $p .= 1:length($v); sort!($p, Base.Sort.DEFAULT_UNSTABLE, Base.Order.Perm(Base.Order.Forward, $v)); end
@btime begin $p .= 1:length($v); end
nothing
end
WARNING: replacing module mt001.
4.625 ms (2 allocations: 781.30 KiB)
4.658 ms (2 allocations: 781.30 KiB)
16.100 μs (0 allocations: 0 bytes)
Main.mt001
```
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:28am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/27 "2023-03-21T02:28:50Z")
Something is allocating the whole vector. Maybe `sort!`. But it shouldn’t.
I think I’ll need to install 1.9 already. But first I’ll look at source on github for 1.9rc1
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:33am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/28 "2023-03-21T02:33:50Z")
Yup, not just once, but twice…
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:36am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/29 "2023-03-21T02:36:07Z")
Looking at 1.9rc1, the sorting functions are changed. Try to add another named parameter `scratch` which is a preallocated area of equal size to array i.e.:
```julia
const s = similar(p)
....
sort!(.... ; scratch=s)
```
and benchmark with this setup. I have a feeling it would be a new top speed. Same parameter should apply to `sortperm!` (which is preferable).
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:54am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/30 "2023-03-21T02:54:09Z")
Good thinking!
```julia
julia> module mt001
using BenchmarkTools
const v = rand(100_000);
const p = zeros(Int, 100_000);
const s = similar(p)
@btime sortperm!($p, $v; scratch=$s);
# @show p
@btime begin $p .= 1:length($v); sort!($p, Base.Sort.DEFAULT_UNSTABLE, Base.Order.Perm(Base.Order.Forward, $v)); end
@btime begin $p .= 1:length($v); end
nothing
end
WARNING: replacing module mt001.
4.555 ms (0 allocations: 0 bytes)
4.645 ms (2 allocations: 781.30 KiB)
16.000 μs (0 allocations: 0 bytes)
Main.mt001
```
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:56am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/31 "2023-03-21T02:56:09Z")
Great. `sortperm!` should be the one to use. But you can also add the `scratch` parameter to `sort!` benchmark, and it should take care of allocations too.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 2:56am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/32 "2023-03-21T02:56:32Z")
No, apparently it doesn’t go into `sort!`…
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 2:58am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/33 "2023-03-21T02:58:17Z")
Yes it is a parameter of `sort!` (forget nonsense about being positional, hard to read semicolons):
```julia
function sort!(v::AbstractVector{T};
alg::Algorithm=defalg(v),
lt=isless,
by=identity,
rev::Union{Bool,Nothing}=nothing,
order::Ordering=Forward,
scratch::Union{Vector{T}, Nothing}=nothing) where T
```
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 3:03am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/34 "2023-03-21T03:03:52Z")
I think mine is a different `sort!`.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 3:10am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/35 "2023-03-21T03:10:01Z")
Yeah, there is a bit of a mess in the function signatures. `sortperm!` should be the go-to function for this task. But try to add another positional parameter of a named-tuple as follows:
```julia
sort!($p,
Base.Sort.DEFAULT_UNSTABLE,
Base.Order.Perm(Base.Order.Forward, $v), (;scratch=s)
```
---
### Author:  [@uniment](https://discourse.julialang.org/u/uniment)
#### Post date: [March 21, 2023, 3:30am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/36 "2023-03-21T03:30:31Z")
> [@Dan](#):
>
> `for i in 1:length(v) p[i]=i end`
At risk of being annoying, a point of style:
If you wrap `p[i]=i` in parentheses you’ll get a syntax error. Similar weirdness happens if the statement body is a symbol, `:` quoted expression, or array. Example:
```julia
julia> if true [1:5;] end
ERROR: syntax: space before "[" not allowed in "true [" at REPL[1]:1
```
I’ve adopted a style of adding a semicolon `;` after the condition for one-liner `if`, `while`, and `for` statements to avoid syntax surprises.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 21, 2023, 3:36am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/37 "2023-03-21T03:36:30Z")
> [@uniment](#):
>
> At risk of being annoying, a point of style:
> [@uniment](#):
>
> I’ve adopted a style of adding a semicolon `;`
Thanks. Not annoying at all. The semicolon `;` is something I looked for, because the statement interacted badly with `@btime`.
```julia
julia> @btime for i in 1:length($v); $p[i]=i end
```
is what was required.
---
### Author:  [@uniment](https://discourse.julialang.org/u/uniment)
#### Post date: [March 21, 2023, 3:44am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/38 "2023-03-21T03:44:42Z")
> [@Dan](#):
>
> `@btime for i in 1:length($v); $p[i]=i end`
Ah, that’s a new one for me—interaction with `@btime` interpolation! The error is quite unintuitive 😅
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [March 21, 2023, 11:01am UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/39 "2023-03-21T11:01:38Z")
> [@PetrKryslUCSD](#):
>
> it appears to allocate a few arrays?
that’s also the consequence of radixsort which requires double the memory. for less allocation, you can try to implement the ideas in `sorttwo!` but using something like quicksort but i bet it will be slower since that’s `O(nlog(n))` algorithm but radixsort is `O(n)`
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 21, 2023, 5:58pm UTC](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357/40 "2023-03-21T17:58:57Z")
And for my application the winners are:
```julia
sort!(prm; alg=Base.Sort.QuickSort, order=Base.Order.Perm(Base.Order.Forward, rows), scratch=scratcha);
```
on 1.9.0-rc1, and
```julia
sort!(prm, Base.Sort.QuickSort, Base.Order.Perm(Base.Order.Forward, rows))
```
on 1.8.5. (This version is marginally faster than 1.9.0-rc1.)
`sortperm!(prm, rows; scratch=scratcha)` was noticeably slower on 1.9.0-rc1 than the
code fragment above.
[Previous page](https://discourse.julialang.org/t/fast-permutation-vector-code-needed/96357.md?page=1)