195385 - jsparse.c suggestion: avoid recursion in RecycleTree

Status: VERIFIED FIXED

(Core :: JavaScript Engine, enhancement, P1)

Description

[Igor Bukanov]

Currently RecycleTree uses recursion to flatten a parse subtree into a recycled
list. But this uncontrolled recursion that can trigger potentially a stack
overflow can be avoided if tree flattening will be delayed until the subtree
root is reused. 

To implement this, RecycleTree can simply append the subtree root to the
recycled tree and only when the root node will re-used, its direct children will
be recycled.

This setup will bring another advantages if the parser recycles more nodes then
it needs, since during recycling the children of unused subtree roots will not
be touched at all.

Comment 1

[Igor Bukanov]

Attachment: Patch to implement the above suggestions

I tried to preserve the current assertion checks semantics and recycling debug
counting in RecycleTree with the patch, but I may miss something in this area.

Comment 2

[Phil Schwartau]

Reassigning, and cc'ing Brendan for consideration of this patch -

Comment 3

[Brendan Eich [:brendan]]

Igor, great idea.  I took your patch and reduced old open-coded
JS_ARENA_ALLOCATE macro calls (my fault) further, to avoid both
ConsumeRecycledHead and its callers having to load tc->nodeList, and then do the
arena allocation if that list is empty.  I also fixed the METER_PARSENODES code
that lacked a pn-> in front of pn_count ;-).  Patch (diff -u and -wu) in a moment.

/be

Comment 4

[Brendan Eich [:brendan]]

Attachment: my take on Igor's patch

Comment 5

[Brendan Eich [:brendan]]

Attachment: diff -w version of last patch

For easier reviewing, but I'll request r=shaver on the last patch.

/be

Comment 6

[Phil Schwartau]

The patch passes the JS testsuite on both WinNT and Linux.
I ran it in both the debug and optimized JS shells.

No test regressions were observed -

Comment 7

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 115948 [details] [diff] [review]
diff -w version of last patch

I like it.  I'd like it more if we inlined RecycleNode, since it's so tiny, but
we don't have a good JS_INLINE to use, so I'll live.

r=shaver.

Comment 8

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 115947 [details] [diff] [review]
my take on Igor's patch

I meant to r+ this one, alas.

Comment 9

[Brendan Eich [:brendan]]

Inlining can blow your icache; I'll let compilers be brave about it, if not
smart (a static function whose address is not taken can be inlined everywhere
that it's called if the compiler thinks that wins).

I did make one more change: I eliminated the static forward prototype for
NewOrRecycledNode, by moving RecycleTree and NewOrRecycledNode up above the
latter's first caller, NewParseNode (where the static forward was).

Thanks again to Igor, and thanks to shaver for the review+ -- checked in.

/be

Comment 10

[Phil Schwartau]

Checkin verified; passes the JS testsuite on Linux and WinNT -