Allocations when iterating Combinatorics.Combinations

General Usage
1

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:

#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:

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:

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)
2

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.

3

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

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)
4

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).

5

I’ve opened an issue at Combinatorics:

6

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

7

Yeah, I thought that too.

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

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?

8

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.

3 Likes
9

Yes, I think that’s it.

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

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

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)