« Return to Thread: Tail calls via trampolining and an explicit instruction
Re: Tail calls via trampolining and an explicit instruction
by csar
::
Rate this Message:
Impressive:
user=> (time (trampoline #(foo 1000)) )
"Elapsed time: 0.547556 msecs"
user=> (time (foo 1000))
"Elapsed time: 0.375466 msecs"
Looks like the penalty is not that high, but after the JIT kicked in the trampolined version takes twice as long as the recusive version - hard to call this a TCO when the tail-call takes actually longer. Probably not a solution for a more performance focussed language like Scala:
user=> (dotimes [_ 100] (time (foo 5000 )))
"Elapsed time: 0.653994 msecs"
"Elapsed time: 1.023594 msecs"
"Elapsed time: 0.553143 msecs"
"Elapsed time: 0.638629 msecs"
"Elapsed time: 0.808762 msecs"
"Elapsed time: 0.602032 msecs"
"Elapsed time: 1.754692 msecs"
"Elapsed time: 3.244546 msecs"
"Elapsed time: 0.810438 msecs"
"Elapsed time: 0.635276 msecs"
"Elapsed time: 0.810159 msecs"
"Elapsed time: 0.958501 msecs"
"Elapsed time: 0.768813 msecs"
"Elapsed time: 0.940343 msecs"
"Elapsed time: 1.066057 msecs"
"Elapsed time: 0.871619 msecs"
"Elapsed time: 1.461359 msecs"
"Elapsed time: 1.232838 msecs"
"Elapsed time: 3.270248 msecs"
"Elapsed time: 0.597841 msecs"
"Elapsed time: 1.21915 msecs"
"Elapsed time: 0.569904 msecs"
"Elapsed time: 0.816305 msecs"
"Elapsed time: 1.208813 msecs"
"Elapsed time: 0.563759 msecs"
"Elapsed time: 0.564597 msecs"
"Elapsed time: 1.501866 msecs"
"Elapsed time: 0.555657 msecs"
"Elapsed time: 0.931683 msecs"
"Elapsed time: 4.408661 msecs"
"Elapsed time: 1.952762 msecs"
"Elapsed time: 1.630374 msecs"
"Elapsed time: 0.764064 msecs"
"Elapsed time: 0.561523 msecs"
"Elapsed time: 0.815746 msecs"
"Elapsed time: 0.550908 msecs"
"Elapsed time: 1.218311 msecs"
"Elapsed time: 0.967721 msecs"
"Elapsed time: 1.265803 msecs"
"Elapsed time: 0.979454 msecs"
"Elapsed time: 0.885587 msecs"
"Elapsed time: 3.627556 msecs"
"Elapsed time: 0.836699 msecs"
"Elapsed time: 0.814629 msecs"
"Elapsed time: 1.529245 msecs"
"Elapsed time: 0.564038 msecs"
"Elapsed time: 0.540851 msecs"
"Elapsed time: 2.006679 msecs"
"Elapsed time: 0.754286 msecs"
"Elapsed time: 1.038679 msecs"
"Elapsed time: 0.735289 msecs"
"Elapsed time: 2.170108 msecs"
"Elapsed time: 0.824965 msecs"
"Elapsed time: 1.758603 msecs"
"Elapsed time: 0.986158 msecs"
"Elapsed time: 1.199594 msecs"
"Elapsed time: 0.56348 msecs"
"Elapsed time: 1.221105 msecs"
"Elapsed time: 0.60287 msecs"
"Elapsed time: 0.798426 msecs"
"Elapsed time: 0.560965 msecs"
"Elapsed time: 0.846755 msecs"
"Elapsed time: 0.553981 msecs"
"Elapsed time: 1.272787 msecs"
"Elapsed time: 1.913093 msecs"
"Elapsed time: 4.565105 msecs"
"Elapsed time: 0.740876 msecs"
"Elapsed time: 0.936431 msecs"
"Elapsed time: 0.555658 msecs"
"Elapsed time: 0.546438 msecs"
"Elapsed time: 1.569474 msecs"
"Elapsed time: 0.630527 msecs"
"Elapsed time: 0.54113 msecs"
"Elapsed time: 0.870781 msecs"
"Elapsed time: 0.543644 msecs"
"Elapsed time: 3.667506 msecs"
"Elapsed time: 1.010743 msecs"
"Elapsed time: 1.566121 msecs"
"Elapsed time: 0.993422 msecs"
"Elapsed time: 0.903746 msecs"
"Elapsed time: 0.555378 msecs"
"Elapsed time: 0.55007 msecs"
"Elapsed time: 0.557892 msecs"
"Elapsed time: 1.256025 msecs"
"Elapsed time: 0.725512 msecs"
"Elapsed time: 1.02499 msecs"
"Elapsed time: 0.781384 msecs"
"Elapsed time: 2.289397 msecs"
"Elapsed time: 0.550629 msecs"
"Elapsed time: 1.059352 msecs"
"Elapsed time: 3.169677 msecs"
"Elapsed time: 0.832508 msecs"
"Elapsed time: 1.014375 msecs"
"Elapsed time: 1.175568 msecs"
"Elapsed time: 0.692546 msecs"
"Elapsed time: 1.797715 msecs"
"Elapsed time: 0.663492 msecs"
"Elapsed time: 1.708039 msecs"
"Elapsed time: 2.835277 msecs"
"Elapsed time: 0.8448 msecs"
user=> (dotimes [_ 100] (time (trampoline #(foo 5000 ))))
"Elapsed time: 7.796522 msecs"
"Elapsed time: 1.891581 msecs"
"Elapsed time: 1.577017 msecs"
"Elapsed time: 2.259785 msecs"
"Elapsed time: 1.782909 msecs"
"Elapsed time: 1.713626 msecs"
"Elapsed time: 3.076089 msecs"
"Elapsed time: 4.407264 msecs"
"Elapsed time: 2.485232 msecs"
"Elapsed time: 2.570439 msecs"
"Elapsed time: 1.990756 msecs"
"Elapsed time: 2.692241 msecs"
"Elapsed time: 5.366604 msecs"
"Elapsed time: 2.504788 msecs"
"Elapsed time: 2.344712 msecs"
"Elapsed time: 2.395556 msecs"
"Elapsed time: 3.39708 msecs"
"Elapsed time: 4.998121 msecs"
"Elapsed time: 2.778007 msecs"
"Elapsed time: 2.577702 msecs"
"Elapsed time: 2.498083 msecs"
"Elapsed time: 2.049422 msecs"
"Elapsed time: 2.771302 msecs"
"Elapsed time: 3.368026 msecs"
"Elapsed time: 2.136026 msecs"
"Elapsed time: 2.048025 msecs"
"Elapsed time: 4.829105 msecs"
"Elapsed time: 2.302248 msecs"
"Elapsed time: 2.315378 msecs"
"Elapsed time: 3.378921 msecs"
"Elapsed time: 2.387455 msecs"
"Elapsed time: 2.093562 msecs"
"Elapsed time: 2.907353 msecs"
"Elapsed time: 1.943543 msecs"
"Elapsed time: 2.022045 msecs"
"Elapsed time: 5.502096 msecs"
"Elapsed time: 1.927619 msecs"
"Elapsed time: 1.823696 msecs"
"Elapsed time: 2.601727 msecs"
"Elapsed time: 2.067022 msecs"
"Elapsed time: 3.73567 msecs"
"Elapsed time: 2.536077 msecs"
"Elapsed time: 2.476292 msecs"
"Elapsed time: 4.919899 msecs"
"Elapsed time: 2.737498 msecs"
"Elapsed time: 2.006121 msecs"
"Elapsed time: 2.946463 msecs"
"Elapsed time: 2.147759 msecs"
"Elapsed time: 3.583416 msecs"
"Elapsed time: 2.334375 msecs"
"Elapsed time: 2.472102 msecs"
"Elapsed time: 1.99327 msecs"
"Elapsed time: 3.815848 msecs"
"Elapsed time: 2.738337 msecs"
"Elapsed time: 2.386896 msecs"
"Elapsed time: 5.070477 msecs"
"Elapsed time: 2.417905 msecs"
"Elapsed time: 2.936407 msecs"
"Elapsed time: 3.320813 msecs"
"Elapsed time: 2.537194 msecs"
"Elapsed time: 2.01087 msecs"
"Elapsed time: 2.029308 msecs"
"Elapsed time: 2.771302 msecs"
"Elapsed time: 2.966858 msecs"
"Elapsed time: 2.334654 msecs"
"Elapsed time: 4.746692 msecs"
"Elapsed time: 2.362312 msecs"
"Elapsed time: 2.59642 msecs"
"Elapsed time: 2.217042 msecs"
"Elapsed time: 3.168279 msecs"
"Elapsed time: 2.558147 msecs"
"Elapsed time: 2.596978 msecs"
"Elapsed time: 2.750629 msecs"
"Elapsed time: 2.259785 msecs"
"Elapsed time: 2.545854 msecs"
"Elapsed time: 5.08221 msecs"
"Elapsed time: 2.454223 msecs"
"Elapsed time: 1.681219 msecs"
"Elapsed time: 2.257829 msecs"
"Elapsed time: 2.400585 msecs"
"Elapsed time: 2.859022 msecs"
"Elapsed time: 2.075682 msecs"
"Elapsed time: 2.739455 msecs"
"Elapsed time: 2.42433 msecs"
"Elapsed time: 2.017855 msecs"
"Elapsed time: 5.994616 msecs"
"Elapsed time: 2.90428 msecs"
"Elapsed time: 1.769219 msecs"
"Elapsed time: 2.405333 msecs"
"Elapsed time: 2.227658 msecs"
"Elapsed time: 2.327949 msecs"
"Elapsed time: 2.189384 msecs"
"Elapsed time: 2.968534 msecs"
"Elapsed time: 2.795328 msecs"
"Elapsed time: 1.956953 msecs"
"Elapsed time: 2.138261 msecs"
"Elapsed time: 1.801905 msecs"
"Elapsed time: 2.024559 msecs"
"Elapsed time: 2.949816 msecs"
"Elapsed time: 2.733867 msecs"
/Carsten
user=> (time (trampoline #(foo 1000)) )
"Elapsed time: 0.547556 msecs"
user=> (time (foo 1000))
"Elapsed time: 0.375466 msecs"
Looks like the penalty is not that high, but after the JIT kicked in the trampolined version takes twice as long as the recusive version - hard to call this a TCO when the tail-call takes actually longer. Probably not a solution for a more performance focussed language like Scala:
user=> (dotimes [_ 100] (time (foo 5000 )))
"Elapsed time: 0.653994 msecs"
"Elapsed time: 1.023594 msecs"
"Elapsed time: 0.553143 msecs"
"Elapsed time: 0.638629 msecs"
"Elapsed time: 0.808762 msecs"
"Elapsed time: 0.602032 msecs"
"Elapsed time: 1.754692 msecs"
"Elapsed time: 3.244546 msecs"
"Elapsed time: 0.810438 msecs"
"Elapsed time: 0.635276 msecs"
"Elapsed time: 0.810159 msecs"
"Elapsed time: 0.958501 msecs"
"Elapsed time: 0.768813 msecs"
"Elapsed time: 0.940343 msecs"
"Elapsed time: 1.066057 msecs"
"Elapsed time: 0.871619 msecs"
"Elapsed time: 1.461359 msecs"
"Elapsed time: 1.232838 msecs"
"Elapsed time: 3.270248 msecs"
"Elapsed time: 0.597841 msecs"
"Elapsed time: 1.21915 msecs"
"Elapsed time: 0.569904 msecs"
"Elapsed time: 0.816305 msecs"
"Elapsed time: 1.208813 msecs"
"Elapsed time: 0.563759 msecs"
"Elapsed time: 0.564597 msecs"
"Elapsed time: 1.501866 msecs"
"Elapsed time: 0.555657 msecs"
"Elapsed time: 0.931683 msecs"
"Elapsed time: 4.408661 msecs"
"Elapsed time: 1.952762 msecs"
"Elapsed time: 1.630374 msecs"
"Elapsed time: 0.764064 msecs"
"Elapsed time: 0.561523 msecs"
"Elapsed time: 0.815746 msecs"
"Elapsed time: 0.550908 msecs"
"Elapsed time: 1.218311 msecs"
"Elapsed time: 0.967721 msecs"
"Elapsed time: 1.265803 msecs"
"Elapsed time: 0.979454 msecs"
"Elapsed time: 0.885587 msecs"
"Elapsed time: 3.627556 msecs"
"Elapsed time: 0.836699 msecs"
"Elapsed time: 0.814629 msecs"
"Elapsed time: 1.529245 msecs"
"Elapsed time: 0.564038 msecs"
"Elapsed time: 0.540851 msecs"
"Elapsed time: 2.006679 msecs"
"Elapsed time: 0.754286 msecs"
"Elapsed time: 1.038679 msecs"
"Elapsed time: 0.735289 msecs"
"Elapsed time: 2.170108 msecs"
"Elapsed time: 0.824965 msecs"
"Elapsed time: 1.758603 msecs"
"Elapsed time: 0.986158 msecs"
"Elapsed time: 1.199594 msecs"
"Elapsed time: 0.56348 msecs"
"Elapsed time: 1.221105 msecs"
"Elapsed time: 0.60287 msecs"
"Elapsed time: 0.798426 msecs"
"Elapsed time: 0.560965 msecs"
"Elapsed time: 0.846755 msecs"
"Elapsed time: 0.553981 msecs"
"Elapsed time: 1.272787 msecs"
"Elapsed time: 1.913093 msecs"
"Elapsed time: 4.565105 msecs"
"Elapsed time: 0.740876 msecs"
"Elapsed time: 0.936431 msecs"
"Elapsed time: 0.555658 msecs"
"Elapsed time: 0.546438 msecs"
"Elapsed time: 1.569474 msecs"
"Elapsed time: 0.630527 msecs"
"Elapsed time: 0.54113 msecs"
"Elapsed time: 0.870781 msecs"
"Elapsed time: 0.543644 msecs"
"Elapsed time: 3.667506 msecs"
"Elapsed time: 1.010743 msecs"
"Elapsed time: 1.566121 msecs"
"Elapsed time: 0.993422 msecs"
"Elapsed time: 0.903746 msecs"
"Elapsed time: 0.555378 msecs"
"Elapsed time: 0.55007 msecs"
"Elapsed time: 0.557892 msecs"
"Elapsed time: 1.256025 msecs"
"Elapsed time: 0.725512 msecs"
"Elapsed time: 1.02499 msecs"
"Elapsed time: 0.781384 msecs"
"Elapsed time: 2.289397 msecs"
"Elapsed time: 0.550629 msecs"
"Elapsed time: 1.059352 msecs"
"Elapsed time: 3.169677 msecs"
"Elapsed time: 0.832508 msecs"
"Elapsed time: 1.014375 msecs"
"Elapsed time: 1.175568 msecs"
"Elapsed time: 0.692546 msecs"
"Elapsed time: 1.797715 msecs"
"Elapsed time: 0.663492 msecs"
"Elapsed time: 1.708039 msecs"
"Elapsed time: 2.835277 msecs"
"Elapsed time: 0.8448 msecs"
user=> (dotimes [_ 100] (time (trampoline #(foo 5000 ))))
"Elapsed time: 7.796522 msecs"
"Elapsed time: 1.891581 msecs"
"Elapsed time: 1.577017 msecs"
"Elapsed time: 2.259785 msecs"
"Elapsed time: 1.782909 msecs"
"Elapsed time: 1.713626 msecs"
"Elapsed time: 3.076089 msecs"
"Elapsed time: 4.407264 msecs"
"Elapsed time: 2.485232 msecs"
"Elapsed time: 2.570439 msecs"
"Elapsed time: 1.990756 msecs"
"Elapsed time: 2.692241 msecs"
"Elapsed time: 5.366604 msecs"
"Elapsed time: 2.504788 msecs"
"Elapsed time: 2.344712 msecs"
"Elapsed time: 2.395556 msecs"
"Elapsed time: 3.39708 msecs"
"Elapsed time: 4.998121 msecs"
"Elapsed time: 2.778007 msecs"
"Elapsed time: 2.577702 msecs"
"Elapsed time: 2.498083 msecs"
"Elapsed time: 2.049422 msecs"
"Elapsed time: 2.771302 msecs"
"Elapsed time: 3.368026 msecs"
"Elapsed time: 2.136026 msecs"
"Elapsed time: 2.048025 msecs"
"Elapsed time: 4.829105 msecs"
"Elapsed time: 2.302248 msecs"
"Elapsed time: 2.315378 msecs"
"Elapsed time: 3.378921 msecs"
"Elapsed time: 2.387455 msecs"
"Elapsed time: 2.093562 msecs"
"Elapsed time: 2.907353 msecs"
"Elapsed time: 1.943543 msecs"
"Elapsed time: 2.022045 msecs"
"Elapsed time: 5.502096 msecs"
"Elapsed time: 1.927619 msecs"
"Elapsed time: 1.823696 msecs"
"Elapsed time: 2.601727 msecs"
"Elapsed time: 2.067022 msecs"
"Elapsed time: 3.73567 msecs"
"Elapsed time: 2.536077 msecs"
"Elapsed time: 2.476292 msecs"
"Elapsed time: 4.919899 msecs"
"Elapsed time: 2.737498 msecs"
"Elapsed time: 2.006121 msecs"
"Elapsed time: 2.946463 msecs"
"Elapsed time: 2.147759 msecs"
"Elapsed time: 3.583416 msecs"
"Elapsed time: 2.334375 msecs"
"Elapsed time: 2.472102 msecs"
"Elapsed time: 1.99327 msecs"
"Elapsed time: 3.815848 msecs"
"Elapsed time: 2.738337 msecs"
"Elapsed time: 2.386896 msecs"
"Elapsed time: 5.070477 msecs"
"Elapsed time: 2.417905 msecs"
"Elapsed time: 2.936407 msecs"
"Elapsed time: 3.320813 msecs"
"Elapsed time: 2.537194 msecs"
"Elapsed time: 2.01087 msecs"
"Elapsed time: 2.029308 msecs"
"Elapsed time: 2.771302 msecs"
"Elapsed time: 2.966858 msecs"
"Elapsed time: 2.334654 msecs"
"Elapsed time: 4.746692 msecs"
"Elapsed time: 2.362312 msecs"
"Elapsed time: 2.59642 msecs"
"Elapsed time: 2.217042 msecs"
"Elapsed time: 3.168279 msecs"
"Elapsed time: 2.558147 msecs"
"Elapsed time: 2.596978 msecs"
"Elapsed time: 2.750629 msecs"
"Elapsed time: 2.259785 msecs"
"Elapsed time: 2.545854 msecs"
"Elapsed time: 5.08221 msecs"
"Elapsed time: 2.454223 msecs"
"Elapsed time: 1.681219 msecs"
"Elapsed time: 2.257829 msecs"
"Elapsed time: 2.400585 msecs"
"Elapsed time: 2.859022 msecs"
"Elapsed time: 2.075682 msecs"
"Elapsed time: 2.739455 msecs"
"Elapsed time: 2.42433 msecs"
"Elapsed time: 2.017855 msecs"
"Elapsed time: 5.994616 msecs"
"Elapsed time: 2.90428 msecs"
"Elapsed time: 1.769219 msecs"
"Elapsed time: 2.405333 msecs"
"Elapsed time: 2.227658 msecs"
"Elapsed time: 2.327949 msecs"
"Elapsed time: 2.189384 msecs"
"Elapsed time: 2.968534 msecs"
"Elapsed time: 2.795328 msecs"
"Elapsed time: 1.956953 msecs"
"Elapsed time: 2.138261 msecs"
"Elapsed time: 1.801905 msecs"
"Elapsed time: 2.024559 msecs"
"Elapsed time: 2.949816 msecs"
"Elapsed time: 2.733867 msecs"
/Carsten
On Wed, Nov 26, 2008 at 4:08 PM, James Iry <jamesiry@...> wrote:
http://groups.google.com/group/clojure/msg/3addf875319c5c10
« Return to Thread: Tail calls via trampolining and an explicit instruction
| Free embeddable forum powered by Nabble | Forum Help |
