517199 - Typed GC free lists

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

+++ This bug was initially created as a followup for bug #516226 comment 2 +++

Currently GC free lists are based on the size of allocated things. This requires to store the type information in the GC flags. As a consequence during finalization the code has to take an extra dispatch on the thing's type to choose the finalizer. 

To remove this overhead a typed free lists can be used with one free list per finalizer. It would allow to to choose the finalizer outside the main sweep loop.

Comment 1

[Igor Bukanov]

Attachment: v1 - newborn refactoring

Here is a preparation patch to refactor newborn roots in preparation for typed lists.

Comment 2

[Igor Bukanov]

Attachment: v1 - typed free lists

Here is an implementation itself that uses template inline function to choose the finalizer only once per allocation list. For the following test case where the GC is dominated by the finalization the patch speeds up the GC timing by 10-15% depending on CPU:

function test()
{
    var array = [];
    for (var j = 0; j != 12; ++j) {
        var array2 = [];
        for (var i = 0; i != 1e5; ++i) {
            array2.push({});
            array2.push("test"+i);
        }
        array.push(array2);
    }
    return array;
}

test();
var t = Date.now();
gc();
print(Date.now() - t);

The benchmark is rather sensitive to the amount of if checks in the finalizer. It should possible to make things run faster via using few more typed free lists like separated free lists for dependent strings or fast arrays. But that can be costly from the heap fragmentation point of view especially in view of bigger GC arenas.

Comment 3

[Igor Bukanov]

Attachment: v2 - newborn refactoring

This patch decouples newborn weak roots from the GCX_ enumeration and avoids passing gcflags to various js_NewGCSomething functions to minimize the following patch.

Comment 4

[Igor Bukanov]

Attachment: v2 - typed free lists

The patch implements that idea about typed GC lists to optimize the finalization. The patch uses specialized arena list finalizers to avoid checks for external string type and cx->debugHooks->objectHook which is particularly costly. Still there are few more possibilities for faster finalization. I will file them as separated bugs.

Comment 5

[Andreas Gal :gal]

SFX uses a template class for each GC arena type. Do you think thats worth a try? It generates more specialized code.

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> SFX uses a template class for each GC arena type. Do you think thats worth a
> try? It generates more specialized code.

What I have seen from benchmarks like in the comment 2 is that the issue is not the choice of the finalizer itself. Rather it is a complexity of the finalizer for each particular type that hurts most.

For example, in that benchmark avoiding cx->debugHooks->objectHook check was responsible for almost 30% of the speedup in the object finalizer. Another example is the check for the deflated bit in the string finalizer. If it would be possible to avoid it, a gain like 10% speedup of string finalization should be possible. So using more specialized GC type is just one of the ways to make things faster.

Comment 7

[Igor Bukanov]

Attachment: v3 - newborn refactoring

The new version fixes aliasing warning in v2 when it stored JSFunction in newbornObject. v3 just extends JSFunction from JSObject to fix that.

Comment 8

[Igor Bukanov]

Attachment: v3 - typed free lists

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 403284 [details] [diff] [review]
v3 - newborn refactoring

> JS_NewExternalString(JSContext *cx, jschar *chars, size_t length, intN type)
> {
>-    JSString *str;
>-
>     CHECK_REQUEST(cx);
>-    JS_ASSERT((uintN) type < (uintN) (GCX_NTYPES - GCX_EXTERNAL_STRING));
>+    JS_ASSERT(uint32(type) < JS_EXTERNAL_STRING_LIMIT);

Is there a need for the uint32 type here rather than uintN or just unsigned? On an ILP64 target this will cost and appear to change semantics, even if it doesn't for reasons that can't be proven with types.

> 
>-    str = js_NewGCString(cx, (uintN) type + GCX_EXTERNAL_STRING);
>+    JSString *str = js_NewGCExternalString(cx, uint32(type));

Ditto (see below on js_NewGCExternalString parameter type).

>+template <typename T, typename NewbornType> static JS_INLINE T*

Nit, pre-existing: newline instead of space before static.

>@@ -1990,17 +1990,17 @@ testReservedObjects:
>             *flagp = GCF_FINAL;
>             goto fail;
>         }
>     } else {
>         /*
>          * No local root scope, so we're stuck with the old, fragile model of
>          * depending on a pigeon-hole newborn per type per context.
>          */
>-        cx->weakRoots.newborn[flags & GCF_TYPEMASK] = thing;
>+        *newbornRoot = (T *) thing;

This is interesting in view of the added NewbornType type-parameter to the template. Is it as strong a claim as we can make about the necessary relationship between T and NewbornType?

>+JSObject*

Space before * (pointer-to declarator mode), same nit throughout.

>+js_NewGCExternalString(JSContext *cx, uint32 type)

Is it necessary or desirable to use uint32 here? A much narrower int type could be used, to match domain, but our general approach is to use natural unsigned and int types for such parameters.

>+JSFunction*
>+js_NewGCFunction(JSContext *cx)
> {
>-    return NewGCThing<JSXML>(cx, flags);
>+    return NewGCThing<JSFunction>(cx, GCX_OBJECT,
>+                                      &cx->weakRoots.newbornObject);

Indentation nit. Could slightly exceed old line length max?

>+struct JSFunction: JSObject {

Space before :, and don't we want public JSObject as the base specifier?

/be

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 403285 [details] [diff] [review]
v3 -  typed free lists

Looks pretty good, but JSALK_ hurts my ears/eyes.

Observing MapArenaListKindToTrace I wonder if MapArenaListToTraceKind would be better. This brings to light JSTRACE_ as the prefix (now-misleading in light of trace-JITting, but still more readable than a JSTK_ or JSTRACEKIND_ prefix).

How about working from GC THING KIND or (better) GC TYPE as the "name seed"?

GC_TYPE_OBJECT
GC_TYPE_FUNCTION
GC_TYPE_STRING
GC_TYPE_XML
GC_TYPE_EXTERNAL_STRING*

Looking for simpler names, fewer magic TLAs.

/be

Comment 11

[Jeff Walden [:Waldo]]

(In reply to comment #10)
> Looks pretty good, but JSALK_ hurts my ears/eyes.

Agreed, although I bet it would do wonders for stiff legs!

Why not FinalizerKind and FINALIZE_OBJECT, FINALIZE_XML, FINALIZE_FUN, &c.?  Throwing out ideas here, less abbreviation is much better.

Comment 12

[Brendan Eich [:brendan]]

The "type" is more than the finalizer, although that's the narrow interpretation.

/be

Comment 13

[Igor Bukanov]

(In reply to comment #10)
> How about working from GC THING KIND or (better) GC TYPE as the "name seed"?

The purpose of that enumeration is just to give names for indexes into the array of free lists. The array is rather specific since it does not include doubles. Moreover, it may not include dependent strings if it would be worth to allocate them on a separated list to avoid running the finalizer for them. So it is not a GC type.

> Why not FinalizerKind and FINALIZE_OBJECT, FINALIZE_XML, FINALIZE_FUN, &c.? 

The names do not corresponds to the finalizers since there are 2 finalizers for object and function and one for all external strings. Still this is a good hint since those list names are for lists containing GC things with finalizers.

So what about JSFAL_ or JSFALK_ aka finalizable arena list kind ?

Comment 14

[Igor Bukanov]

(In reply to comment #13)
> > Why not FinalizerKind and FINALIZE_OBJECT, FINALIZE_XML, FINALIZE_FUN, &c.? 

I started to like this suggesting since "finalize" can be interpreted to "finalize by what ever means but do finalize".

Comment 15

[Igor Bukanov]

(In reply to comment #9)
> >+template <typename T, typename NewbornType> static JS_INLINE T*
NewbornType **newbornRoot
...
> >+        *newbornRoot = (T *) thing;
> 
> This is interesting in view of the added NewbornType type-parameter to the
> template. Is it as strong a claim as we can make about the necessary
> relationship between T and NewbornType?

This requires that NewbornType* is assignable from T*. Since T cannot be void (the function calls sizeof(T)) this implies that NewbornType is either T or subclasses T.

Comment 16

[Igor Bukanov]

Attachment: v4 - newborn refactoring

the new version addresses the comment 9

Comment 17

[Igor Bukanov]

Attachment: v4 - typed free lists

In the new patch I use FINALIZE_ as the prefix following the suggestion from the comment 11.

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 403504 [details] [diff] [review]
v4 -  typed free lists

>+JS_STATIC_ASSERT(FINALIZE_EXTERNAL_STRING_LAST - FINALIZE_EXTERNAL_STRING0 ==
>+                JS_EXTERNAL_STRING_LIMIT - 1);

Nit: indent second line one more space.

r=me with that -- good patch.

/be

Comment 19

[Igor Bukanov]

landed with two changesets:

http://hg.mozilla.org/tracemonkey/rev/19b4c1cacdb8
http://hg.mozilla.org/tracemonkey/rev/47619e6bad9a

Comment 20

[Igor Bukanov]

http://tinderbox.mozilla.org/showbuilds.cgi?tree=TraceMonkey shows a failure in the windows leak test after landing, but the log http://tinderbox.mozilla.org/showlog.cgi?log=TraceMonkey/1254370624.1254373496.12128.gz is unclear.

Comment 21

[Igor Bukanov]

The error logs for failed windows tests shows at the end:

 END OF RUN - NOW DOING SCHEDULED REBOOT; FOLLOWING ERROR MESSAGE EXPECTED 

I am not sure how this could affect the tests.

Comment 22

[Igor Bukanov]

The try server shows a success on Windows. I backed out the back out and relanded the patch assuming that failures on Windows was due to the reboot.

Comment 23

[Igor Bukanov]

I backed out the second patch again due to persistent Windows-only failures on tracemonkey's tinderboxes. If the first part, the newborns changes, will stay, I will file a separated bug for that so that can be tracked separately.

Comment 24

[Igor Bukanov]

Attachment: v5

My current theory about Windows failures is that the patch went too far optimizing the finalizers and made a bug that is visible only on Windows. So here is v4 that just optimizes the switch over GC thing kind without changing the finalizers itself. It is still a win for the benchmarks, so I plan to land this and optimize the finalizers in a different bug. Note also that newborns refactoring was landed as a part of bug 520046.

Comment 25

[Igor Bukanov]

http://hg.mozilla.org/tracemonkey/rev/ee059eb9d9e2

Comment 26

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/ee059eb9d9e2