# Can the result of @time measure the spatial complexity of the algorithm?

**URL:** <https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509>\
**Category:** General Usage\
**Tags:** question\
**Created:** [July 20, 2022, 6:03am UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509 "2022-07-20T06:03:22Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 6:03am UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/1 "2022-07-20T06:03:22Z")

</div>

```julia
julia> function myfunc(n::Int64)
           D=20
           a=rand(D,D)
           for i in 1:n
               a*a
           end
       end
myfunc (generic function with 1 method)

julia> @time myfunc(100)
  0.000193 seconds (101 allocations: 328.250 KiB)

julia> @time myfunc(1000)
  0.003475 seconds (1.00 k allocations: 3.177 MiB)

julia> @time myfunc(10000)
  0.070506 seconds (10.00 k allocations: 31.741 MiB, 53.73% gc time)

julia> @time myfunc(100000)
  0.398272 seconds (100.00 k allocations: 317.386 MiB, 48.57% gc time)

julia> @time myfunc(1000000)
  1.612816 seconds (1.00 M allocations: 3.099 GiB, 5.19% gc time)

julia> @time myfunc(10000000)
 15.534450 seconds (10.00 M allocations: 30.994 GiB, 4.64% gc time)

```

This example seems to indicate that the memory consumption of @time is cumulative and does not reflect the maximum memory allocation (that is, memory complexity) that can occur during a program’s execution. So what operations can represent the memory complexity of a function?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [July 20, 2022, 10:22am UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/2 "2022-07-20T10:22:55Z")

</div>

I think I see what you mean, but just in case, I’m interpreting “maximum memory allocation”/“memory complexity” to mean the amount of memory needed for the method call to work. For example, if I allocate and free 100 bytes 5 times in a row, the cumulative memory consumption is 500 bytes, but I only need 100 bytes to do the work.

Here’s the problem with what you’re asking: you cannot manually free memory, and there’s no guarantee when the garbage collector runs. Although `myfunc` theoretically only needs heap memory for 2 arrays `a` and `a*a`, the garbage collector probably isn’t running in each iteration of the for-loop, and for all we know, it might only run after the method finishes and free 1+n arrays at once (`@time` reflects the numbers in this case). That’s not even the least responsive scenario, maybe it runs after 3 of these method calls and frees 3\*(1+n) arrays.

If you really need to save memory and don’t mind slowing the method to a crawl, you could try calling `GC.gc()` after reassignments. But the practical solution is to only allocate what you need and use in-place methods, if available. In this case, there is `LinearAlgebra.mul!`; below is a quick edit of your method:

```julia
julia> using LinearAlgebra

julia> function myfunc2(n::Int64)
           D=20
           a=rand(D,D)
           aa=zeros(D,D)
           for i in 1:n
               mul!(aa, a, a)
           end
       end
myfunc2 (generic function with 1 method)

julia> @time myfunc2(100)
  0.000103 seconds (2 allocations: 6.500 KiB)

julia> @time myfunc2(1000)
  0.000930 seconds (2 allocations: 6.500 KiB)

julia> @time myfunc2(10000)
  0.009923 seconds (2 allocations: 6.500 KiB)

julia> @time myfunc2(100000)
  0.093000 seconds (2 allocations: 6.500 KiB)

```

Incidentally, I think dead code elimination isn’t happening, despite none of the computations being returned, because `1:n` could be defined to mutate `n`, and the `n::Int64` annotation is just a subtype restriction that cannot inform the method the argument is immutable.

---

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 12:52pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/3 "2022-07-20T12:52:11Z")

</div>

> [@Benny](#):
>
> (`@time` reflects the numbers in this case). That’s not even the least responsive scenario, maybe it runs after 3 of these method calls and frees 3\*(1+n) arrays.

Oh, so the memory allocation returned by @time refers to the maximum memory required by myfunc(), which can be used to express the size of space complexity, right?

---

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 12:58pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/4 "2022-07-20T12:58:11Z")

</div>

> [@Benny](#):
>
> If you really need to save memory and don’t mind slowing the method to a crawl, you could try calling `GC.gc()` after reassignments.

I don’t konw why my code doesn’t free some memory when it calls gc.gc ():

```julia
julia> function myfunc1(n::Int64)
           D=20
           a=rand(D,D)
           for i in 1:n
               a*a
               GC.gc()
           end
       end
myfunc1 (generic function with 1 method)

julia> function myfunc2(n::Int64)
           D=20
           a=rand(D,D)
           for i in 1:n
               a*a
           end
       end
myfunc2 (generic function with 1 method)

julia> @time myfunc2(100)
  0.000273 seconds (101 allocations: 328.250 KiB)

julia> @time myfunc2(1000)
  0.002338 seconds (1.00 k allocations: 3.177 MiB)

julia> @time myfunc1(100)
  6.571333 seconds (101 allocations: 328.250 KiB, 99.97% gc time)

julia> @time myfunc1(1000)
 64.667089 seconds (1.00 k allocations: 3.177 MiB, 99.98% gc time)

```

Of course, it takes up quite a bit of time

---

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 1:03pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/5 "2022-07-20T13:03:21Z")

</div>

> [@Benny](#):
>
> But the practical solution is to only allocate what you need and use in-place methods, if available. In this case, there is `LinearAlgebra.mul!`; below is a quick edit of your method:

This works well for the example . Are there any other general methods? What do I do when I’m not multiplying matrices in the loop? GC.gc() takes too long.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [July 20, 2022, 1:21pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/6 "2022-07-20T13:21:59Z")

</div>

You’re still misunderstanding what `@time` is measuring. Let’s say you have a method that allocates 3 times. 1st time allocates 5 bytes, 2nd time 4 bytes, 3rd time 8 bytes. `@time` will report 3 allocations and 5+4+8=17 bytes. If you’re `@time`ing the first call with JIT compilation, `@time` will also count all the allocations done for compilation. `@time` is just not designed to measure space complexity or “maximum memory”, the latter baselessly assuming the garbage collector somehow runs right before the method call then right after. I’m guessing you might think that the garbage collector frees memory specific to a method call; it does not, it works on the entire heap and can free allocations from multiple method calls that were long over.

For the same reason, you will not see the effects of `GC.gc()` reflected in `@time`. The count of allocations and sum of memory per allocation can only go up, garbage collection doesn’t decrease them. Since you are triggering garbage collection, you can be sure that there are fewer live allocations and less allocated memory at any given point during the method call than what `@time` eventually prints.

> [@F-YF](#):
>
> Are there any other general methods?

Since Julia cares a lot about performance and needless allocations hurts performance, it is common to implement in-place methods; reading the documentation or asking in forums can help you find them. However, that’s not a guarantee, it is still possible to find an allocating method with no corresponding in-place version, even if it would make sense to have one.

---

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 1:46pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/7 "2022-07-20T13:46:53Z")

</div>

> [@Benny](#):
>
> For the same reason, you will not see the effects of `GC.gc()` reflected in `@time`. The count of allocations and sum of memory per allocation can only go up, garbage collection doesn’t decrease them. Since you are triggering garbage collection, you can be sure that there are fewer live allocations and less allocated memory at any given point during the method call than what `@time` eventually prints

Huh, I get it. So now I’m interested in measuring the spatial complexity of the algorithm, and although we can infer the spatial complexity, I want to know if there’s a function that gives us the maximum amount of memory that we need at a particular runtime

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 20, 2022, 1:55pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/8 "2022-07-20T13:55:44Z")

</div>

`Base.gc_live_bytes()` will give you the total amount of live heap memory.

---

<div class="post-metadata">

**Author:** ![F-YF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f-yf/32/17363_2.png) [@F-YF](https://discourse.julialang.org/u/F-YF)\
**Post date:** [July 20, 2022, 2:12pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/9 "2022-07-20T14:12:13Z")

</div>

Well. that’s a good idea. Thanks

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 20, 2022, 2:18pm UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/10 "2022-07-20T14:18:14Z")

</div>

Also note the existence of the memory profiler in Julia 1.8: [Profiling · The Julia Language](https://docs.julialang.org/en/v1.8.0-rc3/manual/profile/#Memory-allocation-analysis)

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [July 21, 2022, 3:16am UTC](https://discourse.julialang.org/t/can-the-result-of-time-measure-the-spatial-complexity-of-the-algorithm/84509/11 "2022-07-21T03:16:24Z")

</div>

To demonstrate how the garbage collector’s inconsistent timing throws off any measure of memory usage, here’s a version of the original function where `Base.gc_live_bytes` is used to measure the change in heap memory occupation:

```julia
julia> function myfunc_checkgc(n::Int64)
           start = Base.gc_live_bytes()
           D=20
           a=rand(D,D)
           for i in 1:n
               a*a
           end
           Base.gc_live_bytes() - start
       end
myfunc_checkgc (generic function with 1 method)

julia> @time myfunc_checkgc(100)
  0.000166 seconds (101 allocations: 328.250 KiB)
336128

julia> @time myfunc_checkgc(100)
  0.000140 seconds (101 allocations: 328.250 KiB)
336128

julia> @time myfunc_checkgc(1000000)
  2.711456 seconds (1.00 M allocations: 3.099 GiB, 33.98% gc time)
-29624217

julia> @time myfunc_checkgc(1000000)
  2.403197 seconds (1.00 M allocations: 3.099 GiB, 31.69% gc time)
24925936

julia> @time myfunc_checkgc(1000000)
  2.410707 seconds (1.00 M allocations: 3.099 GiB, 31.21% gc time)
24845856

```

When the number of allocations are small enough, the garbage collector often doesn’t run over the course of the method call and you get mostly consistent results, but when the garbage collector triggers in the middle of the method call, you can’t know how much memory was actually occupied. You can end up with _less_ occupied heap memory by the end.

The `@time` number would reflect how much more heap memory was occupied by the method call if the garbage collector isn’t triggered, but that’s just not something you can rely on happening. You could treat it as a very generous upper bound for 1 call.