Closed Bug 528486 Opened 15 years ago Closed 15 years ago

eliminating GCF_CHILDREN flag

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(2 files, 1 obsolete file)

Currently the garbage collection implementation uses GCF_CHILDREN to flag the GC things that are marked but for which a call to JS_TraceChildren is deferred. This allows the GC to avoid too deep recursion during the marking phase. GCF_CHILDREN is stored in the flag byte of GC things. This prevents replacing the byte flag with a mark bitmap for better performance as suggested in the bug 528200. So the idea is to remove GCF_CHILDREN.

The observation here is that the GC arena already contains a bitmap for a fast lookup of deferred GC things. The bitmap spans just one word so a fast lookup of an arbitrary set bits in the bitmap can be done using count-leading-zeros machine instructions. As such each bit in the bitmap covers several things in the arena and GCF_CHILDREN is used to distinguish the deferred things from other marked-and-scanned-for-children things. This avoids unnecessary JS_TraceChildren calls.

But this is just an optimization as the GC graph must allow repeated traversal of its nodes. In particular, the cycle collector and various GC heap traversal tools may call JS_TraceChildren several times for the same thing so doing that call from the GC itself should be fine. Thus at worst the removal of GCF_CHILDREN implies that for some truly pathological object graphs the marking phase of the GC will run 4 times slower. Here 4 comes from the maximum number of things per lookup bitmap that is archived on 32 bit system for JSObject. There we have less than 128 objects per arena leading to 4 things per bitmap's bit.

In practice the slowdown should not happen as the object graph where just handful of GC things will be deferred requires a very special setup.
Attached patch v1 (obsolete) — Splinter Review
The patch implements the idea from the comment 0, consolidates comments about non-recursive GC marking in one place and uses consistently "mark", not "trace" in various function and field names. The patch also removes the cx parameter from js_IsAboutToBeFinalized as this parameter is not used there.
Attachment #412380 - Flags: review?(brendan)
Comment on attachment 412380 [details] [diff] [review]
v1

>+     * A link field for the list of arenas with marked things that haven't yet
>+     * been scanned for live children. The field is encoded as arena's page to

"as arena's page" is a bit terse, or potentially confusing. Could say "to hold only the high-order arena-counting bits", or something like that.

>+ * To implement such delayed marking of the children with a minimal overhead

s/a minimal/minimal/

>+ * for a normal case of a sufficient native stack the code adds two fields to

s/a normal case/the normal case/
s/a sufficient/sufficient/

Add a comma after "native stack".

>+ * JSGCArenaInfo. The first field, JSGCArenaInfo::prevUnmarkedPage, links all
>+ * arenas with delayed things into a stack list with the top of stack pointer in

s/a stack top/the pointer to stack top/

>+ * JSRuntime::gcUnmarkedArenaStackTop. DelayMarkingChildren adds arenas to the
>+ * stack as necessary while MarkDelayedChildren picks the arenas from the
>+ * stack until it empties.

s/picks/pops/

Nit: does ThingsPerUnmarkedBit need to be static inline, or with C++ can it be just inline now?

>          * The following assert verifies that the current arena belongs to the
>+         * unmarked stack, since DelayMarkingChildren ensures that even for

s/for/for the/

>+         * stack's bottom prevUnmarkedPage != 0 but rather points to itself.

comma after "bottom".

r=me with these nits picked. Thanks,

/be
Attachment #412380 - Flags: review?(brendan) → review+
Attached patch v2Splinter Review
patch with nits addressed
Attachment #417336 - Flags: review+
Attached patch v2Splinter Review
patch with nits addressed
Attachment #412380 - Attachment is obsolete: true
Attachment #417337 - Flags: review+
https://hg.mozilla.org/tracemonkey/rev/71d3c73a6337
Whiteboard: fixed-in-tracemonkey
Blocks: 534590
http://hg.mozilla.org/mozilla-central/rev/71d3c73a6337
Status: NEW → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
blocking2.0: ? → ---
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: