(define (expt x n)
(cond ((= 0 n) 1)
((= 1 n) x)
(else (expt (* x x) (- n 1)))))
(defn f [t y] (- t y)) (defn solveit [t0 y0 h its] (if (> its 0) (let [t1 (+ t0 h) y1 (+ y0 (* h (f t0 y0)))] (recur t1 y1 h (dec its))) [t0 y0 h its]))
He points out that "if this was an assembly language program that worked the way you'd expect, each loop would take 7 cycles." So he tests it for Clojure. The result? On his netbook with Clojure 1.4: 2400 cycles. As he says, "We're looking at a slowdown of about 300 times over what we could probably achieve coding in assembler or in C with a good optimizing compiler." That's not surprising, I suppose, but it's still a little disheartening. After all, you want your language to be fast, right? Well, after a few iterations, he manages to reduce the cycles way down - all the way down, in fact, to 37, which is quite a feat. Like so:
Final Solution
(defn solveit-4 [t0 y0 h its] (let [zero (long 0)] (loop [t0 (double t0) y0 (double y0) h (double h) its (long its)] (if (> its zero) (let [t1 (+ t0 h) y1 (+ y0 (* h (- t0 y0)))] (recur t1 y1 h (dec its))) [t0 y0 h its]))))But the thing is, between the recur macro, explicit typecasting, and the loop construct, yes, you have a very significant performance increase, but it the code's gotten bigger, much less readable, and much less elegant.
The bottom line
My idea, which is probably very naive, but one which I'm curious about, is:
Is it possible to have some sort of set of automatic-optimizing macros that work on Clojure code to preserve elegance while maximizing performance?
In theory, it would be kind of an abstraction layer. There would be one file that would store the code that gets read and another output file that stores the code that actually gets evaluated by the REPL, and a set of macros to optimize the "front-end", "abstracted" file into the output, "nuts-and-bolts" file to be evaluated by the REPL. Probably this would be a very intensive process - I don't know. But maybe it's worth the trouble after all to save a ton of programmer-hours by increasing readability.
Thoughts?
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
An added gripe is that the else form within cond in Clojure uses a keyword, :else, instead of the more consistent parenthetical form used in Scheme. I suppose that's to make it less "Lispy." But it just ends up making it a little less elegant.
Perhaps I didn't choose my examples in a very illustrative way. It was meant to be a general approach. There are probably several other examples where the need for performance causes elegance to suffer, but I'm drawing a blank right now because I'm not a Clojure expert. As I familiarize myself with the language I'll be able to cite more varied examples.
Thanks for your feedback. I see your point with the :else keyword.
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Example 1: Tail-call recursionSchemeOne example would be tail-call recursion. For instance, normally in Scheme I'd naively implement an iterative exponent function like this:(define (expt x n)
(cond ((= 0 n) 1)((= 1 n) x)(else (expt (* x x) (- n 1)))))Pure. Simple. Beautiful. (Not that I'm the best Scheme programmer ever, but to me it looks beautiful, and it conforms well to the base of the problem. You get the point.)
Pure. Simple. Beautiful. (Not that I'm the best Scheme programmer ever, but to me it looks beautiful, and it conforms well to the base of the problem. You get the point.)This is not implementing expt as it is usually known, it looks more like repeated squaring to me.
This is not implementing expt as it is usually known, it looks more like repeated squaring to me.
Agreed. There's a certain irony that the OP declares the code pure, simple, and beautiful, when it isn't correct code. Seems to me that if you can't tell at a glance what a 3-line program is doing, there's something wrong :)
(define (even? n) (= (remainder n 2) 0))
(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) ;even O(log(n)) (else (* b (fast-expt b (- n 1)))))) ;odd O(n)
Sorry for the apparently awful examples in the original post. :/
My idea, which is probably very naive, but one which I'm curious about, is:Is it possible to have some sort of set of automatic-optimizing macros that work on Clojure code to preserve elegance while maximizing performance?
In theory, it would be kind of an abstraction layer. There would be one file that would store the code that gets read and another output file that stores the code that actually gets evaluated by the REPL, and a set of macros to optimize the "front-end", "abstracted" file into the output, "nuts-and-bolts" file to be evaluated by the REPL. Probably this would be a very intensive process - I don't know. But maybe it's worth the trouble after all to save a ton of programmer-hours by increasing readability.
This is not implementing expt as it is usually known, it looks more like repeated squaring to me.
Agreed. There's a certain irony that the OP declares the code pure, simple, and beautiful, when it isn't correct code. Seems to me that if you can't tell at a glance what a 3-line program is doing, there's something wrong :)
True. There are much better/more efficient implementations like:
(define (expt x n) (define (iter x1 n1 result) (cond ((= 0 n1) 1) ((= 1 n1) result) (else (iter x1 (- n1 1) (* x1 result))))) (iter x n x))
On Tue, Jul 9, 2013 at 8:11 AM, Alexander Gunnarson <alexander...@gmail.com> wrote:My idea, which is probably very naive, but one which I'm curious about, is:Is it possible to have some sort of set of automatic-optimizing macros that work on Clojure code to preserve elegance while maximizing performance?
In theory, it would be kind of an abstraction layer. There would be one file that would store the code that gets read and another output file that stores the code that actually gets evaluated by the REPL, and a set of macros to optimize the "front-end", "abstracted" file into the output, "nuts-and-bolts" file to be evaluated by the REPL. Probably this would be a very intensive process - I don't know. But maybe it's worth the trouble after all to save a ton of programmer-hours by increasing readability.
I think you're probably underestimating the scope of what the Clojure compiler already does. Arguably, it already is an auto-optimizing process that works on Clojure code to preserve elegance while maximing performance.
For the most part, Clojure programmers seem to be satisfied with dropping down to Java when the Clojure code gets too low-level to be elegant (although I think many would disagree that your examples have reached the level of inelegance). Still, there's probably room for something that targets the performance gap between Clojure and Java.
I'm interested in an assembly-like DSL that could be easily interwoven with Clojure code, something like:
http://www.rebol.com/docs/rebcode.html
Zach Tellman recently released a library that does something like that:
https://github.com/ztellman/primitive-math
So far, the vast majority of Clojure performance improvements have focused on making it easier to work with primitive numbers (in loops and as function inputs), because Java's boxed numerics is what usually kills performance. I've only found these improvements marginally useful because I find that most numbers eventually end up in a Clojure data structure, where they become boxed.
For me, the most useful thing would be an ability to drop down and do fast pointer manipulation and other mutable work, without having to go all the way to Java.
Going in the other direction, I'd be interested in mechanisms that made it easier to write recursive code without having to worry about stack overflow.
A reasonably simple optimisation would be to automatically identify self-recursion in tail position and convert it directly to "recur". I think that's possibly the kind of optimisation pass that the OP was suggesting.
A reasonably simple optimisation would be to automatically identify self-recursion in tail position and convert it directly to "recur". I think that's possibly the kind of optimisation pass that the OP was suggesting.
The TCO macro already exists: https://github.com/cjfrisz/clojure-tco
--
Clojure people say that jvm doesn't support tco, which it doesn't. So
they implemented a recur macro that turns the function into an
explicitly tcoable function. But, take a look at scala. It can do
(naive) tco optimization without any extra effort from the developer.
And on other lispy languages, check out sisc which is a scheme in jvm
which too can do tco within jvm. Are clojure designers just lazy or is
there a good reason for this .. lie?
Are clojure designers just lazy or is
there a good reason for this .. lie?
SISC has its own stack, so it doesn't do TCO within the jvm. There's a significant performance impact from this choice.
I remain convinced that the solution is better compile-time inference: if the compiler can infer that a var is never used dynamically, why should we pay the overhead for extra indirection / dynamic features?
Clojure people say that jvm doesn't support tco, which it doesn't. So
they implemented a recur macro that turns the function into an
explicitly tcoable function. But, take a look at scala. It can do
(naive) tco optimization without any extra effort from the developer.
And on other lispy languages, check out sisc which is a scheme in jvm
which too can do tco within jvm. Are clojure designers just lazy or is
there a good reason for this .. lie?
The Clojure philosophy is that it is rather irritating to think your recursive call is going to be cleverly optimized into a loop, and then if you're wrong, you have no good way to know that. So the idea is that you use the word "recur" to indicate that *you* think it can be optimized into a loop, and then the compiler tells you if you are right or wrong.