379973 - Optimizing tracing when tracer is interested only in objects

Status: RESOLVED INACTIVE

(Core :: JavaScript: GC, enhancement)

Description

[Igor Bukanov]

(In reply to bug 379718 comment 2)
> Created an attachment (id=264002) [details]
> v1
> 
> This works, if used with the patches for bug 340212 and bug 379220. Note that
> we need to protect against too much recursion, so we can't just call
> JS_TraceChildren from within the trace callback (it was nice that the GC took
> care of this for us when we used the gcThingCallback approach). I used a
> nsDeque for storing children that need to be traced.

If one ignores JSTRACE_STRING case, then one can call JS_TraceChildren directly   when the trace kind is nether object nor xml. It would lead to maximum 2 levels of recursion via attom->hidden_atom->object.

This, of cause, binds xpconnect deeply to JS implementation details. So I suggest to add an option to allow to skip invoking the tracer when the thing is not object nor xml. To be presice, I suggest to add a macro like

JS_SET_TRACER_NEEDS_ONLY_OBJECTS(trc)

It would a set a flag altering the tracer invocation in JS_CallTracer in the following way:

1. The tracer would not be invoked when kind == JSTRACE_STRING || kind == JSTRACE_OBJECT.

2. When kind == JSTRACE_XMLQName || kind == JSTRACE_XMLNamespace, the tracer would be called directly on XMLQName.object or XMLNamespace.object

3. When kind == JSTRACE_JSXML and XML is text, the tracer would be invoked for JSXML.object. With other types of XML the tracer has to be invoked on the XML itself as it can have unbounded amount of children.

4. When kind == JSTRACE_ATOM, the tracer is called on object contained in the atom if any.

In this way the tracer would need to deal only with xml and objects and details about the JS interanals would not be exposed to xpconnect.

Comment 1

[Igor Bukanov]

Attachment: implementation v1

This is a straightforward implementation of the plan from comment 0. I tested it via temporarily calling JS_SET_TRACER_WANTS_ONLY_OBJECTS in JS_DumpHeap.

Comment 2

[Brendan Eich [:brendan]]

So a caller of this JS_SET_TRACER_NEEDS_ONLY_OBJECTS(trc) macro would avoid stack overflow only by refraining in its tracer callback from calling JS_TraceChildren for JSTRACE_OBJECT and non-leaf JSTRACE_XML?

I'm being slow today: how does this usefully trace edges for the cycle collector?

/be

Comment 3

[Igor Bukanov]

(In reply to comment #2)
> So a caller of this JS_SET_TRACER_NEEDS_ONLY_OBJECTS(trc) macro would avoid
> stack overflow only by refraining in its tracer callback from calling
> JS_TraceChildren for JSTRACE_OBJECT and non-leaf JSTRACE_XML?

With this option set the tracer callback will only see JSTRACE_OBJECT and JSTRACE_XML.

> how does this usefully trace edges for the cycle collector?

The cycle collector needs to know only about edges that can participates in the XPCOM cycles. So it does not need to know about any edges into JSString and jsdouble as they can not point directly or indirectly to xpcom.

Moreover, when several JS things are singly-linked one can fuse that list into the single edge as it does not affect refcounts. This allows to exclude JSAtom, JSXMLQName and JSXMLNamespace from the graph the cycle collector sees.

What is left is precisely JSObject and JSXML. 

Theoretically if JSXML would not allow for the cycles, it could also be excluded as it is possible to navigate JSXML in constant space. Thus if JSObject instances a1...aN refres to several JSObject instances b1...bM through XML tree, one can pretend that there are direct edges from each a1..aN into each b1..bM and enumerate these pseudo-edges when tracing XML tree in constant space. But even in that theoretical case one still wants to refcount JSXML to trace the potentially unbounded JSXML structure only once, not N times when tracing each a1..aN.

And in practice since JSXML can form cycles with itself its ref counting is a must.

even JSXML can be excluded as 

Comment 4

[Brendan Eich [:brendan]]

> even JSXML can be excluded as 

Sorry, your last line looks cut off -- what were you saying?

/be

Comment 5

[Johnny Stenback (:jst)]

Igor, can you follow up on brendans last question? 

Comment 6

[Igor Bukanov]

(In reply to comment #4)
> > even JSXML can be excluded as 
> 
> Sorry, your last line looks cut off -- what were you saying?

The last line was bogus. The comments ends before it.

Comment 7

[Brendan Eich [:brendan]]

Fresh patch? I'll review same day.

/be

Comment 8

[Igor Bukanov]

(In reply to comment #7)
> Fresh patch? I'll review same day.

I still consider options to exclude XML from the picture completely. It seems the only way to archive this is to duplicate what the cycle and this is pointless. So it is time to update the patch indeed.

Comment 9

[Peter Van der Beken [:peterv]]

(In reply to comment #3)
> (In reply to comment #2)
> > So a caller of this JS_SET_TRACER_NEEDS_ONLY_OBJECTS(trc) macro would avoid
> > stack overflow only by refraining in its tracer callback from calling
> > JS_TraceChildren for JSTRACE_OBJECT and non-leaf JSTRACE_XML?
> 
> With this option set the tracer callback will only see JSTRACE_OBJECT and
> JSTRACE_XML.

And should still avoid stack overflow by not calling JS_TraceChildren, right? What'd be nice to have is a tracer that calls the callback for JSTRACE_OBJECT and JSTRACE_XML and then recursively traces (and avoids stack overflow :-)). That way the callback wouldn't have to recurse and deal with stack overflow.

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 264054 [details] [diff] [review]
implementation v1

Need new patch -- is this bug still wantfix?

/be

Comment 11

[Igor Bukanov]

I am not working on the bug.

Comment 12

[Olli Pettay [:smaug][[e-mail]]]

Would this optimize js_TraceObject/JS_CallTracer calls during CC?
When Shark-profiling cycle collector, I'm seeing very deep
js_TraceObject/JS_CallTracer recursions and lots of time is spent somewhere there.
(Another slow thing is GCGraphBuilder::NoteScriptChild)

Comment 13

[Ryan VanderMeulen [:RyanVM]]

Is this still valid?

Comment 14

[Andrew McCreight [:mccr8]]

This is talking about the JSTrace infrastructure for looking through the heap, not the trace compiler.

I guess something along these lines could avoid some work in the CC.  I'm not sure how much, though.

Comment 15

[André Bargull [:anba]]

Old bug without progress, not even sure if this relevant anymore, comment #1 refers to various e4x things which aren't even present anymore.

Comment 16

[Andrew McCreight [:mccr8]]

This bug seems to be proposing a specialized tracer for the cycle collector, because the CC is only interested in certain kinds of JS GC things. I'm not sure of the details of the JS tracer to know if it is relevant.