Allocations when iterating Combinations

[GregPlowman]

It seems iterating Combinations allocates. Am I measuring this correctly? Is there 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)

[GregPlowman]

Here's an attempt to come up with an allocation-free version:

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)

[GregPlowman]

It was suggested on a discourse thread that the lack of @inline on the iterate function caused the creation of the return tuple to allocate. Marking iterate with @inline does indeed appear to eliminate the allocations.

https://discourse.julialang.org/t/allocations-when-iterating-combinatorics-combinations/107389/8?u=greg_plowman