# Combinatorics.permutations creating a lot of allocations

**URL:** <https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665>\
**Category:** Performance\
**Tags:** question\
**Created:** [July 12, 2025, 1:09pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665 "2025-07-12T13:09:52Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![jonbir](https://avatars.discourse-cdn.com/v4/letter/j/ec9cab/32.png) [@jonbir](https://discourse.julialang.org/u/jonbir)\
**Post date:** [July 12, 2025, 1:09pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/1 "2025-07-12T13:09:52Z")

</div>

This is my first post here, so I hope I can explain the problem I’ve come across as I’m writing code for my master thesis in Maths. Compared to others here I’m definitely no expert, but I trusted code from Packages to give good performance, so I’m not sure what I do wrong here or if there is in fact badly performing code in `Combinatorics.permutations`  
I want to **iterate over all permutations** that keep a small vector `v` (length \< 6) constant so if `v = [2,1,1,1]` it would be any permutation of only the last three entries. This function is called many times (for the same vector `v`) within another loop, so allocations are the most important thing for me.  
This is a straight forward `testperm1()` equivalent to my first implementation and an dumber `testperm2()` that somehow performs better

```julia
using Combinatorics
using LinearAlgebra
using BenchmarkTools

v = [2,1,1,1];
vPerm = similar(v);
n = length(v);
permArray = collect(permutations(1:n));
permMat = zeros(Int, n, n);

function testPerm1(v, n, vPerm, permMat)
    for perm in permutations(1:n)
        updatePermMatFromPermVec!(permMat, perm)
        mul!(vPerm, permMat, v)
        if vPerm == v
        end
    end
end

function testPerm2(v, n, vPerm, permArray, permMat)
    for i in 1:factorial(n)
        updatePermMatFromPermVec!(permMat, permArray[i])
        mul!(vPerm, permMat, v)
        if vPerm == v
        end
    end
end

function updatePermMatFromPermVec!(permMat, permVec)
    for j in eachindex(permVec)
        for i in eachindex(permVec)
            if permVec[i] == j
                permMat[i,j] = 1;
            end
        end
    end
end

```

Again I’m not really asking for other optimizations, `updatePermMatFromPermVec!` might be far from optimal, my concern is that the allocations are

```julia
@btime testPerm1(v, n, vPerm, permMat)
  3.450 μs (98 allocations: 4.59 KiB)

```

while

```julia
@btime testPerm2(v, n, vPerm, permArray, permMat)
  1.350 μs (0 allocations: 0 bytes)

```

and I only have to allocate `permArray` once on top before hand, which gives me `1.978 μs (102 allocations: 4.91 KiB)`, so only looping over `testperm1` a second time makes it a lot worse than collecting the whole array.  
It seems to allocate every `perm` that is iterated over, I thought using the iterator should be a lot better for performance.  
I read about `@inline` in another topic (I got an message saying I can’t link to it in my post), but I don’t really understand if that is also the problem here or what I can do to improve the code.  
Is some dumb mistake of mine the problem or does `Combinatorics` really have some bad code?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 12, 2025, 1:47pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/2 "2025-07-12T13:47:41Z")

</div>

> <https://github.com/JuliaMath/Combinatorics.jl/pull/186>
>
> \## Code changes
> 
> As noted in #151, \`multiset\_permutations\` is much faster than… \`permutations\`, so we can exploit it to optimize the latter (this was suggested in a comment \[here\](https://github.com/JuliaMath/Combinatorics.jl/issues/151#issuecomment-2853774222)).
> 
> The code does the equivalent of
> 
> \`\`\`julia
> permutations(a, t::Integer=length(a)) =
> Iterators.map(
> indices -\> \[a\[i\] for i in indices\],
> multiset\_permutations(eachindex(a), t))
> \`\`\`
> 
> but we construct the iterator manually so that we can define \`eltype\` or it (otherwise, with \`Iterators.map\`, type inference would deduce \`Any\`).
> 
> This closes #151; it possibly closes #185 too.
> 
> \## Simple benchmark
> 
> \<details\>\<summary\>Benchmark code\</summary\>
> 
> \`\`\`julia
> using BenchmarkTools
> using Combinatorics
> 
> count\_permutations(a) = count(Returns(true), permutations(a))
> count\_permutations(a, t) = count(Returns(true), permutations(a, t))
> 
> \# compile
> count\_permutations(1:3)
> for t in 0:3
> count\_permutations(1:3, t)
> end
> 
> for n in \[3, 5, 7, 8, 9\]
> println("\\nn = $(n)\\n")
> a = collect(1:n)
> display(@benchmark count\_permutations($a))
> end
> 
> println("\\nn = 10, t = 6\\n")
> display(@benchmark count\_permutations(1:10, 6))
> \`\`\`
> \</details\>
> 
> \<details\>\<summary\>Before\</summary\>
> 
> \`\`\`
> n = 3
> 
> BenchmarkTools.Trial: 10000 samples with 20 evaluations per sample.
> Range (min … max): 977.800 ns … 108.978 μs ┊ GC (min … max): 0.00% … 97.93%
> Time (median): 1.003 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 1.160 μs ± 1.842 μs ┊ GC (mean ± σ): 2.62% ± 1.68%
> 
> █▇▃▅▃ ▃▁ ▁
> █████▆▃▆▆▆▆▅▇▆▆▆▅▃▅▅▃▃▅▄▅▄▄▃▃▅▅▆▅▆▆▇▆▇▆▆██▇▇▇▇▇▆▇▇▆▆▇▄▅▆▅▅▄▅▆ █
> 978 ns Histogram: log(frequency) by time 2.47 μs \<
> 
> Memory estimate: 624 bytes, allocs estimate: 16.
> 
> n = 5
> 
> BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
> Range (min … max): 109.018 μs … 2.817 ms ┊ GC (min … max): 0.00% … 94.72%
> Time (median): 118.300 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 121.273 μs ± 36.502 μs ┊ GC (mean ± σ): 0.40% ± 1.33%
> 
> █ ▂
> ▁▁▇▅▂█▅▃█▅▃▇▆▃▃▄▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
> 109 μs Histogram: frequency by time 173 μs \<
> 
> Memory estimate: 11.41 KiB, allocs estimate: 244.
> 
> n = 7
> 
> BenchmarkTools.Trial: 155 samples with 1 evaluation per sample.
> Range (min … max): 27.639 ms … 41.011 ms ┊ GC (min … max): 0.00% … 0.00%
> Time (median): 31.259 ms ┊ GC (median): 0.00%
> Time (mean ± σ): 32.352 ms ± 3.509 ms ┊ GC (mean ± σ): 0.06% ± 0.47%
> 
> ▃▆▆▁ ██▆▆▁▃ ▁ ▁ ▁ ▃ ▁ ▁ ▁ ▁
> ▄▄▇████▇██████▇█▇█▇█▆▄▁▇█▄█▆▆█▇▆▁▆▁▁▇▇▄▄▄▁█▄▄▄▄▆▁▁█▆▄▁▁▄▁▇▄ ▄
> 27.6 ms Histogram: frequency by time 40.7 ms \<
> 
> Memory estimate: 551.42 KiB, allocs estimate: 10084.
> 
> n = 8
> 
> BenchmarkTools.Trial: 9 samples with 1 evaluation per sample.
> Range (min … max): 591.173 ms … 673.411 ms ┊ GC (min … max): 0.00% … 0.00%
> Time (median): 604.497 ms ┊ GC (median): 0.00%
> Time (mean ± σ): 609.657 ms ± 24.487 ms ┊ GC (mean ± σ): 0.03% ± 0.08%
> 
> █ ██ █ ████ █
> █▁▁▁██▁█▁████▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
> 591 ms Histogram: frequency by time 673 ms \<
> 
> Memory estimate: 4.92 MiB, allocs estimate: 80644.
> 
> n = 9
> 
> BenchmarkTools.Trial: 1 sample with 1 evaluation per sample.
> Single result which took 14.473 s (0.01% GC) to evaluate,
> with a memory estimate of 44.30 MiB, over 725764 allocations.
> 
> n = 10, t = 6
> 
> BenchmarkTools.Trial: 121 samples with 1 evaluation per sample.
> Range (min … max): 39.323 ms … 45.142 ms ┊ GC (min … max): 0.00% … 0.00%
> Time (median): 41.299 ms ┊ GC (median): 3.36%
> Time (mean ± σ): 41.409 ms ± 1.035 ms ┊ GC (mean ± σ): 2.86% ± 1.18%
> 
> █ ▄
> ▄▃▃▁▁▁▁▆▆▆▆▅▄▇▄▇▄▆█▅▆▇▆▄▄▆█▄▆▅▄▄▇▃▃▇▁▃▁▃▃▁▁▁▁▁▁▃▃▁▁▁▁▁▁▁▁▁▃ ▃
> 39.3 ms Histogram: frequency by time 45 ms \<
> 
> Memory estimate: 16.15 MiB, allocs estimate: 302403.
> \`\`\`
> \</details\>
> 
> \<details\>\<summary\>After\</summary\>
> 
> \`\`\`
> n = 3
> 
> BenchmarkTools.Trial: 10000 samples with 10 evaluations per sample.
> Range (min … max): 1.071 μs … 217.489 μs ┊ GC (min … max): 0.00% … 97.94%
> Time (median): 1.126 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 1.271 μs ± 4.475 μs ┊ GC (mean ± σ): 9.03% ± 2.59%
> 
> █▆
> ▂▇███▄▃▂▂▂▂▂▂▂▂▂▁▁▁▂▂▂▂▂▂▂▂▂▂▂▁▂▁▂▂▂▂▂▁▂▂▂▂▂▂▂▁▁▁▂▂▂▂▂▂▂▁▂▂ ▂
> 1.07 μs Histogram: frequency by time 2.13 μs \<
> 
> Memory estimate: 2.56 KiB, allocs estimate: 63.
> 
> n = 5
> 
> BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
> Range (min … max): 11.350 μs … 2.772 ms ┊ GC (min … max): 0.00% … 98.82%
> Time (median): 12.043 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 13.577 μs ± 56.440 μs ┊ GC (mean ± σ): 9.17% ± 2.21%
> 
> █▇
> ▃███▆▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▂▁▁▁▁▁▂▂▂▂▂▂▂▂▂▂▂▂ ▂
> 11.4 μs Histogram: frequency by time 25 μs \<
> 
> Memory estimate: 35.22 KiB, allocs estimate: 755.
> 
> n = 7
> 
> BenchmarkTools.Trial: 8577 samples with 1 evaluation per sample.
> Range (min … max): 461.444 μs … 3.088 ms ┊ GC (min … max): 0.00% … 73.05%
> Time (median): 480.591 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 580.974 μs ± 262.912 μs ┊ GC (mean ± σ): 15.87% ± 19.68%
> 
> ██▅▄▃▂ ▂▃▃▃▂▁▁▁ ▂
> ███████▇▇▇▆▆▆▆▄▄▃▅▅▁▄▁▁▁▃▄▄▄▄▁▁▃▄▄▁▄▃▁▁▄▁▁▃▁▁▃▁▁█████████▇▇▆▆ █
> 461 μs Histogram: log(frequency) by time 1.38 ms \<
> 
> Memory estimate: 1.62 MiB, allocs estimate: 30283.
> 
> n = 8
> 
> BenchmarkTools.Trial: 1046 samples with 1 evaluation per sample.
> Range (min … max): 3.837 ms … 10.550 ms ┊ GC (min … max): 0.00% … 17.33%
> Time (median): 4.818 ms ┊ GC (median): 19.09%
> Time (mean ± σ): 4.778 ms ± 488.635 μs ┊ GC (mean ± σ): 16.78% ± 7.33%
> 
> ▃▄▁▂▂ ▄█▇▅▅▆▅▄▂▁▁
> █████▇█▇▄▅▄▅▄▅▄▄▅▁▄▁▄▁▄▁▁▁▁████████████▇█▇▇▆▇▇▅▆▆▇▆▄▆▆▆▆▅▆▅ █
> 3.84 ms Histogram: log(frequency) by time 5.79 ms \<
> 
> Memory estimate: 14.77 MiB, allocs estimate: 241967.
> 
> n = 9
> 
> BenchmarkTools.Trial: 114 samples with 1 evaluation per sample.
> Range (min … max): 41.082 ms … 47.521 ms ┊ GC (min … max): 8.59% … 16.64%
> Time (median): 43.978 ms ┊ GC (median): 16.26%
> Time (mean ± σ): 44.119 ms ± 926.061 μs ┊ GC (mean ± σ): 16.19% ± 1.33%
> 
> ▃▃ ▂ ▅▃▃█▅▃ ▅ ▆
> ▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▇▇██▇▇█▅██████▅▄█▄▅█▇▅▅▁▄▄▅█▁▁▁▁▄▁▁▁▄▁▁▁▄▄ ▄
> 41.1 ms Histogram: frequency by time 47 ms \<
> 
> Memory estimate: 132.89 MiB, allocs estimate: 2177332.
> 
> n = 10, t = 6
> 
> BenchmarkTools.Trial: 308 samples with 1 evaluation per sample.
> Range (min … max): 13.125 ms … 19.379 ms ┊ GC (min … max): 0.00% … 17.51%
> Time (median): 16.235 ms ┊ GC (median): 18.53%
> Time (mean ± σ): 16.227 ms ± 654.551 μs ┊ GC (mean ± σ): 18.60% ± 2.95%
> 
> ▂██ ▂▂▂▂ ▅█▄▁▃▂▁ ▂ ▁
> ▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▃▃▆▅▅▇███▇████████████▅▆█▃▇█▃▃▁▁▃▁▃▃ ▄
> 13.1 ms Histogram: frequency by time 17.9 ms \<
> 
> Memory estimate: 53.07 MiB, allocs estimate: 907255.
> \`\`\`
> \</details\>

sounds like they need a new release

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [July 12, 2025, 2:47pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/3 "2025-07-12T14:47:03Z")

</div>

Hi, and welcome to the Julia community!

> [@jonbir](#):
>
> It seems to allocate every `perm` that is iterated over, I thought using the iterator should be a lot better for performance.

This is indeed why you get allocations (see \* below). A faster implementation of the iterator, like the one `jling` refers to, will have the same problem.

```julia
permutations_b(a, t::Integer=length(a)) =
    Iterators.map(
        indices -> [a[i] for i in indices],
        multiset_permutations(eachindex(a), t))

function testPerm1_b(v, n, vPerm, permMat)
    for perm in permutations_b(1:n)
        updatePermMatFromPermVec!(permMat, perm)
        mul!(vPerm, permMat, v)
        if vPerm == v
       end
    end
end

@btime testPerm1($v, $n, $vPerm, $permMat) # 9.400 μs (74 allocations: 3.09 KiB)
@btime testPerm1_b($v, $n, $vPerm, $permMat) # 3.513 μs (174 allocations: 8.06 KiB)
@btime testPerm2($v, $n, $vPerm, $permArray, $permMat) # 932.143 ns (0 allocations: 0 bytes)

```

In your `testPerm2` approach, you just move the allocations (of each permutation individually, and of the `Vector{Vector{Int}}` `permArray` storing these) outside of the benchmark.

* * *

There exists an inplace function to get the `n`-th permutation: `nthperm!`, but it consumes the input array. Nevertheless, if you keep resetting this input, you can use this function to avoid most allocations:

```julia
function testPerm3(v, n, vPerm, permMat)
    perm = similar(v)
    for i in 1:factorial(n)
        perm .= 1:n
        nthperm!(perm, i) # Now perm contains the i-th permutation of 1:n
        updatePermMatFromPermVec!(permMat, perm)
        mul!(vPerm, permMat, v)
        if vPerm == v
        end
    end
end

@btime testPerm3($v, $n, $vPerm, $permMat) # 1.510 μs (2 allocations: 96 bytes)

```

* * *

\*: Concretely, in the file permutations.jl we find

```julia
function Base.iterate(p::Permutations, state::Vector{Int}=fill(firstindex(p.data), p.length))
    next_permutation!(state, firstindex(p.data), lastindex(p.data))
    if first(state) > lastindex(p.data)
        return nothing
    end
    [p.data[i] for i in state], state
end

```

Here the `[p.data[i] for i in state]` causes the allocations. But in our case with `p.data == 1:n`, there is no difference between the permutation and the `state`, so you could use

```julia
function testPerm4(v, n, vPerm, permMat)
    perm = collect(1:n) # the first permutation of 1:n
    while first(perm) <= n
        updatePermMatFromPermVec!(permMat, perm)
        mul!(vPerm, permMat, v)
        if vPerm == v
        end
        Combinatorics.next_permutation!(perm, 1, n)
    end
end

@btime testPerm4($v, $n, $vPerm, $permMat) # 7.175 μs (2 allocations: 96 bytes)

```

which does indeed get rid of most allocations, though is also quite a lot slower than `testPerm3`, for some reason. Additionally, `testPerm4` relies on an unexported method, a practice which is safer to avoid.

---

<div class="post-metadata">

**Author:** ![jonbir](https://avatars.discourse-cdn.com/v4/letter/j/ec9cab/32.png) [@jonbir](https://discourse.julialang.org/u/jonbir)\
**Post date:** [July 12, 2025, 3:08pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/4 "2025-07-12T15:08:33Z")

</div>

Wow, thank you a lot for your reply.  
I understood that between my `testperm1` and `testperm2` I just shifted the allocations, but the function is called a lot of times (probably millions of times), and if its called multiple times its a lot better to collect the array once and then pass it as an argument (I still believe this is true).  
The 2 allocations in your `testPerm3` come from `perm = similar(v)` I suppose, I will preallocate this outside, but your function is perfect thank you!  
I didn’t really understand what an “unexported method” is and what’s your thought behind the fourth function but I will look this up, you really don’t need to explain it, you have already helped a lot.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [July 12, 2025, 8:31pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/5 "2025-07-12T20:31:35Z")

</div>

My packages SmallCollections.jl and SmallCombinatorics.jl (recently split off from SmallCollections.jl) may be helpful. With the code

```julia
using SmallCollections, SmallCombinatorics, Chairmarks

function testPerm3(v)
    s = 0
    for perm in SmallCombinatorics.permutations(length(v))
        if @inbounds v[perm] == v
            s += 1
        end
    end
    s
end

```

I get

```julia
julia> @b testPerm2($v, $n, $vPerm, $permArray, $permMat)
1.030 μs

julia> w = SmallVector{8,Int8}([2, 1, 1, 1]);

julia> @b testPerm3($w)
297.680 ns (2 allocs: 64 bytes)

```

(The two allocations shouldn’t be there. I have to investigate this.)

The branch `SmallCollections#shuffle` (soon to be merged into master) has fast vector indexing for `SmallVector` for Intel/AMD processors. With this branch I get

```julia
julia> @b testPerm3($w)
79.720 ns

```

---

<div class="post-metadata">

**Author:** ![jonbir](https://avatars.discourse-cdn.com/v4/letter/j/ec9cab/32.png) [@jonbir](https://discourse.julialang.org/u/jonbir)\
**Post date:** [July 14, 2025, 7:02pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/6 "2025-07-14T19:02:05Z")

</div>

Thanks for your answer!  
I cleared the bottleneck with `testperm3` of @eldee’s implementation, but it is nonetheless very helpful to know that there is a better performing combinatorics package.  
The last remaining allocation problem in my code has to do with `Combinatorics.multiset_permutations`, as far as I could see you haven’t implemented an alternative for that, or did I miss that?  
I will create another topic for the remaining part (as I think that’s how topics should be separated in this forum, they are both part of the same program but are independent of each other).

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [July 14, 2025, 9:30pm UTC](https://discourse.julialang.org/t/combinatorics-permutations-creating-a-lot-of-allocations/130665/7 "2025-07-14T21:30:23Z")

</div>

> [@jonbir](#):
>
> you haven’t implemented an alternative for that

That’s correct. It’s still a young package …