Reviewed by Darin and Geoff.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 23 Apr 2007 21:54:33 +0000 (21:54 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 23 Apr 2007 21:54:33 +0000 (21:54 +0000)
        - move mark and collectOnMainThreadOnly bits into separate bitmaps

        This saves 4 bytes per cell, allowing shrink of cell size to 32,
        which leads to a .8% speed improvement on iBench.

        This is only feasible because of all the previous changes on the branch.

        * kjs/collector.cpp:
        (KJS::allocateBlock): Adjust for some renames of constants.
        (KJS::Collector::markStackObjectsConservatively): Now that cells are 32 bytes (64
        bytes on 64-bit) the cell alignment check can be made much more strict, and also
        obsoletes the need for a % sizeof(CollectorCell) check. Also, we can mask off the low
        bits of the pointer to have a potential block pointer to look for.
        (KJS::Collector::collectOnMainThreadOnly): Use bitmap.
        (KJS::Collector::markMainThreadOnlyObjects): Use bitmap.
        (KJS::Collector::collect): When sweeping, use bitmaps directly to find mark bits.
        * kjs/collector.h:
        (KJS::): Move needed constants and type declarations here.
        (KJS::CollectorBitmap::get): Bit twiddling to get a bitmap value.
        (KJS::CollectorBitmap::set): Bit twiddling to set a bitmap bit to true.
        (KJS::CollectorBitmap::clear): Bit twiddling to set a bitmap bit to false.
        (KJS::CollectorBitmap::clearAll): Clear whole bitmap at one go.
        (KJS::Collector::cellBlock): New operation, compute the block pointer for
        a cell by masking off low bits.
        (KJS::Collector::cellOffset): New operation, compute the cell offset for a
        cell by masking off high bits and dividing (actually a shift).
        (KJS::Collector::isCellMarked): Check mark bit in bitmap
        (KJS::Collector::markCell): Set mark bit in bitmap.
        * kjs/value.h:
        (KJS::JSCell::JSCell): No more bits.
        (KJS::JSCell::marked): Let collector handle it.
        (KJS::JSCell::mark): Let collector handle it.

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

JavaScriptCore/ChangeLog
JavaScriptCore/kjs/collector.cpp
JavaScriptCore/kjs/collector.h
JavaScriptCore/kjs/value.h

index bf6e679..6a1dd9a 100644 (file)
@@ -1,3 +1,40 @@
+2007-04-23  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin and Geoff.
+        
+        - move mark and collectOnMainThreadOnly bits into separate bitmaps
+        
+        This saves 4 bytes per cell, allowing shrink of cell size to 32,
+        which leads to a .8% speed improvement on iBench.
+        
+        This is only feasible because of all the previous changes on the branch.
+
+        * kjs/collector.cpp:
+        (KJS::allocateBlock): Adjust for some renames of constants. 
+        (KJS::Collector::markStackObjectsConservatively): Now that cells are 32 bytes (64 
+        bytes on 64-bit) the cell alignment check can be made much more strict, and also
+        obsoletes the need for a % sizeof(CollectorCell) check. Also, we can mask off the low
+        bits of the pointer to have a potential block pointer to look for.
+        (KJS::Collector::collectOnMainThreadOnly): Use bitmap.
+        (KJS::Collector::markMainThreadOnlyObjects): Use bitmap.
+        (KJS::Collector::collect): When sweeping, use bitmaps directly to find mark bits.
+        * kjs/collector.h:
+        (KJS::): Move needed constants and type declarations here.
+        (KJS::CollectorBitmap::get): Bit twiddling to get a bitmap value.
+        (KJS::CollectorBitmap::set): Bit twiddling to set a bitmap bit to true.
+        (KJS::CollectorBitmap::clear): Bit twiddling to set a bitmap bit to false.
+        (KJS::CollectorBitmap::clearAll): Clear whole bitmap at one go.
+        (KJS::Collector::cellBlock): New operation, compute the block pointer for
+        a cell by masking off low bits.
+        (KJS::Collector::cellOffset): New operation, compute the cell offset for a
+        cell by masking off high bits and dividing (actually a shift).
+        (KJS::Collector::isCellMarked): Check mark bit in bitmap
+        (KJS::Collector::markCell): Set mark bit in bitmap.
+        * kjs/value.h:
+        (KJS::JSCell::JSCell): No more bits.
+        (KJS::JSCell::marked): Let collector handle it.
+        (KJS::JSCell::mark): Let collector handle it.
+
 2007-04-23  Anders Carlsson  <andersca@apple.com>
 
         Build fix.
index bbaaf2e..1e097fc 100644 (file)
@@ -67,43 +67,12 @@ namespace KJS {
 
 // tunable parameters
 
-template<size_t bytesPerWord> struct CellSize;
-template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 40; }; // 32-bit
-template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; // 64-bit
-
-const size_t BLOCK_SIZE = (16 * 4096); // 64k
 const size_t SPARE_EMPTY_BLOCKS = 2;
 const size_t MIN_ARRAY_SIZE = 14;
 const size_t GROWTH_FACTOR = 2;
 const size_t LOW_WATER_FACTOR = 4;
 const size_t ALLOCATIONS_PER_COLLECTION = 1000;
 
-// derived constants
-const size_t PTR_IN_BLOCK_MASK = (BLOCK_SIZE - 1);
-const size_t BLOCK_MASK = (~PTR_IN_BLOCK_MASK);
-const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
-const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? 1 : 0);
-const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
-const size_t CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void*) * 8) / (CELL_SIZE * 8));
-
-
-struct CollectorCell {
-  union {
-    double memory[CELL_ARRAY_LENGTH];
-    struct {
-      void *zeroIfFree;
-      ptrdiff_t next;
-    } freeCell;
-  } u;
-};
-
-
-struct CollectorBlock {
-  CollectorCell cells[CELLS_PER_BLOCK];
-  uint32_t usedCells;
-  CollectorCell *freeList;
-};
-
 struct CollectorHeap {
   CollectorBlock **blocks;
   size_t numBlocks;
@@ -145,7 +114,7 @@ static CollectorBlock* allocateBlock()
 {
 #if PLATFORM(DARWIN)    
     vm_address_t address = 0;
-    vm_map(current_task(), &address, BLOCK_SIZE, PTR_IN_BLOCK_MASK, VM_FLAGS_ANYWHERE, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);
+    vm_map(current_task(), &address, BLOCK_SIZE, BLOCK_OFFSET_MASK, VM_FLAGS_ANYWHERE, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);
 #elif PLATFORM(WIN)
      // windows virtual address granularity is naturally 64k
     LPVOID address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
@@ -164,8 +133,8 @@ static CollectorBlock* allocateBlock()
     uintptr_t address = reinterpret_cast<uintptr_t>(mmapResult);
 
     size_t adjust = 0;
-    if ((address & PTR_IN_BLOCK_MASK) != 0)
-        adjust = BLOCK_SIZE - (address & PTR_IN_BLOCK_MASK);
+    if ((address & BLOCK_OFFSET_MASK) != 0)
+        adjust = BLOCK_SIZE - (address & BLOCK_OFFSET_MASK);
 
     if (adjust > 0)
         munmap(reinterpret_cast<void*>(address), adjust);
@@ -410,23 +379,23 @@ void Collector::registerThread()
 
 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
 
-// cells are 8-byte aligned
-#define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
+// cell size needs to be a power of two for this to be valid
+#define IS_CELL_ALIGNED(p) (((intptr_t)(p) & CELL_MASK) == 0)
 
 void Collector::markStackObjectsConservatively(void *start, void *end)
 {
   if (start > end) {
-    void *tmp = start;
+    voidtmp = start;
     start = end;
     end = tmp;
   }
 
-  ASSERT(((char *)end - (char *)start) < 0x1000000);
+  ASSERT(((char*)end - (char*)start) < 0x1000000);
   ASSERT(IS_POINTER_ALIGNED(start));
   ASSERT(IS_POINTER_ALIGNED(end));
   
-  char **p = (char **)start;
-  char **e = (char **)end;
+  char** p = (char**)start;
+  char** e = (char**)end;
   
   size_t usedBlocks = heap.usedBlocks;
   CollectorBlock **blocks = heap.blocks;
@@ -434,13 +403,14 @@ void Collector::markStackObjectsConservatively(void *start, void *end)
   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 
   while (p != e) {
-    char *x = *p++;
+    charx = *p++;
     if (IS_CELL_ALIGNED(x) && x) {
+      uintptr_t offset = reinterpret_cast<uintptr_t>(x) & BLOCK_OFFSET_MASK;
+      CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(x - offset);
       for (size_t block = 0; block < usedBlocks; block++) {
-        size_t offset = x - reinterpret_cast<char *>(blocks[block]);
-        if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0) {
-          if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
-            JSCell *imp = reinterpret_cast<JSCell *>(x);
+        if ((blocks[block] == blockAddr) & (offset <= lastCellOffset)) {
+          if (((CollectorCell*)x)->u.freeCell.zeroIfFree != 0) {
+            JSCell* imp = reinterpret_cast<JSCell*>(x);
             if (!imp->marked())
               imp->mark();
           }
@@ -685,7 +655,7 @@ void Collector::collectOnMainThreadOnly(JSValue* value)
       return;
 
     JSCell* cell = value->downcast();
-    cell->m_collectOnMainThreadOnly = true;
+    cellBlock(cell)->collectOnMainThreadOnly.set(cellOffset(cell));
     ++mainThreadOnlyObjectCount;
 }
 
@@ -728,10 +698,11 @@ void Collector::markMainThreadOnlyObjects()
             if (cell->u.freeCell.zeroIfFree == 0)
                 ++minimumCellsToProcess;
             else {
-                JSCell* imp = reinterpret_cast<JSCell*>(cell);
-                if (imp->m_collectOnMainThreadOnly) {
-                    if(!imp->marked())
+                if (curBlock->collectOnMainThreadOnly.get(i)) {
+                    if (!curBlock->marked.get(i)) {
+                        JSCell* imp = reinterpret_cast<JSCell*>(cell);
                         imp->mark();
+                    }
                     if (++count == mainThreadOnlyObjectCount)
                         return;
                 }
@@ -799,20 +770,22 @@ bool Collector::collect()
     if (usedCells == CELLS_PER_BLOCK) {
       // special case with a block where all cells are used -- testing indicates this happens often
       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
-        CollectorCell *cell = curBlock->cells + i;
-        JSCell *imp = reinterpret_cast<JSCell *>(cell);
-        if (imp->m_marked) {
-          imp->m_marked = false;
-        } else {
+        if (!curBlock->marked.get(i)) {
+          CollectorCell* cell = curBlock->cells + i;
+
           // special case for allocated but uninitialized object
           // (We don't need this check earlier because nothing prior this point 
           // assumes the object has a valid vptr.)
           if (cell->u.freeCell.zeroIfFree == 0)
             continue;
 
-          ASSERT(currentThreadIsMainThread || !imp->m_collectOnMainThreadOnly);
-          if (imp->m_collectOnMainThreadOnly)
+          JSCell* imp = reinterpret_cast<JSCell*>(cell);
+
+          ASSERT(currentThreadIsMainThread || !curBlock->collectOnMainThreadOnly.get(i));
+          if (curBlock->collectOnMainThreadOnly.get(i)) {
+            curBlock->collectOnMainThreadOnly.clear(i);
             --mainThreadOnlyObjectCount;
+          }
           imp->~JSCell();
           --usedCells;
           --numLiveObjects;
@@ -830,13 +803,13 @@ bool Collector::collect()
         if (cell->u.freeCell.zeroIfFree == 0) {
           ++minimumCellsToProcess;
         } else {
-          JSCell *imp = reinterpret_cast<JSCell *>(cell);
-          if (imp->m_marked) {
-            imp->m_marked = false;
-          } else {
-            ASSERT(currentThreadIsMainThread || !imp->m_collectOnMainThreadOnly);
-            if (imp->m_collectOnMainThreadOnly)
+          if (!curBlock->marked.get(i)) {
+            JSCell *imp = reinterpret_cast<JSCell *>(cell);
+            ASSERT(currentThreadIsMainThread || !curBlock->collectOnMainThreadOnly.get(i));
+            if (curBlock->collectOnMainThreadOnly.get(i)) {
+              curBlock->collectOnMainThreadOnly.clear(i);
               --mainThreadOnlyObjectCount;
+            }
             imp->~JSCell();
             --usedCells;
             --numLiveObjects;
@@ -852,6 +825,7 @@ bool Collector::collect()
     
     curBlock->usedCells = static_cast<uint32_t>(usedCells);
     curBlock->freeList = freeList;
+    curBlock->marked.clearAll();
 
     if (usedCells == 0) {
       emptyBlocks++;
index e2a3b90..0282293 100644 (file)
 #ifndef KJSCOLLECTOR_H_
 #define KJSCOLLECTOR_H_
 
-#include "value.h"
 #include <wtf/HashCountedSet.h>
 
 #define KJS_MEM_LIMIT 500000
 
 namespace KJS {
 
+  class JSCell;
+  class JSValue;
+  class CollectorBlock;
+
   class Collector {
   public:
     static void* allocate(size_t s);
@@ -60,7 +63,14 @@ namespace KJS {
     
     static void registerAsMainThread();
 
+    static bool isCellMarked(const JSCell*);
+    static void markCell(JSCell*);
+
   private:
+    static const CollectorBlock* cellBlock(const JSCell*);
+    static CollectorBlock* cellBlock(JSCell*);
+    static size_t cellOffset(const JSCell* cell);
+
     Collector();
 
     static void markProtectedObjects();
@@ -74,6 +84,76 @@ namespace KJS {
     static bool memoryFull;
   };
 
+  // tunable parameters
+  template<size_t bytesPerWord> struct CellSize;
+
+  // cell size needs to be a power of two for certain optimizations in collector.cpp
+  template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; }; // 32-bit
+  template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; }; // 64-bit
+  const size_t BLOCK_SIZE = 16 * 4096; // 64k
+  
+  // derived constants
+  const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
+  const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
+  const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
+  const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
+  const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
+  const size_t CELL_MASK = CELL_SIZE - 1;
+  const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
+  const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
+  const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
+  
+  struct CollectorBitmap {
+    uint32_t bits[BITMAP_WORDS];
+    bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); } 
+    void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); } 
+    void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); } 
+    void clearAll() { memset(bits, 0, sizeof(bits)); }
+  };
+  
+  struct CollectorCell {
+    union {
+      double memory[CELL_ARRAY_LENGTH];
+      struct {
+        void* zeroIfFree;
+        ptrdiff_t next;
+      } freeCell;
+    } u;
+  };
+
+  struct CollectorBlock {
+    CollectorCell cells[CELLS_PER_BLOCK];
+    uint32_t usedCells;
+    CollectorCell* freeList;
+    CollectorBitmap marked;
+    CollectorBitmap collectOnMainThreadOnly;
+  };
+
+  inline const CollectorBlock* Collector::cellBlock(const JSCell* cell)
+  {
+    return reinterpret_cast<const CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
+  }
+
+  inline CollectorBlock* Collector::cellBlock(JSCell* cell)
+  {
+    return const_cast<CollectorBlock*>(cellBlock(const_cast<const JSCell*>(cell)));
+  }
+
+  inline size_t Collector::cellOffset(const JSCell* cell)
+  {
+    return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
+  }
+
+  inline bool Collector::isCellMarked(const JSCell* cell)
+  {
+    return cellBlock(cell)->marked.get(cellOffset(cell));
+  }
+
+  inline void Collector::markCell(JSCell* cell)
+  {
+    cellBlock(cell)->marked.set(cellOffset(cell));
+  }
+
 } // namespace KJS
 
 #endif /* KJSCOLLECTOR_H_ */
index 8b1d416..44eaf32 100644 (file)
@@ -25,6 +25,7 @@
 #define KJS_VALUE_H
 
 #include "JSImmediate.h"
+#include "collector.h"
 #include "ustring.h"
 #include <stddef.h> // for size_t
 
@@ -154,10 +155,6 @@ public:
     void *operator new(size_t);
     virtual void mark();
     bool marked() const;
-
-private:
-    bool m_collectOnMainThreadOnly : 1;
-    bool m_marked : 1;
 };
 
 JSValue *jsNumberCell(double);
@@ -204,8 +201,6 @@ inline JSValue::~JSValue()
 }
 
 inline JSCell::JSCell()
-    : m_collectOnMainThreadOnly(false)
-    , m_marked(false)
 {
 }
 
@@ -230,12 +225,12 @@ inline bool JSCell::isObject() const
 
 inline bool JSCell::marked() const
 {
-    return m_marked;
+    return Collector::isCellMarked(this);
 }
 
 inline void JSCell::mark()
 {
-    m_marked = true;
+    return Collector::markCell(this);
 }
 
 inline JSCell *JSValue::downcast()