tail call optimization implemented in Javascript
G. Lathoud
Hello,
I experimented recently with tail call
http://glathoud.easypagez.com/publications/tailopt-js/tailopt-js.xhtml
optimization on Firefox 3.6. This is working
http://glathoud.easypagez.com/publications/tailopt-js/tailopt-js.xhtml#gcdconcise
very well , *except* in a tree traversal code, where recursive runs faster
als tail recursive, itself much faster as tail optimized (respectively
"treeforeach_rec", "treeforeach_tail" and "treeforeach_tailopt" in the
http://glathoud.easypagez.com/publications/tailopt-js/tailopt-js.xhtml#crossbrowser
results ).
I was expecting exactly the opposite. If anyone could provide an
explanation, I would be very interested (especially since the other test
cases show a good speedup with tail call optimization).
Best regards,
Guillaume
--
View this message in context: http://old.nabble.com/tail-call-optimization-implemented-in-Javascript-tp27420247p27420247.html
Sent from the Mozilla - JavaScript Engine mailing list archive at Nabble.com.
Boris Zbarsky
> I experimented recently with tail call
> http://glathoud.easypagez.com/publications/tailopt-js/tailopt-js.xhtml
> optimization on Firefox 3.6.
Note that you might be interested in
https://bugzilla.mozilla.org/show_bug.cgi?id=445363
Also note that to some extent the jit already performs something akin to
tail call optimization when tracing recursion (because it effectively
treats recursion as a loop), whenever it manages to trace it.
> I was expecting exactly the opposite. If anyone could provide an
> explanation, I would be very interested (especially since the other test
> cases show a good speedup with tail call optimization).
What happens to the numbers if you turn the jit off? DOM traversal and
the jit can interact weirdly at this point, so depending on what your
generated code looks like all sorts of things can happen.
-Boris
G. Lathoud
Hello,
I am glad to see that TCO is in the pipes. I hope that other browsers
follow.
The results with and without JIT are below (both .chrome and .content or
none),
with interspersed comments. I find the first 2 results very positive
(factorial and GCD),
and the last 2 quite puzzling (non-DOM and DOM tree traversal).
Regards,
Guillaume
---------
Results: durations in seconds, the lower, the better (relative value in
brackets)
Stack depth: case name Firefox 3.6 (JIT on) Firefox 3.6 (JIT
off)
Factorial:
n: fact_rec 1.801e-6 s (100: base) 1.840e-6 s (100:
base)
n: fact_tail 3.281e-6 s (182) 3.146e-6 s
(171)
1: fact_tailopt 2.209e-7 s (12) 1.543e-6 s
(84)
1: fact_iter 1.347e-7 s (7) 6.950e-7 s
(38)
Greatest Common Divisor (GCD):
n: gcd_rec 1.481e-5 s (100: base) 1.543e-5 s (100:
base)
n: gcd_tail 1.457e-5 s (98) 1.430e-5 s
(93)
1: gcd_tailopt 1.251e-6 s (8) 7.331e-6 s
(48)
1: gcd_iter 4.593e-7 s (3) 5.779e-6 s
(37)
--> so far, so good, actually the advantages of TCO and JIT seem to
cumulate!
Now, a non-DOM tree traversal example:
n: treeforeach_rec() 1.834e-4 s (100: base) 1.834e-4 s (100:
base)
n: treeforeach_tail() 2.220e-4 s (121) 2.192e-4 s (119)
1: treeforeach_tailopt() 5.438e-4 s (296) 1.871e-4 s (102)
--> JIT hurts here!
And finally the DOM tree traversal example:
n: DOMtreeforeach_rec() 2.156e-3 s (100: base) 1.905e-3 s (100: base)
1: DOMtreeforeach_tail() 1.629e-3 s (76) 1.899e-3 s (100)
1: DOMtreeforeach_tailopt() 2.904e-3 s (135) 1.823e-3 s (96)
--> JIT hurts here, but not as bad as previously. It may be actually
removing the recursion from DOMtreeforeach_tail() better than my
DOMtreeforeach_tailopt().
> _______________________________________________
> dev-tech-js-engine mailing list
> dev-tech-...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-tech-js-engine
>
>
--
View this message in context: http://old.nabble.com/tail-call-optimization-implemented-in-Javascript-tp27420247p27422027.html
Boris Zbarsky
> --> JIT hurts here!
Yep; you might be ending up with something that doesn't jit well and
hence ends up with trace entry/exit overhead without spending much time
on trace....
If you want to file a bug and attach a testcase, ideally one that makes
it simple to run just the tailopt version of each test, I'll take a look
at what's going on.
-Boris
Nicholas Nethercote
>
> The results with and without JIT are below (both .chrome and .content or
> none),
> with interspersed comments. I find the first 2 results very positive
> (factorial and GCD),
> and the last 2 quite puzzling (non-DOM and DOM tree traversal).
>
> brackets)
>
> Stack depth: case name Firefox 3.6 (JIT on) Firefox 3.6 (JIT
> off)
>
> Factorial:
>
> n: fact_rec 1.801e-6 s (100: base) 1.840e-6 s (100:base)
> n: fact_tail 3.281e-6 s (182) 3.146e-6 s (171)
> 1: fact_tailopt 2.209e-7 s (12) 1.543e-6 s (84)
> 1: fact_iter 1.347e-7 s (7) 6.950e-7 s (38)
I barely trust modern machines to have timing accuracy beyond 0.1 of a
second. You're reporting numbers like 0.000001801s. I don't what
tool you use to achieve such a (claimed) level of precision but I
wouldn't trust it at all. I'd suggest tweaking your microbenchmarks
to run for much longer times, eg. 1 second or more.
Nick
glathoud
> On Wed, Feb 3, 2010 at 2:11 AM, G. Lathoud <glath...@yahoo.fr> wrote:
>
> I barely trust modern machines to have timing accuracy beyond 0.1 of a
> second. You're reporting numbers like 0.000001801s. I don't what
> tool you use to achieve such a (claimed) level of precision but I
> wouldn't trust it at all. I'd suggest tweaking your microbenchmarks
> to run for much longer times, eg. 1 second or more.
>
> Nick
Yes, I also noticed that problem. Therefore, each test runs many
times, to achieve a total duration of 1 second. The number I reported
is the duration of a single iteration ( duration = 1 / niter ).
In addition, a given test runs 3 times, and the total number of
iterations is adjusted to have a total duration as close as possible
to 1 second. This intends to make results as stable as possible, and
comparisons between tests as fair as possible.
Greetings,
Guillaume
glathoud
> If you want to file a bug and attach a testcase, ideally one that makes
> it simple to run just the tailopt version of each test, I'll take a look
> at what's going on.
>
> -Boris
Here it is: https://bugzilla.mozilla.org/show_bug.cgi?id=544201
I hope this helps. If you need some adjustments in the test case, I'm
happy to help.
Guillaume