989379 - [meta] Reduce arena fragmentation

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Compacting GC (bug 650161) is the ultimate fix for fragmentation within arenas. However, that won't be finished for some time, and there may be some cheap ways to reduce arena fragmentation in the meantime.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Instrument creation of objects

This patch prints out an entry for every object allocated, showing its AllocKind. I've distinguished AllocateObject() and AllocateObjectForCacheHit(), which I think are the two places where objects are allocated.

Here's an example distribution from a session in which I opened a few news sites (nytimes.com, techcrunch.com, etc) and also ran Octane.

10612066 counts:
( 1) 3347381 (31.5%, 31.5%): obj: object4_background
( 2) 1628625 (15.3%, 46.9%): obj: object8_background
( 3) 1276185 (12.0%, 58.9%): obj: object2_background
( 4) 833787 ( 7.9%, 66.8%): oCH: object8_background
( 5) 745752 ( 7.0%, 73.8%): oCH: object2_background
( 6) 617083 ( 5.8%, 79.6%): obj: object12_background
( 7) 597602 ( 5.6%, 85.2%): oCH: object4_background
( 8) 584218 ( 5.5%, 90.8%): obj: object16_background
( 9) 529848 ( 5.0%, 95.7%): oCH: object12_background
(10) 183196 ( 1.7%, 97.5%): oCH: object16_background
(11) 105705 ( 1.0%, 98.5%): obj: object4
(12)  56269 ( 0.5%, 99.0%): obj: object0_background
(13)  38266 ( 0.4%, 99.4%): oCH: object4
(14)  32735 ( 0.3%, 99.7%): obj: object2
(15)  17985 ( 0.2%, 99.8%): oCH: object0_background
(16)  13334 ( 0.1%,100.0%): oCH: object2
(17)   2019 ( 0.0%,100.0%): obj: object8
(18)    964 ( 0.0%,100.0%): obj: object16
(19)    522 ( 0.0%,100.0%): oCH: object8
(20)    342 ( 0.0%,100.0%): obj: object12
(21)    248 ( 0.0%,100.0%): oCH: object12

(You can get output similar to this with 'sort | uniq -c | sort -r -n'.)

The most notable thing is that less than 2% of objects are non-background-finalizable objects.

We've also got the various non-object AllocKinds (shapes, scripts, etc.) which this patch doesn't cover.

Comment 2

[Nicholas Nethercote [inactive]]

See also bug 989367.

Comment 4

[Andrew McCreight [:mccr8]]

Bug 989367 has some information about how this is showing up on B2G in particular, and how I wrote a script to analyze a JS heap dump to determine arena fragmentation, which could be useful.

Comment 5

[Nicholas Nethercote [inactive]]

Attachment: Instrument creation of objects

An updated patch which fixed a bug in the previous patch that caused some objects to be counted twice. I also removed the obj/oCH distinction, which wasn't useful. In this run, non-background-finalizable objects were 2.6% of all objects.

6824228 counts:
( 1) 2908072 (42.6%, 42.6%): obj: object4_background
( 2) 1303408 (19.1%, 61.7%): obj: object8_background
( 3) 855380 (12.5%, 74.2%): obj: object12_background
( 4) 847536 (12.4%, 86.7%): obj: object2_background
( 5) 673527 ( 9.9%, 96.5%): obj: object16_background
( 6) 151020 ( 2.2%, 98.8%): obj: object4
( 7)  55774 ( 0.8%, 99.6%): obj: object0_background
( 8)  27112 ( 0.4%,100.0%): obj: object2
( 9)   1567 ( 0.0%,100.0%): obj: object8
(10)    524 ( 0.0%,100.0%): obj: object16
(11)    308 ( 0.0%,100.0%): obj: object12

Comment 6

[Terrence Cole [:terrence]]

Attachment: spark_arenas_heap_visualization-v0.diff

A visualization of the heap that prints spark-lines for arena usage at every gc. It's pretty raw at this point, but could be useful for qualitative analysis of any algorithmic changes we make.

Comment 8

[Nicholas Nethercote [inactive]]

Bug 999926 has some test pages that might be useful (at www.mangahere.com).

Comment 10

[Nicholas Nethercote [inactive]]

Terrence thought this might be a contributing factor:

>/*
> * We cannot search the arena list for free things while the
> * background finalization runs and can modify head or cursor at any
> * moment. So we always allocate a new arena in that case.
> */

I tried instrumenting allocateFromArenaInline() and got the following numbers while browsing through a few sites for a few minutes:

> 278600 counts:
> ( 1) 147141 (52.8%, 52.8%): alloc: old
> ( 2) 130215 (46.7%, 99.6%): alloc: new genuine
> ( 3)   1244 ( 0.4%,100.0%): alloc: new due to BF

Only 0.4% of calls ended up hitting the BF case, which isn't high. Perhaps it's higher on other workloads or hardware configurations, but there is no smoking gun for now.

Comment 11

[Nicholas Nethercote [inactive]]

Comment on attachment 8398997 [details] [diff] [review]
spark_arenas_heap_visualization-v0.diff

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

::: js/src/gc/Heap.h
@@ +172,5 @@
>      }
>  
> +    size_t size() const {
> +        return last - first;
> +    }

This is incorrect:
- If this isn't the last freespan, it's |thingSize| too small.
- Otherwise, it's 1 too small.

I'm attempting to rewrite FreeSpan to make it simpler and saner.

Comment 12

[Nicholas Nethercote [inactive]]

Attachment: Visualize arenas

This is a revised, rebased version of Terrence's sparklines patch. Changes of
note are as follows.

- Arenas are now labelled with kind names ("object0", "shape", etc) instead of
  kind numbers.

- The size calculation is correct.

- There's a comma in each line to separate the current freeLists[] arena
  (printed first) from the other arenas (printed subsequently).

- I got rid of the colour coding. It was nice, but I kept wanting to pipe the
  output to file and view it in a text editor and it didn't work for that. I'm
  using "X" to represent an arena with no free space, and "><" marks to
  indicate the cursor arena, like so:

           object0: X,
        bg-object0: X,
           object2: X,XX>█<▅▇▆▄▄▄▅▆██▇▇█▅▅▆▆▆▇▁▃▇▆▆▆▇▅▄▆▇▆▇▅▆▆▅█▆▆▄▃▄▇▅▅▄▆▆▄▅▄▄▄▆▄▅▄▃▄▅█▃▃▄▅▃▂▃▂▂▁▃▂▂
        bg-object2: X,
           object4: X,XXXXXXXXXXXXXXXX>▅<▃▇▄▇▅▅▆▅▆▄▅▅▄▅▄▅▃▄▄▄▆▅▃▂▃▃▄▄▁▃▄▅▃

Comment 13

[Nicholas Nethercote [inactive]]

(In reply to Nicholas Nethercote [:njn] from comment #12)
> Created attachment 8416333 [details] [diff] [review]
> Visualize arenas
> 
> This is a revised, rebased version of Terrence's sparklines patch. Changes of
> note are as follows.

Oh: it applies on top of the patches from bug 1004790 and bug 1004816.

Comment 14

[Nicholas Nethercote [inactive]]

Comment on attachment 8398997 [details] [diff] [review]
spark_arenas_heap_visualization-v0.diff

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

::: js/src/jsgc.h
@@ +466,5 @@
>      }
>  
> +    ArenaHeader *getCursorArena(AllocKind thingKind) const {
> +        ArenaHeader **cursor = arenaLists[thingKind].cursor;
> +        return cursor ? *cursor : nullptr;

FWIW, this code gives the correct answer but is more complicated than it needs to be. |cursor| is never null, so |return *cursor;| would suffice. (I'm in the process of encapsulating and adding better comments to ArenaList, which will make things like this easier to understand.)

Comment 15

[Nicholas Nethercote [inactive]]

I was wondering how often we allocate a new arena in a zone despite the fact
that we have one or more non-full arenas of the right kind. We already know
that BF can cause this to happen, but I found that there's another case that
happens more often, and it's caused by incremental GC.

For example, during some brief browsing, here's the breakdown:
- 96.6% of arenas had to be allocated because there were no non-full arenas 
-  0.5% of arenas had to be allocated due to BF
-  2.8% of arenas didn't have to be allocated -- there was one non-full arena
   we could have used instead

This last case is the bad one. Here's how it can happen. The following diagrams
are inspired by Terrences sparklines patch. Each line represents all the arenas
of a particular kind within one zone. '>' is the cursor, which sits between
arenas. An 'X' is a full arena. An '.' s a non-full arena. '[]' around an arena
indicate that it's pointed to by freeLists[kind]; if there's no '[]' it means
freeLists[kind] is empty.

Here's the sequence of interest.

>   >            start with an empty arena list
> 
>   [.]>         the first thing is allocated; freeList[] is now set
> 
>   [X]>         allocate more things until the first arena is free
> 
>   [.]X>        allocate one more thing; a new arena is allocated, and
>                 freeList[] is updated
> 
>   [.]XXX>      allocate a bunch more to give us four arenas, the last of
>                which is half-full
> 
>   .XXX>        Collect() occurs; the list is not finalized but freeLists[] is
>                reset as empty, and so we lose our pointer to our
>                half-filled arena
> 
>   [.].XXX>     do another allocation; the half-filled arena isn't used

That half-filled arena will sit under-utilized for a while, until this arena
list is finalized (I think).

Instrumentation indicates that freeLists[] is reset as empty due to this
purge() call within BeginMarkPhase():

    if (rt->gc.isIncremental) {
        for (GCZonesIter zone(rt); !zone.done(); zone.next())
            zone->allocator.arenas.purge();
    }

If I disable incremental GC, these bad arena allocations go away.

billm, does it seem possible to avoid this problem? I greatly dislike the whole
thing where the current arena gets marked as full in its own header but marked
as non-full in freeLists[], and we have all this copying back and forth there.
I tried removing it but hit all sorts of problems, so it's playing a bigger
role than I currently understand.

Comment 16

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

2.8% seems like a high number. I wonder how you're measuring.

There's an explanation of this code in bug 774104 comments 2 and 5. As background, consider that any object allocated during incremental GC is automatically considered to be live for that GC. For efficiency, we keep track of which objects were allocated during incremental GC with a single flag on the arena. So one object allocated during incremental GC prevents the entire arena from being collected in that GC.

The purge calls are trying to work around that issue. If we have an arena that we're allocating into before the GC started, we can:
1. Set the allocatedDuringIncremental flag on this arena when the GC starts. In that case, all the objects in that arena will be marked and therefore cannot be collected.
2. Or, purge the arena from the freelist when the GC starts. In that case, we'll stop allocating into that arena for the time being. When the GC finishes, we'll reconstruct the freelist and we'll be able to allocate into that arena again (this often happens on the background thread).

At the time, it seemed better to me to choose option 2. The free cells in the arena will only be unavailable for allocation during the GC, which is usually pretty short. And there's at most one arena per (finalizekind,zone) pair that this can happen to in a given GC. I don't think it should be possible for them to build up over time. So 2.8% seems quite high to me.

Comment 17

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Also, I noticed while looking over the code that prepareForIncrementalGC no longer seems to serve any purpose. At the end of the first slice, all the arenas should be purged, so there should be no need to set allocatedDuringIncremental on anything. In later slices, the flag should already be set. Maybe we should put off removing it until we decide what to do about purge, though.

Comment 18

[Nicholas Nethercote [inactive]]

Attachment: Instrument arena allocations

This is the instrumentation patch. I just did another run and here's the
aggregated results:

( 1)  41592 (97.6%, 97.6%): new arena with 0 non-full arenas present
( 2)    625 ( 1.5%, 99.0%): new arena with 1 non-full arenas present
( 3)    402 ( 0.9%,100.0%): new arena due to BF

So, 1.5% that time.

Comment 19

[Nicholas Nethercote [inactive]]

Another odd thing I was seeing sometimes at start-up:

> bg-object16: X▅>11111111111111111

This means we had a Zone with the following bg-object16 arenas list: a full arena (X), a half-full arena, the cursor, and then a bunch of arenas each with a single object.

I eventually worked out that this is caused by MergeCompartments -- we have several different zones that each allocate one bg-object16 and then they get merged into a single compartment. This relates to off-thread parsing, AFAICT. In the cases I've seen it doesn't hang around for a long time, so it's not a obvious problem. Though I wonder if it could ever become pathological.

Comment 20

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

By the way, there's no reason we can't comment out that purge call. Its purpose is to save memory, so we should only keep it if it's doing that.

Comment 21

[Nicholas Nethercote [inactive]]

Bug 1016264 has a site that might allow us to reproduce this problem reliably (albeit slowly).

Comment 22

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: Visualize arenas

Now that bug 1017165 has landed, here's an updated version of this patch. This version:

1) Rebases across several things, including Symbols landing and GCRuntime state being made private.

2) Updates the size calculation to be (I think) more obviously correct (and independent of the arena size, but s/4096/ArenaSize/ would have achieved that as well).

3) Indicates the arena supplying the currently active free list by wrapping it in [ ] (and no longer duplicates it at the front of the list).

4) Removes the < after the arena following the cursor. The cursor conceptually sits between arenas, and it's obvious from the > which arena follows the cursor already.

5) Removes the color coding functions altogether. They could be easily added back, but I don't think they serve much purpose at this point (especially with arenas being sorted by the number of free things now) and were already commented out in the previous version.

Comment 23

[Emanuel Hoogeveen [:ehoogeveen]]

Attachment: Visualize arenas

The previous version lost information on how many objects are free in the free list; this version copies the free lists in before visualizing the arenas. In addition I made it show the cursor even if it's sitting at the end of the list, to avoid confusion.

(In reply to Emanuel Hoogeveen [:ehoogeveen] from comment #22)
> 3) Indicates the arena supplying the currently active free list by wrapping
> it in [ ] (and no longer duplicates it at the front of the list).

Here's an example of how this looks (hopefully the blocks show up right for everyone):
string: XXXXX[▆]>▃▃▃▂▂▂▂▁▁▁▁

Comment 24

[Nicholas Nethercote [inactive]]

Given the great progress that jonco's been making on compacting GC, and the lack of progress I was able to make here, I don't think this bug will end up going anywhere. Please reopen if you disagree.