2011-01-29 Geoffrey Garen <ggaren@apple.com>
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 30 Jan 2011 05:58:30 +0000 (05:58 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 30 Jan 2011 05:58:30 +0000 (05:58 +0000)
        Reviewed by Maciej Stachowiak.

        Switched heap to use the Bitmap class and removed CollectorBitmap
        https://bugs.webkit.org/show_bug.cgi?id=53391

        SunSpider says 1.005x as fast. Seems like a fluke.

        * runtime/MarkedSpace.cpp:
        (JSC::MarkedSpace::allocate): Updated for rename and returning a value
        rather than taking a value by reference.

        * runtime/MarkedSpace.h: Code reuse is good.

        * wtf/Bitmap.h:
        (WTF::::testAndSet): Added, since this is the one thing Bitmap was missing
        which CollectorBitmap had. (Renamed from the less conventional "getset".)

        (WTF::::nextPossiblyUnset): Renamed and changed to return a value for
        clarity. It's all the same with inlining.

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@77080 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/MarkedSpace.cpp
Source/JavaScriptCore/runtime/MarkedSpace.h
Source/JavaScriptCore/wtf/Bitmap.h

index 16bd377752c3e6393c4c820f5115bc4a51e1b080..d52f914afac80b1584574eabb5dbc20ca7a05122 100644 (file)
@@ -1,3 +1,25 @@
+2011-01-29  Geoffrey Garen  <ggaren@apple.com>
+
+        Reviewed by Maciej Stachowiak.
+
+        Switched heap to use the Bitmap class and removed CollectorBitmap
+        https://bugs.webkit.org/show_bug.cgi?id=53391
+        
+        SunSpider says 1.005x as fast. Seems like a fluke.
+
+        * runtime/MarkedSpace.cpp:
+        (JSC::MarkedSpace::allocate): Updated for rename and returning a value
+        rather than taking a value by reference.
+
+        * runtime/MarkedSpace.h: Code reuse is good.
+
+        * wtf/Bitmap.h:
+        (WTF::::testAndSet): Added, since this is the one thing Bitmap was missing
+        which CollectorBitmap had. (Renamed from the less conventional "getset".)
+
+        (WTF::::nextPossiblyUnset): Renamed and changed to return a value for
+        clarity. It's all the same with inlining.
+
 2011-01-28  Geoffrey Garen  <ggaren@apple.com>
 
         Reviewed by Maciej Stachowiak.
index aeb520f6a236b725638fba48c4635df6894b569d..f26e4f2d25ab1127d768ef23f1efca27940c1fe6 100644 (file)
@@ -150,7 +150,7 @@ void* MarkedSpace::allocate(size_t s)
                 ++m_heap.nextCell;
                 return cell;
             }
-            block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);
+            m_heap.nextCell = block->marked.nextPossiblyUnset(m_heap.nextCell);
         } while (m_heap.nextCell != HeapConstants::cellsPerBlock);
         m_heap.nextCell = 0;
     } while (++m_heap.nextBlock != m_heap.usedBlocks);
index 3b23d8c1c0ed2ef3b6fe8f229060606779a7a326..a51e697b4921cf5ea059f3d3e50fb99e335d6ebf 100644 (file)
@@ -24,6 +24,7 @@
 
 #include "MachineStackMarker.h"
 #include "PageAllocationAligned.h"
+#include <wtf/Bitmap.h>
 #include <wtf/FixedArray.h>
 #include <wtf/HashCountedSet.h>
 #include <wtf/Noncopyable.h>
@@ -124,50 +125,6 @@ namespace JSC {
     const size_t CELL_ALIGN_MASK = ~CELL_MASK;
     const size_t CELLS_PER_BLOCK = (BLOCK_SIZE - sizeof(MarkedSpace*)) * 8 * CELL_SIZE / (8 * CELL_SIZE + 1) / CELL_SIZE; // one bitmap byte can represent 8 cells.
     
-    const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
-    const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
-
-    struct CollectorBitmap {
-        FixedArray<uint32_t, BITMAP_WORDS> bits;
-        bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 
-        void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 
-        bool getset(size_t n)
-        {
-            unsigned i = (1 << (n & 0x1F));
-            uint32_t& b = bits[n >> 5];
-            bool r = !!(b & i);
-            b |= i;
-            return r;
-        } 
-        void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 
-        void clearAll() { memset(bits.data(), 0, sizeof(bits)); }
-        ALWAYS_INLINE void advanceToNextPossibleFreeCell(size_t& startCell)
-        {
-            if (!~bits[startCell >> 5])
-                startCell = (startCell & (~0x1F)) + 32;
-            else
-                ++startCell;
-        }
-        size_t count(size_t startCell = 0)
-        {
-            size_t result = 0;
-            for ( ; (startCell & 0x1F) != 0; ++startCell) {
-                if (get(startCell))
-                    ++result;
-            }
-            for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i)
-                result += WTF::bitCount(bits[i]);
-            return result;
-        }
-        size_t isEmpty() // Much more efficient than testing count() == 0.
-        {
-            for (size_t i = 0; i < BITMAP_WORDS; ++i)
-                if (bits[i] != 0)
-                    return false;
-            return true;
-        }
-    };
-  
     struct CollectorCell {
         FixedArray<double, CELL_ARRAY_LENGTH> memory;
     };
@@ -175,7 +132,7 @@ namespace JSC {
     class CollectorBlock {
     public:
         FixedArray<CollectorCell, CELLS_PER_BLOCK> cells;
-        CollectorBitmap marked;
+        WTF::Bitmap<CELLS_PER_BLOCK> marked;
         Heap* heap;
     };
 
@@ -208,7 +165,7 @@ namespace JSC {
 
     inline bool MarkedSpace::checkMarkCell(const JSCell* cell)
     {
-        return cellBlock(cell)->marked.getset(cellOffset(cell));
+        return cellBlock(cell)->marked.testAndSet(cellOffset(cell));
     }
 
     inline void MarkedSpace::markCell(JSCell* cell)
index 4dd88f6d6be909fbd25c8c9f56b1b3aab4ee31fc..2fb73050002c716d5f1485b993befcdc0ce26893 100644 (file)
@@ -21,7 +21,6 @@
 
 #include "FixedArray.h"
 #include "StdLibExtras.h"
-
 #include <stdint.h>
 
 namespace WTF {
@@ -36,9 +35,10 @@ public:
 
     bool get(size_t) const;
     void set(size_t);
+    bool testAndSet(size_t);
+    size_t nextPossiblyUnset(size_t) const;
     void clear(size_t);
     void clearAll();
-    void advanceToNextFreeBit(size_t&) const;
     size_t count(size_t = 0) const;
     size_t isEmpty() const;
     size_t isFull() const;
@@ -75,6 +75,16 @@ inline void Bitmap<size>::set(size_t n)
     bits[n / wordSize] |= (one << (n % wordSize));
 }
 
+template<size_t size>
+inline bool Bitmap<size>::testAndSet(size_t n)
+{
+    WordType mask = one << (n % wordSize);
+    size_t index = n / wordSize;
+    bool result = bits[index] & mask;
+    bits[index] |= mask;
+    return result;
+}
+
 template<size_t size>
 inline void Bitmap<size>::clear(size_t n)
 {
@@ -88,12 +98,11 @@ inline void Bitmap<size>::clearAll()
 }
 
 template<size_t size>
-inline void Bitmap<size>::advanceToNextFreeBit(size_t& start) const
+inline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const
 {
     if (!~bits[start / wordSize])
-        start = ((start / wordSize) + 1) * wordSize;
-    else
-        ++start;
+        return ((start / wordSize) + 1) * wordSize;
+    return start + 1;
 }
 
 template<size_t size>