low performance compared to Scipy minimize

mrozkamil commented 3 years ago

I was attacked to Julia by its reputation about its speed compared to e.g. python. Therefore, I tested it with one of the problems I need to solve on a daily basis, i.e. function minimisation. I compared the speed of Optim.jl to the one of scipy.optimize.minimize with the Rosenbrock function. I used two minimisation methods in the comparison: BFGS and Nelder-Mead. For both methods, Scipy is approx. 150-200 times taster than Optim.jl as it can be seen below:

julia Rosenbrock.jl

  1.514074 seconds (1.54 M allocations: 81.810 MiB, 3.03% gc time)
BFGS
fun: 5.471432684244042e-17
  x: [0.9999999926033423, 0.9999999852005353]
iterations: 16
success: true
gradient calls: 53
#################################################

  1.093265 seconds (196.22 k allocations: 10.489 MiB)
Nelder-Mead
fun: 3.5255270584829996e-9
  x: [0.9999634355313174, 0.9999315506115275]
iterations: 60
success: true
gradient calls: 0
#################################################

python Rosenbrock.py
BFGS
0.007476s used
      fun: 2.0055911509295948e-11
 hess_inv: array([[0.49982839, 0.99975297],
       [0.99975297, 2.00463718]])
      jac: array([ 7.50728268e-10, -3.72302189e-10])
  message: 'Optimization terminated successfully.'
     nfev: 104
      nit: 21
     njev: 26
   status: 0
  success: True
        x: array([0.99999552, 0.99999104])
#################################################

Nelder-Mead
0.006312s used
 final_simplex: (array([[1.00000439, 1.00001064],
       [0.99996163, 0.99992454],
       [1.00002803, 1.00005254]]), array([3.68617692e-10, 1.63627702e-09, 2.02249112e-09]))
           fun: 3.6861769151759075e-10
       message: 'Optimization terminated successfully.'
          nfev: 146
           nit: 79
        status: 0
       success: True
             x: array([1.00000439, 1.00001064])
#################################################

These are two pieces of code I generated:

Rosenbrock.jl:

using Optim

function print_res(res)

    println(Optim.summary(res))
    println("fun: $(Optim.minimum(res))")
    println("  x: $(Optim.minimizer(res))")
    println("iterations: $(Optim.iterations(res))")
    println("success: $(Optim.converged(res))")
    println("gradient calls: $(Optim.g_calls(res))")    
    println("#################################################")
    println()
end

f(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2

println()
@time res_BFGS = optimize(f, [0.0, 0.0], BFGS(), Optim.Options(g_tol = 1e-8))
print_res(res_BFGS)

println()
@time res_NM = optimize(f, [0.0, 0.0], NelderMead(), Optim.Options(f_tol = 1e-8))
print_res(res_NM)

Rosenbrock.py:

import numpy as np
from scipy.optimize import minimize
import timeit

f = lambda x: (1.0 - x[0])**2 + 100.0 * (x[1] - x[0]**2)**2
print('BFGS')
t = timeit.default_timer()
res = minimize(f, [0.0,0.0], method = 'BFGS', 
        options={'gtol':1e-8})
print('%.6fs used' % (timeit.default_timer()-t,))
print(res)
print("#################################################")
print()

print('Nelder-Mead')
t = timeit.default_timer()
res = minimize(f, [0.0,0.0], method = 'Nelder-Mead',
        options={'fatol':1e-8})
print('%.6fs used' % (timeit.default_timer()-t,))
print(res)
print("#################################################")
print()

Any explanation of such a low performance of Julia?

antoine-levitt commented 3 years ago

Hi and welcome to julia! Hard to say because of the formatting (use triple backquotes to format blocks of code), but are you measuring the time to do julia test.jl against python test.py, or running @time function()? If so you're measuring julia's compilation overhead (each function is compiled when called for the first time). Measure twice, and discount the first measurement.

mrozkamil commented 3 years ago

@antoine-levitt In both cases I just measured the execution time of the minimization, i.e. @time function. However, what really matters for a user is the execution time which turns to be even longer for Julia compared to Scipy.

antoine-levitt commented 3 years ago

It's a known tradeoff with julia: functions have to be compiled the first time they're used, which takes time. It's one thing that is being worked on by the julia people, but the first execution is never going to be as fast as python. The preferred workflow is to open one julia session and do all your computations inside, in which case one second overhead does not matter.

Eg I get

julia> @time res_BFGS = optimize(f, [0.0, 0.0], BFGS(), Optim.Options(g_tol = 1e-8))
  0.749115 seconds (1.57 M allocations: 83.518 MiB, 9.02% gc time)
julia> @time res_BFGS = optimize(f, [0.0, 0.0], BFGS(), Optim.Options(g_tol = 1e-8))
  0.000102 seconds (575 allocations: 23.906 KiB)

which looks faster than python?

mrozkamil commented 3 years ago

@antoine-levitt Indeed it looks faster but I do not understand how can it help in improving performance of any code (except some massive loops). It may sound naive but if I need to execute the code twice to see any gain I could just read the output of the first run. Don't I? Is there a way to compile the code first to get this performance boost in the first go? What's the compilation time?

antoine-levitt commented 3 years ago

The point is that for any realistic computation precompilation does not matter. The precompilation of f is very fast (you can see by running it once, redefining f and running it again), what takes time here is precompiling Optim, which happens on every new julia session. It's only triggered the first time, so if you leave your julia session open (eg using https://github.com/timholy/Revise.jl to minimize the need for restarts) it's basically not a problem. There are workflow tips on the julia manual if that helps. For that kind of questions you can also use the discourse or stackoverflow forum.

pkofod commented 3 years ago

It's possible that we can reduce compile time by reorganizing the code, but from Optim's side, we cannot avoid this completely because of the points Antoine made about Julia in general.

timholy commented 3 years ago

@mrozkamil, here's one way to think about it:

if you have a really long-running optimization problem (one that takes minutes or hours to reach the minimum), you'd probably like that to run quickly. In such cases you'd be glad that Julia invested in generating well-optimized code.
if you have an optimization problem that runs in ~1s, you probably don't care about making it any faster. If you do, it's probably because you have a lot of them, in which case again Julia's approach of optimizing the code (and then running them all from a single session, rather than many different sessions) is again a win for you.

In other words, in any case where it actually matters, Julia's model is probably a win.

That said, all of us understand the frustration of latency. @pkofod, don't know if you saw the new SnoopCompile announcement on discourse, but there's at least a chance that could help Optim. (And more goodness to come...)

pkofod commented 3 years ago

That said, all of us understand the frustration of latency. @pkofod, don't know if you saw the new SnoopCompile announcement on discourse, but there's at least a chance that could help Optim. (And more goodness to come...)

I will try to find the time, I didn't see the announcement so thanks!

ma-sadeghi commented 11 months ago

What about the (re)compilation time when the objective function changes? Here's my use case:

I have thousands of target functions which I want to test against some experimental data to see which target function better fits the data. In my experience, when I pass in a new target function, there seems to be a massive (re)compilation overhead. I don't have any MWE now, but here's the output of @time optimize(...) command after it's been called at least once, but on a different objective function:

  0.036213 seconds (29.97 k allocations: 2.328 MiB, 95.46% compilation time: 100% of which was recompilation)

JuliaNLSolvers / Optim.jl

low performance compared to Scipy minimize #896