Oilpan: Try to allocate from a smaller FreeListEntry.

Oilpan: Try to allocate from a smaller FreeListEntry.

PerformanceTests/ShadowDOM/LargeDistributionWithoutLayout allocates a lot of
collection backings with 32KB size and 16KB size. allocateFromFreeList failed
to allocate memory for them frequently even if there were FreeListEntry
with enough sizes because:
 - Actual required size is 32KB+8B or 16KB+8B because of object headers
 - allocateFromFreeList only checked the minimum size of a bucket.  For example,
   a 32KB+8B free slot was listed in the 32KB bucket, and 32KB is smaller than
   32KB+8B.

This CL reduces the peak number of HeapPages in LargeDistributionWithoutLayout
test by 200.

BUG=420515
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=185112

[tkent, 2014-11-11 06:11:43]

Patchset #1 (id:1) has been deleted

[tkent, 2014-11-11 06:21:34]

tkent@chromium.org changed reviewers:
+ oilpan-reviews@chromium.org

[tkent, 2014-11-11 06:21:35]

Please review this.

[haraken, 2014-11-11 06:29:15]

LGTM

[tkent, 2014-11-11 07:53:03]

The CQ bit was checked by tkent@chromium.org

[commit-bot: I haz the power, 2014-11-11 07:53:57]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/711173004/20001

[sof, 2014-11-11 08:29:35]

sigbjornf@opera.com changed reviewers:
+ sigbjornf@opera.com

[sof, 2014-11-11 08:29:36]

https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
Source/platform/heap/Heap.cpp:748: m_freeList.m_biggestFreeListIndex = i;
I don't understand m_biggestFreeListIndex and this update; I must be missing
some detail..?

If you call allocateFromFreeList(17) and it fails as there are no entries in its
bucket, then m_biggestFreeListIndex will be set to 4. If you then call
allocateFromFreeList(65534), and there are free list entries at that bucket,
these will never be considered afaict.

[tkent, 2014-11-11 08:46:59]

https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
File Source/platform/heap/Heap.cpp (right):

https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
Source/platform/heap/Heap.cpp:748: m_freeList.m_biggestFreeListIndex = i;
On 2014/11/11 08:29:36, sof wrote:
> I don't understand m_biggestFreeListIndex and this update; I must be missing
> some detail..?
> 
> If you call allocateFromFreeList(17) and it fails as there are no entries in
its
> bucket, then m_biggestFreeListIndex will be set to 4. If you then call
> allocateFromFreeList(65534), and there are free list entries at that bucket,
> these will never be considered afaict.

We always allocate from a FreeListEntry in the largest bucket.
If we hit the |break| in the loop, it means we have no FreeListEntries in
m_freeLists[i+1 or greater].

[sof, 2014-11-11 08:55:34]

On 2014/11/11 08:46:59, tkent wrote:
>
https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
> File Source/platform/heap/Heap.cpp (right):
> 
>
https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
> Source/platform/heap/Heap.cpp:748: m_freeList.m_biggestFreeListIndex = i;
> On 2014/11/11 08:29:36, sof wrote:
> > I don't understand m_biggestFreeListIndex and this update; I must be missing
> > some detail..?
> > 
> > If you call allocateFromFreeList(17) and it fails as there are no entries in
> its
> > bucket, then m_biggestFreeListIndex will be set to 4. If you then call
> > allocateFromFreeList(65534), and there are free list entries at that bucket,
> > these will never be considered afaict.
> 
> We always allocate from a FreeListEntry in the largest bucket.
> If we hit the |break| in the loop, it means we have no FreeListEntries in
> m_freeLists[i+1 or greater].

Unusual allocation scheme given the buckets.

[haraken, 2014-11-11 08:59:41]

On 2014/11/11 08:55:34, sof wrote:
> On 2014/11/11 08:46:59, tkent wrote:
> >
>
https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
> > File Source/platform/heap/Heap.cpp (right):
> > 
> >
>
https://codereview.chromium.org/711173004/diff/20001/Source/platform/heap/Hea...
> > Source/platform/heap/Heap.cpp:748: m_freeList.m_biggestFreeListIndex = i;
> > On 2014/11/11 08:29:36, sof wrote:
> > > I don't understand m_biggestFreeListIndex and this update; I must be
missing
> > > some detail..?
> > > 
> > > If you call allocateFromFreeList(17) and it fails as there are no entries
in
> > its
> > > bucket, then m_biggestFreeListIndex will be set to 4. If you then call
> > > allocateFromFreeList(65534), and there are free list entries at that
bucket,
> > > these will never be considered afaict.
> > 
> > We always allocate from a FreeListEntry in the largest bucket.
> > If we hit the |break| in the loop, it means we have no FreeListEntries in
> > m_freeLists[i+1 or greater].
> 
> Unusual allocation scheme given the buckets.

In order to allocate as many things as possible in inlined Heap::allocate, it is
important to find the largest free space from the free lists. That is what we're
doing, although I'm not quite sure if this is a sane allocation scheme.

[tkent, 2014-11-11 09:05:38]

On 2014/11/11 08:55:34, sof wrote:
> > We always allocate from a FreeListEntry in the largest bucket.
> > If we hit the |break| in the loop, it means we have no FreeListEntries in
> > m_freeLists[i+1 or greater].
> 
> Unusual allocation scheme given the buckets.

Yeah, this behavior might be causing serious memory-fragmentation.  Object
allocation rate in LargeDistributionWithoutLayout test is still bad with this
CL.

[haraken, 2014-11-11 09:12:43]

On 2014/11/11 09:05:38, tkent wrote:
> On 2014/11/11 08:55:34, sof wrote:
> > > We always allocate from a FreeListEntry in the largest bucket.
> > > If we hit the |break| in the loop, it means we have no FreeListEntries in
> > > m_freeLists[i+1 or greater].
> > 
> > Unusual allocation scheme given the buckets.
> 
> Yeah, this behavior might be causing serious memory-fragmentation.  Object
> allocation rate in LargeDistributionWithoutLayout test is still bad with this
> CL.

Probably can we try to search a bucket from smaller ones to larger ones, not
from larger ones to smaller ones? It will realize an approximately best fit.

[sof, 2014-11-11 09:22:55]

On 2014/11/11 09:12:43, haraken wrote:
> On 2014/11/11 09:05:38, tkent wrote:
> > On 2014/11/11 08:55:34, sof wrote:
> > > > We always allocate from a FreeListEntry in the largest bucket.
> > > > If we hit the |break| in the loop, it means we have no FreeListEntries
in
> > > > m_freeLists[i+1 or greater].
> > > 
> > > Unusual allocation scheme given the buckets.
> > 
> > Yeah, this behavior might be causing serious memory-fragmentation.  Object
> > allocation rate in LargeDistributionWithoutLayout test is still bad with
this
> > CL.
> 
> Probably can we try to search a bucket from smaller ones to larger ones, not
> from larger ones to smaller ones? It will realize an approximately best fit.

Trying out such a scheme sounds worthwhile, but I don't know what bucket
distributions we're in practice seeing yet. With some bailout if we skip across
too many empty buckets. i.e., re-using a 64k freelist entry for a 15 byte
allocation is questionable.

[commit-bot: I haz the power, 2014-11-11 09:56:07]

Committed patchset #1 (id:20001) as 185112

[blink-reviews, 2014-11-11 11:35:53]

Worst-fit works best for lots of small allocations of objects that
tend to live and die
together. You get a fast bump allocation and objects created together
are placed together,
which can be good for locality.

It doesn't work as well for very large allocations where the speed of
allocation is not
so critical. It also works badly if you are allocating long lived and
short lived objects
with the same bump allocator, because you get lots of holes.

Since we can't (yet) move objects it is important that we place them
in the right places. This
means that objects that are likely to have the same lifetime should be
allocated together. So
any objects that have a DOM-tied lifetime can go in one area. and
objects that will
likely be dead by the next event loop (eg parser-related) should be in
their own pages.
The main hint we have in oilpan is the type.

My guess is that collection backings are very special. Since we are
not allocating strings on our
heap yet, they are likely to be the only really big objects, and they
have special lifetime
characteristics. They probably always have one of a few sizes.  I
think something like best fit
or a buddy system is likely to be good for them, especially the bigger
ones that are likely to be
longer lived.

Ian did some work on the lifetime characteristics of various types on
the Oilpan heap.  I'll try to
find it.

To unsubscribe from this group and stop receiving emails from it, send an email
to blink-reviews+unsubscribe@chromium.org.

[haraken, 2014-11-11 12:58:22]

On 2014/11/11 11:35:53, blink-reviews wrote:
> Worst-fit works best for lots of small allocations of objects that
> tend to live and die
> together. You get a fast bump allocation and objects created together
> are placed together,
> which can be good for locality.
> 
> It doesn't work as well for very large allocations where the speed of
> allocation is not
> so critical. It also works badly if you are allocating long lived and
> short lived objects
> with the same bump allocator, because you get lots of holes.
> 
> Since we can't (yet) move objects it is important that we place them
> in the right places. This
> means that objects that are likely to have the same lifetime should be
> allocated together. So
> any objects that have a DOM-tied lifetime can go in one area. and
> objects that will
> likely be dead by the next event loop (eg parser-related) should be in
> their own pages.
> The main hint we have in oilpan is the type.
> 
> My guess is that collection backings are very special. Since we are
> not allocating strings on our
> heap yet, they are likely to be the only really big objects, and they
> have special lifetime
> characteristics. They probably always have one of a few sizes.  I
> think something like best fit
> or a buddy system is likely to be good for them, especially the bigger
> ones that are likely to be
> longer lived.
> 
> Ian did some work on the lifetime characteristics of various types on
> the Oilpan heap.  I'll try to
> find it.

FWIW, previously I tried to implement per-size heaps for collection backings
(i.e., a heap for < 64 bytes, a heap for < 128 bytes, a heap for < 256 bytes and
a heap for >= 256 bytes). It regressed performance :(

[tkent, 2014-11-12 01:08:29]

FYI. This CL improved LargeDistributionWithoutLayout test.
39% worse than non-Oilpan -> 31% worse than non-Oilpan
on Mac.


On 2014/11/11 12:58:22, haraken wrote:
> FWIW, previously I tried to implement per-size heaps for collection backings
> (i.e., a heap for < 64 bytes, a heap for < 128 bytes, a heap for < 256 bytes
and
> a heap for >= 256 bytes). It regressed performance :(

It's interesting.  I thought it would have improvement.

[haraken, 2014-11-12 01:40:50]

On 2014/11/12 01:08:29, tkent wrote:
> FYI. This CL improved LargeDistributionWithoutLayout test.
> 39% worse than non-Oilpan -> 31% worse than non-Oilpan
> on Mac.
> 
> 
> On 2014/11/11 12:58:22, haraken wrote:
> > FWIW, previously I tried to implement per-size heaps for collection backings
> > (i.e., a heap for < 64 bytes, a heap for < 128 bytes, a heap for < 256 bytes
> and
> > a heap for >= 256 bytes). It regressed performance :(
> 
> It's interesting.  I thought it would have improvement.

Yeah, that's why I landed the per-size heap only for GeneralHeaps. I think we
need more investigation on collection backing heaps.