5 ms·

Can I take advantage of this thread to ask the HN crowd a technical question? Some time ago, I implemented an automatic differentiation tool. Using operator o

Can I take advantage of this thread to ask the HN crowd a technical question? Some time ago, I implemented an automatic differentiation tool. Using operator overloading on a special "autodouble" type the tool would trace the execution of a block of numerical code. Then, some calculus would automatically happen, and it would output and compile fast c-code that would compute the original function and derivatives in pure c. This was great, except the c-code that was output was freaking gigantic (like hundreds or thousands of megabytes) albeit very simple, and so the c compiler would take forever to run. Sigh. My question is: could I leverage pypy somehow to avoid this? Can I output RPython? Can I output whatever RPython is compiled down to instead? Can I do this with no more than, say, a 3x penalty compared to c? (I apologize for asking a question only marginally related to the particular article here...)

carterschonwald 15y ago
Off hand and guessing about the problem: You might want to look at approaches that use dual numbers. Likewise, in instead of inlining the procedures, generate a differentiated version of each procedure with a new name. If those don't cover your problems, perhaps look at how other autodiff tools for C do it?
- lliiffee 15y ago
  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...
  - carterschonwald 15y ago
    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 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!
    - lliiffee 15y ago
      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.
deleted 15y ago
[deleted]
sjs 15y ago
LLVM? I don't have much experience with runtime code generation but you might find it useful.
- lliiffee 15y ago
  LLVM would seem to (maybe? possibly!?) be a good solution, but I was never able to convincingly determine if it was likely to solve my problems, and the documentation seemed to be quite sparse for doing what I wanted to do. (This was a couple years ago, however, and I've love to be proven wrong.)
  - sjs 15y ago
    Instead of generating C code you might be able to generate LLVM IR and have it execute immediately, saved to disk, or both. I don't know how it will perform for you or how high level your generated C is though, it may not be realistic. Or use it to compile your C as it is pretty quick. It's not going to speed things up by orders of magnitude but every bit helps.
    - lliiffee 15y ago
      Awesome. Am I right in understanding that LLVM IR should be LLVM IF or LLVM assembly? The generated code is most extremely simplistic. An example would be: A[12800]=A[0] * A[6400]; A[12801]=A[1] * A[6480]; A[12802]=A[12800] + A[12801]; A[12803]=A[2] * A[6560]; A[12804]=A[12802] + A[12803]; A[12805]=A[3] * A[6640]; Which would be very easy to deal with. The only problem is that I sometimes call out to libraries for exp, log, sin, cos, etc.
      - sjs 15y ago
        That's right it's a platform independent representation. I think LLVM assembly is really low level, I'm pretty sure you want to generate IR. You should be able to link the math lib. py2llvm looks pretty interesting. http://code.google.com/p/py2llvm/ http://code.google.com/p/py2llvm/ http://code.google.com/p/py2llvm/source/browse/trunk/CodeGenLLVM.py http://code.google.com/p/py2llvm/source/browse/trunk/CodeGen...
beambot 15y ago
Theano (http://deeplearning.net/software/theano/introduction.html http://deeplearning.net/software/theano/introduction.html) might be worth a shot if you have closed-form expressions. '''Theano is a Python library that lets you to define, optimize, and evaluate mathematical expressions, especially ones with multi-dimensional arrays (numpy.ndarray). Using Theano it is possible to attain speeds rivaling hand-crafted C implementations for problems involving large amounts of data. It can also surpass C on a CPU by many orders of magnitude by taking advantage of recent GPUs.'''
ori_b 15y ago
RPython compiles down to C. Also, do you have an example of the generated code? I'm not sure what sorts of patterns would need it to be hundreds of megabytes. (Also, if Pypy's compilation time is any guide, it takes massive amounts of time to compile rpython)

carterschonwald 15y ago

Off hand and guessing about the problem: You might want to look at approaches that use dual numbers. Likewise, in instead of inlining the procedures, generate a differentiated version of each procedure with a new name. If those don't cover your problems, perhaps look at how other autodiff tools for C do it?

lliiffee 15y ago
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...
- carterschonwald 15y ago
  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 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!
  - lliiffee 15y ago
    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.

deleted 15y ago

[deleted]

sjs 15y ago

LLVM? I don't have much experience with runtime code generation but you might find it useful.

lliiffee 15y ago
LLVM would seem to (maybe? possibly!?) be a good solution, but I was never able to convincingly determine if it was likely to solve my problems, and the documentation seemed to be quite sparse for doing what I wanted to do. (This was a couple years ago, however, and I've love to be proven wrong.)
- sjs 15y ago
  Instead of generating C code you might be able to generate LLVM IR and have it execute immediately, saved to disk, or both. I don't know how it will perform for you or how high level your generated C is though, it may not be realistic. Or use it to compile your C as it is pretty quick. It's not going to speed things up by orders of magnitude but every bit helps.
  - lliiffee 15y ago
    Awesome. Am I right in understanding that LLVM IR should be LLVM IF or LLVM assembly? The generated code is most extremely simplistic. An example would be: A[12800]=A[0] * A[6400]; A[12801]=A[1] * A[6480]; A[12802]=A[12800] + A[12801]; A[12803]=A[2] * A[6560]; A[12804]=A[12802] + A[12803]; A[12805]=A[3] * A[6640]; Which would be very easy to deal with. The only problem is that I sometimes call out to libraries for exp, log, sin, cos, etc.
    - sjs 15y ago
      That's right it's a platform independent representation. I think LLVM assembly is really low level, I'm pretty sure you want to generate IR. You should be able to link the math lib. py2llvm looks pretty interesting. http://code.google.com/p/py2llvm/ http://code.google.com/p/py2llvm/ http://code.google.com/p/py2llvm/source/browse/trunk/CodeGenLLVM.py http://code.google.com/p/py2llvm/source/browse/trunk/CodeGen...

beambot 15y ago

Theano (http://deeplearning.net/software/theano/introduction.html http://deeplearning.net/software/theano/introduction.html) might be worth a shot if you have closed-form expressions. '''Theano is a Python library that lets you to define, optimize, and evaluate mathematical expressions, especially ones with multi-dimensional arrays (numpy.ndarray). Using Theano it is possible to attain speeds rivaling hand-crafted C implementations for problems involving large amounts of data. It can also surpass C on a CPU by many orders of magnitude by taking advantage of recent GPUs.'''

ori_b 15y ago

RPython compiles down to C. Also, do you have an example of the generated code? I'm not sure what sorts of patterns would need it to be hundreds of megabytes. (Also, if Pypy's compilation time is any guide, it takes massive amounts of time to compile rpython)