Oilpan heap compaction question and possible bug.

[s1341]

Hi,

I'm confused about Oilpan's heap compaction.

From what I can tell from the code, it looks like sweepAndCompact (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapPage.cpp?type=cs&l=449), checks IsCompactingArena (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=65) before performing a sweep and compact operation.

IsCompactingArena consults the compactable_arenas_ bitfield (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=148) in order to check if the given arena is compactable.

It appears that this is set from HeapCompact::UpdateHeapResidency (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=365), which seems to set only arenas from  BlinkGC::kVector1ArenaIndex to BlinkGC::kHashTableArenaIndex as compactable.

So my question is: are normal arenas really not compactable? Isn't this bad as I'm certain that those arenas can become very fragmented over time?

In addition, there appears to be a bug in HeapCompact::UpdateHeapResidency. At line 387 (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=387), we see the following:

    compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));

Note that the index used for the shift operation adds i to BlinkGC::kVector1ArenaIndex. However, if we look at the loop itself (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=373) we see that it is:

    for (int i = BlinkGC::kVector1ArenaIndex; i <= BlinkGC::kHashTableArenaIndex;

           ++i)

Note that i begins at BlinkGC::kVector1ArenaIndex. This means that the first shift index will actually be twice the value of  BlinkGC::kVector1ArenaIndex, instead of  BlinkGC::kVector1ArenaIndex itself. This seems wrong.

Is it possible that no compaction is occurring at all on any arena as a result of this bug?

Thanks

s1341

[Kentaro Hara]

+Sigbjorn

--
You received this message because you are subscribed to the Google Groups "blink-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/blink-dev/d10c3f32-5538-4a70-9a9d-373feb8dde86%40chromium.org.

--

Kentaro Hara, Tokyo, Japan

[Sigbjorn Finne]

Den 5/25/2017 10:26, skreiv s1341:
> Hi,
>
> I'm confused about Oilpan's heap compaction.
>

Hi,

thanks for the careful study of the heap compaction code, I hope I can clear up a point of confusion or two.. :)

> From what I can tell from the code, it looks like sweepAndCompact
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapPage.cpp?type=cs&l=449),
> checks IsCompactingArena
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=65)
> before performing a sweep and compact operation.
>
> IsCompactingArena consults the compactable_arenas_ bitfield
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=148)
> in order to check if the given arena is compactable.
>
> It appears that this is set from HeapCompact::UpdateHeapResidency
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=365),
> which seems to set only arenas from BlinkGC::kVector1ArenaIndex to
> BlinkGC::kHashTableArenaIndex as compactable.
>
> So my question is: are normal arenas really not compactable? Isn't this bad
> as I'm certain that those arenas can become very fragmented over time?
>

Implementing heap compaction for those/all arenas have been considered, and might be in the future, but the first cut at compaction doesn't support movement of objects (as a result of compaction) that are part of arbitrary object graphs, just a limited form for container objects. I've certainly observed badly fragmented normal arenas over time on sites (normal4, in particular.)

The design writeup that went along with the heap compaction intent-to-implement,

https://docs.google.com/document/d/1k-vivOinomDXnScw8Ew5zpsYCXiYqj76OCOYZSvHkaU

explains this in a bit more detail.

> In addition, there appears to be a bug in HeapCompact::UpdateHeapResidency.
> At line 387
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=387),
> we see the following:
>
> compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>

Great catch - a bug that snuck in at some point; I'll fix. It effectively means that only inline-vector and hash table arenas were being compacted. The latter is certainly the arena that Blink manages to fragment the most, but we clearly do want all the vector arenas compacted also.

cheers
--sigbjorn

[ma...@shmarya.net]

On Thursday, May 25, 2017 at 4:04:17 PM UTC+3, sof wrote:

Den 5/25/2017 10:26, skreiv s1341:
> Hi,
>
> I'm confused about Oilpan's heap compaction.
>

Hi,

thanks for the careful study of the heap compaction code, I hope I can clear up a point of confusion or two.. :)

>  From what I can tell from the code, it looks like sweepAndCompact
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapPage.cpp?type=cs&l=449),
> checks IsCompactingArena
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=65)
> before performing a sweep and compact operation.
>
> IsCompactingArena consults the compactable_arenas_ bitfield
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.h?type=cs&l=148)
> in order to check if the given arena is compactable.
>
> It appears that this is set from HeapCompact::UpdateHeapResidency
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=365),
> which seems to set only arenas from  BlinkGC::kVector1ArenaIndex to
> BlinkGC::kHashTableArenaIndex as compactable.
>
> So my question is: are normal arenas really not compactable? Isn't this bad
> as I'm certain that those arenas can become very fragmented over time?
>

Implementing heap compaction for those/all arenas have been considered, and might be in the future, but the first cut at compaction doesn't support movement of objects (as a result of compaction) that are part of arbitrary object graphs, just a limited form for container objects. I've certainly observed badly fragmented normal arenas over time on sites (normal4, in particular.)

The design writeup that went along with the heap compaction intent-to-implement,

 https://docs.google.com/document/d/1k-vivOinomDXnScw8Ew5zpsYCXiYqj76OCOYZSvHkaU

explains this in a bit more detail.

So far as I can tell from that doc, the reason we don't have compaction for normal pages is just because of the complexity of updating N pointers after an object has moved? Isn't this a solved problem though? V8 has a fully compacting heap, doesn't it?

Is there any plan to implement compaction for the normal arenas?

 

> In addition, there appears to be a bug in HeapCompact::UpdateHeapResidency.
> At line 387
> (https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/heap/HeapCompact.cpp?type=cs&l=387),
> we see the following:
>
>      compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>

Great catch - a bug that snuck in at some point; I'll fix. It effectively means that only inline-vector and hash table arenas were being compacted. The latter is certainly the arena that Blink manages to fragment the most, but we clearly do want all the vector arenas compacted also.

 Glad to have helped. Do you want me to open a crbug for this?

 

cheers
--sigbjorn

[Sigbjorn Finne]

Den 5/25/2017 15:45, skreiv ma...@shmarya.net:
>
....

>>> So my question is: are normal arenas really not compactable? Isn't this
>> bad
>>> as I'm certain that those arenas can become very fragmented over time?
>>>
>>
>> Implementing heap compaction for those/all arenas have been considered,
>> and might be in the future, but the first cut at compaction doesn't support
>> movement of objects (as a result of compaction) that are part of arbitrary
>> object graphs, just a limited form for container objects. I've certainly
>> observed badly fragmented normal arenas over time on sites (normal4, in
>> particular.)
>>
>> The design writeup that went along with the heap compaction
>> intent-to-implement,
>>
>>
>> https://docs.google.com/document/d/1k-vivOinomDXnScw8Ew5zpsYCXiYqj76OCOYZSvHkaU
>>
>> explains this in a bit more detail.
>>
>> So far as I can tell from that doc, the reason we don't have compaction
> for normal pages is just because of the complexity of updating N pointers
> after an object has moved? Isn't this a solved problem though? V8 has a
> fully compacting heap, doesn't it?
>

It is known how to implement general compaction, but for various tedious reasons that hasn't happened yet.

One point worth mentioning wrt v8 is if it is worth adding more Blink GC sophistication (like compaction, like generational collection, like concurrency or parallel schemes, ...) instead of building on top of v8's mature and extensive GC support instead. I hear there are plans afoot to do something in that area, or at least it is being carefully considered.

> Is there any plan to implement compaction for the normal arenas?
>

see above :)

>>> compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>>>
>>
>> Great catch - a bug that snuck in at some point; I'll fix. It effectively
>> means that only inline-vector and hash table arenas were being compacted.
>> The latter is certainly the arena that Blink manages to fragment the most,
>> but we clearly do want all the vector arenas compacted also.
>>
>
> Glad to have helped. Do you want me to open a crbug for this?
>

CL in flight, created crbug.com/726335 to track it; Cc:ed your email.

--sigbjorn

[ma...@shmarya.net]

On Thursday, May 25, 2017 at 5:42:58 PM UTC+3, sof wrote:

Den 5/25/2017 15:45, skreiv ma...@shmarya.net:
>
....
>>> So my question is: are normal arenas really not compactable? Isn't this
>> bad
>>> as I'm certain that those arenas can become very fragmented over time?
>>>
>>
>> Implementing heap compaction for those/all arenas have been considered,
>> and might be in the future, but the first cut at compaction doesn't support
>> movement of objects (as a result of compaction) that are part of arbitrary
>> object graphs, just a limited form for container objects. I've certainly
>> observed badly fragmented normal arenas over time on sites (normal4, in
>> particular.)
>>
>> The design writeup that went along with the heap compaction
>> intent-to-implement,
>>
>>  
>> https://docs.google.com/document/d/1k-vivOinomDXnScw8Ew5zpsYCXiYqj76OCOYZSvHkaU
>>
>> explains this in a bit more detail.
>>
>> So far as I can tell from that doc, the reason we don't have compaction
> for normal pages is just because of the complexity of updating N pointers
> after an object has moved? Isn't this a solved problem though? V8 has a
> fully compacting heap, doesn't it?
>

It is known how to implement general compaction, but for various tedious reasons that hasn't happened yet.

One point worth mentioning wrt v8 is if it is worth adding more Blink GC sophistication (like compaction, like generational collection, like concurrency or parallel schemes, ...) instead of building on top of v8's mature and extensive GC support instead. I hear there are plans afoot to do something in that area, or at least it is being carefully considered.

What, like the powers that be might choose to just use the v8 GC for Blink? That would certainly reduce the complexity of the code in my opinion. Is there any documentation/discussion available I can follow regarding this?

 

> Is there any plan to implement compaction for the normal arenas?
>  

see above :)

>>>       compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>>>
>>
>> Great catch - a bug that snuck in at some point; I'll fix. It effectively
>> means that only inline-vector and hash table arenas were being compacted.
>> The latter is certainly the arena that Blink manages to fragment the most,
>> but we clearly do want all the vector arenas compacted also.
>>
>
>   Glad to have helped. Do you want me to open a crbug for this?
>  

CL in flight, created crbug.com/726335 to track it; Cc:ed your email.

Awesome! 

--sigbjorn

[Kentaro Hara]

On Fri, May 26, 2017 at 12:02 AM, <ma...@shmarya.net> wrote:

On Thursday, May 25, 2017 at 5:42:58 PM UTC+3, sof wrote:

Den 5/25/2017 15:45, skreiv ma...@shmarya.net:
>
....
>>> So my question is: are normal arenas really not compactable? Isn't this
>> bad
>>> as I'm certain that those arenas can become very fragmented over time?
>>>
>>
>> Implementing heap compaction for those/all arenas have been considered,
>> and might be in the future, but the first cut at compaction doesn't support
>> movement of objects (as a result of compaction) that are part of arbitrary
>> object graphs, just a limited form for container objects. I've certainly
>> observed badly fragmented normal arenas over time on sites (normal4, in
>> particular.)
>>
>> The design writeup that went along with the heap compaction
>> intent-to-implement,
>>
>>  
>> https://docs.google.com/document/d/1k-vivOinomDXnScw8Ew5zpsYCXiYqj76OCOYZSvHkaU
>>
>> explains this in a bit more detail.
>>
>> So far as I can tell from that doc, the reason we don't have compaction
> for normal pages is just because of the complexity of updating N pointers
> after an object has moved? Isn't this a solved problem though? V8 has a
> fully compacting heap, doesn't it?
>

It is known how to implement general compaction, but for various tedious reasons that hasn't happened yet.

One point worth mentioning wrt v8 is if it is worth adding more Blink GC sophistication (like compaction, like generational collection, like concurrency or parallel schemes, ...) instead of building on top of v8's mature and extensive GC support instead. I hear there are plans afoot to do something in that area, or at least it is being carefully considered.

What, like the powers that be might choose to just use the v8 GC for Blink? That would certainly reduce the complexity of the code in my opinion. Is there any documentation/discussion available I can follow regarding this?

Not yet. We started thinking about the design.

 

 

> Is there any plan to implement compaction for the normal arenas?
>  

see above :)

>>>       compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>>>
>>
>> Great catch - a bug that snuck in at some point; I'll fix. It effectively
>> means that only inline-vector and hash table arenas were being compacted.
>> The latter is certainly the arena that Blink manages to fragment the most,
>> but we clearly do want all the vector arenas compacted also.
>>
>
>   Glad to have helped. Do you want me to open a crbug for this?
>  

CL in flight, created crbug.com/726335 to track it; Cc:ed your email.

Awesome! 

--sigbjorn

--

You received this message because you are subscribed to the Google Groups "blink-dev" group.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/blink-dev/4c69b695-dc1b-4857-9fd9-9bc46e87dc73%40chromium.org.

[Shmarya]

Now I'm excited to see if it will happen ;) 

 

 

> Is there any plan to implement compaction for the normal arenas?
>  

see above :)

>>>       compactable_arenas_ |= (0x1u << (BlinkGC::kVector1ArenaIndex + i));
>>>
>>
>> Great catch - a bug that snuck in at some point; I'll fix. It effectively
>> means that only inline-vector and hash table arenas were being compacted.
>> The latter is certainly the arena that Blink manages to fragment the most,
>> but we clearly do want all the vector arenas compacted also.
>>
>
>   Glad to have helped. Do you want me to open a crbug for this?
>  

CL in flight, created crbug.com/726335 to track it; Cc:ed your email.

Awesome! 

--sigbjorn

--
You received this message because you are subscribed to the Google Groups "blink-dev" group.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/blink-dev/4c69b695-dc1b-4857-9fd9-9bc46e87dc73%40chromium.org.

--

Kentaro Hara, Tokyo, Japan

--

Shmarya