Introduce lazy sweeping.

src/mark-compact.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 145 matching lines @@
 
 void MarkCompactCollector::CollectGarbage() {
   // Make sure that Prepare() has been called. The individual steps below will
   // update the state as they proceed.
   ASSERT(state_ == PREPARE_GC);
 
   // Prepare has selected whether to compact the old generation or not.
   // Tell the tracer.
   if (IsCompacting()) tracer_->set_is_compacting();
 
-  if (heap_->incremental_marking()->IsStopped()) {
+  if (!heap_->incremental_marking()->IsMarking()) {
+    heap_->incremental_marking()->Abort();
     MarkLiveObjects();
   } else {
     {
       GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_MARK);
       heap_->incremental_marking()->Finalize();
-      ASSERT(heap_->incremental_marking()->IsStopped());
     }
     MarkLiveObjects();
   }
+  ASSERT(heap_->incremental_marking()->IsStopped());
 
   if (FLAG_collect_maps) ClearNonLiveTransitions();
 
 #ifdef DEBUG
   VerifyMarking();
 #endif
 
   SweepSpaces();
 
   // TODO(gc) ISOLATES
@@ skipping 2194 matching lines @@
 }
 
 
 // Sweeps a space conservatively.  After this has been done the larger free
 // spaces have been put on the free list and the smaller ones have been
 // ignored and left untouched.  A free space is always either ignored or put
 // on the free list, never split up into two parts.  This is important
 // because it means that any FreeSpace maps left actually describe a region of
 // memory that can be ignored when scanning.  Dead objects other than free
 // spaces will not contain the free space map.
-static void SweepConservatively(PagedSpace* space,
-                                Page* p) {
+int MarkCompactCollector::SweepConservatively(PagedSpace* space, Page* p) {
+  int freed_bytes = 0;
+
   MarkBit::CellType* cells = p->markbits()->cells();
 
   p->SetFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
 
   // This is the start of the 32 word block that we are currently looking at.
   Address block_address = p->ObjectAreaStart();
 
   int last_cell_index =
       Page::MarkbitsBitmap::IndexToCell(
           Page::MarkbitsBitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
 
   int cell_index = Page::kFirstUsedCell;
 
   // Skip over all the dead objects at the start of the page and mark them free.
   for (cell_index = Page::kFirstUsedCell;
        cell_index < last_cell_index;
        cell_index++, block_address += 32 * kPointerSize) {
     if (cells[cell_index] != 0) break;
   }
   int size = block_address - p->ObjectAreaStart();
   if (cell_index == last_cell_index) {
-    space->Free(p->ObjectAreaStart(), size);
-    return;
+    freed_bytes += space->Free(p->ObjectAreaStart(), size);
+    return freed_bytes;
   }
   // Grow the size of the start-of-page free space a little to get up to the
   // first live object.
   Address free_end = StartOfLiveObject(block_address, cells[cell_index]);
   // Free the first free space.
   size = free_end - p->ObjectAreaStart();
-  space->Free(p->ObjectAreaStart(), size);
+  freed_bytes += space->Free(p->ObjectAreaStart(), size);
   // The start of the current free area is represented in undigested form by
   // the address of the last 32-word section that contained a live object and
   // the marking bitmap for that cell, which describes where the live object
   // started.  Unless we find a large free space in the bitmap we will not
   // digest this pair into a real address.  We start the iteration here at the
   // first word in the marking bit map that indicates a live object.
   Address free_start = block_address;
   uint32_t free_start_cell = cells[cell_index];
 
   for ( ;
        cell_index < last_cell_index;
        cell_index++, block_address += 32 * kPointerSize) {
     ASSERT((unsigned)cell_index ==
         Page::MarkbitsBitmap::IndexToCell(
             Page::MarkbitsBitmap::CellAlignIndex(
                 p->AddressToMarkbitIndex(block_address))));
     uint32_t cell = cells[cell_index];
     if (cell != 0) {
       // We have a live object.  Check approximately whether it is more than 32
       // words since the last live object.
       if (block_address - free_start > 32 * kPointerSize) {
         free_start = DigestFreeStart(free_start, free_start_cell);
         if (block_address - free_start > 32 * kPointerSize) {
           // Now that we know the exact start of the free space it still looks
           // like we have a large enough free space to be worth bothering with.
           // so now we need to find the start of the first live object at the
           // end of the free space.
           free_end = StartOfLiveObject(block_address, cell);
-          space->Free(free_start, free_end - free_start);
+          freed_bytes += space->Free(free_start, free_end - free_start);
         }
       }
       // Update our undigested record of where the current free area started.
       free_start = block_address;
       free_start_cell = cell;
     }
   }
 
   // Handle the free space at the end of the page.
   if (block_address - free_start > 32 * kPointerSize) {
     free_start = DigestFreeStart(free_start, free_start_cell);
-    space->Free(free_start, block_address - free_start);
+    freed_bytes += space->Free(free_start, block_address - free_start);
   }
+
+  return freed_bytes;
 }
 
 
 // Sweep a space precisely.  After this has been done the space can
 // be iterated precisely, hitting only the live objects.  Code space
 // is always swept precisely because we want to be able to iterate
 // over it.  Map space is swept precisely, because it is not compacted.
 static void SweepPrecisely(PagedSpace* space,
                            Page* p) {
   MarkBit::CellType* cells = p->markbits()->cells();
@@ skipping 30 matching lines @@
     }
   }
   if (free_start != p->ObjectAreaEnd()) {
     space->Free(free_start, p->ObjectAreaEnd() - free_start);
   }
 }
 
 
 void MarkCompactCollector::SweepSpace(PagedSpace* space,
                                       SweeperType sweeper) {
-  space->set_was_swept_conservatively(sweeper == CONSERVATIVE);
+  space->set_was_swept_conservatively(sweeper == CONSERVATIVE ||
+                                      sweeper == LAZY_CONSERVATIVE);
 
   space->ClearStats();
 
   PageIterator it(space);
 
-  // During sweeping of paged space we are trying to find longest sequences
-  // of pages without live objects and free them (instead of putting them on
-  // the free list).
-
-  // Page preceding current.
-  Page* prev = Page::FromAddress(NULL);
+  int freed_bytes = 0;
+  int newspace_size = space->heap()->new_space()->Size();
 
   while (it.has_next()) {
     Page* p = it.next();
-    space->IncreaseCapacity(p->ObjectAreaEnd() - p->ObjectAreaStart());
 
-    if (sweeper == CONSERVATIVE) {
-      SweepConservatively(space, p);
-    } else {
-      ASSERT(sweeper == PRECISE);
-      SweepPrecisely(space, p);
+    switch (sweeper) {
+      case CONSERVATIVE:
+        SweepConservatively(space, p);
+        break;
+      case LAZY_CONSERVATIVE:
+        freed_bytes += SweepConservatively(space, p);
+        if (freed_bytes >= newspace_size && p != space->LastPage()) {
+          space->SetPagesToSweep(p->next_page(), space->LastPage());
+          return;

[Erik Corry, 2011/05/09 21:20:11]

I think we will want to tune this heuristic.  If we are not finding any garbage
to put on the free list then we shouldn't sweep the whole old space before
giving up and expanding the old space.  That will cause too long a pause for no
gain.

+        }
+        break;
+      case PRECISE:
+        SweepPrecisely(space, p);
+        break;
+      default:
+        UNREACHABLE();
     }
-    prev = p;
   }
+
   // TODO(gc): set up allocation top and limit using the free list.
 }
 
 
 void MarkCompactCollector::SweepSpaces() {
   GCTracer::Scope gc_scope(tracer_, GCTracer::Scope::MC_SWEEP);
 #ifdef DEBUG
   state_ = SWEEP_SPACES;
 #endif
 
   ASSERT(!IsCompacting());
-  SweeperType how_to_sweep = CONSERVATIVE;
+  SweeperType how_to_sweep =
+      FLAG_lazy_sweeping ? LAZY_CONSERVATIVE : CONSERVATIVE;
   if (sweep_precisely_) how_to_sweep = PRECISE;
   // Noncompacting collections simply sweep the spaces to clear the mark
   // bits and free the nonlive blocks (for old and map spaces).  We sweep
   // the map space last because freeing non-live maps overwrites them and
   // the other spaces rely on possibly non-live maps to get the sizes for
   // non-live objects.
   SweepSpace(HEAP->old_pointer_space(), how_to_sweep);
   SweepSpace(HEAP->old_data_space(), how_to_sweep);
   SweepSpace(HEAP->code_space(), PRECISE);
   // TODO(gc): implement specialized sweeper for cell space.
@@ skipping 93 matching lines @@
 }
 
 
 void MarkCompactCollector::Initialize() {
   StaticPointersToNewGenUpdatingVisitor::Initialize();
   StaticMarkingVisitor::Initialize();
 }
 
 
 } }  // namespace v8::internal