5 ms·

I've spent a number of months working on using CPS and trampolining to add proper tail calls to Clojure. I have a video presenting my work here: http://www.chri

by cjfrisz 14y ago

I've spent a number of months working on using CPS and trampolining to add proper tail calls to Clojure. I have a video presenting my work here: http://www.chrisfrisz.com/blog/?p=220 http://www.chrisfrisz.com/blog/?p=220 . You can also take a look at the code here: https://github.com/cjfrisz/clojure-tco https://github.com/cjfrisz/clojure-tco . The punchline is that there are several things you can do to improve your performance: first, a number of more efficient CPS algorithms have been developed over the last 10+ years. I currently use one presented by Danvy in the 2001 paper "A First-Order One-Pass CPS algorithm" linked here: www.brics.dk/RS/01/49/BRICS-RS-01-49.pdf . It's major focus is to distinguish between "serious" and "trivial" expressions, because the serious ones are the only ones that actually require a new continuation to be generated. This saves a lot of administrative redexes that can kill your performance. Some other CPS-related avenues you may want to look into include "The Essence of Compiling with Continuations" (co-authored by one of my heroes, Amr Sabry) which formalizes A-normal form, an alternative to compiling with continuations that was ground-breaking in pointing out the number of unnecessary redexes introduced by traditional CPS algorithms. There's also a more recent paper by Andrew Kennedy at MS Research called "Compiling with Continuations, Continued" which I admittedly have not gotten a chance to dig into yet. It's stated goal is to revive some of the ideas of the original "Compiling with Continuations" by Andrew Appel. Of course with the method you present, continuation application isn't your only performance hit. If you're using a trampoline, you're undoubtedly thunkifying the code to delimit the bounces on the trampoline. I also need to do some work in this area, but I'm familiar with at least one paper on doing minimal thunkification from 1993 and linked here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.7919 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.... . I'm a big fan of both CPS+trampolining and the work like ClojureScript that's bringing efficient Lisp programming to the JavaScript arena. I'm hoping to get a chance to look over the work that you've done with Outlet and I'd love to chat with you about it. It sounds like we share quite similar interests.

jlongster 14y ago
I already watched your video! It was one of the things that inspired me to try this. Some of it was over my head (not extremely involved in the academic world), but I'm at a place now where I can dig into clojure-tco and see what you've done. Thanks for the papers, I'll look at them. I'm worried about spending a lot of time on this, only to realize that the performance hit is simply too large. I want this for debugging, and what I really want to try is to write a web-based byte code VM and compile Outlet to it. But the same concern exists there: can I get it fast enough to run sufficiently? I'm leaning more towards the CPS route though. First of all, there's tons of research going into it. Secondly, I lose all the benefits of JIT-ed Javascript if I run it in a VM. There's actually a much higher chance that I'll be able to get CPS-ed code running fast than compiled byte code. I admit that my current implementation is naive, and yes, the trampolines require even more thunks. I'd love to talk, I'm very interested in this as well. How far has clojure-tco come? What's the performance hit, and how do you return code to the trampoline? I will look at your code soon, and be lurking around #clojure as jlongster.
- cjfrisz 14y ago
  I've been finishing up grad school for the past couple of weeks, so Clojure TCO hasn't seen updates for a while. One of the things on my to-do list for it is to do more extensive benchmarking, but I've thrown a lot of ad-hoc tests at it, and I'm getting remarkably close performance to standard Clojure code. Especially with your interest, I want to nail down some numbers to have solid performance comparisons. I noticed that somebody commented about allocation being a big source of slow down. Someone suggested to me that if you have low-level enough access to your implementation, you can reuse the thunk after each invocation. It took me a while to get my head around it, and I'm not even sure it can be done in Clojure TCO. If you can change the contents of a underlying closure data structure, then you only have to allocate one thunk. I suspect that you're taking advantage of JavaScript's closures, so you may not have any more luck with it than me. If you're interested, one of my next goals now that I'm done with school is to start writing about the algorithms that Clojure TCO uses. I want to write something fairly accessible that describes the Danvy CPS algorithm.
  - jlongster 14y ago
    "... I've thrown a lot of ad-hoc tests at it, and I'm getting remarkably close performance to standard Clojure code" That's amazing! "Someone suggested to me that if you have low-level enough access to your implementation, you can reuse the thunk after each invocation ..." Yep, I thought of that when I was looking at the generated js code. I'm think of out of luck as well. However, as I mentioned at the end of my article, I think you should be able to hoist all the functions into top-level forms and pass around an environment. This way, functions are statically allocated once, and the performance hit of passing around environments can't be nearly as great as function allocation.
- ericbb 14y ago
  Personally, I like the VM technique over compilation to JS source. With a VM, you can track the continuation by simple stack operations rather than furiously allocating JS closures. Think about the effect in memory: when you do a return in a VM, you just pop some stuff off the stack(s) and there is no closure left hanging around for the GC to collect. The Dybvig "Three implementations of scheme" paper presents a really nice VM and Norvig's PAIP book presents a nice simple compiler for Scheme. Those are the two main sources that I've used for my simple compiler. Edit: Also... > I lose all the benefits of JIT-ed Javascript if I run it in a VM. But if you are using CPS, then your JS functions are going to be really small and the JIT won't have much to work with, right? It's not clear to me that the JIT will be more effective working on CPS JS given that you want to have fine-grained continuations for debugging.

by cjfrisz 14y ago

jlongster 14y ago

I already watched your video! It was one of the things that inspired me to try this. Some of it was over my head (not extremely involved in the academic world), but I'm at a place now where I can dig into clojure-tco and see what you've done. Thanks for the papers, I'll look at them. I'm worried about spending a lot of time on this, only to realize that the performance hit is simply too large. I want this for debugging, and what I really want to try is to write a web-based byte code VM and compile Outlet to it. But the same concern exists there: can I get it fast enough to run sufficiently? I'm leaning more towards the CPS route though. First of all, there's tons of research going into it. Secondly, I lose all the benefits of JIT-ed Javascript if I run it in a VM. There's actually a much higher chance that I'll be able to get CPS-ed code running fast than compiled byte code. I admit that my current implementation is naive, and yes, the trampolines require even more thunks. I'd love to talk, I'm very interested in this as well. How far has clojure-tco come? What's the performance hit, and how do you return code to the trampoline? I will look at your code soon, and be lurking around #clojure as jlongster.

cjfrisz 14y ago
I've been finishing up grad school for the past couple of weeks, so Clojure TCO hasn't seen updates for a while. One of the things on my to-do list for it is to do more extensive benchmarking, but I've thrown a lot of ad-hoc tests at it, and I'm getting remarkably close performance to standard Clojure code. Especially with your interest, I want to nail down some numbers to have solid performance comparisons. I noticed that somebody commented about allocation being a big source of slow down. Someone suggested to me that if you have low-level enough access to your implementation, you can reuse the thunk after each invocation. It took me a while to get my head around it, and I'm not even sure it can be done in Clojure TCO. If you can change the contents of a underlying closure data structure, then you only have to allocate one thunk. I suspect that you're taking advantage of JavaScript's closures, so you may not have any more luck with it than me. If you're interested, one of my next goals now that I'm done with school is to start writing about the algorithms that Clojure TCO uses. I want to write something fairly accessible that describes the Danvy CPS algorithm.
- jlongster 14y ago
  "... I've thrown a lot of ad-hoc tests at it, and I'm getting remarkably close performance to standard Clojure code" That's amazing! "Someone suggested to me that if you have low-level enough access to your implementation, you can reuse the thunk after each invocation ..." Yep, I thought of that when I was looking at the generated js code. I'm think of out of luck as well. However, as I mentioned at the end of my article, I think you should be able to hoist all the functions into top-level forms and pass around an environment. This way, functions are statically allocated once, and the performance hit of passing around environments can't be nearly as great as function allocation.
ericbb 14y ago
Personally, I like the VM technique over compilation to JS source. With a VM, you can track the continuation by simple stack operations rather than furiously allocating JS closures. Think about the effect in memory: when you do a return in a VM, you just pop some stuff off the stack(s) and there is no closure left hanging around for the GC to collect. The Dybvig "Three implementations of scheme" paper presents a really nice VM and Norvig's PAIP book presents a nice simple compiler for Scheme. Those are the two main sources that I've used for my simple compiler. Edit: Also... > I lose all the benefits of JIT-ed Javascript if I run it in a VM. But if you are using CPS, then your JS functions are going to be really small and the JIT won't have much to work with, right? It's not clear to me that the JIT will be more effective working on CPS JS given that you want to have fine-grained continuations for debugging.