530900 - TM: recursion broken with STOP, inner loop

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Duncan Loveday]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.5) Gecko/20091102 Firefox/3.5.5 (.NET CLR 2.0.50727)
Build Identifier: Local m-c build

Does tracemonkey trace recursive functions ? I see little or no speedup for a simple quicksort type algorithm

$ ./js a.js
Quick sort 1000000 elements time=10579
Bubble sort 10000 elements time=31237
$ ./js -j a.js
Quick sort 1000000 elements time=9751
Bubble sort 10000 elements time=10017
$ 

Reproducible: Always

Steps to Reproduce:
Run the attached in the shell - times are a bit variable but JIT definitely does more for the bubble sort than the recursive sort.


Expected Results:  
It'd be "nice" if it could stay on trace for recursive functions. Can it ?

Comment 1

[Duncan Loveday]

Attachment: Test case

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

We do trace some recursive functions (see bug 459301), and your control flow looks like something we should be tracing. But we're aborting somewhere. I'll take a look.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

There's two problems here. The first is that if a recursion function runs off the end (i.e. hits JSOP_STOP instead of JSOP_RETURN), it won't compile. The second problem is that we can get abnormal loop exits.

AttemptToStabilizeTree() starts a generic recording once it sees a RECURSIVE_UNLINKED_EXIT. In theory these could get tied together, but that's invalid. We have to separate traces from "loop" or "recursive" traces. This way it will start a recursive trace, then call the loop trace, and continue on.

Comment 4

[Duncan Loveday]

With a return statement at the end of each sort function

$ ./js a.js
Quick sort 1000000 elements time=11327
Bubble sort 10000 elements time=22340
$ ./js -j a.js
Quick sort 1000000 elements time=5734
Bubble sort 10000 elements time=6936
$

Comment 5

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: fixes JSOP_STOP issue

keima:src dvander$ ./Opt/js ~/rec.js 
Quick sort 1000000 elements time=5261
keima:src dvander$ ./Opt/js -j ~/rec.js 
Quick sort 1000000 elements time=2239

Looks better with this patch, but the other issue remains.

Comment 6

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 414413 [details] [diff] [review]
fixes JSOP_STOP issue

Will use a separate bug for that, actually.

Comment 7

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/tracemonkey/rev/783ce7ce6ed7

Comment 8

[David Anderson [:dvander] - inactive, e-mail if emergency]

Backed out to see if sudden orange goes away. http://hg.mozilla.org/tracemonkey/rev/2d4418c5ac72

Comment 9

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/783ce7ce6ed7

Comment 10

[David Anderson [:dvander] - inactive, e-mail if emergency]

this had been backed out.

Comment 11

[David Anderson [:dvander] - inactive, e-mail if emergency]

Rebased, re-tested, so pushing again. http://hg.mozilla.org/tracemonkey/rev/12827fc411c1

Comment 12

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/12827fc411c1