Hacker News Reader

Comment by marcuspolo | Hacker News Reader

I am not a Julia user, can the compiler optimize away the run-time type checking when `foo`'s argument is not easily known at compile time?

e.g.,

    foo(function_which_returns_dynamic_type())

View on HN

Yes, this is another reason to prefer julia's dispatch over manual dispatch. In this case the cost of the dynamic type being returned is just a _single_ dynamic dispatch. Dynamic dispach means that the correct function foo will be looked up in julia's method table. But when this foo is called, all types are inferred, and it will run optimized for these types.

This is called a function barrier.

A function barrier can be used as an optimization too: if you have a large function where one of the local variables has a type that is abstract / not concrete / not properly inferred by the compiler (e.g. `::Union{A,B,C}`, `::AbstractVector`, `::Any`), it can be beneficial to split the function into two functions, such that the latter function can be optimized for concrete types, and the former function only has the overhead of a single dynamic dispatch.

I think you may have some misconceptions. Julia is not compiled ahead of time. A function does not spring into existence until the definition of the function is executed. Same applies to a struct definition.

In a statically typed language you might write a function that takes an integer like this `foo(x::Int)` but in Julia it is completely possible to replace the `Int` with an expression that returns a type object. Meaning you actually run code at runtime to figure out what the defined function should actually operate on.

So there is nothing known at compile time, because everything happens at runtime. However when a function is called for the first time, then the JIT compiler will compile it and store the result. But it will store different compiled versions of the same function depending on the type of the argument it was called with. If you call the same function later with the same type of argument, it will reuse a previously compiled version.

If this is all very unclear. You could look at an article I wrote contrasting static typing with how typing works in Julia: https://medium.com/@Jernfrost/types-in-c-c-and-julia-ce0fcbe...

> A function does not spring into existence until the definition of the function is executed.

Methods and their type signatures do exist within the runtime as soon as the function expression is evaluated. To simplify the example from your article

  julia> a = 20
  20

  julia> foo(x::(a < 10 ? Int : Float64)) = "thing"
  foo (generic function with 1 method)

  julia> methods(foo)
  # 1 method for generic function "foo":
  [1] foo(x::Float64) in Main at REPL[2]:1

Here you see that one method of the function foo has been defined, and the code in the type signature has already run, resulting in a method which takes x::Float64. After this point, changing the value of `a` will not change anything about foo.

> when `foo`'s argument is not easily known at compile time?

There's no such thing. In Julia, all types are computed at compile time.

The catch is types such as `Union{Int, Float64}`. If fwrdt returns that, the compiler will generate a specialized method for `foo(::Union{Int,Float64})`. But `Union{Int,Float64} isa Int` can not be evaluated at compile time, so that specialized method will have run time type checks.

Julia provides some static analysis tools to detect this, and help you locate the `1` in fwrdt which should be a `1.0`.

While it's true that all code is typed (e.g. the compiler knows what types to expect at different points throughout the program), it's completely possible to have essentially "worthless" types computed. E.g. if I have the following:

    foo(x::Int) = x + 1
    foo(x::Float64) = x + 2
    foo(x::String) = "$(x) $(x)"

    function eval_user_input()
        user_input = readline(stdin)
        user_obj = eval(Meta.parse(user_input))
        return foo(user_obj)
    end

Then clearly there is no way the compiler can know what the type of `user_obj` is, however it will do its best to infer the entire function. We can use `@code_warntype` to quickly and easily find places where Julia's type inference gives a suboptimal result (which is often a source of performance issues, since there will be runtime overhead in those cases).

    julia> @code_warntype eval_user_input()
    Variables
      #self#::Core.Compiler.Const(eval_user_input, false)
      user_input::String
      user_obj::Any

    Body::Union{Float64, Int64, String}
    1 ─      (user_input = Main.readline(Main.stdin))
    │   %2 = Base.Meta.parse::Core.Compiler.Const(Base.Meta.parse, false)
    │   %3 = (%2)(user_input)::Any
    │        (user_obj = Main.eval(%3))
    │   %5 = Main.foo(user_obj)::Union{Float64, Int64, String}
    └──      return %5

You can see that `user_obj` is annotated as type `Any`, and that invoking `foo()` is said to itself return a type of `Union{Float64, Int64, String}`, which is to say, it has no idea which `foo` it's going to call ahead of time. I will note that in the REPL, all the suboptimal stuff is highlighted in red, making this a very nice debugging tool for immediately finding poorly-inferred sections of code. If we ask the compiler to run this code through its optimization passes as well by passing the `optimize=true` flag to `@code_warntype`, we can even see how the compiler tries to inline `foo` by turning the call to `foo()` into a series of `isa()` conditionals, checking the type of the return from `eval()`. I'm pasting the relevant section here, for the full example you can see the screenshot linked below, showcasing the red highlighting as well:

    10 ┄ %20 = φ (#8 => %12, #9 => %18)::String
    │    %21 = Base.Meta.parse::Core.Compiler.Const(Base.Meta.parse, false)
    │    %22 = invoke Base.Meta.:(var"#parse#4")(true::Bool, true::Bool, %21::typeof(Base.Meta.parse), %20::String)::Any
    │    %23 = Main.eval(%22)::Any
    │    %24 = (isa)(%23, String)::Bool
    └───       goto #12 if not %24
    11 ─ %26 = π (%23, String)
    │    %27 = invoke Base.string(%26::String, " "::String, %26::Vararg{String,N} where N)::String
    └───       goto #17
    12 ─ %29 = (isa)(%23, Float64)::Bool
    └───       goto #14 if not %29
    13 ─ %31 = π (%23, Float64)
    │    %32 = Base.sitofp(Float64, 2)::Float64
    │    %33 = Base.add_float(%31, %32)::Float64
    └───       goto #17
    14 ─ %35 = (isa)(%23, Int64)::Bool
    └───       goto #16 if not %35
    15 ─ %37 = π (%23, Int64)
    │    %38 = Base.add_int(%37, 1)::Int64
    └───       goto #17

[0] https://i.imgur.com/DZPWUvi.png

Reply on news.ycombinator.com