WebKit Bugzilla
Attachment 361863 Details for
Bug 194566
: Create a randomized free list for new StructureIDs on StructureIDTable resize.
Home
|
New
|
Browse
|
Search
|
[?]
|
Reports
|
Requests
|
Help
|
New Account
|
Log In
Remember
[x]
|
Forgot Password
Login:
[x]
[patch]
proposed patch.
bug-194566.patch (text/plain), 4.83 KB, created by
Mark Lam
on 2019-02-12 16:34:01 PST
(
hide
)
Description:
proposed patch.
Filename:
MIME Type:
Creator:
Mark Lam
Created:
2019-02-12 16:34:01 PST
Size:
4.83 KB
patch
obsolete
>Index: Source/JavaScriptCore/ChangeLog >=================================================================== >--- Source/JavaScriptCore/ChangeLog (revision 241326) >+++ Source/JavaScriptCore/ChangeLog (working copy) >@@ -1,3 +1,20 @@ >+2019-02-12 Mark Lam <mark.lam@apple.com> >+ >+ Create a randomized free list for new StructureIDs on StructureIDTable resize. >+ https://bugs.webkit.org/show_bug.cgi?id=194566 >+ <rdar://problem/47975502> >+ >+ Reviewed by NOBODY (OOPS!). >+ >+ This patch appears to be perf neutral on JetStream2 (as run from the command line). >+ >+ * runtime/StructureIDTable.cpp: >+ (JSC::StructureIDTable::StructureIDTable): >+ (JSC::StructureIDTable::makeFreeListFromRange): >+ (JSC::StructureIDTable::resize): >+ (JSC::StructureIDTable::allocateID): >+ * runtime/StructureIDTable.h: >+ > 2019-02-12 Michael Catanzaro <mcatanzaro@igalia.com> > > Unreviewed, fix -Wimplicit-fallthrough warning after r241140 >Index: Source/JavaScriptCore/runtime/StructureIDTable.cpp >=================================================================== >--- Source/JavaScriptCore/runtime/StructureIDTable.cpp (revision 241316) >+++ Source/JavaScriptCore/runtime/StructureIDTable.cpp (working copy) >@@ -33,12 +33,67 @@ namespace JSC { > > StructureIDTable::StructureIDTable() > : m_table(makeUniqueArray<StructureOrOffset>(s_initialSize)) >- , m_size(0) >+ , m_size(1) > , m_capacity(s_initialSize) > { > // We pre-allocate the first offset so that the null Structure > // can still be represented as the StructureID '0'. >- allocateID(0); >+ table()[0].structure = nullptr; >+ >+ makeFreeListFromRange(m_size, m_capacity - 1); >+} >+ >+void StructureIDTable::makeFreeListFromRange(uint32_t first, uint32_t last) >+{ >+ ASSERT(!m_firstFreeOffset); >+ ASSERT(!m_lastFreeOffset); >+ >+ // Put all the new IDs on the free list sequentially. >+ uint32_t head = first; >+ uint32_t tail = last; >+ for (uint32_t i = first; i < last; ++i) >+ table()[i].offset = i + 1; >+ table()[last].offset = 0; >+ >+ // Randomize the free list. >+ uint32_t size = last - first + 1; >+ uint32_t maxIterations = (size * 2) / 3; >+ for (uint32_t count = 0; count < maxIterations; ++count) { >+ // Move a random pick either to the head or the tail of the free list. >+ uint32_t random = m_weakRandom.getUint32(); >+ uint32_t nodeBefore = first + (random % size); >+ uint32_t pick = table()[nodeBefore].offset; >+ if (pick) { >+ uint32_t nodeAfter = table()[pick].offset; >+ table()[nodeBefore].offset = nodeAfter; >+ if ((random & 1) || !nodeAfter) { >+ // Move to the head. >+ table()[pick].offset = m_firstFreeOffset; >+ head = pick; >+ if (!nodeAfter) >+ tail = nodeBefore; >+ } else { >+ // Move to the tail. >+ table()[pick].offset = 0; >+ table()[tail].offset = pick; >+ tail = pick; >+ } >+ } >+ } >+ >+ // Cut list in half and swap halves. >+ uint32_t cut = first + (m_weakRandom.getUint32() % size); >+ uint32_t afterCut = table()[cut].offset; >+ if (afterCut) { >+ table()[tail].offset = head; >+ tail = cut; >+ head = afterCut; >+ table()[cut].offset = 0; >+ } >+ >+ m_firstFreeOffset = head; >+ m_lastFreeOffset = tail; >+ m_size = m_capacity; > } > > void StructureIDTable::resize(size_t newCapacity) >@@ -60,6 +115,8 @@ void StructureIDTable::resize(size_t new > > // Update the capacity. > m_capacity = newCapacity; >+ >+ makeFreeListFromRange(m_size, m_capacity - 1); > } > > void StructureIDTable::flushOldTables() >@@ -74,21 +131,8 @@ StructureID StructureIDTable::allocateID > RELEASE_ASSERT(m_capacity <= UINT_MAX); > if (m_size == m_capacity) > resize(m_capacity * 2); >- ASSERT(m_size < m_capacity); >- >- StructureOrOffset newEntry; >- newEntry.structure = structure; >- >- if (m_size == s_unusedID) { >- m_size++; >- return allocateID(structure); >- } >- >- StructureID result = m_size; >- table()[result] = newEntry; >- m_size++; >- ASSERT(!isNuked(result)); >- return result; >+ ASSERT(m_size == m_capacity); >+ ASSERT(m_firstFreeOffset); > } > > ASSERT(m_firstFreeOffset != s_unusedID); >Index: Source/JavaScriptCore/runtime/StructureIDTable.h >=================================================================== >--- Source/JavaScriptCore/runtime/StructureIDTable.h (revision 241316) >+++ Source/JavaScriptCore/runtime/StructureIDTable.h (working copy) >@@ -97,6 +97,7 @@ public: > > private: > void resize(size_t newCapacity); >+ void makeFreeListFromRange(uint32_t first, uint32_t last); > > union StructureOrOffset { > WTF_MAKE_FAST_ALLOCATED;
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Diff
View Attachment As Raw
Actions:
View
|
Formatted Diff
|
Diff
Attachments on
bug 194566
:
361863
|
361899