Changeset 103030 in webkit


Ignore:
Timestamp:
Dec 15, 2011 11:14:30 PM (12 years ago)
Author:
commit-queue@webkit.org
Message:

PODIntervalTree takes 1.7MB memory on www.nytimes.com.
https://bugs.webkit.org/show_bug.cgi?id=73712

Patch by Yongjun Zhang <yongjun_zhang@apple.com> on 2011-12-15
Reviewed by Kenneth Russell.

Source/WebCore:

For a RenderBlock which has floating objects inside, we will create a PODIntervalTree and a PODArena with
at least one 16KB chunk. A page could have a large number of such RenderBlocks and they could take huge
amount of memory. To fix that, we can create a shared PODArena in the root RenderView. Instead of having
their own PODArena, each RenderBlock with floating objects could share this PODArena to reduce memory consumption.

The shared PODArena could grow unboundedly if we keep removing and adding floating objects. We can fix that
by reusing the freed memory in each chunk. However, a PODArena could allocate objects of different sizes and
it would be complex to keep track of the size for each allocation in PODArena. To address that, this patch
added class PODFreeListArena<T> which only allocates objects of type T (hence the same size). We can then use a
free list to track freed nodes inside the chunk and reuse the free nodes in future allocations.

Manually tested on nytimes.com and the heap consumption of PODIntervalTree reduced from 1.7MB to 16KB. Performance
doesn't regress on test PerformanceTests/Layout/floats.html.

  • WebCore.xcodeproj/project.pbxproj: add new header file PODFreeListArena.h.
  • platform/PODArena.h:

(WebCore::PODArena::~PODArena): change dtor to virtual.
(WebCore::PODArena::Chunk::~Chunk): ditto.

  • platform/PODFreeListArena.h: Added.

(WebCore::PODFreeListArena::create):
(WebCore::PODFreeListArena::allocateObject): allocate an object.
(WebCore::PODFreeListArena::freeObject): free an object, find the right chunk and update its free list.
(WebCore::PODFreeListArena::allocate): allocate memory from the free list or current chunk.
(WebCore::PODFreeListArena::FreeListChunk::FreeListChunk): add m_freeList to track freed cells.
(WebCore::PODFreeListArena::FreeListChunk::allocate): reuse a free cell if there is one.
(WebCore::PODFreeListArena::FreeListChunk::free): make the memory taken by this object is free, and link it to m_freeList.
(WebCore::PODFreeListArena::FreeListChunk::contains): check if a pointer is inside this chunk.
(WebCore::PODFreeListArena::FreeListChunk::hasFreeList): check if this chunk has free cells.

  • platform/PODRedBlackTree.h:

(WebCore::PODRedBlackTree::PODRedBlackTree): take PODFreeListArena instead of PODArena, since nodes of a particular PODRedBlackTree

is always of the same size.

(WebCore::PODRedBlackTree::clear): mark all nodes before clearing the tree.
(WebCore::PODRedBlackTree::initIfNeeded): add initIfNeeded to take an external PODFreeListArena.
(WebCore::PODRedBlackTree::add):
(WebCore::PODRedBlackTree::deleteNode): mark the node free in arena after it is removed from the tree.
(WebCore::PODRedBlackTree::markFree): mark all node free in the tree.

  • rendering/RenderBlock.cpp:

(WebCore::RenderBlock::insertFloatingObject):
(WebCore::RenderBlock::addOverhangingFloats):
(WebCore::RenderBlock::addIntrudingFloats):
(WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTree): passing the shared PODFreeListArena to m_placedFloatsTree.

  • rendering/RenderBlock.h:

(WebCore::RenderBlock::FloatingObjects::FloatingObjects):

  • rendering/RenderView.cpp:

(WebCore::RenderView::intervalArena): create the shared PODFreeListArena lazily.

  • rendering/RenderView.h:

Source/WebKit/chromium:

Change the test code in chromium port since PODRedBlackTree now takes PODFreeListArena<T>
in its constructor.

  • tests/PODRedBlackTreeTest.cpp:

(WebCore::TEST):

Location:
trunk/Source
Files:
1 added
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r103027 r103030  
     12011-12-15  Yongjun Zhang  <yongjun_zhang@apple.com>
     2
     3        PODIntervalTree takes 1.7MB memory on www.nytimes.com.
     4        https://bugs.webkit.org/show_bug.cgi?id=73712
     5
     6        Reviewed by Kenneth Russell.
     7
     8        For a RenderBlock which has floating objects inside, we will create a PODIntervalTree and a PODArena with
     9        at least one 16KB chunk.  A page could have a large number of such RenderBlocks and they could take huge
     10        amount of memory.  To fix that, we can create a shared PODArena in the root RenderView.  Instead of having
     11        their own PODArena, each RenderBlock with floating objects could share this PODArena to reduce memory consumption.
     12
     13        The shared PODArena could grow unboundedly if we keep removing and adding floating objects.  We can fix that
     14        by reusing the freed memory in each chunk.  However, a PODArena could allocate objects of different sizes and
     15        it would be complex to keep track of the size for each allocation in PODArena.  To address that, this patch
     16        added class PODFreeListArena<T> which only allocates objects of type T (hence the same size).  We can then use a
     17        free list to track freed nodes inside the chunk and reuse the free nodes in future allocations.
     18
     19        Manually tested on nytimes.com and the heap consumption of PODIntervalTree reduced from 1.7MB to 16KB. Performance
     20        doesn't regress on test PerformanceTests/Layout/floats.html.
     21
     22        * WebCore.xcodeproj/project.pbxproj: add new header file PODFreeListArena.h.
     23        * platform/PODArena.h:
     24        (WebCore::PODArena::~PODArena): change dtor to virtual.
     25        (WebCore::PODArena::Chunk::~Chunk): ditto.
     26        * platform/PODFreeListArena.h: Added.
     27        (WebCore::PODFreeListArena::create):
     28        (WebCore::PODFreeListArena::allocateObject): allocate an object.
     29        (WebCore::PODFreeListArena::freeObject): free an object, find the right chunk and update its free list.
     30        (WebCore::PODFreeListArena::allocate): allocate memory from the free list or current chunk.
     31        (WebCore::PODFreeListArena::FreeListChunk::FreeListChunk): add m_freeList to track freed cells.
     32        (WebCore::PODFreeListArena::FreeListChunk::allocate): reuse a free cell if there is one.
     33        (WebCore::PODFreeListArena::FreeListChunk::free): make the memory taken by this object is free, and link it to m_freeList.
     34        (WebCore::PODFreeListArena::FreeListChunk::contains): check if a pointer is inside this chunk.
     35        (WebCore::PODFreeListArena::FreeListChunk::hasFreeList): check if this chunk has free cells.
     36        * platform/PODRedBlackTree.h:
     37        (WebCore::PODRedBlackTree::PODRedBlackTree): take PODFreeListArena instead of PODArena, since nodes of a particular PODRedBlackTree
     38            is always of the same size.
     39        (WebCore::PODRedBlackTree::clear): mark all nodes before clearing the tree.
     40        (WebCore::PODRedBlackTree::initIfNeeded): add initIfNeeded to take an external PODFreeListArena.
     41        (WebCore::PODRedBlackTree::add):
     42        (WebCore::PODRedBlackTree::deleteNode): mark the node free in arena after it is removed from the tree.
     43        (WebCore::PODRedBlackTree::markFree): mark all node free in the tree.
     44        * rendering/RenderBlock.cpp:
     45        (WebCore::RenderBlock::insertFloatingObject):
     46        (WebCore::RenderBlock::addOverhangingFloats):
     47        (WebCore::RenderBlock::addIntrudingFloats):
     48        (WebCore::RenderBlock::FloatingObjects::computePlacedFloatsTree):  passing the shared PODFreeListArena to m_placedFloatsTree.
     49        * rendering/RenderBlock.h:
     50        (WebCore::RenderBlock::FloatingObjects::FloatingObjects):
     51        * rendering/RenderView.cpp:
     52        (WebCore::RenderView::intervalArena): create the shared PODFreeListArena lazily.
     53        * rendering/RenderView.h:
     54
    1552011-12-15  Tony Chang  <tony@chromium.org>
    256
  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r103007 r103030  
    643643                1F3C3BEA135CAF3C00B8C1AC /* MediaControls.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1F3C3BE8135CAF3C00B8C1AC /* MediaControls.cpp */; };
    644644                1F3C3BEB135CAF3C00B8C1AC /* MediaControls.h in Headers */ = {isa = PBXBuildFile; fileRef = 1F3C3BE9135CAF3C00B8C1AC /* MediaControls.h */; };
     645                1F3F19531499CA7600A5AEA7 /* PODFreeListArena.h in Headers */ = {isa = PBXBuildFile; fileRef = 1F3F19521499CA7600A5AEA7 /* PODFreeListArena.h */; settings = {ATTRIBUTES = (Private, ); }; };
    645646                20D629261253690B00081543 /* InspectorInstrumentation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 20D629241253690B00081543 /* InspectorInstrumentation.cpp */; };
    646647                20D629271253690B00081543 /* InspectorInstrumentation.h in Headers */ = {isa = PBXBuildFile; fileRef = 20D629251253690B00081543 /* InspectorInstrumentation.h */; };
     
    77797780                1F3C3BE8135CAF3C00B8C1AC /* MediaControls.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MediaControls.cpp; sourceTree = "<group>"; };
    77807781                1F3C3BE9135CAF3C00B8C1AC /* MediaControls.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MediaControls.h; sourceTree = "<group>"; };
     7782                1F3F19521499CA7600A5AEA7 /* PODFreeListArena.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PODFreeListArena.h; sourceTree = "<group>"; };
    77817783                20D629241253690B00081543 /* InspectorInstrumentation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = InspectorInstrumentation.cpp; sourceTree = "<group>"; };
    77827784                20D629251253690B00081543 /* InspectorInstrumentation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InspectorInstrumentation.h; sourceTree = "<group>"; };
     
    2025620258                                935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
    2025720259                                BCBB8AB413F1AFB000734DF0 /* PODArena.h */,
     20260                                1F3F19521499CA7600A5AEA7 /* PODFreeListArena.h */,
    2025820261                                BCBB8AB513F1AFB000734DF0 /* PODInterval.h */,
    2025920262                                BCBB8AB613F1AFB000734DF0 /* PODIntervalTree.h */,
     
    2487524878                                0F580FA31496939100FB5BD8 /* WebTileCacheLayer.h in Headers */,
    2487624879                                0F580FAF149800D400FB5BD8 /* AnimationUtilities.h in Headers */,
     24880                                1F3F19531499CA7600A5AEA7 /* PODFreeListArena.h in Headers */,
    2487724881                                49ECEB681499790D00CDD3A4 /* FECompositeArithmeticNEON.h in Headers */,
    2487824882                                49ECEB6A1499790D00CDD3A4 /* FEGaussianBlurNEON.h in Headers */,
  • trunk/Source/WebCore/platform/PODArena.h

    r95901 r103030  
    113113
    114114protected:
    115     ~PODArena() { }
     115    virtual ~PODArena() { }
    116116    friend class WTF::RefCounted<PODArena>;
    117117
    118 private:
    119118    PODArena()
    120119        : m_allocator(FastMallocAllocator::create())
     
    174173        // Frees the memory allocated from the Allocator in the
    175174        // constructor.
    176         ~Chunk()
     175        virtual ~Chunk()
    177176        {
    178177            m_allocator->free(m_base);
     
    195194        }
    196195
    197     private:
     196    protected:
    198197        Allocator* m_allocator;
    199198        uint8_t* m_base;
  • trunk/Source/WebCore/platform/PODRedBlackTree.h

    r95901 r103030  
    7373#define PODRedBlackTree_h
    7474
    75 #include "PODArena.h"
     75#include "PODFreeListArena.h"
    7676#include <wtf/Assertions.h>
    7777#include <wtf/Noncopyable.h>
     
    9898class PODRedBlackTree {
    9999public:
     100    class Node;
     101
    100102    // Visitor interface for walking all of the tree's elements.
    101103    class Visitor {
     
    120122
    121123    // Constructs a new red-black tree, allocating temporary objects
    122     // from a newly constructed PODArena.
     124    // from a newly constructed PODFreeListArena.
    123125    PODRedBlackTree()
    124         : m_arena(PODArena::create())
     126        : m_arena(PODFreeListArena<Node>::create())
    125127        , m_root(0)
    126128        , m_needsFullOrderingComparisons(false)
     
    133135    // Constructs a new red-black tree, allocating temporary objects
    134136    // from the given PODArena.
    135     explicit PODRedBlackTree(PassRefPtr<PODArena> arena)
     137    explicit PODRedBlackTree(PassRefPtr<PODFreeListArena<Node> > arena)
    136138        : m_arena(arena)
    137139        , m_root(0)
     
    149151    void clear()
    150152    {
     153        markFree(m_root);
    151154        m_arena = 0;
    152155        m_root = 0;
     
    161164    {
    162165        if (!m_arena)
    163             m_arena = PODArena::create();
     166            m_arena = PODFreeListArena<Node>::create();
     167    }
     168
     169    void initIfNeeded(PODFreeListArena<Node>* arena)
     170    {
     171        if (!m_arena)
     172            m_arena = arena;
    164173    }
    165174
     
    167176    {
    168177        ASSERT(isInitialized());
    169         Node* node = m_arena->allocateObject<Node, T>(data);
     178        Node* node = m_arena->template allocateObject<T>(data);
    170179        insertNode(node);
    171180    }
     
    236245#endif
    237246
    238 protected:
    239247    enum Color {
    240248        Red = 1,
     
    291299    };
    292300
     301protected:
    293302    // Returns the root of the tree, which is needed by some subclasses.
    294303    Node* root() const { return m_root; }
     
    691700        if (y->color() == Black)
    692701            deleteFixup(x, xParent);
     702
     703        m_arena->freeObject(y);
    693704    }
    694705
     
    701712        if (node->right())
    702713            visitInorderImpl(node->right(), visitor);
     714    }
     715
     716    void markFree(Node *node)
     717    {
     718        if (!node)
     719            return;
     720
     721        if (node->left())
     722            markFree(node->left());
     723        if (node->right())
     724            markFree(node->right());
     725        m_arena->freeObject(node);
    703726    }
    704727
     
    793816    // Data members
    794817
    795     RefPtr<PODArena> m_arena;
     818    RefPtr<PODFreeListArena<Node> > m_arena;
    796819    Node* m_root;
    797820    bool m_needsFullOrderingComparisons;
  • trunk/Source/WebCore/rendering/RenderBlock.cpp

    r103020 r103030  
    3939#include "InlineTextBox.h"
    4040#include "LayoutRepainter.h"
     41#include "PODFreeListArena.h"
    4142#include "Page.h"
    4243#include "PaintInfo.h"
     
    32723273    // Create the list of special objects if we don't aleady have one
    32733274    if (!m_floatingObjects)
    3274         m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
     3275        m_floatingObjects = adoptPtr(new FloatingObjects(this, isHorizontalWritingMode()));
    32753276    else {
    32763277        // Don't insert the object again if it's already in the list
     
    39373938                // We create the floating object list lazily.
    39383939                if (!m_floatingObjects)
    3939                     m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
     3940                    m_floatingObjects = adoptPtr(new FloatingObjects(this, isHorizontalWritingMode()));
    39403941
    39413942                m_floatingObjects->add(floatingObj);
     
    40104011                // We create the floating object list lazily.
    40114012                if (!m_floatingObjects)
    4012                     m_floatingObjects = adoptPtr(new FloatingObjects(isHorizontalWritingMode()));
     4013                    m_floatingObjects = adoptPtr(new FloatingObjects(this, isHorizontalWritingMode()));
    40134014                m_floatingObjects->add(floatingObj);
    40144015            }
     
    70117012    if (m_set.isEmpty())
    70127013        return;
    7013     m_placedFloatsTree.initIfNeeded();
     7014    m_placedFloatsTree.initIfNeeded(m_renderer->view()->intervalArena());
    70147015    FloatingObjectSetIterator it = m_set.begin();
    70157016    FloatingObjectSetIterator end = m_set.end();
  • trunk/Source/WebCore/rendering/RenderBlock.h

    r103020 r103030  
    917917    RenderRegion* clampToStartAndEndRegions(RenderRegion*) const;
    918918
    919 private:
     919protected:
    920920    struct FloatingObjectHashFunctions {
    921921        static unsigned hash(FloatingObject* key) { return DefaultHash<RenderBox*>::Hash::hash(key->m_renderer); }
     
    931931    typedef PODInterval<int, FloatingObject*> FloatingObjectInterval;
    932932    typedef PODIntervalTree<int, FloatingObject*> FloatingObjectTree;
     933    typedef PODFreeListArena<PODRedBlackTree<FloatingObjectInterval>::Node> IntervalArena;
    933934   
    934935    template <FloatingObject::Type FloatTypeValue>
     
    958959    class FloatingObjects {
    959960    public:
    960         FloatingObjects(bool horizontalWritingMode)
     961        FloatingObjects(const RenderBlock* renderer, bool horizontalWritingMode)
    961962            : m_placedFloatsTree(UninitializedTree)
    962963            , m_leftObjectsCount(0)
     
    964965            , m_positionedObjectsCount(0)
    965966            , m_horizontalWritingMode(horizontalWritingMode)
     967            , m_renderer(renderer)
    966968        {
    967969        }
     
    10001002        unsigned m_positionedObjectsCount;
    10011003        bool m_horizontalWritingMode;
     1004        const RenderBlock* m_renderer;
    10021005    };
    10031006    OwnPtr<FloatingObjects> m_floatingObjects;
  • trunk/Source/WebCore/rendering/RenderView.cpp

    r102333 r103030  
    926926}
    927927
     928RenderBlock::IntervalArena* RenderView::intervalArena()
     929{
     930    if (!m_intervalArena)
     931        m_intervalArena = IntervalArena::create();
     932    return m_intervalArena.get();
     933}
     934
    928935} // namespace WebCore
  • trunk/Source/WebCore/rendering/RenderView.h

    r102333 r103030  
    2525#include "FrameView.h"
    2626#include "LayoutState.h"
     27#include "PODFreeListArena.h"
    2728#include "RenderBlock.h"
    2829#include <wtf/ListHashSet.h>
     
    193194    void styleDidChange(StyleDifference, const RenderStyle* oldStyle);
    194195
     196    IntervalArena* intervalArena();
     197
    195198protected:
    196199    virtual void mapLocalToContainer(RenderBoxModelObject* repaintContainer, bool useTransforms, bool fixed, TransformState&, bool* wasFixed = 0) const;
     
    235238    friend class LayoutStateMaintainer;
    236239    friend class LayoutStateDisabler;
    237        
     240
    238241protected:
    239242    FrameView* m_frameView;
     
    279282    RenderFlowThread* m_currentRenderFlowThread;
    280283    RenderRegion* m_currentRenderRegion;
     284    RefPtr<IntervalArena> m_intervalArena;
    281285};
    282286
  • trunk/Source/WebKit/chromium/ChangeLog

    r103025 r103030  
     12011-12-15  Yongjun Zhang  <yongjun_zhang@apple.com>
     2
     3        PODIntervalTree takes 1.7MB memory on www.nytimes.com.
     4        https://bugs.webkit.org/show_bug.cgi?id=73712
     5
     6        Reviewed by Kenneth Russell.
     7
     8        Change the test code in chromium port since PODRedBlackTree now takes PODFreeListArena<T>
     9        in its constructor.
     10
     11        * tests/PODRedBlackTreeTest.cpp:
     12        (WebCore::TEST):
     13
    1142011-12-15  Joshua Bell  <jsbell@chromium.org>
    215
  • trunk/Source/WebKit/chromium/tests/PODRedBlackTreeTest.cpp

    r95901 r103030  
    4646    RefPtr<TrackedAllocator> allocator = TrackedAllocator::create();
    4747    {
    48         RefPtr<PODArena> arena = PODArena::create(allocator);
     48        typedef PODFreeListArena<PODRedBlackTree<int>::Node> PODIntegerArena;
     49        RefPtr<PODIntegerArena> arena = PODIntegerArena::create(allocator);
    4950        PODRedBlackTree<int> tree(arena);
    5051        int numAdditions = 2 * PODArena::DefaultChunkSize / sizeof(int);
Note: See TracChangeset for help on using the changeset viewer.