1464387 - We instantiate too many trace functions

Status: RESOLVED FIXED

(Core :: JavaScript: GC, enhancement)

Description

[Jon Coppeard (:jonco)]

As mentioned in bug 1459577, we instantiate lots of template functions for tracing.  There are 12 trace functions and we instantiate one of each per derived pointer type of which there are currently 40, but there should be many more if we were to count all derived pointer types.

The list of pointer types in gc/Policy.h is also pretty unmanageable, with new types only being added when someone notices they can't link a call to a trace function.

We should make the outermost trace functions into template functions in Tracing.h and the compiler can instantiate the ones it needs.  This should also remove the necessity to have a list of derived pointer types.

Comment 1

[Jon Coppeard (:jonco)]

Attachment: bug1464387-unbloat-trace-functions

Make tracing functions (TraceEdge and friends) inline functions which cast to the base pointer type and call an internal function to do the tracing.  There is now a much smaller set of instantiated function tempales.  This also has the advantage that the null check in TraceNullableEdge is now inline.

I wondered about moving TraceEdgeInternal into a 'detail' namespace or something like that but didn't do it.  Let me know if you think I should.

Comment 2

[Jon Coppeard (:jonco)]

Attachment: bug1464387-unbloat-trace-functions-2

Do the same thing for IsMarked and IsAboutToBeFinalized functions and kill the list of derived GC types in gc/Policy.h.

I spent a while being confused about specialization vs overloading and why the compiler was trying to call the wrong version of a function.  Eventually I remembered that overloading happens first and only then are specializations of the selected function template considered.  So here there are two templated overloads of IsMarkedInternal, not a single template function with a partial specialization as I initially assumed (the latter being illegal).

Again, let me know if you think I should move the *Internal functions somewhere more internal-looking.

Comment 3

[Jon Coppeard (:jonco)]

Attachment: bug1464387-fix-concrete-traceable

The previous patches caused a link failure on Windows.  I'm not sure why, but passing TraceNullableRoot as a function pointer didn't seem to instantiate it.  I changed the root marking functions by adding a specialisation of TraceNullableRoot that means passing this function pointer is unnecessary.

Comment 4

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8980662 [details] [diff] [review]
bug1464387-unbloat-trace-functions

Review of attachment 8980662 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/gc/Marking.cpp
@@ +83,5 @@
>  //   '---------'    '---------'    '--------------------------'       '----------'              //
>  //        \              \                        /                        /                    //
> +//         \              \  .-----------------. /                        /                     //
> +//          o------------->o-|TraceEdgeInternal|-o<----------------------o                      //
> +//                           '-----------------'                                                //

The renaming is the only part I didn't really follow -- both new and old names are fine with me, but nothing really changed, right? DispatchToTracer's name indicated that it is doing a dynamic dispatch to whatever tracing is currently active. As far as I can tell, that is still true of TraceEdgeInternal.

That said, I don't think the verb "dispatch" necessarily helps understanding, so the new name works too. And as for putting it in a detail namespace or something -- meh. Maybe if we were more strict with that convention elsewhere, but "Internal" does the "don't call this directly" job well enough.

Comment 5

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8980670 [details] [diff] [review]
bug1464387-unbloat-trace-functions-2

Review of attachment 8980670 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/gc/Marking.h
@@ +57,5 @@
>  
> +template <typename T>
> +bool IsMarkedInternal(JSRuntime* rt, T* thing);
> +template <typename T>
> +bool IsMarkedInternal(JSRuntime* rt, T** thing); // Note, overload not specialization.

Whoa, you're making my head hurt.

I didn't understand your explanation in the bug (or in this comment.) To me, it seems like this is trivially wrong because if something is looking for IsMarkedInternal(JSRuntime*, JSObject**), then both of these work (with T=JSObject* and T=JSObject, respectively), and the first one is a superset of the second, so the second is unnecessary. And "overload not specialization" is obviously wrong, because you *are* declaring a specialization.

Then I tried to take it out, and found that you're right, you need it. Here's my attempt at why:

You want to declare overloads with completely different bodies for eg JSObject* and JSObject**. template <typename T> IsMI(T*) would match both of those, so if you only had it here then you'd get the same body for T=JSObject and T=JSObject*. You need two declarations to get two different bodies.

That leads to the question of why IsMI(JSObject**) is instantiated using the IsMI(T**) one instead of the IsMI(T*) one. I played around with various things for a while, eventually begging for help on stackoverflow, and apparently you will always get a single instantiation, and the rules for selecting which one are very similar to the rules for selecting an overload (here, the T** is preferred because it is more specialized; it accepts fewer possibilities than T*.) https://stackoverflow.com/questions/50538457/are-all-valid-templates-instantiated

Oh, I see. "// Note, overload not specialization." is just calling out that we didn't just say template <typename T*> or something.

I still don't follow your "overloading happens first and only then are specializations of the selected function template considered"? It seems to me like when the compiler sees

    template bool IsMarkedInternal(JSRuntime*, JSObject**);

it first looks for templates to use and instantiates the second one here. It then uses overloading to choose JSObject** over JSScript** or whatever. So I would say this does the specialization first, then the overload?

I'm not sure what comment would make this more clear for people like me who aren't that familiar with all these template rules. Maybe

// Define two families of overloads. The one accepting a T** is more specialized and will therefore be chosen when possible. It handles forwarded nursery pointers, when applicable.

?

At any rate, I have managed to convince myself of the correctness of this code! :-)

::: js/src/gc/Policy.h
@@ -113,5 @@
> -    FOR_EACH_PUBLIC_GC_POINTER_TYPE(D) \
> -    FOR_EACH_PUBLIC_TAGGED_GC_POINTER_TYPE(D) \
> -    FOR_EACH_INTERNAL_GC_POINTER_TYPE(D) \
> -    FOR_EACH_INTERNAL_TAGGED_GC_POINTER_TYPE(D)
> -

Wow. This is a pretty awesome removal of a (1) large chunk of (2) internal stuff from a public header.

Comment 6

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8980697 [details] [diff] [review]
bug1464387-fix-concrete-traceable

Review of attachment 8980697 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/gc/RootMarking.cpp
@@ +60,1 @@
>  static inline void

Whoa, wait. What's going on? It seems like this is just hardcoding everything to use TraceNullableRoot instead of accepting TraceRoot? Is that because nothing was making use of that, and was null-checking already? Hm... yeah, looks like it. Then does js::DispatchWrapper<ConcreteTraceable>::TraceWrapped() do a null check or not? I guess it just directly calls the function pointer embedded in the root list, and that is... oh, never mind. Please tell me what's going on here, I don't want to do another code dive at the moment! ;-)

I also wonder if just doing

- template <typename T, TraceFunction<T> TraceFn = TraceNullableRoot>
+ template <typename T, TraceFunction<T> TraceFn = TraceNullableRoot<T>>

would have helped? I mean, TraceFn should know the full signature and thus be able to find the right TraceNullableRoot, but... yeesh, these poor compilers!

Comment 7

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #4)
> The renaming is the only part I didn't really follow -- both new and old
> names are fine with me, but nothing really changed, right?

Right, it's just the function is now exposed in the header.  I wanted to make it clear that this is internal and used in the implementation of the TraceEdge functions which 'DispatchToTracer' doesn't achieve for me.

> And as for putting it in a detail
> namespace or something -- meh. Maybe if we were more strict with that
> convention elsewhere, but "Internal" does the "don't call this directly" job
> well enough.

Great, I'll leave it like this then.

Comment 8

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #5)
> You want to declare overloads with completely different bodies for eg
> JSObject* and JSObject**.

In particular we need to handle tagged pointers values (e.g. T = JS::Value) separately from normal pointers (e.g. T = JObject*).

> template <typename T> IsMI(T*) would match both of
> those, so if you only had it here then you'd get the same body for
> T=JSObject and T=JSObject*. You need two declarations to get two different
> bodies.

Yes.

> Oh, I see. "// Note, overload not specialization." is just calling out that
> we didn't just say template <typename T*> or something.

My terse comment is trying to say that these are separate declarations, and that the second is not a specialization of the first (which it looked like to me).  

> I still don't follow your "overloading happens first and only then are
> specializations of the selected function template considered"? It seems to
> me like when the compiler sees
> 
>     template bool IsMarkedInternal(JSRuntime*, JSObject**);
> 
> it first looks for templates to use and instantiates the second one here. It
> then uses overloading to choose JSObject** over JSScript** or whatever. So I
> would say this does the specialization first, then the overload?

I got this from a stackoverflow answer ( https://stackoverflow.com/a/7108123 ) but I'm not sure this is correct any more.  Looking at the spec it seems that both overloads and function template specializations are considered at the same time: http://eel.is/c++draft/over.match.funcs#7

"A given name can refer to one or more function templates and also to a set of overloaded non-template functions.
In such a case, the candidate functions generated from each function template are combined with the set of non-template candidate functions."

The more specialised candidate wins as per: http://eel.is/c++draft/over.match.best#1.7

> I'm not sure what comment would make this more clear for people like me who
> aren't that familiar with all these template rules. Maybe
> 
> // Define two families of overloads. The one accepting a T** is more
> specialized and will therefore be chosen when possible. It handles forwarded
> nursery pointers, when applicable.

Yeah this needs more comments.  I'll try and come up with something.

Comment 9

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #6)
> Whoa, wait. What's going on? It seems like this is just hardcoding
> everything to use TraceNullableRoot instead of accepting TraceRoot?

TraceFn was defaulted to TraceNullableRoot before so there's no change except for the ConcreteTraceable case.

> I also wonder if just doing
> 
> - template <typename T, TraceFunction<T> TraceFn = TraceNullableRoot>
> + template <typename T, TraceFunction<T> TraceFn = TraceNullableRoot<T>>
> 
> would have helped? I mean, TraceFn should know the full signature and thus
> be able to find the right TraceNullableRoot, but... yeesh, these poor
> compilers!

Yeah maybe, but I find this clearer than passing function pointers as template parameters.

Comment 10

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8980697 [details] [diff] [review]
bug1464387-fix-concrete-traceable

Review of attachment 8980697 [details] [diff] [review]:
-----------------------------------------------------------------

Ok yeah, this is fine. It's a little weird that TraceNullableRoot<ConcreteTraceable> is specialized purely so it can choose to *not* be nullable -- or rather, pass that decision on to the function pointer. (This is as opposed to doing the null check directly in Trace{ExactStack,Persistent}RootList and then calling TraceRoot.) But then, the Nullable name is not entirely accurate either -- for pointers, it's a null check, but for other types it might be something like Value::isGCThing().

One result of this, if I traced through everything correctly, is that TraceRoot() called with a ConcreteTraceable appears that it wouldn't work? Maybe that's just a "don't do that, then" type of thing?

At any rate, I agree that this is an improvement over the status quo.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/191538349350
Don't instantiate so many trace functions r=sfink

Comment 12

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #10)
> It's a little weird that
> TraceNullableRoot<ConcreteTraceable> is specialized purely so it can choose
> to *not* be nullable -- or rather, pass that decision on to the function
> pointer.

Oh yeah, I see what you mean.  I'll refactor this slightly to use a separate function that either calls TraceNullableRoot or traces the ConcreteTraceable.

> One result of this, if I traced through everything correctly, is that
> TraceRoot() called with a ConcreteTraceable appears that it wouldn't work?
> Maybe that's just a "don't do that, then" type of thing?

Yes, ConcreteTraceable is an implementation detail of how stack roots work and shouldn't be traced directly.

Comment 13

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/191538349350