Attachment 361863 Details for Bug 194566 – proposed patch.

[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:

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;

Actions: View | Formatted Diff | Diff

Attachments on bug 194566: 361863 | 361899