4 ms·
Places where this bites you is using numerical optimization algorithms in Python/Numpy, particularly when using gradient based methods. They make a HUGE boat lo
by srean 12y ago
Places where this bites you is using numerical optimization algorithms in Python/Numpy, particularly when using gradient based methods. They make a HUGE boat load of calls to evaluate the objective function value and objective function gradient. Typically both are callback functions. Worse they do it in a very tight and CPU bound loop.
This is one place where the much repeated "write your most expensive part in C or Fortran" does not give enough benefit unless you encapsulate the entire thing in C. Here I have assumed that the objective function and the gradient function has been exposed to Python's runtime through a C module.
Although the time spent evaluating the function and evaluating the gradient can be reduced hugely by switching to C explicitly, or implicitly by using Numpy vectorized expressions, there is still this large overhead of making that many calls to a Python function. Same issue with JNI.
Cython helps some here by encapsulating the entire thing in C, however if you have to call out to Python's or Numpy's C-API you are back to square one. This is important because if you want to write readable Cython (meaning something that looks like Numpy) that is free of low low level loops, it is very hard to avoid those API calls.
I would assume that a JIT with a good inliner would help a lot here.
In fact C itself does not fair well for this use case. This is one place where, ... wait for it.... a smart enough compiler for a high level language like Lisp can give a lot of speedup, example Stalin, and Stalingrad. You can do a lot with C++ and D's compile time metaprogramming machinery. C++ metaprogramming is quite painful if you are rolling your own. It was never designed for this use case. D is great but code-generation part of their toolchain arent that mature yet. Although it can be as fast as C++, one often has to desugar manually. Hopefully it will get better at it soon.
Fortran is also supposed to beat C routinely here, but I am not quite sure why/how it does it. If you know why it turns out to be faster I would be eager to know. I think Fortran semantics restricts possible data dependency paths enough that the compiler can (a) do a lot of SIMD vectorization and (b) avoid reloading data from memory and work with cached values. I dont know whether Fortran semantics helps in inlining away function calls.
- nostrademons 12y agoI would guess that Fortran's advantage is because Fortran's semantics prohibit aliasing - it is clear to the Fortran compiler whether a variable will ever have its address taken, and the compiler doesn't have to be as conservative in assuming that some pointer may silently change the value within a function's execution. This opens up a lot of optimizations for inlining and storing variables - even complex structs - in registers, which in turn opens up options for SIMD vectorization.
- srean 12y agoI am aware of the aliasing issue and that is exactly what I hinting at with (a) and (b) I think aliasing is only a part of the story. I have benchmarked (now long lost) Fortran and C++ with __restrict__ pointers(non-standard, but supported on gcc which is what I was using). Fortran still came out faster, and yes __restrict__ did make a difference in the runtime of the loop. In retrospect I should have kept the code around so that I could show the assembly to someone who could read and see whats going on. I dont really know Fortran, it was just a one-off noodling fueled by curiosity.
- zatkin 12y agoFortran outperforms C because it doesn't allow aliasing, so it's up to the programmer to detect errors with aliasing. More here: http://stackoverflow.com/a/146186/1112551 http://stackoverflow.com/a/146186/1112551