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

JuliaHub is happy to announce a new open source tool for static code analysis to prove that a Julia function is allocation-free. Use this to ensure that codes are safe for real-time applications, such as how we use it for JuliaSim to analyze SciML control codes!

The primary entry point to check allocations is the macro @check_allocs which is used to annotate a function definition that you’d like to enforce allocation checks for:

julia> using AllocCheck

julia> @check_allocs multiply(x,y) = x * y
multiply (generic function with 1 method)

julia> multiply(1.5, 2.5) # call automatically checked for allocations
3.75

julia> multiply(rand(3,3), rand(3,3)) # result matrix requires an allocation
ERROR: @check_alloc function encountered 1 errors (1 allocations / 0 dynamic dispatches).

To use it, check out the repository in JuliaLang:

For more on how Julia is developing for real-time controls applications, check out JuliaSim:

Please give all of the credit to the real developers, Cody Tapscott and @gbaraldi.

89 Likes

Turning allocations into errors (with a stack trace)! Very nice!

Fun little historical remark: This was already asked for by @rdeits at JuliaCon London 2018 with a (somewhat) famous reply by @jeff.bezanson!

(Relatedly: A macro that forbids allocation – turning allocation into error · Issue #34248 · JuliaLang/julia · GitHub)

15 Likes

Would it be possible to use the same technique from outside a function, to check in the tests for example that a given function signature cannot allocate? Because I can imagine that people don’t always want to have the dynamic dispatch behavior in their actual package but it seems currently you have to apply it to the actual function. You could of course do a wrapper function with the same arguments but it seems tedious maybe

5 Likes
1 Like

Hard agree on making that the main interface instead of the current method-level annotation. I don’t see myself using this on functions on the critical path, where not getting dynamic dispatch is as important (if not more so) as not getting allocations.

3 Likes

It’s a tool, you can use it however you want. The README example is just one way. There’s two main ways we are starting to make use of the new tool. The first one is to create unit tests that enforce that package code does not allocate in its inner loops. This makes sure that performance doesn’t regress.

But the second way is to ensure builds are safe. When we are building for safety-critical real-time applications, you want to ensure that the real-time loop has certain properties, such as not allocating and thus having no GC pauses. What you can do is add this macro to the binary build so that you have a confirmation that your binary will only build if this property is satisfied, otherwise you get an error before deployment.

4 Likes

Ah thanks I missed the functional version reading the docs, focus was on the macro.

I’m (still) wondering why there isn’t a call site macro (similar to @code_*) but only one for method definitions.

6 Likes

Open an issue.

5 Likes

Done: Call-site macro · Issue #45 · JuliaLang/AllocCheck.jl · GitHub

7 Likes

This is really exciting for real time work in Julia!

The last missing piece IMO will be to opt-out functions from GC pauses caused by other threads if the have been proved allocation-free by this macro.

In our current application we have pairs of hard real time and non latency-critical supervisory threads. At the moment, too many allocations on the supervisory thread cause the real time one to pause too.

6 Likes

Hey, this is useful for real-time audio! :radio:

Some ideas:

  1. Can it be extended to check for locks/files/sleep/sockets? Note that Compare-and-Swap (CAS) and similar paradigms are okay.
  2. At the recent Audio Developer Conference, I saw a Clang-based tool that hijacks malloc from libc and errors at runtime. Since it is not just a static check, it will also work for code that you did not write, but merely linked to.

Bumper.jl might be interesting to people needing more memory control.

5 Likes

Is it possible to integrate this into the VSCode extension somehow, to highlight allocations automatically?

9 Likes

Also if I’m not gravely misunderstanding something, profiling a call signature seems more properly “static”. The macro’ed function needs to be called with runtime inputs to count allocations and does return a value, though the allocations are supposedly searched in the IR itself so the input values and code execution doesn’t sound strictly necessary.

That does sound like a good next step.

17 Likes

Do you have any tips for using it with code that uses broadcasting? Since it seems any broadcasted operation has the potential to allocate. For example:

julia> using AllocCheck

julia> function f!(x, y)
        @. x += y
        end
f! (generic function with 1 method)

julia> x = zeros(10); y = zeros(10);

julia> check_allocs(f!, typeof.((x, y)))
1-element Vector{Any}:
 Allocation of Array in ./array.jl:365
  | copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)

Stacktrace:
  [1] copy
    @ ./array.jl:365 [inlined]
  [2] unaliascopy
    @ ./abstractarray.jl:1498 [inlined]
  [3] unalias
    @ ./abstractarray.jl:1482 [inlined]
  [4] broadcast_unalias
    @ ./broadcast.jl:947 [inlined]
  [5] preprocess
    @ ./broadcast.jl:954 [inlined]
  [6] preprocess_args
    @ ./broadcast.jl:957 [inlined]
  [7] preprocess_args
    @ ./broadcast.jl:956 [inlined]
  [8] preprocess
    @ ./broadcast.jl:953 [inlined]
  [9] copyto!
    @ ./broadcast.jl:970 [inlined]
 [10] copyto!
    @ ./broadcast.jl:926 [inlined]
 [11] materialize!
    @ ./broadcast.jl:884 [inlined]
 [12] materialize!
    @ ./broadcast.jl:881 [inlined]
 [13] f!(x::Vector{Float64}, y::Vector{Float64})
    @ Main ./REPL[23]:2

BTW: thank you! This helped me catch r .= -g in a tight loop :smile:. Should be r .= (-1) .* g to not allocate on the right-hand side.

edit: this seems helpful for ignoring aliasing allocations:

function check_allocs_ignore_alias(f, args)
    ret = check_allocs(f, args)
    filter!(ret) do s
        all(x -> x.func != :unalias, s.backtrace)
    end
    return ret
end
5 Likes

I guess the proper solution here would be to tell the compiler that there is no aliasing in the first place. Something like restrict from C would be nice.

UPDATE:

Out of curiosity, I tried this but unfortunately there is still a potential allocation reported (maybe the hint is only lexically scoped):

julia> using Base.Experimental: @aliasscope, Const

julia> function f_noalias!(x, y)
           @aliasscope begin
               @. x += Const(y)
           end
       end
f_noalias! (generic function with 1 method)

julia> check_allocs(f_noalias!, typeof.((x, y)))
1-element Vector{Any}:
 Allocation of Array in ./array.jl:409
  | copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)

Stacktrace:
  [1] copy
    @ ./array.jl:409 [inlined]
  [2] unaliascopy
    @ ./abstractarray.jl:1490 [inlined]
  [3] unalias
    @ ./abstractarray.jl:1474 [inlined]
  [4] broadcast_unalias
    @ ./broadcast.jl:977 [inlined]
  [5] preprocess
    @ ./broadcast.jl:984 [inlined]
  [6] preprocess_args
    @ ./broadcast.jl:987 [inlined]
  [7] preprocess
    @ ./broadcast.jl:983 [inlined]
  [8] preprocess_args
    @ ./broadcast.jl:987 [inlined]
  [9] preprocess_args
    @ ./broadcast.jl:986 [inlined]
 [10] preprocess
    @ ./broadcast.jl:983 [inlined]
 [11] copyto!
    @ ./broadcast.jl:1000 [inlined]
 [12] copyto!
    @ ./broadcast.jl:956 [inlined]
 [13] materialize!
    @ ./broadcast.jl:914 [inlined]
 [14] materialize!
    @ ./broadcast.jl:911 [inlined]
 [15] macro expansion
    @ ./REPL[34]:3 [inlined]
 [16] macro expansion
    @ ./experimental.jl:49 [inlined]
 [17] f_noalias!(x::Vector{Float64}, y::Vector{Float64})
    @ Main ./REPL[34]:2

Related issues/PRs: julia#8087, julia#19658, julia#31018

2 Likes

FTR, the equivalent code with my package UnsafeAssume.jl might look something like this:

using UnsafeAssume

function f_noalias!(x, y)
  @inline begin
    unsafe_assume_condition(!Base.mightalias(x, y))
    @. x += y
  end
end

But it’s no better at eliminating the allocations. EDIT: there is no allocating code generated, it was a bug with AllocCheck for nightly Julia v1.11.

EDIT: another option would be to use LLVM’s assume intrinsic to mark a pointer as noalias, but this would be more complicated to use, because loading Ptr then requires weird stuff like GC.@preserve.

I notice that Julia for some reason doesn’t seem to be able to infer any effects for f!(x, y) = @. x += y:

julia> Base.infer_effects(f!, Tuple{Vector{Int}, Vector{Int}})
(!c,!e,!n,!t,!s,!m,!u)′

So there may be other issues at play here, I think.

2 Likes

On second thought, I don’t think this would work. For the call to have an effect, LLVM must be able to infer that x and y don’t alias from the fact that Base.mightalias(x, y) is false, but I’m not sure that’s even possible.