You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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)
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)
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.
Activity
GregPlowman commentedon Dec 11, 2023
Here's an attempt to come up with an allocation-free version:
GregPlowman commentedon Dec 12, 2023
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