Why is functional style so much slower here?

I wrote my first program in Julia today, which is a solution to Advent of Code day 15.

I wrote it in a functional style at first and was very surprised with how slow it ran.

I narrowed it down to the score functions. Here are 3 versions of it:

# Using .|> and |>
score_pipe((boxnum, box)::Tuple{Int, Vector{Lens}})::Int =
  box |> enumerate .|>
  (((slot, lens)::Tuple{Int, Lens},) -> boxnum * slot * lens.focal)
  |> sum

# Using sum(f, iter)
score_sum_fn((boxnum, box)::Tuple{Int, Vector{Lens}})::Int =
  sum(enumerate(box); init=0) do (slot, lens)::Tuple{Int, Lens}
    boxnum * slot * lens.focal

# Using a for loop
function score_loop((boxnum, box)::Tuple{Int, Vector{Lens}})::Int
  result = 0
  for (slot, lens) in enumerate(box)
    result += boxnum * slot * lens.focal
@time sum(Iterators.map(score, enumerate(boxes))) |> println
1.   score_pipe: 0.108080 seconds (237.70 k allocations: 16.374 MiB, 99.81% compilation time)
2. score_sum_fn: 0.082646 seconds (178.00 k allocations: 12.024 MiB, 99.75% compilation time)
3.   score_loop: 0.068665 seconds (112.36 k allocations: 7.630 MiB, 99.73% compilation time)
  1. Why is there such a huge difference between 3 and 1? Is it bad practice to write functional code in Julia? That would be unfortunate.
  2. Why do any of these do allocations at all? They’re simply iterating over a vector and accumulating everything into a single number, there shouldn’t be any heap allocations.

Full code: https://replit.com/@glebm1/Julia-AoC-2023-Day-15#main.jl

For the first question: Most of the time you measure is compilation time anyway.

For benchmarking, use BenchmarkTools.jl


Oh, do allocations also include allocations for compilation?

1 Like

Note how more than 99% of your timing is compilation time. All of your codes are pretty much equal when accounted for that:

julia> 0.108080 * (1.0 - .9981)

julia> 0.082646 * (1.0 - .9975)

julia> 0.068665 * (1.0 - .9973)

@time is a very naive timing mechanism. It includes everything, no matter whether its compilation or GC work that just happened to occur during its invocation. It also only measures once, so is subject to noise on tight measurements.


Also, someone correct me if I am wrong, but the type annotations in your code are completely unnecessary here. They can be useful to restrict valid input types of the function arguments but the other ones are just distraction.


Technically they are acting as type assertions for the return type as well. That’s one way to ensure type stability.

Running @time twice gets rid of the compilation time and is often good enough.

Well no it does not ensure type stability, but only “hide” type instability behind a barrier. They are still there.

Defined distinct notions of type stability and type groundedness.

Type stability (return type inserted) is enough to prevent propagation. Propagating instabilities can of course be quite bad.

The functions that take up most of your runtime being grounded is enough for instabilities to not be a major runtime performance concern (but they can still negatively impact compile times!). E.g., a function barrier is grounded, but the code calling it isn’t.