JuliaMath / JuliaMath/Combinatorics.jl
Performance regression: in `iterate` method for `Permutations`.
- Dominant language
- Julia
- Stars
- 230
- Forks
- 62
- PR merge metrics
- No merged PRs in 30d
Description
A newer `iterate()` method was first defined for `Permutations` in PR #122 and then updated with PR #186 to work with `MultisetPermutations` under the hood. This appears to have increased the number of allocations by 50% when compared to the original method (which, in turn, also leads to slower evaluation).
Benchmarking
Benchmarking code
```julia
using BenchmarkTools
println("iterate")
display(@benchmark iterate(permutations(1:10)))
println()
println("collect")
display(@benchmark collect(permutations(1:10)))
```
With current `iterate()` method (v1.1.0)
```julia
iterate
BenchmarkTools.Trial: 10000 samples with 18 evaluations per sample.
Range (min … max): 893.333 ns … 2.623 ms ┊ GC (min … max): 0.00% … 99.69%
Time (median): 1.667 μs ┊ GC (median): 0.00%
Time (mean ± σ): 2.023 μs ± 26.215 μs ┊ GC (mean ± σ): 12.93% ± 1.00%
▂▄▄ ▁▄▇█▇▄▄▄▄▃▃▁
▂▅████▅▄▃▄▅████████████▅▅▄▃▂▃▃▂▃▃▃▃▃▄▃▄▃▃▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁ ▃
893 ns Histogram: frequency by time 3.79 μs <
Memory estimate: 2.47 KiB, allocs estimate: 42.
collect
BenchmarkTools.Trial: 4 samples with 1 evaluation per sample.
Range (min … max): 977.102 ms … 1.601 s ┊ GC (min … max): 24.63% … 56.08%
Time (median): 1.362 s ┊ GC (median): 48.62%
Time (mean ± σ): 1.326 s ± 300.633 ms ┊ GC (mean ± σ): 46.45% ± 13.85%
█ █ █ █
█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁█ ▁
977 ms Histogram: frequency by time 1.6 s <
Memory estimate: 1.49 GiB, allocs estimate: 21772839.
```
With previous `iterate()` method (
I suspect the problem lies in `MultisetPermutations` needing a work-around to deal with `Permutations`. This work-around requires the output for `permutations()` to effectively be written twice, once as an array of indices in `nextpermutation()`, and then again when this index array is mapped to the output array in `iterate()`. This appears to be easily fixed by reverting to the `Permutations` specific `iterate()` method which did not use an array of indices. In fact, it's effectively the same `iterate()` method that is currently being used for `MultisetPermutations`, only using a different state.
iterate methods
Current `iterate()` method:
```julia
function Base.iterate(p::Permutations110, state=nothing)
if state === nothing
mp = multiset_permutations110(collect(eachindex(p.data)), p.length)
it = iterate(mp)
if it === nothing return nothing end
else
mp, mp_state = state
it = iterate(mp, mp_state)
if it === nothing return nothing end
end
indices, mp_state = it
return [p.data[i] for i in indices], (mp=mp, mp_state=mp_state)
end
```
Possible reversion:
```julia
function Base.iterate(p::Permutations, state = collect(eachindex(p.data)))
(!isempty(state) && max(state[1], p.length) > length(p.data) || (isempty(state) && p.length > 0)) && return
nextpermutation(p.data, p.length , state)
end
```
Current `iterate` method for `MultisetPermutations` for comparison:
```julia
function Base.iterate(p::MultiSetPermutations, s=p.ref)
(!isempty(s) && max(s[1], p.t) > length(p.ref) || (isempty(s) && p.t > 0)) && return
nextpermutation(p.m, p.t, s)
end
```
I believe all other parts of `permutations.jl` could remain as they are. However, there is one other potential inefficiency which I saw in `multiset_permutations(a, t)` which appears to be O($n^2$), but could be made linear with use of a counter.
multiset_permutations(a, t)
Current:
```julia
function multiset_permutations(a, t::Integer)
m = unique(a)
f = [sum(c == x for c in a)::Int for x in m]
multiset_permutations110(m, f, t)
end
```
Linear implementation:
```julia
function multiset_permutations(a, t::Integer)
counts, m = Dict{eltype(a), Int}(), eltype(a)[]
for i in eachindex(a)
n = get(counts, a[i], 0) + 1
counts[a[i]] = n
isone(n) && push!(m, a[i])
end
f = [counts[key] for key in m]
multiset_permutations(m, f, t)
end
```
Edit: changed to use indexing instead of iteration of `a`.
I've also done some testing for correctness with both of the proposed changes, and they have been giving the same output as `v1.1.0`. Testing has included:
- All `permutations(a, t)` with `a ∈ 1:10` and `t ∈ 1:a`
- Dozens of runs of `multiset_permutations(a)` with `a = rand(1:10, 8)`
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.