Hacker News Reader

Comment by lliiffee | Hacker News Reader

For being offhand, those are very good guesses! Dual numbers won't be efficient, as I want reverse-mode autodiff.

As to the multiple procedures: Well, as I was doing it, even a single procedure can be many hundreds of megabytes large. Even for very very simple code, however, I noticed that GCC was superlinear in code size. I suppose I could somewhat arbitrarily break up the code into arbitrary functions. I wonder if that would speed things up?

Other autodiff tools: Well, they basically trace execution, but then run an interpreter instead of trying to actual generate compiled code. I wanted to both be faster than that and have the wonderful experience of writing pure python...

View on HN

it sounds like you're getting lots of code duplication. 1) try running a common subexpression elimination process on your code before doing the autodiffing, and create a procedure for each shared expression 2) for prim ops, again, have a procedure created for the diffed version instead of inlining, and sub in the procedure instead.

perhaps something like these ideas would help

If you want an example of a nice high level Auto diff lib, a nice one that works via operator overloading is http://hackage.haskell.org/package/ad , which seems quite nice though I've not had the opportunity to use it myself.

yes, optimizing compilers such as gcc use algorithms that are superlinear in code size when they're optimizing. Perhaps you should instead try out the operator overloading approach (and see if you can )?

gl :-)

Aside: When I hear the phrase execution trace in the context of program analysis, i think abstract interpretation, though I'm not sure if thats relevant for you.

cheers!

It isn't exactly common subexpressions. Basically the problem is things like matrix multiplies always get unrolled.

I've used lots of operator overloading based autodiff packages for C++. They are great, but the issue is not how the function is recorded (I used operator overloading myself in my python package) but how it gets executed at runtime. Unless a compiler (or JIT) is called sometime between when the operator overloading happens and execution happens, the function is basically being interpreted at runtime. This is what happens in, e.g. ADOL-C, SACADE, and CPPAD, all of which come with a significant (e.g. 20x) performance penalty as compared with hand-written derivatives.

Reply on news.ycombinator.com