How to get rid of allocations in this simple filtered generator example?

General Usage
,
1

Here’s a MWE of the allocating code (Julia 1.11.2):

function foo()
    arr = [Ref(i) for i=1:100]
    iter = (i for i in arr if rand()>0)
    @time begin
        elem, state = iterate(iter)
        while true
            next = iterate(iter, state)
            isnothing(next) && break
            elem, state = next
        end
    end
    return nothing
end
foo()

which will show:

  0.000003 seconds (200 allocations: 6.250 KiB)

If you make the element bitstype/immutable (Ref(i) → i) it becomes non-allocating, or if you remove the if rand()>0 it also becomes non-allocating. But the combination (which is unavoidable in my real code) apparently allocates every single element twice.

Any suggestions how to fix this?

2

The allocations go away if you don’t use the global rng state:

using Random

function foo()
    rng = Xoshiro(0)
    arr = [Ref(i) for i=1:100]
    iter = (i for i in arr if rand(rng)>0)
    @time begin
        elem, state = iterate(iter)
        while true
            next = iterate(iter, state)
            isnothing(next) && break
            elem, state = next
        end
    end
    return nothing
end

julia> foo()
  0.000000 seconds
1 Like
3

Cool.

  1. Is there any special method which can point this out quickly?
  2. The rng allocations are because of per thread state? Asking because, normally one wouldn’t expect some global state to allocate.
4

new to Julia, what’s the use case of the Ref(i)? I get it’s an MWE though, but trying to figureout Rel

Also, the version without Ref(i), but using rand() doesn’t allocate for me:

julia> function foo()
           arr = [i for i=1:100]
           iter = (i for i in arr if rand()>0)
           @time begin
               elem, state = iterate(iter)
               while true
                   next = iterate(iter, state)
                   isnothing(next) && break
                   elem, state = next
               end
           end
           return nothing
       end
foo (generic function with 1 method)

julia> foo()
  0.000004 seconds

julia> versioninfo()
Julia Version 1.11.2
Commit 5e9a32e7af2 (2024-12-01 20:02 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × Intel(R) Core(TM) i5-8400H CPU @ 2.50GHz
  WORD_SIZE: 64
  LLVM: libLLVM-16.0.6 (ORCJIT, skylake)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)