Closed gus-massa closed 9 years ago
Interesting!!!
Although my earliest version of this did have the procedure?
check "inline", I was concerned about code size explosion. Just like in this diff. So I moved it to a helper procedure.
Unfortunately that trades size for speed. An extra function call isn't free.
Fortunately, you're pointing out that actually, the Racket compiler can optimize the test away -- at least when, say, compile-enforce-module-constants
is #t
?
Is there a way to test that the optimization does in fact happen? (If so, then Travis CI, while running the tests against Racket HEAD could warn us if that behavior ever were to change someday.)
Is the optimization done in the production of byte code (could it be confirmed in a .zo file) or does this happen later as part of JIT?
I was worried about code size explosion too. My first implementation was:
[(_ x:expr y:expr)
#'(cond [(procedure? x) (#%app x y)]
[else (maybe-dict-ref x y)]))]
Instead of:
[(_ x:expr y:expr)
#'(let ([x_ x] [y_ y])
(cond [(procedure? x_) (#%app x_ y_)]
[else (maybe-dict-ref x_ y_)]))]
The first implementation is exponential (and wrong), but the second
adds only a linear coefficient in the worst case. And in many cases
the let
also disappears during the optimization.
On the other hand, I think that moving the dict?
tests will increase
the size of the code without improving the performance.
These optimizations are done during the compilation of the bytecode. Racket has test for many of them in optimize.rktl. If they broke, it will be discovered in the Racket build.
Merged -- thanks!!
I was browsing Racket commits and just noticed this one from you. These seem related. Are they, and if so how?
It's related, but not directly. There were many optimizations for procedures, and the procedure?
predicate. I added a few more. (And Matthew added a case that I detected but I couldn't solve.)
After reading the Rackjure details, I thought that in this and other similar languages it's very important to recognize procedures in order to simplify them when possible, enable constant folding, ... I like the idea of using (v 3)
instead of (vector-ref v 3)
, but it's a problem for optimizations.
So I read more carefully the optimizations related to procedures and tried to find some parts to improve. Now Racket detects even more expressions as procedures during the optimization step. That will reduce a little the size of the programs in Rackjure (and similar languages) and improve a little the speed.
Nice.
I guess I was concerned that maybe this change to rackjure needed a very new release of Racket, and it would perform poorly on older Rackets. If that were the case, I'd want to keep this change -- but document that so people are aware.
However it sounds like maybe you're saying it will perform fine on older Rackets compared to the old approach. And maybe perform even better with newer Racket and your additional optimizations.
It should work in older versions of Racket. The benchmarks I submitted with the PR used the old version of Racket 6.1.1. I just added a few additional cases (and I may add even more cases later.)
The original commit that reduces (procedure? x) => #t
is https://github.com/plt/racket/commit/1ce720cffd58ef38d7f8b447470660fe81a014a4 from September 2007. So this should work in Racket 4.0 and perhaps even in Racket 372. I guess nobody is still using an older version.
The original commit that reduces (procedure? x) => #t is plt/racket@1ce720c from September 2007. So this should work in Racket 4.0 and perhaps even in Racket 372. I guess nobody is still using an older version.
That should be fine. :smile: (By "older" I was thinking something like 5.3.2, which is currently the oldest version that rackjure claims to support and tests in .travis.yml
.)
Sorry to disturb you, I just wanted to make sure.
Thank you very much for such excellent contributions to rackjure and to Racket!
The Racket compiler can optimize at compile time some expressions like
(procedure? f)
whenf
is neverset!
ed. So in the normal case the test disappears. This also enables other optimizations like constant folding.The problem is that some tests become too verbose and it leaks too many implementation details. The second commit is a try to fix this.
This example shows the improvements in the running time: