3 ms·

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),

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.
- jlongster 14y ago
  The VM makes it easy to make continuation operations trivial, yes, but at the cost of normal code running slower and having to re-implement lots of things. I think both ideas have potential, and I need to implement both and see which one wins out. I'm not sure how well the JIT works with CPS-ed code. There's a Firefox addon to inspect the JIT which we could use to find out (https://addons.mozilla.org/en-US/firefox/addon/jit-inspector/ https://addons.mozilla.org/en-US/firefox/addon/jit-inspector...). It's possible we could optimize loops in a way that is more JIT-friendly. More research is needed!
  - ericbb 14y ago
    > More research is needed! Agreed. And I'm looking forward to more posts on Outlet! I have a project that's similar in that it's a Lisp dialect designed to match my own tastes and to eventually run on a variety of platforms. So far, I've had variants of it running on JavaScript and Go. It's in a rough state at the moment but you can see it here: https://github.com/ebb/lumgua https://github.com/ebb/lumgua and another, rather different incarnation here: http://norstrulde.org/ilge10/ http://norstrulde.org/ilge10/ (with some more description here: http://norstrulde.org/ilge10/about.html http://norstrulde.org/ilge10/about.html)

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.

jlongster 14y ago
The VM makes it easy to make continuation operations trivial, yes, but at the cost of normal code running slower and having to re-implement lots of things. I think both ideas have potential, and I need to implement both and see which one wins out. I'm not sure how well the JIT works with CPS-ed code. There's a Firefox addon to inspect the JIT which we could use to find out (https://addons.mozilla.org/en-US/firefox/addon/jit-inspector/ https://addons.mozilla.org/en-US/firefox/addon/jit-inspector...). It's possible we could optimize loops in a way that is more JIT-friendly. More research is needed!
- ericbb 14y ago
  > More research is needed! Agreed. And I'm looking forward to more posts on Outlet! I have a project that's similar in that it's a Lisp dialect designed to match my own tastes and to eventually run on a variety of platforms. So far, I've had variants of it running on JavaScript and Go. It's in a rough state at the moment but you can see it here: https://github.com/ebb/lumgua https://github.com/ebb/lumgua and another, rather different incarnation here: http://norstrulde.org/ilge10/ http://norstrulde.org/ilge10/ (with some more description here: http://norstrulde.org/ilge10/about.html http://norstrulde.org/ilge10/about.html)