# Allocations in advent of code

**URL:** <https://discourse.julialang.org/t/allocations-in-advent-of-code/72759>\
**Category:** Performance\
**Tags:** memory-allocation\
**Created:** [December 8, 2021, 10:50am UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759 "2021-12-08T10:50:35Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![weymouth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/weymouth/32/15839_2.png) [@weymouth](https://discourse.julialang.org/u/weymouth)\
**Post date:** [December 8, 2021, 10:50am UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/1 "2021-12-08T10:50:35Z")

</div>

I was fiddling around with the super fun advent of code this year and got surprised by an allocation in the day 5 puzzle.

```julia
input = [3,4,3,1,2]
histogram = [count(==(i),input) for i in 0:8]
phase(day) = mod(day-1,9)+1
@allocated for day in 1:256
   histogram[phase(day-2)] += histogram[phase(day)]
end
sum(histogram)

```

`@time` says there are 533 allocations (8.328 KiB) in the loop. Why is that? Or have I just benchmarked poorly?

---

<div class="post-metadata">

**Author:** ![trahflow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/trahflow/32/30585_2.png) [@trahflow](https://discourse.julialang.org/u/trahflow)\
**Post date:** [December 8, 2021, 11:02am UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/2 "2021-12-08T11:02:13Z")

</div>

Did you put that code into a function? (see [Performance Tips · The Julia Language](https://docs.julialang.org/en/v1/manual/performance-tips/))

If I put this in a function and `@time` it, I get:

```julia
0.000004 seconds (2 allocations: 224 bytes)

```

and that’s just the two allocations for `input` and `histogram`.

---

<div class="post-metadata">

**Author:** ![weymouth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/weymouth/32/15839_2.png) [@weymouth](https://discourse.julialang.org/u/weymouth)\
**Post date:** [December 8, 2021, 11:25am UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/3 "2021-12-08T11:25:45Z")

</div>

I tried to just put the loop in the function, and I was still getting issues. Putting the whole thing in a function gives 2 allocations, as you say.

---

<div class="post-metadata">

**Author:** ![trahflow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/trahflow/32/30585_2.png) [@trahflow](https://discourse.julialang.org/u/trahflow)\
**Post date:** [December 8, 2021, 11:47am UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/4 "2021-12-08T11:47:11Z")

</div>

Did you pass `inputs` and `histograms` as arguments to your function, or did you access them as global variables inside that function? This makes a big difference (the latter is much less performant), as also discussed in the page that I linked

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [December 8, 2021, 12:27pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/5 "2021-12-08T12:27:05Z")

</div>

For quick stuff like this, you can use `let` blocks, or wrap everything in functions, like:

```julia
let
    #stuff
end

function main()
    #stuff
end
main() # call function

```

The later is very nice if you use `Revise` and include the file with `includet`, such that in the REPL you can continuously just run `julia> main()` while changing the content of the function.

---

<div class="post-metadata">

**Author:** ![weymouth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/weymouth/32/15839_2.png) [@weymouth](https://discourse.julialang.org/u/weymouth)\
**Post date:** [December 8, 2021, 1:13pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/6 "2021-12-08T13:13:31Z")

</div>

I passed it in as an argument. There were still lots (hundreds) of allocations when I did that. What’s the right way to isolate this?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [December 8, 2021, 1:22pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/7 "2021-12-08T13:22:35Z")

</div>

Some alternatives:

1. let block

```julia
julia> using BenchmarkTools

julia> @ballocated let 
       input = [3,4,3,1,2]
       histogram = [count(==(i),input) for i in 0:8]
       phase(day) = mod(day-1,9)+1
       for day in 1:256
          histogram[phase(day-2)] += histogram[phase(day)]
       end
       sum(histogram)
       end
224

```

1. everthing in a function

```julia
julia> function main() 
       input = [3,4,3,1,2]
       histogram = [count(==(i),input) for i in 0:8]
       phase(day) = mod(day-1,9)+1
       for day in 1:256
          histogram[phase(day-2)] += histogram[phase(day)]
       end
       sum(histogram)
       end
       @ballocated main()
224

```

1. the data outside the function, but as parameters:

```julia
julia> input = [3,4,3,1,2]
       histogram = [count(==(i),input) for i in 0:8]
       phase(day) = mod(day-1,9)+1
       function main(input,histogram)
       for day in 1:256
          histogram[phase(day-2)] += histogram[phase(day)]
       end
       sum(histogram)
       end
       @ballocated main($input,$histogram) # interpolate the input parameters! 
0

```

always using `@ballocated` from `BenchmarkTools`, to avoid computing compilation, etc.

---

<div class="post-metadata">

**Author:** ![weymouth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/weymouth/32/15839_2.png) [@weymouth](https://discourse.julialang.org/u/weymouth)\
**Post date:** [December 8, 2021, 1:49pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/8 "2021-12-08T13:49:36Z")

</div>

Interpolating the inputs must have been the key! Does that work with @allocated as well, or only @ballocated?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [December 8, 2021, 2:28pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/9 "2021-12-08T14:28:42Z")

</div>

@allocated does not need that, but it has its quirks. First, it will count all stuff associated to the compilation on the first call to the function. Second, it may report allocations associated to the returning of the value from the function to the REPL. Thus, for example:

```julia
julia> f(x) = sum(x)
f (generic function with 1 method)

julia> x = rand(10);

julia> @allocated f(x)
4026434

julia> @allocated f(x)
16

```

On the first call it counted everything associated to compilation. In the second call it still reports 16 allocations, which are associated to the return value to the REPL. These are correctly discounted with `@ballocated` (properly used, with the variable interpolated):

```julia
julia> @ballocated f($x)
0

```

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [December 9, 2021, 5:24pm UTC](https://discourse.julialang.org/t/allocations-in-advent-of-code/72759/10 "2021-12-09T17:24:44Z")

</div>

I like to use [`TimerOutputs`](https://github.com/KristofferC/TimerOutputs.jl) to track allocations in cases like this one. Here is how it could be used on your example:

```julia
using TimerOutputs

# global TimerOutput object
const to = TimerOutput()

# wrap everything in a function (benchmarking in the global scope is tricky)
function foo(input)
    phase(day) = mod(day-1,9)+1

    # annotate lines or code sections with @timeit
    @timeit to "histogram" histogram = [count(==(i),input) for i in 0:8]
    @timeit to "for" for day in 1:256
        histogram[phase(day-2)] += histogram[phase(day)]
    end
    @timeit to "sum" sum(histogram)
end

# Make sure everything is compiled
input = [3,4,3,1,2]
foo(input)

# Reset the timer and re-run to get meaningful results
reset_timer!(to)
foo(input)
print_timer(to)

```

The `print_timer` invocation above yields an output like

```julia
julia> print_timer(to)
 ────────────────────────────────────────────────────────────────────
                             Time Allocations      
                     ────────────────────── ───────────────────────
  Tot / % measured: 1.17ms / 0.27% 41.0KiB / 0.31%    

 Section ncalls time %tot avg alloc %tot avg
 ────────────────────────────────────────────────────────────────────
 for 1 1.86μs 59.9% 1.86μs 0.00B 0.00% 0.00B
 histogram 1 1.01μs 32.3% 1.01μs 128B 100% 128B
 sum 1 241ns 7.74% 241ns 0.00B 0.00% 0.00B
 ────────────────────────────────────────────────────────────────────

```

which helps you see that the only allocations come from instantiating the histogram (which is expected)