High number of memory allocations.

[saolof]

Hi there!

I tried a basic segmented sieve of eratosthenes benchmark ( https://pastebin.com/WLmDZzh8 ), and noticed that the number of memory allocations made by of the version using @resumable and @yield was very high, roughly a factor of ten more than the one pushing values into a channel, with more memory allocated than a naive non-segmented sieve.

Resumablefunctions is much, much faster than the channel version. However, the body of the generator in both cases allocates all its memory in the beginning and then only mutates that in place. I believe that the memory allocations from the channel versions are due to pushing the values one by one into the channel. I'm not sure where the allocations in the resumablefunction case come from.

A third version that I wrote as an explicit iterator(struct with state, mutated in place by next) with the exact same algorithm, apart from being 5 times faster (understandable), is completely nonallocating (unlike resumablefunctions, which did surprise me).

Does resumablefunctions reallocate its iterator struct on every yield? I'm having trouble maintaining an intuition for the memory cost of resumable functions.

I'm a huge fan of the library, by the way. Being able to write reasonably fast iterators without having to deal with the next() mess is a big timesaver and makes the code much more readable.

[BenLauwens]

Hi

Sorry for the delay but it took some time before I could address this issue. The problem comes from inference of the type of your sieve. Because a @resumable function is a macro it can not include the runtime type of an object. You can remedy this problem by specifying it manually:

@resumable function segmentedsieve(n::Int64)
    segmentstart::Int64 = 0
    segmentend::Int64 = Int(ceil(sqrt(n)))
    initialsieve = basicsieve(segmentend)::BitArray{1}
    segment = copy(initialsieve)
    lastprime::Int64 = 2
    p::Int64 = 3
    while p <= n
        while p <= segmentend
           if segment[p-segmentstart]
                @yield lastprime
                lastprime = p
            end
            p+=1
        end
        segmentstart  += length(segment)
        segmentend += length(segment)
        segmentend = min(segmentend,n)
        segment .= true
        sievesegment(initialsieve,segment,segmentstart)
    end
    lastprime
end

This gives on my computer for n=10000 the following benchmark results:

julia> @btime bench1()
  130.895 μs (7 allocations: 400 bytes)

julia> @btime bench2()
  7.433 ms (3707 allocations: 61.94 KiB)

julia> @btime bench3()
  121.794 μs (7 allocations: 4.41 KiB)

If you do a @macroexpand of the @resumable function you see what the resulting code is and you can find out what the types are.

Can you keep me informed whether this solves your problem? I think I will include a kind of best practice section in the documentation with your segmented sieve as an example (if you allow me).

Kind regards

Ben

[saolof]

Ah right, adding type annotations did indeed eliminate the allocations. I'm impressed by how well it performs.

Interestingly enough, the allocations seemed to be coming exclusively from the function argument n being noninferrable. Once I specified the type of n, all allocations disappeared. Maybe it could be made to work for more general function type parameters with generated function and a parametrically typed struct?

Feel free to add the segmented sieve as an example.

Kind regards, Olof

[BenLauwens]

Thanks!

Parametric @resumable functions are possible. I hope that one day the Julia compiler is good enough to avoid these type annotations. I will close the issue.

Kind regards

Ben