528200 - replacing GC thing flags with a mark bitmap

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

With recent changes from bug 517199 and bug 505315 we use only 3 flags per GC thing while still allocating one byte for flags. Moreover, the GCF_CHILDREN flag can be eliminated with slower GC marking phase performance only in truly specially-constructed pathological cases (I will a separated bug about this). That leaves only 2 flags per GC thing, GCF_MARK and GCF_LOCK where the latter is used only as an optimization to avoid hashing JSStrings that are rooted using JS_LockGCThing API.

This suggests to replace the flag bytes with a bitmap storing just the mark flag. The saving from such reduction should be more then enough to compensate for the bigger hash of locked GC things.

Moreover, the saving is enough to afford using fixed-sized bitmap for GC arenas containing things of different sizes. As Andreas Gal suggested, the idea is to use one bit per each 8 bytes of GC things. This will avoid costly integer division and arena->list->thingSize dereferencing when mapping things to flags during the marking phase of the GC leaving some flags unused. On 32 bits this will be tight for JSString while wasting 3 extra bits per each JSOject. This is still a win compared with the current wasting of 7 bits.

Another advantage of this is that it will allow to use the same allocation and marking code for doubles as for the rest of GC things. Currently that is specialized but with fixed-sized flag bitmap that would not be necessary. That should allow to simplify the allocator.

Comment 1

[Igor Bukanov]

Attachment: v1 - double flags changes

The patch changes the code dealing with the mark bitmap for doubles so the bitmap can be cleared with simple memset(, 0, ). It allows sharing of that code with the other types of arenas.

Comment 2

[Igor Bukanov]

Attachment: v1 - gcarena

This patch introduces the JSGCArena struct which size is exactly GC_ARENA_SIZE and whic contains JSGCArenaInfo. The the rest of the code is updated to use this new struct, not JSGCArenaInfo, to refer to GC arenas.

Comment 3

[Igor Bukanov]

Attachment: v1 - mark bitmap

This patch contains the essence of the changes. It replaces the flag bytes with the mark bitmap with an optimized layout to avoid expensive integer divisions during the marking pahse of the GC.

Comment 4

[Igor Bukanov]

Just how expensive the integer division during the marking phase can be deduced from the following benchmark that tries to measure the minimal time of object allocation, marking and finalization:

function test()
{
    var N = 1e6;
    var a = [];
    var time0 = Date.now();
    for(var i = 0; i != N; ++i) {
        a[i] = {};
    }
    var time0 = Date.now() - time0;
    gc();
    var time1 = Date.now();
    gc();
    time1 = Date.now() - time1;
    a = null;
    var time2 = Date.now();
    gc();
    time2 = Date.now() - time2;
    return [time0, time1, time2];
}

// warmup
test();


var min_times = [Infinity, Infinity, Infinity];

for (var i = 0; i != 10; ++i) {
    var times = test();
    min_times[0] = Math.min(min_times[0], times[0]);
    min_times[1] = Math.min(min_times[1], times[1]);
    min_times[2] = Math.min(min_times[2], times[2]);
}
print("Alloc time: "+min_times[0]);
print("GC time all used: "+min_times[1]);
print("GC time all free: "+min_times[2]);


Results before the patch from the comment 3:
Alloc time: 1193
GC time all used: 350
GC time all free: 50

Results after the patch:
Alloc time: 1133
GC time all used: 251
GC time all free: 54

That is, the patch speedups the object marking by 40%. It also show the slowdown of about 10% for the finalization. That can be related to the fact that just accessing a byte flag is faster than accessing a bit in the marking bitmap. Still it should be possible to optimize FinalizeArenaList to make things faster there.

Comment 5

[Igor Bukanov]

Attachment: v1 - mark bitmap

The new patch tunes FinalizeArenaList so now the finalizer is only 1-2% slower compared with the unpatched version while for the marking phase the benchmark still shows 40% win.

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> Created an attachment (id=418564) [details]
> v1 - mark bitmap
> 
> The new patch tunes FinalizeArenaList so now the finalizer is only 1-2% slower
> compared with the unpatched version while for the marking phase the benchmark
> still shows 40% win.

Note that the above numbers are for Atom N270 CPU. For 2.6 GHz Xenon the benchmark show 5% improvement in the marking phase with no changes for the finalization phase.

Comment 7

[Igor Bukanov]

Attachment: v2 - double flags changes

Here is the first of 3 patch updates to sync the changes with TM tip.

Comment 8

[Igor Bukanov]

Attachment: v2 - gcarena

Comment 9

[Igor Bukanov]

Attachment: v2 - mark bitmap

Comment 10

[Igor Bukanov]

review ping

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 419590 [details] [diff] [review]
v2 - double flags changes

Why DOUBLE_ARENA_BITMAP but DOUBLES_ARENA_BITMAP_WORDS (DOUBLES plural)? May as well singularize everywhere for concision and consistency.

Nit: jsbitmap(1) instead of (jsbitmap)1, etc.

r=me with these addressed.

/be

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 419591 [details] [diff] [review]
v2 - gcarena

> const uint32 ARENA_INFO_OFFSET = GC_ARENA_SIZE - (uint32) sizeof(JSGCArenaInfo);

GC_ARENA_SIZE is jsuword, IIRC. Why force the const to uint32 instead of using jsuword or (better) size_t?

Typo: checkAddrress

>     JSGCArena * getPrevUnmarked() const {
Nit: no space after *.

Any reason GetArenaIndex, MakeNewArenaFreeList, etc. are not methods (getIndex, etc.) on JSGCArena? Some want to be static methods, akin to JSGCArena::fromPageStart.

Looks great otherwise but I skimmed a bit. Will r+ fully on next patch addressing above.

/be

Comment 13

[Igor Bukanov]

Attachment: part 1 - double flags changes, v3

The updates patch consistently uses the DOUBLE_ARENA prefix.

Comment 14

[Igor Bukanov]

Attachment: part 2 - gcarena, v3

The new patch fixes the nits from the comment 12 and uses size_t, not uint32, for ARENA_INFO_OFFSET. I have kept most of the current macros and inline methods dealing with arena as-is focusing in this part on JSArenaInfo->JSArena refactoring. The arena methods come in the part 3.

Comment 15

[Igor Bukanov]

Attachment: part 3 - mark bitmap, v3

Comment 16

[Brendan Eich [:brendan]]

Comment on attachment 420539 [details] [diff] [review]
part 2 - gcarena, v3

Sorry for delayed r+, this looks good. Asking gregor to look so he can be a stronger jsgc peer.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 420540 [details] [diff] [review]
part 3 - mark bitmap, v3

I keep thinking I reviewed this...

/be

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 420540 [details] [diff] [review]
part 3 - mark bitmap, v3

>+ * A GC arena contains GC_ARENA_SIZE bytes aligned on GC_ARENA_SIZE boundary.
>+ * The arena holds thing of the same size, JSGCArenaInfo descriptor and a

Nit: "... same size, a JSGCArenaInfo descriptor, and a"

>+ * mark bitmap.
>+ *
>+ * The size of each thing must be dividable by GC_CELL_SIZE, the minimal

Nit: divisible.

>+ * Another advantage of the fixed size of the bitmap is that it allows to put

"allows us to put"

/be

Comment 19

[Gregor Wagner [:gwagner]]

Comment on attachment 420539 [details] [diff] [review]
part 2 - gcarena, v3

+    static JSGCArena * fromPageStart(jsuword pageStart) {

space nit.

Comment 20

[Gregor Wagner [:gwagner]]

Comment on attachment 420540 [details] [diff] [review]
part 3 - mark bitmap, v3

* size of the system word is less then the word size, the sum
* could be less then the arena size. We add the extra space to data.

nit "less than"

Maybe another !isStatic assert in functions with just one "thing" argument like  	
ThingToOffset(void *thing)

Comment 21

[Igor Bukanov]

Attachment: part 2 - gcarena, v4

The new version addresses the nits.

Comment 22

[Igor Bukanov]

Attachment: part 3 - mark bitmap, v4

In the new version, besides addressing the nits, I also renamed GC_CELL_SIZE_(SHIFT|MASK) into GC_CELL_(SHIFT|MASK) for consistency in naming between GC_ARENA_(SHIFT|SIZE|MASK) and GC_CELL_(SHIFT|SIZE|MASK).

Comment 23

[Brendan Eich [:brendan]]

Oops, should have caught that SIZE/SHIFT/MASK name nit. Thanks!

/be

Comment 24

[Igor Bukanov]

https://hg.mozilla.org/tracemonkey/rev/d26338c22cc6

Comment 25

[Robert Sayre]

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