Changeset 2845 in webkit for trunk/JavaScriptCore/kjs/collector.cpp

Timestamp:

Nov 23, 2002, 4:04:08 PM (23 years ago)

Author:

mjs

Message:

Numerous collector changes for a net gain of 3% on JS ibench:

• Replaced per-block bitmap with free list.
• Increased number of empty blocks kept around to 2.
• Doubled block size.
• When scanning heap in collector, skip scanning the rest of a block as soon as we see as many live cells as the the number of used cells it had originally.

Also the following collector changes unrelated to performance:

• Made constants const int' instead of static const int'.
• Miscellaneous code cleanup.

• kjs/collector.cpp:

• Added debugging mode enabled by defining DEBUG_GC which asserts when a destroyed ValueImp

• kjs/internal.cpp: (ContextImp::mark):
• kjs/value.cpp: (Value::Value):
• kjs/value.h:
• kjs/config.h:

File:

• trunk/JavaScriptCore/kjs/collector.cpp (modified) (17 diffs)

trunk/JavaScriptCore/kjs/collector.cpp

@@ -2 +2 @@
 /*
  *  This file is part of the KDE libraries
- *  Copyright (C) 2002 Apple Computer, Inc.
+ *  Copyright (C) 2002 Apple Computer, Inc
  *
  *  This library is free software; you can redistribute it and/or
@@ -30 +30 @@
 #endif
 
+#include <collector.h>
+#include <value.h>
+#include <internal.h>
+
 namespace KJS {
 
 // tunable parameters
-static const int CELL_SIZE = 56;
-static const int BLOCK_SIZE = (4 * 4096);
-static const int SPARE_EMPTY_BLOCKS = 1;
-static const int MIN_ARRAY_SIZE = 14;
-static const int GROWTH_FACTOR = 2;
-static const int LOW_WATER_FACTOR = 4;
+const int MINIMUM_CELL_SIZE = 56;
+const int BLOCK_SIZE = (8 * 4096);
+const int SPARE_EMPTY_BLOCKS = 2;
+const int MIN_ARRAY_SIZE = 14;
+const int GROWTH_FACTOR = 2;
+const int LOW_WATER_FACTOR = 4;
+const int ALLOCATIONS_PER_COLLECTION = 1000;
 
 // derived constants
-static const int WORD_SIZE = sizeof(uint32_t);
-static const int BITS_PER_WORD = WORD_SIZE * 8;
-static const uint32_t ALL_BITS_ON = 0xffffffff;
-static const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - 32) / (CELL_SIZE * 8 + 1));
-static const int BITMAP_SIZE = (CELLS_PER_BLOCK / BITS_PER_WORD) + (CELLS_PER_BLOCK % BITS_PER_WORD != 0 ? 1 : 0);
+const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
+const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
+const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
+
 
 
 struct CollectorCell {
-  char memory[CELL_SIZE];
+  union {
+    double memory[CELL_ARRAY_LENGTH];
+    struct {
+      void *zeroIfFree;
+      CollectorCell *next;
+    } freeCell;
+  } u;
 };
 
-static const int ALLOCATIONS_PER_COLLECTION = 1000;
 
 struct CollectorBlock {
-  CollectorBlock() : usedCells(0) { memset(bitmap, 0, BITMAP_SIZE * WORD_SIZE); }
-  
-  uint32_t bitmap[BITMAP_SIZE];
+  CollectorCell cells[CELLS_PER_BLOCK];
   int32_t usedCells;
-  CollectorCell cells[CELLS_PER_BLOCK];
+  CollectorCell *freeList;
 };
 
@@ -66 +73 @@
   int numBlocks;
   int usedBlocks;
+  int firstBlockWithPossibleSpace;
   
   CollectorCell **oversizeCells;
@@ -75 +83 @@
 };
 
-static CollectorHeap heap = {NULL, 0, 0, NULL, 0, 0, 0, 0};
+static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
 
 bool Collector::memoryFull = false;
-
 
 void* Collector::allocate(size_t s)
@@ -86 +93 @@
   
   // collect if needed
-  if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION)
+  if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
     collect();
+  }
   
   if (s > (unsigned)CELL_SIZE) {
@@ -109 +117 @@
   CollectorBlock *targetBlock = NULL;
   
-  // try to find free space in an existing block
-  for (int i = 0; i < heap.usedBlocks; i++) {
+  int i;
+  for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
     if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
       targetBlock = heap.blocks[i];
@@ -116 +124 @@
     }
   }
+
+  heap.firstBlockWithPossibleSpace = i;
   
   if (targetBlock == NULL) {
@@ -125 +135 @@
     }
     
-    targetBlock = new CollectorBlock();
+    targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
+    targetBlock->freeList = targetBlock->cells;
     heap.blocks[heap.usedBlocks] = targetBlock;
     heap.usedBlocks++;
   }
   
-  // find a free spot in the block
-  for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-    uint32_t word = targetBlock->bitmap[wordInBitmap];
-    if (word == ALL_BITS_ON) {
-      continue;
-    }
-    for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-      if ((word & (1 << bitInWord)) == 0) {
-        int cellPos = BITS_PER_WORD * wordInBitmap + bitInWord;
-        if (cellPos < CELLS_PER_BLOCK) {
-          targetBlock->bitmap[wordInBitmap] |= (1 << bitInWord);
-          targetBlock->usedCells++;
-          heap.numLiveObjects++;
-
-          ((ValueImp *)(targetBlock->cells + cellPos))->_flags = 0;
-          return (void *)(targetBlock->cells + cellPos);
-        }
-      }
-    }
-  }
-  // unreachable, if the free count wasn't 0 there has to be a free
-  // cell in the block
-  assert(false);
-
-  return false;
+  // find a free spot in the block and detach it from the free list
+  CollectorCell *newCell = targetBlock->freeList;
+
+  if (newCell->u.freeCell.next != NULL) {
+    targetBlock->freeList = newCell->u.freeCell.next;
+  } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
+    // last cell in this block
+    targetBlock->freeList = NULL;
+  } else {
+    // all next pointers are initially 0, meaning "next cell"
+    targetBlock->freeList = newCell + 1;
+  }
+
+  targetBlock->usedCells++;
+  heap.numLiveObjects++;
+
+  ((ValueImp *)(newCell))->_flags = 0;
+  return (void *)(newCell);
 }
 
@@ -174 +178 @@
   // mark any other objects that we wouldn't delete anyway
   for (int block = 0; block < heap.usedBlocks; block++) {
-    for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-      uint32_t word = heap.blocks[block]->bitmap[wordInBitmap];
-      for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-        ValueImp *imp = (ValueImp *)(heap.blocks[block]->cells + BITS_PER_WORD * wordInBitmap + bitInWord);
+
+    int minimumCellsToProcess = heap.blocks[block]->usedCells;
+    CollectorBlock *curBlock = heap.blocks[block];
+
+    for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+      if (minimumCellsToProcess < cell) {
+        goto skip_block_mark;
+      }
         
-        if ((word & (1 << bitInWord)) &&
-            (imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
+      ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+
+      if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
+        
+        if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
             ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
           imp->mark();
         }
-      }
-    }
+      } else {
+        minimumCellsToProcess++;
+      }
+    }
+  skip_block_mark: ;
   }
   
@@ -201 +215 @@
 
   for (int block = 0; block < heap.usedBlocks; block++) {
-    for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-      uint32_t word = heap.blocks[block]->bitmap[wordInBitmap];
-      for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-        
-        if (word & (1 << bitInWord)) {
-        ValueImp *imp = (ValueImp *)(heap.blocks[block]->cells + BITS_PER_WORD * wordInBitmap + bitInWord);
-          if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
-            //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
-            // emulate destructing part of 'operator delete()'
-            imp->~ValueImp();
-            heap.blocks[block]->bitmap[wordInBitmap] &= ~(1 << bitInWord);
-            heap.blocks[block]->usedCells--;
-            heap.numLiveObjects--;
-            deleted = true;
-          } else {
-            imp->_flags &= ~ValueImp::VI_MARKED;
-          }
+    CollectorBlock *curBlock = heap.blocks[block];
+
+    int minimumCellsToProcess = curBlock->usedCells;
+
+    for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+      if (minimumCellsToProcess < cell) {
+        goto skip_block_sweep;
+      }
+
+      ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+
+      if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
+        if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
+          //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
+          // emulate destructing part of 'operator delete()'
+          imp->~ValueImp();
+          curBlock->usedCells--;
+          heap.numLiveObjects--;
+          deleted = true;
+
+          // put it on the free list
+          ((CollectorCell *)imp)->u.freeCell.zeroIfFree = 0;
+          ((CollectorCell *)imp)->u.freeCell.next = curBlock->freeList;
+          curBlock->freeList = (CollectorCell *)imp;
+
+        } else {
+          imp->_flags &= ~ValueImp::VI_MARKED;
         }
-      }
-    }
+      } else {
+        minimumCellsToProcess++;
+      }
+    }
+
+  skip_block_sweep:
 
     if (heap.blocks[block]->usedCells == 0) {
@@ -240 +268 @@
   }
 
+  if (deleted) {
+    heap.firstBlockWithPossibleSpace = 0;
+  }
   
   int cell = 0;
@@ -269 +300 @@
   }
   
-  // possibly free some completely empty collector blocks ?
-  // compact array of collector blocks
-  
   heap.numAllocationsSinceLastCollect = 0;
   
@@ -309 +337 @@
   int count = 0;
   for (int block = 0; block < heap.usedBlocks; block++) {
-    for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-      uint32_t word = heap.blocks[block]->bitmap[wordInBitmap];
-      for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-        ValueImp *imp = (ValueImp *)(heap.blocks[block]->cells + BITS_PER_WORD * wordInBitmap + bitInWord);
-        
-        if ((word & (1 << bitInWord)) &&
-            (imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
-          ++count;
-        }
+    CollectorBlock *curBlock = heap.blocks[block];
+
+    for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+      ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+      
+      if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
+          (imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
+        ++count;
       }
     }
@@ -324 +351 @@
   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
-      if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
-        ++count;
-      }
+    if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
+      ++count;
+    }
   }
 
@@ -336 +363 @@
   int count = 0;
   for (int block = 0; block < heap.usedBlocks; block++) {
-    for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-      uint32_t word = heap.blocks[block]->bitmap[wordInBitmap];
-      for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-        ValueImp *imp = (ValueImp *)(heap.blocks[block]->cells + BITS_PER_WORD * wordInBitmap + bitInWord);
-        
-        if ((word & (1 << bitInWord)) &&
-            imp->refcount != 0) {
-          ++count;
-        }
+    CollectorBlock *curBlock = heap.blocks[block];
+
+    for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+      ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+      
+      if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
+          imp->refcount != 0) {
+        ++count;
       }
     }
@@ -362 +388 @@
 {
   CFMutableSetRef classes = CFSetCreateMutable(NULL, 0, &kCFTypeSetCallBacks);
-
+  
   for (int block = 0; block < heap.usedBlocks; block++) {
-    for (int wordInBitmap = 0; wordInBitmap < BITMAP_SIZE; wordInBitmap++) {
-      uint32_t word = heap.blocks[block]->bitmap[wordInBitmap];
-      for (int bitInWord = 0; bitInWord < BITS_PER_WORD; bitInWord++) {
-        ValueImp *imp = (ValueImp *)(heap.blocks[block]->cells + BITS_PER_WORD * wordInBitmap + bitInWord);
+    CollectorBlock *curBlock = heap.blocks[block];
+    for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+      ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+      
+      if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
+          ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
+        const char *mangled_name = typeid(*imp).name();
+        int status;
+        char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
         
-        if (word & (1 << bitInWord)
-                && ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
-          const char *mangled_name = typeid(*imp).name();
-          int status;
-          char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
-          
-          CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
-          free(demangled_name);
-          CFSetAddValue(classes, className);
-          CFRelease(className);
-        }
+        CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
+        free(demangled_name);
+        CFSetAddValue(classes, className);
+        CFRelease(className);
       }
     }
@@ -388 +412 @@
     
     if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0) {
-        const char *mangled_name = typeid(*imp).name();
-        int status;
-        char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
-        
-        CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
-        free(demangled_name);
-        CFSetAddValue(classes, className);
-        CFRelease(className);
-    }
-  }
-
+      const char *mangled_name = typeid(*imp).name();
+      int status;
+      char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
+      
+      CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
+      free(demangled_name);
+      CFSetAddValue(classes, className);
+      CFRelease(className);
+    }
+  }
+  
   return classes;
 }