[Webkit-unassigned] [Bug 73712] PODIntervalTree takes 1.7MB memory on www.nytimes.com

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=73712





--- Comment #11 from Yongjun Zhang <yongjun_zhang at apple.com>  2011-12-08 18:06:34 PST ---
(In reply to comment #8)
> (From update of attachment 117731 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=117731&action=review
> 
> First, nice work tracking down this issue and proposing a fix.
> 

Thanks for the comments!

> I'm not qualified to review the renderer code; hyatt or darin should.
> 
> However, I am concerned about the overall strategy of adding a free list to the PODArena. As indicated above, the currently proposed changes violate invariants, so they will either have to be fixed or a different approach will need to be taken. Now, it's possible to fix the free list code, but a solution that would be more in line with the design of the arena, red/black and interval trees would be to just clear out the arena wholesale at certain points in time. I don't know whether there's a good point in the layout algorithm to do this, but if there is, I would lean toward a solution of that form. That could introduce the possibility of dangling pointers from existing red/black and interval tree instances, and that might be a worse side-effect than the additional complexity of free list maintenance, so the tradeoffs would have to be carefully considered.

That was also my concern when first looking at the code.  However, it seems like a PODBlackRedTree only allocates fixed size objects from its PODArena, and PODArena is so far only used by PODBlackRedTree.  So this patch makes the assumption that each object allocated from the same arena has the same size, which simplifies the freelist implementation and we don't need to track the size of each cell from a chunk.   I agree it is not future proof if we are to use PODArena with different sized cells.

> 
> I'm marking this patch r- for a couple of style issues as well as the correctness problem with the free list. Will be glad to review future iterations, though again one of the other reviewers will have to give the final r+.
> 

Sure, I will keep working on it.

> >> Source/WebCore/platform/PODArena.h:110
> >> +        }
> > 
> > We normally use a for loop for something like this rather than a while loop.
> 
> Are you sure it is a good idea to introduce a search into this critical point of the algorithm? Would it be possible to map from a pointer to its containing Chunk in constant time? One way to do this would be to always allocate space for the Chunk backpointer before the start of the object, though this would waste space.

>From my test, it doesn't look like we will have lots of chunks in real sites.  And we can reduce the search if we set the chunk size big enough (4K seems to be reasonable,).

> 
> > Source/WebCore/platform/PODArena.h:167
> > +                        break;
> 
> If you're iterating through the chunks already, why not generalize the code and write "if (ptr) break;" instead?

Good point!

> 
> > Source/WebCore/platform/PODArena.h:197
> > +        };
> 
> For correctness as this class is currently written, each entry on the free list would have to keep track of its size.
> 

Again, the assumption is each entry in the free list has the same size.

> > Source/WebCore/platform/PODArena.h:221
> > +            if (m_freeList) {
> 
> You'd better ASSERT that size >= sizeof(FreeCell), or later frees of the returned pointer will blow up.
> 
> > Source/WebCore/platform/PODArena.h:223
> > +                void* p = m_freeList;
> 
> This code violates invariants of the class. The PODArena as written has to handle allocations of multiple sizes. You aren't keeping track of the size of the block of memory pointed to by the freed pointer, so you don't know whether each entry on the free list can satisfy the allocation. Now, the current usage of PODArena in the handling of floating objects happens to make this code work, but you can't rely on that. If you go down the route of adding a free list then either the free list needs to be generalized, or the PODArena has to be specialized to only support allocating one data type per arena instance.

I agree.  How about we make a special cased PODArena for the PODIntervalTree that we know for sure each entry will have the same size, and keep the generalize case as it is?  That way we fix the memory issue without violating the invariants of PODArena.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.