# ReverseDiff resultst do not fit theory

**URL:** <https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549>\
**Category:** Numerics\
**Created:** [June 8, 2018, 8:18pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549 "2018-06-08T20:18:33Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Goysa2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goysa2/32/15517_2.png) [@Goysa2](https://discourse.julialang.org/u/Goysa2)\
**Post date:** [June 8, 2018, 8:18pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/1 "2018-06-08T20:18:33Z")

</div>

I have a question concerning ReverseDiff. I am doing some simple benchmarking with different Julia tools for automatic differentiation. In theory (at least what I know of automatic differentiation theory) computing a gradient should take no more than five times the time it takes to compute the objective function (with the reverse mode).

So I took the extension of the Rosenbrock function:

```julia
function f(x)
	n=1000;
	return 100.0 * sum((x[i] - x[i - 1]^2)^2 for i=2:n) + (1.0 - x[1])^2
end

```

For all the values of n I tested, the time to compute the gradient is much more then 5 times the time it took to compute f(x). The testing I did was simple:

```julia
x = rand(n) # Where n is the right size for f
t = @elapsed f(x)
t_g = @elapsed ReverseDiff.gradient(f, x)

```

With n=100, t=2.224000e-06 and t\_g = 9.482440e-04  
With n = 500, t = 2.054000e-06 and t\_g = 4.637314e-03  
With n = 1000, t =3.007000e-06 and t\_g = 9.125266e-03

Am I misunderstanding the theory? Or is there something in my code that’s wrong? I am really confused by the disparity between theory and real life…

Thanks for your help!

(I am new to discourse so I don’t know if it’s the right place to ask this question…)

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [June 8, 2018, 9:04pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/2 "2018-06-08T21:04:06Z")

</div>

Please don’t post twice, or at least crossref it: [https://github.com/JuliaDiff/ReverseDiff.jl/issues/104](https://github.com/JuliaDiff/ReverseDiff.jl/issues/104).

I was as confused as you and received this answer: [https://github.com/JuliaDiff/ReverseDiff.jl/issues/85](https://github.com/JuliaDiff/ReverseDiff.jl/issues/85)

Basically, the theory is correct but irrelevant: ReverseDiff does compute the gradient in asymptotically optimal time, but it has to store all the operations, which makes it slow. Playing around with vector operations might help.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [June 8, 2018, 9:04pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/3 "2018-06-08T21:04:13Z")

</div>

ReverseDiff works by constructing an “instruction tape”, recording everything that your function does and then using that tape to propagate the gradient information backwards to the inputs. There’s a significant amount of overhead involved in constructing that tape, but fortunately you can do it ahead of time.

See: [https://github.com/JuliaDiff/ReverseDiff.jl/blob/master/examples/gradient.jl](https://github.com/JuliaDiff/ReverseDiff.jl/blob/master/examples/gradient.jl)

First of all, let’s establish a baseline, using BenchmarkTools.jl for more accurate timing:

```julia

julia> n = 1000
1000

julia> function f(x)
               n = length(x)
               return 100.0 * sum((x[i] - x[i - 1]^2)^2 for i=2:n) + (1.0 - x[1])^2
       end
f (generic function with 1 method)

julia> using BenchmarkTools

julia> @btime f(x) setup=(x = rand(n))
  991.692 ns (5 allocations: 96 bytes)

```

Your function `f(x)` is allocating a small amount of memory. You could probably make it faster by computing the `sum` in a loop rather than using a generator as you’re doing now, but this is OK for now.

Just calling `ReverseDiff.gradient` is very expensive because it recomputes the tape every time:

```julia
julia> @btime ReverseDiff.gradient(f, x) setup=(x = rand(n))
  8.637 ms (32012 allocations: 1.00 MiB)

```

Instead, we should pre-record the tape and pre-allocate an output vector to hold the result:

```julia
julia> tape = ReverseDiff.compile(ReverseDiff.GradientTape(f, rand(n)))
ReverseDiff.CompiledTape(f)

julia> @btime ReverseDiff.gradient!(g, $tape, x) setup=(x = rand(n); g = similar(x))
  312.478 μs (0 allocations: 0 bytes)

```

Computing the gradient with the pre-recorded tape is almost _30 times faster_ than re-building the tape every time. ReverseDiff is even smart enough to pre-allocate all the memory it needs, so this function doesn’t even allocate anything.

This still isn’t magically “no more than five times” as slow as the original `f`, but it’s much closer. Getting even better performance will require more than my level of expertise. But the point is that it’s _extremely_ important to consider the overhead involved when benchmarking things like autodiff. Julia’s ReverseDiff is quite competitive in that regard.

---

<div class="post-metadata">

**Author:** ![Goysa2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goysa2/32/15517_2.png) [@Goysa2](https://discourse.julialang.org/u/Goysa2)\
**Post date:** [June 8, 2018, 9:09pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/4 "2018-06-08T21:09:48Z")

</div>

Sorry I didn’t know what was the most appropriate place to post this issue was! Won’t happen again!

---

<div class="post-metadata">

**Author:** ![Goysa2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goysa2/32/15517_2.png) [@Goysa2](https://discourse.julialang.org/u/Goysa2)\
**Post date:** [June 8, 2018, 9:10pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/5 "2018-06-08T21:10:42Z")

</div>

Thank you very much! That will be very useful for the continuation of my testing with automatic differentiation!

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [June 8, 2018, 9:19pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/6 "2018-06-08T21:19:10Z")

</div>

By the way, the future of autodiff in Julia is [https://github.com/JuliaDiff/Capstan.jl](https://github.com/JuliaDiff/Capstan.jl) using [GitHub - JuliaLabs/Cassette.jl: Overdub Your Julia Code](https://github.com/jrevels/Cassette.jl) however neither of those is ready for use yet.

---

<div class="post-metadata">

**Author:** ![Goysa2](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goysa2/32/15517_2.png) [@Goysa2](https://discourse.julialang.org/u/Goysa2)\
**Post date:** [June 8, 2018, 9:21pm UTC](https://discourse.julialang.org/t/reversediff-resultst-do-not-fit-theory/11549/7 "2018-06-08T21:21:24Z")

</div>

I’ll keep an eye out for those! For now ForwardDiff and ReverseDiff should suffice for me!