# Allocations when iterating Combinatorics.Combinations

**URL:** <https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389>\
**Category:** General Usage\
**Created:** [December 10, 2023, 10:41pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389 "2023-12-10T22:41:15Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 10, 2023, 10:41pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/1 "2023-12-10T22:41:15Z")

</div>

I can’t see why/where allocations are occurring when iterating a `Combinatorics.Combinations` object.

Here’s the relevant code extract from the `Combinatorics` package:

```julia
#The Combinations iterator
struct Combinations
    n::Int
    t::Int
end

function Base.iterate(c::Combinations, s = [min(c.t - 1, i) for i in 1:c.t])
    if c.t == 0 # special case to generate 1 result for t==0
        isempty(s) && return (s, [1])
        return
    end
    for i in c.t:-1:1
        s[i] += 1
        if s[i] > (c.n - (c.t - i))
            continue
        end
        for j in i+1:c.t
            s[j] = s[j-1] + 1
        end
        break
    end
    s[1] > c.n - c.t + 1 && return
    (s, s)
end

```

And here’s the allocations:

```julia
using Combinatorics

function test1(combs)
    x = 0
    for c in combs
        x += 1
    end
    x
end

@time test1(Combinatorics.Combinations(30, 12))
  4.099971 seconds (86.49 M allocations: 2.578 GiB, 12.73% gc time)

```

I’ve tried a few variations to eliminate the allocations, but really just stabbing in the dark because I don’t know the reason for the allocations.

This version seems to run allocation-free:

```julia
using Combinatorics

function myiterate(c::Combinatorics.Combinations, state = Int[min(c.t - 1, i) for i in 1:c.t])
    item = myiterate!(state, c.n, c.t)

    if item === nothing
        return nothing
    else
        return (item, state)
    end
end

function myiterate!(s::Vector{Int}, n::Int, t::Int)
    # item is return value, state is s

    if t == 0 # special case to generate 1 result for t==0
    	if isempty(s)
    		push!(s, 1)
    		return Int[]
    	end
		return nothing
    end

    for i in t:-1:1
    	s[i] += 1
        s[i] > (n - t + i) && continue
        for j in i+1:t
        	s[j] = s[j-1] + 1
        end
        break
    end

    s[1] > (n - t + 1) && return nothing
    return s
end

function test2(combs)
    x = 0
    next = myiterate(combs)
    while next !== nothing
    	item, state = next
        x += 1
        next = myiterate(combs, state)
    end
    x
end

@time test2(Combinatorics.Combinations(30, 12))
  1.747497 seconds (1 allocation: 160 bytes)

```

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [December 10, 2023, 10:52pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/2 "2023-12-10T22:52:08Z")

</div>

To identify the source of the allocations I would suggest using a profiler, if you’re using VSCode `@profview_allocs test1(Combinatorics.Combinations(30, 12))` should work in the REPL. Alternatively, Alloccheck.jl may also work.

If your allocations are due to type instabilities, Cthulhu.jl and Jet.jl can be useful for identifying and debugging them.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 11, 2023, 5:25am UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/3 "2023-12-11T05:25:19Z")

</div>

If I’m using them correctly, `@code_warntype` and `JET.@report_opt` don’t show any type instabilities.

```julia
using Combinatorics, JET

c = Combinatorics.Combinations(30, 12) 
(item, state) = iterate(c)

@code_warntype iterate(c)
@code_warntype iterate(c, state)

@report_opt iterate(c)
@report_opt iterate(c, state)

```

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [December 11, 2023, 6:55am UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/4 "2023-12-11T06:55:28Z")

</div>

I would recommend profiling then.

Also it’s probably better to use Cthulhu and Jet on `test1` itself to make sure you didn’t miss anything (but profiling first will probably be quicker).

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 11, 2023, 9:26pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/5 "2023-12-11T21:26:00Z")

</div>

I’ve opened an issue at Combinatorics:

> <https://github.com/JuliaMath/Combinatorics.jl/issues/147>
>
> It seems iterating Combinations allocates. Am I measuring this correctly?
> Is th…ere a way to eliminate the allocations?
> 
> \`\`\`
> using Combinatorics
> 
> function test1(combs)
> x = 0
> for c in combs
> x += 1
> end
> x
> end
> 
> @time test1(Combinatorics.Combinations(30, 12))
> 4.099971 seconds (86.49 M allocations: 2.578 GiB, 12.73% gc time)
> \`\`\`

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [December 11, 2023, 10:10pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/6 "2023-12-11T22:10:27Z")

</div>

Using `@profview_allocs` suggests the problem is due to the `return (s, s)`. I imagine `s` which is a `Vector{Int}` is being copied.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 11, 2023, 10:32pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/7 "2023-12-11T22:32:20Z")

</div>

Yeah, I thought that too.

However, it doesn’t seem to be a “generic” issue with returning a 2-tuple of the same vector:

```julia
using BenchmarkTools

function myiterate(v)
	v[begin] == v[end] && return nothing
	v[begin] += 1
	return v, v
end

function test(v)
	count = 0
	next = myiterate(v)

	while next !== nothing
		item, state = next 
		count += 1
		next = myiterate(v)
	end

	return count
end

@time test([0, 7, 10_000_000])
  0.006705 seconds (1 allocation: 80 bytes)

```

Any ideas on how to eliminate the allocations?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [December 11, 2023, 11:29pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/8 "2023-12-11T23:29:39Z")

</div>

In a recent thread, the lack of `@inline` on the `iterate` function caused the creation of the return tuple to allocate.

Maybe Combinatorics.Combinations does not have that `@inline`.

From my inspection, it is true is isn’t `@inline`.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 11, 2023, 11:54pm UTC](https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/9 "2023-12-11T23:54:07Z")

</div>

> [@Dan](#):
>
> the lack of `@inline` on the `iterate` function caused the creation of the return tuple to allocate.

Yes, I think that’s it.

Are there any reasons why the function shouldn’t be marked `@inline` ?

```julia
struct Combinations
    n::Int
    t::Int
end

@inline function Base.iterate(c::Combinations, s = [min(c.t - 1, i) for i in 1:c.t])
    if c.t == 0 # special case to generate 1 result for t==0
        isempty(s) && return (s, [1])
        return
    end
    for i in c.t:-1:1
        s[i] += 1
        if s[i] > (c.n - (c.t - i))
            continue
        end
        for j in i+1:c.t
            s[j] = s[j-1] + 1
        end
        break
    end
    s[1] > c.n - c.t + 1 && return
    (s, s)
end

```

```julia
function test1(combs)
    x = 0
    for c in combs
        x += 1
    end
    x
end

@time test1(Combinations(30, 12))
 1.607441 seconds (1 allocation: 160 bytes)

```