10 ms·

Automatic Differentiation with Julia

146 points by Acur 8y ago

ncfausti 8y ago
For those curious about Julia, I just found this: https://www.infoworld.com/article/3284380/data-science/what-is-julia-a-fresh-approach-to-numerical-computing.html https://www.infoworld.com/article/3284380/data-science/what-... Close to C speed in a dynamic language? Seems pretty great on paper. Is this generally the case?
- one-more-minute 8y ago
  Generally, yes. It sounds like magic at first, but it's really just like a very lazy C++ compiler. You can happily look through the generated LLVM and machine code if you want to make sure it's reasonable.
- sischoel 8y ago
  While Julia is indeed a dynamically typed language, it also supports type annotations and can in most cases infer the static type of a variable. If you write a function function foo(x) #do something end and you call foo(10) and foo("some string"), then the compiler will create specialized methods foo(x::Int) and foo(x::String). Then there is no need for tracking the dynamic type of x inside these functions.
- FridgeSeal 8y ago
  I've been using it at work and it's pretty great. The performance is awesome, the REPL is super great as well. There's libraries that I'm itching to try out as soon as I've got a relevant project (Flux ML being the top of that list). There's been a lot of situations in using it where I've just gone "this is everything I needed/wanted": the performance, the language features and API design, etc. Plus there's a lot of very interesting things going on with the language and ecosystem, I definitely recommend trying it out.
- jules 8y ago
  As long as you write code that's type stable, yea. Type stable means that the compiler can deduce the types of the variables used in a function given the types of the arguments passed to the function. An example of code that's not type stable is code something like this: function test1(n) x = 0 for i = 1:n if i == 10 x = x + 0.1 else x = x + 1 end end return x end It isn't type stable because x starts out as an int but then changes to a float in the middle of the loop. This code compiles to 78 instructions. The following code is type stable: function test2(n) x = 0.0 for i = 1:n if i == 10 x = x + 0.1 else x = x + 1.0 end end return x end This code compiles to 14 instructions.
  - kristofferc 8y ago
    Julia is pretty good at dealing with this now though julia> @btime test1(10^5) 147.427 μs (0 allocations: 0 bytes) 99999.1 julia> @btime test2(10^5) 88.472 μs (0 allocations: 0 bytes) 99999.1 In earlier versions of Julia, the penalty here would be order of magnitudes worse.
- currymj 8y ago
  surprisingly yes, it really is. Julia is smart about type inference, so it compiles a specialized version of a function as needed for whatever argument types actually get used. the catch is, the first time you run a function there is often a noticeable compile time. but it’s cached after that. other problems with Julia include a somewhat immature/unfinished set of libraries, in part because the language was constantly changing underneath people. but now that 1.0 has been released, the language will be stable for a long time and you can expect that to improve quickly. good language! it gets a lot of hype on HN but that’s because it is actually very nice.
- kazagistar 8y ago
  It's "cost" is in startup times (compiling your code with LLVM at runtime slows things down, no surprise there), and you still have to write somewhat type-stable code (outputs uniquely inferrable from inputs) if you want it to actually run full speed.
- ska 8y ago
  Julia is hardly the first (cf some common lisp environments, 20+ years ago). To really get near (say within 2x) of c you need some sort of type annotation or inference of course, and (more importantly) you have to structure your code such that this works, but it's quite do-able. Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising.
  - byt143 8y ago
    >Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising. That isn't true. Closures, higher order functions and fused broadcast array expressions are all very fast except in some corner cases.
    - ska 8y ago
      I'm not sure we disagree. In my experience you can get "pretty fast" but not "c-like fast" while keeping many language features. The more you chase c-like performance (or even better fortran), the more you start restructuring things in a c-like way. This isn't universal of course, and I don't think it has anything specific to do with c language, just that it is a semi reasonable proxy for hardware architecture (ignoring SIMD). Anyway, this isn't really Julia specific, and I haven't tried with Julia recently so I may be wrong :)
one-more-minute 8y ago
You may like to take a look at Flux's implementation [1]; roughly the same idea but "professionalised" with performance work, tighter integration with the type system, nested AD and so on. It's a little less simple for that, of course, but is still under 500loc of fairly straightforward Julia code, and is generally a bit faster than PyTorch. The Julia world has done a lot of experimentation with AD and is converging on some really cool things, so if you're interested in this field it's definitely worth a look. [1]: https://github.com/FluxML/Flux.jl/blob/master/src/tracker/Tracker.jl https://github.com/FluxML/Flux.jl/blob/master/src/tracker/Tr...
- cbkeller 8y ago
  Flux is awesome. One of the biggest advantages IMO is that kernels you can easily write yourself should be by default just as fast as what's built-in -- since it's all written in Julia and Julia itself is fast, without having to rely on C/C++/FORTRAN under the hood. As the Flux devs say: "You could have written Flux. All of it, from LSTMs to GPU kernels, is straightforward Julia code. When in doubt, it’s well worth looking at the source. If you need something different, you can easily roll your own." http://fluxml.ai/Flux.jl/stable/ http://fluxml.ai/Flux.jl/stable/ edit: and the automatic differentiation works on them too!
0-_-0 8y ago
Julia is a great language, but I'm still waiting for someone to create a Julia fork that uses 0-based indexing.
- pjmlp 8y ago
  There are others that actually like 1-based indexing languages.
  - 0-_-0 8y ago
    And they already have Julia! Looks like you can't joke with array indexing...
    - pjmlp 8y ago
      Actually there are plenty of options with Algol derived languages.
      - eesmith 8y ago
        Apropos, as Algol allowed a user-defined base type, with the default as 1. https://en.wikipedia.org/wiki/Comparison_of_programming_languages_%28array%29#Array_system_cross-reference_list https://en.wikipedia.org/wiki/Comparison_of_programming_lang...
- FridgeSeal 8y ago
  So, fun times: if the 1-based indexing throws you off that much, it is entirely straightforward to configure it to use 0 based indexing if you want (or any other kind of offset that you so desire) https://docs.julialang.org/en/latest/devdocs/offset-arrays/ https://docs.julialang.org/en/latest/devdocs/offset-arrays/ Having said that, I encourage you to try out the 1-based indexing, as I think you might find a lot of things become surprisingly more intuitive.
  - red-tea 8y ago
    > or any other kind of offset that you so desire This is too often the attitude of Julia people. But zero-based indexing is not just some arbitrary offset. Programmers just like it. You say that many things are more intuitive with one-based indexing, but many things are less intuitive too. I don't think python ever would have become popular without zero-based indexing. The thing is, we really don't know why people prefer certain types of language. All we know is that they do. Computer languages can't evolve gradually like natural languages, but if they could I really don't think we'd go to one-based indexing.
IngoBlechschmid 8y ago
For those unaware of what automatic differentiation is: It's a close-to-magical tool which turns code for evaluating a function f into code for evaluating its derivative f'. It uses a special sort of invented numbers which square to zero even though they are not themselves zero. Here is one of the many tutorials on automatic differentiation: https://pizzaseminar.speicherleck.de/automatic-differentiation/notes.pdf https://pizzaseminar.speicherleck.de/automatic-differentiati...
- elcomet 8y ago
  Thid is really neat. Is this really used in practice? It seems to me that most of the AD frameworks used for deep learning implement the backward function that returns the jacobian for every initial function, and then chain those backward functions
  - cultus 8y ago
    I used it for non ML tasks in geophysics, which made my life a lot easier. However, I think most scientists and engineers aren't aware of it. It has been described as "criminally underused."
  - IngoBlechschmid 8y ago
    Yes, definitely, there are even battle-tested implementations for Fortran available. Though I have never seen AD frameworks used in the production contexts for neural networks/backpropagation. As you say, the code for this seems to be mostly handrolled. Please take this negative statement with a grain of salt, I don't actually work in machine learning.
    - kxyvr 8y ago
      Backpropagation is literally the reverse mode AD applied to neural nets. That said, I wish had a paper that I could point to that shows explicitly that. From what I can tell, the AD community has known this basically since the start, but for whatever reason backpropogation is taught rather than the more general technique.
kxyvr 8y ago
Alright, this looks neat, but I'm having a terrible time figuring out what's going on with the benchmark. Typically for AD, it's easiest to see four things: number of variables, time to compute function directly with no AD, time to compute function with AD enabled and calculate the gradient, ratio between these two numbers. Then, we run the same example with a varying number of variables to see how things scale. The advantage of reverse mode is that, theoretically, this ratio is fixed and bounded at 4 or 5 regardless of the number of variables. Realistically, this is much higher, but I think it's fine if it's somewhat between 10-40 times function evaluation as long as it scales. I can't figure out what their ratio is or whether or not it's appropriately scaling. Can anyone else?

146 points by Acur 8y ago

For those curious about Julia, I just found this: https://www.infoworld.com/article/3284380/data-science/what-is-julia-a-fresh-approach-to-numerical-computing.html https://www.infoworld.com/article/3284380/data-science/what-... Close to C speed in a dynamic language? Seems pretty great on paper. Is this generally the case?

one-more-minute 8y ago
Generally, yes. It sounds like magic at first, but it's really just like a very lazy C++ compiler. You can happily look through the generated LLVM and machine code if you want to make sure it's reasonable.
sischoel 8y ago
While Julia is indeed a dynamically typed language, it also supports type annotations and can in most cases infer the static type of a variable. If you write a function function foo(x) #do something end and you call foo(10) and foo("some string"), then the compiler will create specialized methods foo(x::Int) and foo(x::String). Then there is no need for tracking the dynamic type of x inside these functions.
FridgeSeal 8y ago
I've been using it at work and it's pretty great. The performance is awesome, the REPL is super great as well. There's libraries that I'm itching to try out as soon as I've got a relevant project (Flux ML being the top of that list). There's been a lot of situations in using it where I've just gone "this is everything I needed/wanted": the performance, the language features and API design, etc. Plus there's a lot of very interesting things going on with the language and ecosystem, I definitely recommend trying it out.
jules 8y ago
As long as you write code that's type stable, yea. Type stable means that the compiler can deduce the types of the variables used in a function given the types of the arguments passed to the function. An example of code that's not type stable is code something like this: function test1(n) x = 0 for i = 1:n if i == 10 x = x + 0.1 else x = x + 1 end end return x end It isn't type stable because x starts out as an int but then changes to a float in the middle of the loop. This code compiles to 78 instructions. The following code is type stable: function test2(n) x = 0.0 for i = 1:n if i == 10 x = x + 0.1 else x = x + 1.0 end end return x end This code compiles to 14 instructions.
- kristofferc 8y ago
  Julia is pretty good at dealing with this now though julia> @btime test1(10^5) 147.427 μs (0 allocations: 0 bytes) 99999.1 julia> @btime test2(10^5) 88.472 μs (0 allocations: 0 bytes) 99999.1 In earlier versions of Julia, the penalty here would be order of magnitudes worse.
currymj 8y ago
surprisingly yes, it really is. Julia is smart about type inference, so it compiles a specialized version of a function as needed for whatever argument types actually get used. the catch is, the first time you run a function there is often a noticeable compile time. but it’s cached after that. other problems with Julia include a somewhat immature/unfinished set of libraries, in part because the language was constantly changing underneath people. but now that 1.0 has been released, the language will be stable for a long time and you can expect that to improve quickly. good language! it gets a lot of hype on HN but that’s because it is actually very nice.
kazagistar 8y ago
It's "cost" is in startup times (compiling your code with LLVM at runtime slows things down, no surprise there), and you still have to write somewhat type-stable code (outputs uniquely inferrable from inputs) if you want it to actually run full speed.
ska 8y ago
Julia is hardly the first (cf some common lisp environments, 20+ years ago). To really get near (say within 2x) of c you need some sort of type annotation or inference of course, and (more importantly) you have to structure your code such that this works, but it's quite do-able. Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising.
- byt143 8y ago
  >Your code does tend to end up a bit c-like in those performance critical sections, but that's hardly surprising. That isn't true. Closures, higher order functions and fused broadcast array expressions are all very fast except in some corner cases.
  - ska 8y ago
    I'm not sure we disagree. In my experience you can get "pretty fast" but not "c-like fast" while keeping many language features. The more you chase c-like performance (or even better fortran), the more you start restructuring things in a c-like way. This isn't universal of course, and I don't think it has anything specific to do with c language, just that it is a semi reasonable proxy for hardware architecture (ignoring SIMD). Anyway, this isn't really Julia specific, and I haven't tried with Julia recently so I may be wrong :)

one-more-minute 8y ago

You may like to take a look at Flux's implementation [1]; roughly the same idea but "professionalised" with performance work, tighter integration with the type system, nested AD and so on. It's a little less simple for that, of course, but is still under 500loc of fairly straightforward Julia code, and is generally a bit faster than PyTorch. The Julia world has done a lot of experimentation with AD and is converging on some really cool things, so if you're interested in this field it's definitely worth a look. [1]: https://github.com/FluxML/Flux.jl/blob/master/src/tracker/Tracker.jl https://github.com/FluxML/Flux.jl/blob/master/src/tracker/Tr...

cbkeller 8y ago
Flux is awesome. One of the biggest advantages IMO is that kernels you can easily write yourself should be by default just as fast as what's built-in -- since it's all written in Julia and Julia itself is fast, without having to rely on C/C++/FORTRAN under the hood. As the Flux devs say: "You could have written Flux. All of it, from LSTMs to GPU kernels, is straightforward Julia code. When in doubt, it’s well worth looking at the source. If you need something different, you can easily roll your own." http://fluxml.ai/Flux.jl/stable/ http://fluxml.ai/Flux.jl/stable/ edit: and the automatic differentiation works on them too!

0-_-0 8y ago

Julia is a great language, but I'm still waiting for someone to create a Julia fork that uses 0-based indexing.

pjmlp 8y ago
There are others that actually like 1-based indexing languages.
- 0-_-0 8y ago
  And they already have Julia! Looks like you can't joke with array indexing...
  - pjmlp 8y ago
    Actually there are plenty of options with Algol derived languages.
    - eesmith 8y ago
      Apropos, as Algol allowed a user-defined base type, with the default as 1. https://en.wikipedia.org/wiki/Comparison_of_programming_languages_%28array%29#Array_system_cross-reference_list https://en.wikipedia.org/wiki/Comparison_of_programming_lang...
FridgeSeal 8y ago
So, fun times: if the 1-based indexing throws you off that much, it is entirely straightforward to configure it to use 0 based indexing if you want (or any other kind of offset that you so desire) https://docs.julialang.org/en/latest/devdocs/offset-arrays/ https://docs.julialang.org/en/latest/devdocs/offset-arrays/ Having said that, I encourage you to try out the 1-based indexing, as I think you might find a lot of things become surprisingly more intuitive.
- red-tea 8y ago
  > or any other kind of offset that you so desire This is too often the attitude of Julia people. But zero-based indexing is not just some arbitrary offset. Programmers just like it. You say that many things are more intuitive with one-based indexing, but many things are less intuitive too. I don't think python ever would have become popular without zero-based indexing. The thing is, we really don't know why people prefer certain types of language. All we know is that they do. Computer languages can't evolve gradually like natural languages, but if they could I really don't think we'd go to one-based indexing.

IngoBlechschmid 8y ago

For those unaware of what automatic differentiation is: It's a close-to-magical tool which turns code for evaluating a function f into code for evaluating its derivative f'. It uses a special sort of invented numbers which square to zero even though they are not themselves zero. Here is one of the many tutorials on automatic differentiation: https://pizzaseminar.speicherleck.de/automatic-differentiation/notes.pdf https://pizzaseminar.speicherleck.de/automatic-differentiati...

elcomet 8y ago
Thid is really neat. Is this really used in practice? It seems to me that most of the AD frameworks used for deep learning implement the backward function that returns the jacobian for every initial function, and then chain those backward functions
- cultus 8y ago
  I used it for non ML tasks in geophysics, which made my life a lot easier. However, I think most scientists and engineers aren't aware of it. It has been described as "criminally underused."
- IngoBlechschmid 8y ago
  Yes, definitely, there are even battle-tested implementations for Fortran available. Though I have never seen AD frameworks used in the production contexts for neural networks/backpropagation. As you say, the code for this seems to be mostly handrolled. Please take this negative statement with a grain of salt, I don't actually work in machine learning.
  - kxyvr 8y ago
    Backpropagation is literally the reverse mode AD applied to neural nets. That said, I wish had a paper that I could point to that shows explicitly that. From what I can tell, the AD community has known this basically since the start, but for whatever reason backpropogation is taught rather than the more general technique.

kxyvr 8y ago

Alright, this looks neat, but I'm having a terrible time figuring out what's going on with the benchmark. Typically for AD, it's easiest to see four things: number of variables, time to compute function directly with no AD, time to compute function with AD enabled and calculate the gradient, ratio between these two numbers. Then, we run the same example with a varying number of variables to see how things scale. The advantage of reverse mode is that, theoretically, this ratio is fixed and bounded at 4 or 5 regardless of the number of variables. Realistically, this is much higher, but I think it's fine if it's somewhat between 10-40 times function evaluation as long as it scales. I can't figure out what their ratio is or whether or not it's appropriately scaling. Can anyone else?