[ANN] AllocCheck.jl: Static code analysis to prove allocation-free behavior

Package Announcements
, , , ,
21

The reason it doesn’t work is that the alias analysis isn’t happening in LLVM, it is happening at the julia level, so unsafe_assume_condition is operating too late.

1 Like
22

Looks like the easiest way to make the compiler do this, is to just assert that there’s no aliasing by adding an error path.

The compiler is pretty good at using that information.

function f_noalias!(x, y)
    Base.mightalias(x, y) && throw("No aliasing allowed!")
    x .= x .+ y
end

julia> check_allocs(f_noalias!, (Vector{Int}, Vector{Int}))
Any[]
6 Likes
23

Perhaps a newbie question but in which cases would the behavior / results of AllocCheck.jl differ from a good old @ballocated or BenchmarkTools.@ballocated? Is one always more precise than the other, or does it depend?

2 Likes
24

AllocCheck gives stacktraces to pointing to any allocations that the compiler thinks could happen based on the types of the inputs (not the values). @allocated and @ballocated are runtime metrics, where the code actually executes and the change in gc metrics (tracked in the Julia runtime) is inspected to see how many allocations actually took place. So an easy way to make them differ is to allocate conditionally on a runtime value, and then take another path. (if x == 1; arr = ones(n); end or whatever).

7 Likes
25

Actually, it does work, but it depends on the Julia version. On Julia v1.10.0-rc1, check_allocs reports Any[] for both your f_noalias!, the one that throws, and mine, the one that uses UnsafeAssume.jl!

But on v1.11 nightly, two allocations are reported for both versions of the function!

Github issue: Array allocation elimination regression · Issue #52305 · JuliaLang/julia · GitHub

3 Likes
26

Speaking of which, I am considering making a PR so that @check_allocs plays nice with Bumper.jl’s @alloc. The following example demonstrates this:

using AllocCheck
using BenchmarkTools
using Bumper

function test_allocs_bench()
  @no_escape begin
    x = @alloc(Float64, 10)
    nothing
  end
end

@check_allocs test_allocs()  = test_allocs_bench()

let
  bench = @benchmark test_allocs_bench()
  @show maximum(bench).memory # = 0
  try
    test_allocs()
  catch err
    err.errors[1] # Allocation of Vector{Any} in ./boot.jl:477
  end
end

Not sure how much work this would entail though…

27

The Bumper.jl function you showed can allocate though, because the first time you call default_buffer() in a given task, the task local buffer is allocated. Furthermore, default_buffer() itself returns a SlabBuffer which can allocate when it grows, so you’d need to use AllocBuffer

If you want something that can’t possibly allocate, you’d need to do it more like

julia> using AllocCheck, Bumper

julia> function test_allocs_bench(buf)
           @no_escape buf begin
               x = @alloc(Float64, 10)
               nothing
           end
       end
test_allocs_bench (generic function with 1 method)

julia> check_allocs(test_allocs_bench, Tuple{AllocBuffer{Vector{UInt8}}})
Any[]
3 Likes
28

Ah, ok thanks for the clarification!