Changeset 91039 in webkit
- Timestamp:
- Jul 14, 2011 6:40:25 PM (13 years ago)
- Location:
- trunk/Source/JavaScriptCore
- Files:
-
- 11 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r91034 r91039 1 2011-07-14 Filip Pizlo <fpizlo@apple.com> 2 3 GC allocation fast path has too many operations. 4 https://bugs.webkit.org/show_bug.cgi?id=64493 5 6 Reviewed by Darin Adler. 7 8 Changed the timing of the lazy sweep so that it occurs when we land on 9 a previously-unsweeped block, rather than whenever we land on an unsweeped 10 cell. After the per-block lazy sweep occurs, the block is turned into a 11 singly linked list of free cells. The allocation fast path is now just a 12 load-branch-store to remove a cell from the head of the list. 13 14 Additionally, this changes the way new blocks are allocated. Previously, 15 they would be populated with dummy cells. With this patch, they are 16 turned into a free list, which means that there will never be destructor 17 calls for allocations in fresh blocks. 18 19 These changes result in a 1.9% speed-up on V8, and a 0.6% speed-up on 20 SunSpider. There are no observed statistically significant slow-downs 21 on any individual benchmark. 22 23 * JavaScriptCore.exp: 24 * heap/Heap.cpp: 25 (JSC::Heap::allocateSlowCase): 26 (JSC::Heap::collect): 27 (JSC::Heap::canonicalizeBlocks): 28 (JSC::Heap::resetAllocator): 29 * heap/Heap.h: 30 (JSC::Heap::forEachProtectedCell): 31 (JSC::Heap::forEachCell): 32 (JSC::Heap::forEachBlock): 33 (JSC::Heap::allocate): 34 * heap/MarkedBlock.cpp: 35 (JSC::MarkedBlock::MarkedBlock): 36 (JSC::MarkedBlock::lazySweep): 37 (JSC::MarkedBlock::blessNewBlockForFastPath): 38 (JSC::MarkedBlock::blessNewBlockForSlowPath): 39 (JSC::MarkedBlock::canonicalizeBlock): 40 * heap/MarkedBlock.h: 41 * heap/NewSpace.cpp: 42 (JSC::NewSpace::addBlock): 43 (JSC::NewSpace::canonicalizeBlocks): 44 * heap/NewSpace.h: 45 (JSC::NewSpace::allocate): 46 (JSC::NewSpace::SizeClass::SizeClass): 47 (JSC::NewSpace::SizeClass::canonicalizeBlock): 48 * heap/OldSpace.cpp: 49 (JSC::OldSpace::addBlock): 50 1 51 2011-07-14 Filip Pizlo <fpizlo@apple.com> 2 52 -
trunk/Source/JavaScriptCore/JavaScriptCore.exp
r90643 r91039 225 225 __ZN3JSC4Heap11objectCountEv 226 226 __ZN3JSC4Heap16activityCallbackEv 227 __ZN3JSC4Heap16allocateSlowCaseERNS_8NewSpace9SizeClassE 227 228 __ZN3JSC4Heap16objectTypeCountsEv 228 229 __ZN3JSC4Heap17collectAllGarbageEv … … 238 239 __ZN3JSC4Heap7destroyEv 239 240 __ZN3JSC4Heap7protectENS_7JSValueE 240 __ZN3JSC4Heap8allocateERNS_8NewSpace9SizeClassE241 241 __ZN3JSC4Heap8capacityEv 242 242 __ZN3JSC4Heap9unprotectENS_7JSValueE -
trunk/Source/JavaScriptCore/JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.def
r89927 r91039 57 57 ?addStaticGlobals@JSGlobalObject@JSC@@IAEXPAUGlobalPropertyInfo@12@H@Z 58 58 ?allocate@Heap@JSC@@QAEPAXAAUSizeClass@NewSpace@2@@Z 59 ?allocate@Heap@JSC@@QAEPAXI@Z60 59 ?allocatePropertyStorage@JSObject@JSC@@QAEXII@Z 60 ?allocateSlowCase@Heap@JSC@@AAEPAXAAUSizeClass@NewSpace@2@@Z 61 61 ?append@StringBuilder@WTF@@QAEXPBDI@Z 62 62 ?append@StringBuilder@WTF@@QAEXPB_WI@Z -
trunk/Source/JavaScriptCore/heap/Heap.cpp
r90865 r91039 103 103 } 104 104 105 struct ResetAllocator : MarkedBlock::VoidFunctor {106 void operator()(MarkedBlock*);107 };108 109 inline void ResetAllocator::operator()(MarkedBlock* block)110 {111 block->resetAllocator();112 }113 114 105 struct Sweep : MarkedBlock::VoidFunctor { 115 106 void operator()(MarkedBlock*); … … 321 312 } 322 313 323 void* Heap::allocate (NewSpace::SizeClass& sizeClass)314 void* Heap::allocateSlowCase(NewSpace::SizeClass& sizeClass) 324 315 { 325 316 #if COLLECT_ON_EVERY_ALLOCATION … … 559 550 ASSERT(m_isSafeToCollect); 560 551 JAVASCRIPTCORE_GC_BEGIN(); 561 552 553 canonicalizeBlocks(); 554 562 555 markRoots(); 563 556 m_handleHeap.finalizeWeakHandles(); … … 589 582 } 590 583 584 void Heap::canonicalizeBlocks() 585 { 586 m_newSpace.canonicalizeBlocks(); 587 } 588 591 589 void Heap::resetAllocator() 592 590 { 593 591 m_extraCost = 0; 594 592 m_newSpace.resetAllocator(); 595 forEachBlock<ResetAllocator>();596 593 } 597 594 -
trunk/Source/JavaScriptCore/heap/Heap.h
r90865 r91039 25 25 #include "HandleHeap.h" 26 26 #include "HandleStack.h" 27 #include " SlotVisitor.h"27 #include "MarkedBlock.h" 28 28 #include "MarkedBlockSet.h" 29 29 #include "NewSpace.h" 30 #include "SlotVisitor.h" 30 31 #include <wtf/Forward.h> 31 32 #include <wtf/HashCountedSet.h> … … 125 126 126 127 bool isValidAllocation(size_t); 127 void* allocateSlowCase(size_t);128 128 void reportExtraMemoryCostSlowCase(size_t); 129 void canonicalizeBlocks(); 129 130 void resetAllocator(); 130 131 … … 138 139 139 140 void* tryAllocate(NewSpace::SizeClass&); 141 void* allocateSlowCase(NewSpace::SizeClass&); 140 142 141 143 enum SweepToggle { DoNotSweep, DoSweep }; … … 243 245 template<typename Functor> inline typename Functor::ReturnType Heap::forEachProtectedCell(Functor& functor) 244 246 { 247 canonicalizeBlocks(); 245 248 ProtectCountSet::iterator end = m_protectedValues.end(); 246 249 for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it) … … 259 262 template<typename Functor> inline typename Functor::ReturnType Heap::forEachCell(Functor& functor) 260 263 { 264 canonicalizeBlocks(); 261 265 BlockIterator end = m_blocks.set().end(); 262 266 for (BlockIterator it = m_blocks.set().begin(); it != end; ++it) … … 273 277 template<typename Functor> inline typename Functor::ReturnType Heap::forEachBlock(Functor& functor) 274 278 { 279 canonicalizeBlocks(); 275 280 BlockIterator end = m_blocks.set().end(); 276 281 for (BlockIterator it = m_blocks.set().begin(); it != end; ++it) … … 284 289 return forEachBlock(functor); 285 290 } 291 292 inline void* Heap::allocate(NewSpace::SizeClass& sizeClass) 293 { 294 // This is a light-weight fast path to cover the most common case. 295 MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell; 296 if (UNLIKELY(!firstFreeCell)) 297 return allocateSlowCase(sizeClass); 298 299 sizeClass.firstFreeCell = firstFreeCell->next; 300 return firstFreeCell; 301 } 286 302 287 303 inline void* Heap::allocate(size_t bytes) -
trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp
r88519 r91039 50 50 51 51 MarkedBlock::MarkedBlock(const PageAllocationAligned& allocation, Heap* heap, size_t cellSize) 52 : m_nextAtom(firstAtom()) 53 , m_inNewSpace(false) 52 : m_inNewSpace(false) 54 53 , m_allocation(allocation) 55 54 , m_heap(heap) … … 57 56 m_atomsPerCell = (cellSize + atomSize - 1) / atomSize; 58 57 m_endAtom = atomsPerBlock - m_atomsPerCell + 1; 59 60 Structure* dummyMarkableCellStructure = heap->globalData()->dummyMarkableCellStructure.get();61 for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)62 new (&atoms()[i]) JSCell(*heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell);63 58 } 64 59 … … 86 81 } 87 82 83 MarkedBlock::FreeCell* MarkedBlock::lazySweep() 84 { 85 // This returns a free list that is ordered in reverse through the block. 86 // This is fine, since the allocation code makes no assumptions about the 87 // order of the free list. 88 89 FreeCell* result = 0; 90 91 for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) { 92 if (!m_marks.testAndSet(i)) { 93 JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[i]); 94 cell->~JSCell(); 95 FreeCell* freeCell = reinterpret_cast<FreeCell*>(cell); 96 freeCell->next = result; 97 result = freeCell; 98 } 99 } 100 101 return result; 102 } 103 104 MarkedBlock::FreeCell* MarkedBlock::blessNewBlockForFastPath() 105 { 106 // This returns a free list that is ordered in reverse through the block, 107 // as in lazySweep() above. 108 109 FreeCell* result = 0; 110 for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) { 111 m_marks.set(i); 112 FreeCell* freeCell = reinterpret_cast<FreeCell*>(&atoms()[i]); 113 freeCell->next = result; 114 result = freeCell; 115 } 116 return result; 117 } 118 119 void MarkedBlock::blessNewBlockForSlowPath() 120 { 121 Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get(); 122 for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) 123 new (&atoms()[i]) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell); 124 } 125 126 void MarkedBlock::canonicalizeBlock(FreeCell* firstFreeCell) 127 { 128 Structure* dummyMarkableCellStructure = m_heap->globalData()->dummyMarkableCellStructure.get(); 129 130 for (FreeCell* current = firstFreeCell; current;) { 131 FreeCell* next = current->next; 132 size_t i = atomNumber(current); 133 134 m_marks.clear(i); 135 new (static_cast<void*>(current)) JSCell(*m_heap->globalData(), dummyMarkableCellStructure, JSCell::CreatingEarlyCell); 136 137 current = next; 138 } 139 } 140 88 141 #if ENABLE(JSC_ZOMBIES) 89 142 void MarkedBlock::clearMarks() -
trunk/Source/JavaScriptCore/heap/MarkedBlock.h
r89156 r91039 49 49 static const size_t ownerSetsPerBlock = 8; // ~2% overhead. 50 50 51 struct FreeCell { 52 FreeCell* next; 53 }; 54 51 55 struct VoidFunctor { 52 56 typedef void ReturnType; … … 85 89 86 90 void* allocate(); 87 void resetAllocator();88 91 void sweep(); 92 93 // This invokes destructors on all cells that are not marked, marks 94 // them, and returns a linked list of those cells. 95 FreeCell* lazySweep(); 96 97 // These should be called immediately after a block is created. 98 // Blessing for fast path creates a linked list, while blessing for 99 // slow path creates dummy cells. 100 FreeCell* blessNewBlockForFastPath(); 101 void blessNewBlockForSlowPath(); 102 103 // This unmarks all cells on the free list, and allocates dummy JSCells 104 // in their place. 105 void canonicalizeBlock(FreeCell* firstFreeCell); 89 106 90 107 bool isEmpty(); … … 119 136 size_t ownerSetNumber(const JSCell*); 120 137 121 size_t m_nextAtom;122 138 size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom. 123 139 size_t m_atomsPerCell; … … 166 182 } 167 183 168 inline void MarkedBlock::resetAllocator()169 {170 m_nextAtom = firstAtom();171 }172 173 184 inline bool MarkedBlock::isEmpty() 174 185 { … … 236 247 } 237 248 } 238 239 inline void* MarkedBlock::allocate() 240 { 241 while (m_nextAtom < m_endAtom) { 242 if (!m_marks.testAndSet(m_nextAtom)) { 243 JSCell* cell = reinterpret_cast<JSCell*>(&atoms()[m_nextAtom]); 244 m_nextAtom += m_atomsPerCell; 245 destructor(cell); 246 return cell; 247 } 248 m_nextAtom += m_atomsPerCell; 249 } 250 251 return 0; 252 } 253 249 254 250 inline size_t MarkedBlock::ownerSetNumber(const JSCell* cell) 255 251 { -
trunk/Source/JavaScriptCore/heap/MarkedBlockSet.h
r88504 r91039 29 29 #include "MarkedBlock.h" 30 30 #include "TinyBloomFilter.h" 31 #include <wtf/HashSet.h> 31 32 32 33 namespace JSC { -
trunk/Source/JavaScriptCore/heap/NewSpace.cpp
r88519 r91039 49 49 sizeClass.nextBlock = block; 50 50 sizeClass.blockList.append(block); 51 ASSERT(!sizeClass.currentBlock); 52 ASSERT(!sizeClass.firstFreeCell); 53 sizeClass.currentBlock = block; 54 sizeClass.firstFreeCell = block->blessNewBlockForFastPath(); 51 55 } 52 56 … … 70 74 } 71 75 76 void NewSpace::canonicalizeBlocks() 77 { 78 for (size_t cellSize = preciseStep; cellSize < preciseCutoff; cellSize += preciseStep) 79 sizeClassFor(cellSize).canonicalizeBlock(); 80 81 for (size_t cellSize = impreciseStep; cellSize < impreciseCutoff; cellSize += impreciseStep) 82 sizeClassFor(cellSize).canonicalizeBlock(); 83 } 84 72 85 } // namespace JSC -
trunk/Source/JavaScriptCore/heap/NewSpace.h
r89077 r91039 51 51 SizeClass(); 52 52 void resetAllocator(); 53 53 void canonicalizeBlock(); 54 55 MarkedBlock::FreeCell* firstFreeCell; 56 MarkedBlock* currentBlock; 54 57 MarkedBlock* nextBlock; 55 58 DoublyLinkedList<MarkedBlock> blockList; … … 65 68 void addBlock(SizeClass&, MarkedBlock*); 66 69 void removeBlock(MarkedBlock*); 70 71 void canonicalizeBlocks(); 67 72 68 73 size_t waterMark(); … … 116 121 inline void* NewSpace::allocate(SizeClass& sizeClass) 117 122 { 118 for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) { 119 if (void* result = block->allocate()) 120 return result; 121 122 m_waterMark += block->capacity(); 123 } 124 125 return 0; 123 MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell; 124 if (!firstFreeCell) { 125 // There are two possibilities for why we got here: 126 // 1) We've exhausted the allocation cache for currentBlock, in which case 127 // currentBlock == nextBlock, and we know that there is no reason to 128 // repeat a lazy sweep of nextBlock because we won't find anything. 129 // 2) Allocation caches have been cleared, in which case nextBlock may 130 // have (and most likely does have) free cells, so we almost certainly 131 // should do a lazySweep for nextBlock. This also implies that 132 // currentBlock == 0. 133 134 if (sizeClass.currentBlock) { 135 ASSERT(sizeClass.currentBlock == sizeClass.nextBlock); 136 m_waterMark += sizeClass.nextBlock->capacity(); 137 sizeClass.nextBlock = sizeClass.nextBlock->next(); 138 sizeClass.currentBlock = 0; 139 } 140 141 for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) { 142 firstFreeCell = block->lazySweep(); 143 if (firstFreeCell) { 144 sizeClass.firstFreeCell = firstFreeCell; 145 sizeClass.currentBlock = block; 146 break; 147 } 148 149 m_waterMark += block->capacity(); 150 } 151 152 if (!firstFreeCell) 153 return 0; 154 } 155 156 ASSERT(firstFreeCell); 157 158 sizeClass.firstFreeCell = firstFreeCell->next; 159 return firstFreeCell; 126 160 } 127 161 … … 156 190 157 191 inline NewSpace::SizeClass::SizeClass() 158 : nextBlock(0) 192 : firstFreeCell(0) 193 , currentBlock(0) 194 , nextBlock(0) 159 195 , cellSize(0) 160 196 { … … 165 201 nextBlock = blockList.head(); 166 202 } 203 204 inline void NewSpace::SizeClass::canonicalizeBlock() 205 { 206 if (currentBlock) { 207 currentBlock->canonicalizeBlock(firstFreeCell); 208 firstFreeCell = 0; 209 } 210 211 ASSERT(!firstFreeCell); 212 213 currentBlock = 0; 214 firstFreeCell = 0; 215 } 167 216 168 217 } // namespace JSC -
trunk/Source/JavaScriptCore/heap/OldSpace.cpp
r88519 r91039 37 37 { 38 38 m_blocks.append(block); 39 block->blessNewBlockForSlowPath(); 39 40 } 40 41
Note: See TracChangeset
for help on using the changeset viewer.