diff --git a/src/gc/card_table.cc b/src/gc/card_table.cc
index a5531d8..1e978b5 100644
--- a/src/gc/card_table.cc
+++ b/src/gc/card_table.cc
@@ -96,25 +96,6 @@
   memset(mem_map_->Begin(), kCardClean, mem_map_->Size());
 }
 
-void CardTable::PreClearCards(ContinuousSpace* space, std::vector<byte*>& out_cards) {
-  byte* card_end = CardFromAddr(space->End());
-  for (byte* card_cur = CardFromAddr(space->Begin()); card_cur < card_end; ++card_cur) {
-    if (*card_cur == kCardDirty) {
-      out_cards.push_back(card_cur);
-      *card_cur = kCardClean;
-    }
-  }
-}
-
-void CardTable::GetDirtyCards(ContinuousSpace* space, std::vector<byte*>& out_cards) const {
-  byte* card_end = CardFromAddr(space->End());
-  for (byte* card_cur = CardFromAddr(space->Begin());card_cur < card_end; ++card_cur) {
-    if (*card_cur == kCardDirty) {
-      out_cards.push_back(card_cur);
-    }
-  }
-}
-
 bool CardTable::AddrIsInCardTable(const void* addr) const {
   return IsValidCard(biased_begin_ + ((uintptr_t)addr >> kCardShift));
 }
diff --git a/src/gc/card_table.h b/src/gc/card_table.h
index 035c073..2a20fc8 100644
--- a/src/gc/card_table.h
+++ b/src/gc/card_table.h
@@ -22,6 +22,7 @@
 #include "mem_map.h"
 #include "space_bitmap.h"
 #include "UniquePtr.h"
+#include "utils.h"
 
 namespace art {
 
@@ -72,32 +73,146 @@
     return biased_begin_;
   }
 
-  // For every dirty card between begin and end invoke the visitor with the specified argument.
+  /*
+   * Visitor is expected to take in a card and return the new value. When a value is modified, the
+   * modify visitor is called.
+   * visitor: The visitor which modifies the cards. Returns the new value for a card given an old
+   * value.
+   * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables
+   * us to know which cards got cleared.
+   */
+  template <typename Visitor, typename ModifiedVisitor>
+  void ModifyCardsAtomic(byte* scan_begin, byte* scan_end, const Visitor& visitor,
+                      const ModifiedVisitor& modified = VoidFunctor()) {
+    byte* card_cur = CardFromAddr(scan_begin);
+    byte* card_end = CardFromAddr(scan_end);
+    CheckCardValid(card_cur);
+    CheckCardValid(card_end);
+
+    // Handle any unaligned cards at the start.
+    while (!IsAligned<sizeof(word)>(card_cur) && card_cur < card_end) {
+      byte expected, new_value;
+      do {
+        expected = *card_cur;
+        new_value = visitor(expected);
+      } while (expected != new_value && UNLIKELY(byte_cas(expected, new_value, card_cur) != 0));
+      if (expected != new_value) {
+        modified(card_cur, expected, new_value);
+      }
+      ++card_cur;
+    }
+
+    // Handle unaligned cards at the end.
+    while (!IsAligned<sizeof(word)>(card_end) && card_end > card_cur) {
+      --card_end;
+      byte expected, new_value;
+      do {
+        expected = *card_end;
+        new_value = visitor(expected);
+      } while (expected != new_value && UNLIKELY(byte_cas(expected, new_value, card_end) != 0));
+      if (expected != new_value) {
+        modified(card_cur, expected, new_value);
+      }
+    }
+
+    // Now we have the words, we can process words in parallel.
+    uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
+    uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end);
+    uintptr_t expected_word;
+    uintptr_t new_word;
+
+    // TODO: Parallelize.
+    while (word_cur < word_end) {
+      while ((expected_word = *word_cur) != 0) {
+        new_word =
+            (visitor((expected_word >> 0) & 0xFF) << 0) |
+            (visitor((expected_word >> 8) & 0xFF) << 8) |
+            (visitor((expected_word >> 16) & 0xFF) << 16) |
+            (visitor((expected_word >> 24) & 0xFF) << 24);
+        if (new_word == expected_word) {
+          // No need to do a cas.
+          break;
+        }
+        if (LIKELY(android_atomic_cas(expected_word, new_word,
+                                      reinterpret_cast<int32_t*>(word_cur)) == 0)) {
+          for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
+            const byte expected_byte = (expected_word >> (8 * i)) & 0xFF;
+            const byte new_byte = (new_word >> (8 * i)) & 0xFF;
+            if (expected_byte != new_byte) {
+              modified(reinterpret_cast<byte*>(word_cur) + i, expected_byte, new_byte);
+            }
+          }
+          break;
+        }
+      }
+      ++word_cur;
+    }
+  }
+
+  // For every dirty at least minumum age between begin and end invoke the visitor with the
+  // specified argument.
   template <typename Visitor, typename FingerVisitor>
   void Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_end,
-            const Visitor& visitor, const FingerVisitor& finger_visitor) const
+            const Visitor& visitor, const FingerVisitor& finger_visitor,
+            const byte minimum_age = kCardDirty) const
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     DCHECK(bitmap->HasAddress(scan_begin));
     DCHECK(bitmap->HasAddress(scan_end - 1));  // scan_end is the byte after the last byte we scan.
     byte* card_cur = CardFromAddr(scan_begin);
     byte* card_end = CardFromAddr(scan_end);
-    while (card_cur < card_end) {
+    CheckCardValid(card_cur);
+    CheckCardValid(card_end);
+
+    // Handle any unaligned cards at the start.
+    while (!IsAligned<sizeof(word)>(card_cur) && card_cur < card_end) {
+      if (*card_cur >= minimum_age) {
+        uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
+        uintptr_t end = start + kCardSize;
+        bitmap->VisitMarkedRange(start, end, visitor, finger_visitor);
+      }
+      ++card_cur;
+    }
+
+    byte* aligned_end = card_end -
+        (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
+
+    // Now we have the words, we can send these to be processed in parallel.
+    uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
+    uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
+
+    // TODO: Parallelize
+    while (word_cur < word_end) {
       // Find the first dirty card.
-      card_cur = reinterpret_cast<byte*>(memchr(card_cur, kCardDirty, card_end - card_cur));
-      if (card_cur == NULL) {
+      while (*word_cur == 0 && word_cur < word_end) {
+        word_cur++;
+      }
+      if (word_cur >= word_end) {
         break;
       }
-      byte* run_start = card_cur++;
-
-      while (*card_cur == kCardDirty && card_cur < card_end) {
-        card_cur++;
+      uintptr_t start_word = *word_cur;
+      for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
+        if ((start_word & 0xFF) == minimum_age) {
+          byte* card = reinterpret_cast<byte*>(word_cur) + i;
+          DCHECK_EQ(*card, start_word & 0xFF);
+          uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card));
+          uintptr_t end = start + kCardSize;
+          bitmap->VisitMarkedRange(start, end, visitor, finger_visitor);
+        }
+        start_word >>= 8;
       }
-      byte* run_end = card_cur;
+      ++word_cur;
+    }
 
-      uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(run_start));
-      uintptr_t end = reinterpret_cast<uintptr_t>(AddrFromCard(run_end));
-      bitmap->VisitMarkedRange(start, end, visitor, finger_visitor);
+    // Handle any unaligned cards at the end.
+    card_cur = reinterpret_cast<byte*>(word_end);
+    while (card_cur < card_end) {
+      if (*card_cur >= minimum_age) {
+        uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
+        uintptr_t end = start + kCardSize;
+        bitmap->VisitMarkedRange(start, end, visitor, finger_visitor);
+      }
+      ++card_cur;
     }
   }
 
@@ -110,12 +225,6 @@
   // Resets all of the bytes in the card table which do not map to the image space.
   void ClearSpaceCards(ContinuousSpace* space);
 
-  // Clean all the cards which map to a space.
-  void PreClearCards(ContinuousSpace* space, std::vector<byte*>& out_cards);
-
-  // Returns all of the dirty cards which map to a space.
-  void GetDirtyCards(ContinuousSpace* space, std::vector<byte*>& out_cards) const;
-
   // Returns the first address in the heap which maps to this card.
   void* AddrFromCard(const byte *card_addr) const {
     DCHECK(IsValidCard(card_addr))
@@ -138,6 +247,19 @@
   bool AddrIsInCardTable(const void* addr) const;
 
  private:
+  static int byte_cas(byte old_value, byte new_value, byte* address) {
+    // Little endian means most significant byte is on the left.
+    const size_t shift = reinterpret_cast<uintptr_t>(address) % sizeof(uintptr_t);
+    // Align the address down.
+    address -= shift;
+    int32_t* word_address = reinterpret_cast<int32_t*>(address);
+    // Word with the byte we are trying to cas cleared.
+    const int32_t cur_word = *word_address & ~(0xFF << shift);
+    const int32_t old_word = cur_word | (static_cast<int32_t>(old_value) << shift);
+    const int32_t new_word = cur_word | (static_cast<int32_t>(new_value) << shift);
+    return android_atomic_cas(old_word, new_word, word_address);
+  }
+
   CardTable(MemMap* begin, byte* biased_begin, size_t offset);
 
   // Returns true iff the card table address is within the bounds of the card table.
@@ -147,6 +269,13 @@
     return card_addr >= begin && card_addr < end;
   }
 
+  void CheckCardValid(byte* card) const {
+    DCHECK(IsValidCard(card))
+        << " card_addr: " << reinterpret_cast<const void*>(card)
+        << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
+        << " end: " << reinterpret_cast<void*>(mem_map_->End());
+  }
+
   // Verifies that all gray objects are on a dirty card.
   void VerifyCardTable();
 
diff --git a/src/gc/heap_bitmap.h b/src/gc/heap_bitmap.h
index 666fcc7..42c4166 100644
--- a/src/gc/heap_bitmap.h
+++ b/src/gc/heap_bitmap.h
@@ -73,8 +73,7 @@
       // TODO: C++0x auto
       for (Bitmaps::iterator it = bitmaps_.begin(); it != bitmaps_.end(); ++it) {
         SpaceBitmap* bitmap = *it;
-        bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor,
-                                 IdentityFunctor());
+        bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor, VoidFunctor());
       }
       large_objects_->Visit(visitor);
     }
diff --git a/src/gc/mark_sweep.cc b/src/gc/mark_sweep.cc
index 4662cf6..f2617e4 100644
--- a/src/gc/mark_sweep.cc
+++ b/src/gc/mark_sweep.cc
@@ -51,6 +51,7 @@
 static const bool kProfileLargeObjects = false;
 static const bool kMeasureOverhead = false;
 static const bool kCountTasks = false;
+static const bool kCountJavaLangRefs = false;
 
 class SetFingerVisitor {
  public:
@@ -83,6 +84,7 @@
       large_object_test_(0), large_object_mark_(0),
       classes_marked_(0), overhead_time_(0),
       work_chunks_created_(0), work_chunks_deleted_(0),
+      reference_count_(0),
       gc_barrier_(new Barrier),
       large_object_lock_("large object lock") {
   DCHECK(mark_stack_ != NULL);
@@ -272,8 +274,7 @@
   }
 
   void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const
-      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
-                            Locks::mutator_lock_) {
+      NO_THREAD_SAFETY_ANALYSIS {
     mark_sweep_->CheckReference(obj, ref, offset, is_static);
   }
 
@@ -327,7 +328,7 @@
   MarkSweep* const mark_sweep_;
 };
 
-void MarkSweep::ScanGrayObjects() {
+void MarkSweep::ScanGrayObjects(byte minimum_age) {
   const Spaces& spaces = heap_->GetSpaces();
   CardTable* card_table = heap_->GetCardTable();
   ScanObjectVisitor visitor(this);
@@ -339,7 +340,7 @@
     byte* end = space->End();
     // Image spaces are handled properly since live == marked for them.
     SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
-    card_table->Scan(mark_bitmap, begin, end, visitor, IdentityFunctor());
+    card_table->Scan(mark_bitmap, begin, end, visitor, VoidFunctor(), minimum_age);
   }
 }
 
@@ -373,7 +374,7 @@
       uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
       SpaceBitmap* live_bitmap = space->GetLiveBitmap();
       DCHECK(live_bitmap != NULL);
-      live_bitmap->VisitMarkedRange(begin, end, visitor, IdentityFunctor());
+      live_bitmap->VisitMarkedRange(begin, end, visitor, VoidFunctor());
     }
   }
 }
@@ -436,7 +437,7 @@
       }
     }
     if (kDisableFinger) {
-      active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, IdentityFunctor());
+      active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, VoidFunctor());
     } else {
       active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor);
     }
@@ -452,8 +453,8 @@
       !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object);
 }
 
-void MarkSweep::RecursiveMarkDirtyObjects() {
-  ScanGrayObjects();
+void MarkSweep::RecursiveMarkDirtyObjects(byte minimum_age) {
+  ScanGrayObjects(minimum_age);
   ProcessMarkStack();
 }
 
@@ -569,8 +570,8 @@
   virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS {
     // Note: self is not necessarily equal to thread since thread may be suspended.
     Thread* self = Thread::Current();
-    DCHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc)
-        << thread->GetState();
+    CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc)
+        << thread->GetState() << " thread " << thread << " self " << self;
     WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
     thread->VisitRoots(MarkSweep::MarkObjectCallback, mark_sweep_);
     mark_sweep_->GetBarrier().Pass(self);
@@ -585,12 +586,12 @@
 }
 
 void MarkSweep::MarkRootsCheckpoint() {
-  UniquePtr<CheckpointMarkThreadRoots> check_point(new CheckpointMarkThreadRoots(this));
+  CheckpointMarkThreadRoots check_point(this);
   ThreadList* thread_list = Runtime::Current()->GetThreadList();
   // Increment the count of the barrier. If all of the checkpoints have already been finished then
   // will hit 0 and continue. Otherwise we are still waiting for some checkpoints, so the counter
   // will go positive and we will unblock when it hits zero.
-  gc_barrier_->Increment(Thread::Current(), thread_list->RunCheckpoint(check_point.get()));
+  gc_barrier_->Increment(Thread::Current(), thread_list->RunCheckpoint(&check_point));
 }
 
 void MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
@@ -675,7 +676,7 @@
   freed_bytes_ += freed_bytes;
   logger.AddSplit("FreeList");
   allocations->Reset();
-  logger.AddSplit("Reset stack");
+  logger.AddSplit("ResetStack");
 }
 
 void MarkSweep::Sweep(TimingLogger& timings, bool partial, bool swap_bitmaps) {
@@ -799,6 +800,9 @@
   DCHECK(klass->IsReferenceClass());
   Object* pending = obj->GetFieldObject<Object*>(heap_->GetReferencePendingNextOffset(), false);
   Object* referent = heap_->GetReferenceReferent(obj);
+  if (kCountJavaLangRefs) {
+    ++reference_count_;
+  }
   if (pending == NULL && referent != NULL && !IsMarked(referent)) {
     Object** list = NULL;
     if (klass->IsSoftReferenceClass()) {
@@ -826,9 +830,7 @@
   }
 
   void operator ()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */,
-                   bool /* is_static */) const
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+                   bool /* is_static */) const EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
     mark_sweep_->MarkObject(ref);
   }
 
@@ -963,13 +965,9 @@
   virtual void Run(Thread* self) {
     int index;
     while ((index = index_++) < length_) {
-      static const size_t prefetch_look_ahead = 4;
       if (kUseMarkStackPrefetch) {
-        if (index + prefetch_look_ahead < length_) {
-          __builtin_prefetch(&data_[index + prefetch_look_ahead]);
-        } else {
-          __builtin_prefetch(&data_[length_ - 1]);
-        }
+        static const size_t prefetch_look_ahead = 1;
+        __builtin_prefetch(data_[std::min(index + prefetch_look_ahead, length_ - 1)]);
       }
       Object* obj = data_[index];
       DCHECK(obj != NULL);
@@ -1203,25 +1201,29 @@
 }
 
 MarkSweep::~MarkSweep() {
-  if (class_count_ != 0 || array_count_ != 0 || other_count_ != 0) {
-    LOG(INFO) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_
-               << " other=" << other_count_;
+  if (kCountScannedTypes) {
+    VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_
+             << " other=" << other_count_;
   }
 
   if (kCountTasks) {
-    LOG(INFO) << "Total number of work chunks allocated: " << work_chunks_created_;
+    VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_;
   }
 
   if (kMeasureOverhead) {
-    LOG(INFO) << "Overhead time " << PrettyDuration(overhead_time_);
+    VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_);
   }
 
   if (kProfileLargeObjects) {
-    LOG(INFO) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_;
+    VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_;
   }
 
   if (kCountClassesMarked) {
-    LOG(INFO) << "Classes marked " << classes_marked_;
+    VLOG(gc) << "Classes marked " << classes_marked_;
+  }
+
+  if (kCountJavaLangRefs) {
+    VLOG(gc) << "References scanned " << reference_count_;
   }
 
   // Ensure that the mark stack is empty.
diff --git a/src/gc/mark_sweep.h b/src/gc/mark_sweep.h
index f510943..2297ce1 100644
--- a/src/gc/mark_sweep.h
+++ b/src/gc/mark_sweep.h
@@ -82,7 +82,7 @@
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   // Builds a mark stack with objects on dirty cards and recursively mark until it empties.
-  void RecursiveMarkDirtyObjects()
+  void RecursiveMarkDirtyObjects(byte minimum_age = CardTable::kCardDirty)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -165,7 +165,7 @@
         ++other_count_;
       }
       VisitOtherReferences(klass, obj, visitor);
-      if (klass->IsReferenceClass()) {
+      if (UNLIKELY(klass->IsReferenceClass())) {
         DelayReferenceReferent(const_cast<Object*>(obj));
       }
     }
@@ -329,9 +329,8 @@
   template <typename Visitor>
   static void VisitFieldsReferences(const Object* obj, uint32_t ref_offsets, bool is_static,
                              const Visitor& visitor)
-      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
-                            Locks::mutator_lock_) {
-    if (ref_offsets != CLASS_WALK_SUPER) {
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
+    if (LIKELY(ref_offsets != CLASS_WALK_SUPER)) {
       // Found a reference offset bitmap.  Mark the specified offsets.
       while (ref_offsets != 0) {
         size_t right_shift = CLZ(ref_offsets);
@@ -386,8 +385,9 @@
   }
 
   // Blackens objects grayed during a garbage collection.
-  void ScanGrayObjects()
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
+  void ScanGrayObjects(byte minimum_age)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // Schedules an unmarked object for reference processing.
   void DelayReferenceReferent(Object* reference)
@@ -459,6 +459,7 @@
   AtomicInteger overhead_time_;
   AtomicInteger work_chunks_created_;
   AtomicInteger work_chunks_deleted_;
+  AtomicInteger reference_count_;
 
   UniquePtr<Barrier> gc_barrier_;
   Mutex large_object_lock_;
diff --git a/src/gc/mod_union_table.cc b/src/gc/mod_union_table.cc
index 967f795..5dd61e7 100644
--- a/src/gc/mod_union_table.cc
+++ b/src/gc/mod_union_table.cc
@@ -56,7 +56,7 @@
       bitmap_(bitmap) {
   }
 
-  void operator ()(Object* obj) const
+  void operator ()(const Object* obj) const
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
                             Locks::mutator_lock_) {
     DCHECK(obj != NULL);
@@ -76,9 +76,12 @@
     : cleared_cards_(cleared_cards) {
   }
 
-  inline void operator ()(byte* card) const {
-    cleared_cards_->insert(card);
+  inline void operator ()(byte* card, byte expected_value, byte new_value) const {
+    if (expected_value == CardTable::kCardDirty) {
+      cleared_cards_->insert(card);
+    }
   }
+
  private:
   std::set<byte*>* const cleared_cards_;
 };
@@ -89,8 +92,10 @@
     : cleared_cards_(cleared_cards) {
   }
 
-  void operator ()(byte* card) const {
-    cleared_cards_->push_back(card);
+  void operator ()(byte* card, byte expected_card, byte new_card) const {
+    if (expected_card == CardTable::kCardDirty) {
+      cleared_cards_->push_back(card);
+    }
   }
  private:
   std::vector<byte*>* cleared_cards_;
@@ -124,7 +129,7 @@
   CardTable* card_table = heap_->GetCardTable();
   ModUnionClearCardVisitor visitor(&cleared_cards_);
   // Clear dirty cards in the this image space and update the corresponding mod-union bits.
-  card_table->VisitClear(space->Begin(), space->End(), visitor);
+  card_table->ModifyCardsAtomic(space->Begin(), space->End(), AgeCardVisitor(), visitor);
 }
 
 void ModUnionTableBitmap::Update() {
@@ -145,7 +150,7 @@
     // At this point we need to update the mod-union bitmap to contain all the objects which reach
     // the alloc space.
     ModUnionVisitor visitor(heap_, bitmap);
-    space->GetLiveBitmap()->VisitMarkedRange(start, end, visitor, IdentityFunctor());
+    space->GetLiveBitmap()->VisitMarkedRange(start, end, visitor, VoidFunctor());
   }
 }
 
@@ -172,7 +177,7 @@
     const ContinuousSpace* space = it->first;
     uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin());
     uintptr_t end = reinterpret_cast<uintptr_t>(space->End());
-    it->second->VisitMarkedRange(begin, end, image_root_scanner, IdentityFunctor());
+    it->second->VisitMarkedRange(begin, end, image_root_scanner, VoidFunctor());
   }
 }
 
@@ -189,7 +194,7 @@
   CardTable* card_table = GetHeap()->GetCardTable();
   ModUnionClearCardSetVisitor visitor(&cleared_cards_);
   // Clear dirty cards in the this space and update the corresponding mod-union bits.
-  card_table->VisitClear(space->Begin(), space->End(), visitor);
+  card_table->ModifyCardsAtomic(space->Begin(), space->End(), AgeCardVisitor(), visitor);
 }
 
 class AddToReferenceArrayVisitor {
@@ -204,8 +209,8 @@
   // Extra parameters are required since we use this same visitor signature for checking objects.
   void operator ()(const Object* obj, const Object* ref, const MemberOffset& /* offset */,
                      bool /* is_static */) const {
-    // Only add the reference if it fits our criteria.
-    if (mod_union_table_->AddReference(obj, ref)) {
+    // Only add the reference if it is non null and fits our criteria.
+    if (ref != NULL && mod_union_table_->AddReference(obj, ref)) {
       references_->push_back(ref);
     }
   }
@@ -224,7 +229,7 @@
       references_(references) {
   }
 
-  void operator ()(Object* obj) const
+  void operator ()(const Object* obj) const
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_,
                             Locks::mutator_lock_) {
     DCHECK(obj != NULL);
@@ -253,9 +258,10 @@
   // Extra parameters are required since we use this same visitor signature for checking objects.
   void operator ()(const Object* obj, const Object* ref, const MemberOffset& /* offset */,
                      bool /* is_static */) const
-      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
+      SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
     Heap* heap = mod_union_table_->GetHeap();
-    if (mod_union_table_->AddReference(obj, ref) && references_.find(ref) == references_.end()) {
+    if (ref != NULL && mod_union_table_->AddReference(obj, ref) &&
+        references_.find(ref) == references_.end()) {
       ContinuousSpace* from_space = heap->FindSpaceFromObject(obj);
       ContinuousSpace* to_space = heap->FindSpaceFromObject(ref);
       LOG(INFO) << "Object " << reinterpret_cast<const void*>(obj) << "(" << PrettyTypeOf(obj) << ")"
@@ -284,7 +290,7 @@
       references_(references) {
   }
 
-  void operator ()(Object* obj) const
+  void operator ()(const Object* obj) const
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
     DCHECK(obj != NULL);
     CheckReferenceVisitor visitor(mod_union_table_, references_);
@@ -319,7 +325,7 @@
       uintptr_t end = start + CardTable::kCardSize;
       SpaceBitmap* live_bitmap =
               heap->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
-      live_bitmap->VisitMarkedRange(start, end, visitor, IdentityFunctor());
+      live_bitmap->VisitMarkedRange(start, end, visitor, VoidFunctor());
     }
   }
 }
@@ -339,7 +345,7 @@
     uintptr_t end = start + CardTable::kCardSize;
     SpaceBitmap* live_bitmap =
         heap->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
-    live_bitmap->VisitMarkedRange(start, end, visitor, IdentityFunctor());
+    live_bitmap->VisitMarkedRange(start, end, visitor, VoidFunctor());
 
     // Update the corresponding references for the card.
     // TODO: C++0x auto
@@ -383,7 +389,7 @@
   CardTable* card_table = GetHeap()->GetCardTable();
   ModUnionClearCardSetVisitor visitor(&cleared_cards_);
   // Clear dirty cards in the this space and update the corresponding mod-union bits.
-  card_table->VisitClear(space->Begin(), space->End(), visitor);
+  card_table->ModifyCardsAtomic(space->Begin(), space->End(), AgeCardVisitor(), visitor);
 }
 
 // Mark all references to the alloc space(s).
@@ -396,7 +402,7 @@
     uintptr_t end = start + CardTable::kCardSize;
     SpaceBitmap* live_bitmap =
         heap_->FindSpaceFromObject(reinterpret_cast<Object*>(start))->GetLiveBitmap();
-    live_bitmap->VisitMarkedRange(start, end, visitor, IdentityFunctor());
+    live_bitmap->VisitMarkedRange(start, end, visitor, VoidFunctor());
   }
 }
 
diff --git a/src/gc/mod_union_table.h b/src/gc/mod_union_table.h
index 5e4733a..84592a4 100644
--- a/src/gc/mod_union_table.h
+++ b/src/gc/mod_union_table.h
@@ -185,11 +185,9 @@
         return (*it)->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect;
       }
     }
-    if (ref != NULL) {
-      Implementation::GetHeap()->DumpSpaces();
-      LOG(FATAL) << "Reference " << ref << " not in any space!";
-    }
-    return false;
+    // Assume it points to a large object.
+    // TODO: Check.
+    return true;
   }
 };
 
diff --git a/src/gc/space.cc b/src/gc/space.cc
index a7a5942..8595dd0 100644
--- a/src/gc/space.cc
+++ b/src/gc/space.cc
@@ -28,6 +28,8 @@
 
 namespace art {
 
+static const bool kPrefetchDuringDlMallocFreeList = true;
+
 // Magic padding value that we use to check for buffer overruns.
 static const word kPaddingValue = 0xBAC0BAC0;
 
@@ -308,7 +310,7 @@
         *reinterpret_cast<word*>(reinterpret_cast<byte*>(ptr) + AllocationSize(ptr) -
             sizeof(word) - kChunkOverhead), kPaddingValue);
   }
-  const size_t bytes_freed = AllocationSize(ptr);
+  const size_t bytes_freed = InternalAllocationSize(ptr);
   num_bytes_allocated_ -= bytes_freed;
   --num_objects_allocated_;
   mspace_free(mspace_, ptr);
@@ -316,15 +318,21 @@
 }
 
 size_t DlMallocSpace::FreeList(Thread* self, size_t num_ptrs, Object** ptrs) {
+  DCHECK(ptrs != NULL);
+
   // Don't need the lock to calculate the size of the freed pointers.
   size_t bytes_freed = 0;
   for (size_t i = 0; i < num_ptrs; i++) {
-    bytes_freed += AllocationSize(ptrs[i]);
+    Object* ptr = ptrs[i];
+    const size_t look_ahead = 8;
+    if (kPrefetchDuringDlMallocFreeList && i + look_ahead < num_ptrs) {
+      // The head of chunk for the allocation is sizeof(size_t) behind the allocation.
+      __builtin_prefetch(reinterpret_cast<char*>(ptrs[i + look_ahead]) - sizeof(size_t));
+    }
+    bytes_freed += InternalAllocationSize(ptr);
   }
 
-  MutexLock mu(self, lock_);
   if (kDebugSpaces) {
-    CHECK(ptrs != NULL);
     size_t num_broken_ptrs = 0;
     for (size_t i = 0; i < num_ptrs; i++) {
       if (!Contains(ptrs[i])) {
@@ -337,10 +345,14 @@
     }
     CHECK_EQ(num_broken_ptrs, 0u);
   }
-  num_bytes_allocated_ -= bytes_freed;
-  num_objects_allocated_ -= num_ptrs;
-  mspace_bulk_free(mspace_, reinterpret_cast<void**>(ptrs), num_ptrs);
-  return bytes_freed;
+
+  {
+    MutexLock mu(self, lock_);
+    num_bytes_allocated_ -= bytes_freed;
+    num_objects_allocated_ -= num_ptrs;
+    mspace_bulk_free(mspace_, reinterpret_cast<void**>(ptrs), num_ptrs);
+    return bytes_freed;
+  }
 }
 
 // Callback from dlmalloc when it needs to increase the footprint
@@ -384,11 +396,16 @@
   return original_end;
 }
 
-size_t DlMallocSpace::AllocationSize(const Object* obj) {
+// Virtual functions can't get inlined.
+inline size_t DlMallocSpace::InternalAllocationSize(const Object* obj) {
   return mspace_usable_size(const_cast<void*>(reinterpret_cast<const void*>(obj))) +
       kChunkOverhead;
 }
 
+size_t DlMallocSpace::AllocationSize(const Object* obj) {
+  return InternalAllocationSize(obj);
+}
+
 void MspaceMadviseCallback(void* start, void* end, size_t used_bytes, void* /* arg */) {
   // Is this chunk in use?
   if (used_bytes != 0) {
diff --git a/src/gc/space.h b/src/gc/space.h
index 81b03fa..d816a10 100644
--- a/src/gc/space.h
+++ b/src/gc/space.h
@@ -29,11 +29,7 @@
 
 namespace art {
 
-#ifndef NDEBUG
-static const bool kDebugSpaces = true;
-#else
-static const bool kDebugSpaces = false;
-#endif
+static const bool kDebugSpaces = kIsDebugBuild;
 
 class DlMallocSpace;
 class ImageSpace;
@@ -357,6 +353,7 @@
   }
 
  private:
+  size_t InternalAllocationSize(const Object* obj);
   Object* AllocWithoutGrowthLocked(size_t num_bytes) EXCLUSIVE_LOCKS_REQUIRED(lock_);
 
   UniquePtr<SpaceBitmap> live_bitmap_;
diff --git a/src/heap.cc b/src/heap.cc
index b4cf4a9..2c52ff2 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -268,7 +268,7 @@
   // TODO: Count objects in the image space here.
   num_bytes_allocated_ = 0;
 
-  // Max stack size in bytes.
+  // Default mark stack size in bytes.
   static const size_t default_mark_stack_size = 64 * KB;
   mark_stack_.reset(ObjectStack::Create("dalvik-mark-stack", default_mark_stack_size));
   allocation_stack_.reset(ObjectStack::Create("dalvik-allocation-stack",
@@ -854,6 +854,8 @@
 
 void Heap::PreZygoteFork() {
   static Mutex zygote_creation_lock_("zygote creation lock", kZygoteCreationLock);
+  // Do this before acquiring the zygote creation lock so that we don't get lock order violations.
+  CollectGarbage(false);
   Thread* self = Thread::Current();
   MutexLock mu(self, zygote_creation_lock_);
 
@@ -973,6 +975,7 @@
   if (gc_type != kGcTypeSticky) {
     sticky_gc_count_ = 0;
   }
+
   if (concurrent_gc_) {
     CollectGarbageConcurrentMarkSweepPlan(self, gc_type, gc_cause, clear_soft_references);
   } else {
@@ -1024,17 +1027,8 @@
     // Swap allocation stack and live stack, enabling us to have new allocations during this GC.
     SwapStacks();
 
-    // We will need to know which cards were dirty for doing concurrent processing of dirty cards.
-    // TODO: Investigate using a mark stack instead of a vector.
-    std::vector<byte*> dirty_cards;
-    if (gc_type == kGcTypeSticky) {
-      for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
-        card_table_->GetDirtyCards(*it, dirty_cards);
-      }
-    }
-
-    // Clear image space cards and keep track of cards we cleared in the mod-union table.
-    ClearCards(timings);
+    // Process dirty cards and add dirty cards to mod union tables.
+    ProcessCards(timings);
 
     WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
     if (gc_type == kGcTypePartial) {
@@ -1088,7 +1082,9 @@
     if (gc_type != kGcTypeSticky) {
       mark_sweep.RecursiveMark(gc_type == kGcTypePartial, timings);
     } else {
-      mark_sweep.RecursiveMarkCards(card_table_.get(), dirty_cards, timings);
+      // Use -1 since we want to scan all of the cards which we aged earlier when we did
+      // ClearCards. These are the cards which were dirty before the GC started.
+      mark_sweep.RecursiveMarkDirtyObjects(CardTable::kCardDirty - 1);
     }
     mark_sweep.DisableFinger();
 
@@ -1261,7 +1257,7 @@
       ScanVisitor scan_visitor;
       byte* byte_cover_begin = reinterpret_cast<byte*>(card_table->AddrFromCard(card_addr));
       card_table->Scan(bitmap, byte_cover_begin, byte_cover_begin + CardTable::kCardSize,
-                       scan_visitor, IdentityFunctor());
+                       scan_visitor, VoidFunctor());
 
       // Try and see if a mark sweep collector scans the reference.
       ObjectStack* mark_stack = heap_->mark_stack_.get();
@@ -1492,9 +1488,7 @@
 }
 
 void Heap::SwapStacks() {
-  ObjectStack* temp = allocation_stack_.release();
-  allocation_stack_.reset(live_stack_.release());
-  live_stack_.reset(temp);
+  allocation_stack_.swap(live_stack_);
 
   // Sort the live stack so that we can quickly binary search it later.
   if (VERIFY_OBJECT_ENABLED) {
@@ -1502,7 +1496,7 @@
   }
 }
 
-void Heap::ClearCards(TimingLogger& timings) {
+void Heap::ProcessCards(TimingLogger& timings) {
   // Clear image space cards and keep track of cards we cleared in the mod-union table.
   for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
     ContinuousSpace* space = *it;
@@ -1513,8 +1507,10 @@
       zygote_mod_union_table_->ClearCards(space);
       timings.AddSplit("ZygoteModUnionClearCards");
     } else {
-      card_table_->ClearSpaceCards(space);
-      timings.AddSplit("ClearCards");
+      // No mod union table for the AllocSpace. Age the cards so that the GC knows that these cards
+      // were dirty before the GC started.
+      card_table_->ModifyCardsAtomic(space->Begin(), space->End(), AgeCardVisitor(), VoidFunctor());
+      timings.AddSplit("AllocSpaceClearCards");
     }
   }
 }
@@ -1522,12 +1518,11 @@
 void Heap::CollectGarbageConcurrentMarkSweepPlan(Thread* self, GcType gc_type, GcCause gc_cause,
                                                  bool clear_soft_references) {
   TimingLogger timings("ConcurrentCollectGarbageInternal", true);
-  uint64_t gc_begin = NanoTime(), root_begin = 0, root_end = 0, dirty_begin = 0, dirty_end = 0;
+  uint64_t gc_begin = NanoTime(), dirty_begin = 0, dirty_end = 0;
   std::stringstream gc_type_str;
   gc_type_str << gc_type << " ";
 
   ThreadList* thread_list = Runtime::Current()->GetThreadList();
-  std::vector<byte*> dirty_cards;
   size_t bytes_freed = 0;
   Object* cleared_references = NULL;
   {
@@ -1567,30 +1562,34 @@
       mark_sweep.FindDefaultMarkBitmap();
     }
 
-    mark_sweep.MarkRootsCheckpoint();
-    timings.AddSplit("MarkRootsCheckpoint");
-
-    {
-      root_begin = NanoTime();
-
-      // Suspend all threads are get exclusive access to the heap.
+    if (verify_pre_gc_heap_) {
       thread_list->SuspendAll();
-      timings.AddSplit("SuspendAll");
-      Locks::mutator_lock_->AssertExclusiveHeld(self);
-
-      if (verify_pre_gc_heap_) {
+      {
         WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
         if (!VerifyHeapReferences()) {
           LOG(FATAL) << "Pre " << gc_type_str.str() << "Gc verification failed";
         }
         timings.AddSplit("VerifyHeapReferencesPreGC");
       }
+      thread_list->ResumeAll();
+    }
 
-      // Swap the stacks, this is safe since all the mutators are suspended at this point.
-      SwapStacks();
+    // Process dirty cards and add dirty cards to mod union tables.
+    ProcessCards(timings);
 
-      // Check that all objects which reference things in the live stack are on dirty cards.
-      if (verify_missing_card_marks_) {
+    // Need to do this before the checkpoint since we don't want any threads to add references to
+    // the live stack during the recursive mark.
+    SwapStacks();
+    timings.AddSplit("SwapStacks");
+
+    // Tell the running threads to suspend and mark their roots.
+    mark_sweep.MarkRootsCheckpoint();
+    timings.AddSplit("MarkRootsCheckpoint");
+
+    // Check that all objects which reference things in the live stack are on dirty cards.
+    if (verify_missing_card_marks_) {
+      thread_list->SuspendAll();
+      {
         ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
         // Sort the live stack so that we can quickly binary search it later.
         std::sort(live_stack_->Begin(), live_stack_->End());
@@ -1598,35 +1597,22 @@
           LOG(FATAL) << "Pre GC verification of missing card marks failed";
         }
       }
-
-      // We will need to know which cards were dirty for doing concurrent processing of dirty cards.
-      // TODO: Investigate using a mark stack instead of a vector.
-      if (gc_type == kGcTypeSticky) {
-        dirty_cards.reserve(4 * KB);
-        for (Spaces::iterator it = spaces_.begin(); it != spaces_.end(); ++it) {
-          card_table_->GetDirtyCards(*it, dirty_cards);
-        }
-        timings.AddSplit("GetDirtyCards");
-      }
-
-      // Clear image space cards and keep track of cards we cleared in the mod-union table.
-      ClearCards(timings);
+      thread_list->ResumeAll();
     }
 
     if (verify_mod_union_table_) {
+      thread_list->SuspendAll();
       ReaderMutexLock reader_lock(self, *Locks::heap_bitmap_lock_);
       zygote_mod_union_table_->Update();
       zygote_mod_union_table_->Verify();
       mod_union_table_->Update();
       mod_union_table_->Verify();
+      thread_list->ResumeAll();
     }
 
-    // Allow mutators to go again, acquire share on mutator_lock_ to continue.
-    thread_list->ResumeAll();
     {
+      // Allow mutators to go again, acquire share on mutator_lock_ to continue.
       ReaderMutexLock reader_lock(self, *Locks::mutator_lock_);
-      root_end = NanoTime();
-      timings.AddSplit("RootEnd");
 
       // Mark the roots which we can do concurrently.
       WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
@@ -1649,7 +1635,8 @@
         // Recursively mark all the non-image bits set in the mark bitmap.
         mark_sweep.RecursiveMark(gc_type == kGcTypePartial, timings);
       } else {
-        mark_sweep.RecursiveMarkCards(card_table_.get(), dirty_cards, timings);
+        mark_sweep.RecursiveMarkDirtyObjects(CardTable::kCardDirty - 1);
+        timings.AddSplit("RecursiveMarkCards");
       }
       mark_sweep.DisableFinger();
     }
@@ -1779,20 +1766,18 @@
   timings.AddSplit("Finish");
 
   // If the GC was slow, then print timings in the log.
-  uint64_t pause_roots = (root_end - root_begin) / 1000 * 1000;
-  uint64_t pause_dirty = (dirty_end - dirty_begin) / 1000 * 1000;
+  uint64_t pause_time = (dirty_end - dirty_begin) / 1000 * 1000;
   uint64_t duration = (NanoTime() - gc_begin) / 1000 * 1000;
-  total_paused_time_ += pause_roots + pause_dirty;
-  if (pause_roots > MsToNs(5) || pause_dirty > MsToNs(5) ||
-      (gc_cause == kGcCauseForAlloc && duration > MsToNs(20))) {
+  total_paused_time_ += pause_time;
+  if (pause_time > MsToNs(5) || (gc_cause == kGcCauseForAlloc && duration > MsToNs(20))) {
     const size_t percent_free = GetPercentFree();
     const size_t current_heap_size = GetUsedMemorySize();
     const size_t total_memory = GetTotalMemory();
     LOG(INFO) << gc_cause << " " << gc_type_str.str()
               << "Concurrent GC freed " << PrettySize(bytes_freed) << ", " << percent_free
               << "% free, " << PrettySize(current_heap_size) << "/"
-              << PrettySize(total_memory) << ", " << "paused " << PrettyDuration(pause_roots)
-              << "+" << PrettyDuration(pause_dirty) << " total " << PrettyDuration(duration);
+              << PrettySize(total_memory) << ", " << "paused " << PrettyDuration(pause_time)
+              << " total " << PrettyDuration(duration);
     if (VLOG_IS_ON(heap)) {
       timings.Dump();
     }
@@ -1946,8 +1931,8 @@
   Object* head = (*list)->GetFieldObject<Object*>(reference_pendingNext_offset_, false);
   Object* ref;
 
-  // TODO: Remove this lock, use atomic stacks for storing references.
-  MutexLock mu(Thread::Current(), *reference_queue_lock_);
+  // Note: the following code is thread-safe because it is only called from ProcessReferences which
+  // is single threaded.
   if (*list == head) {
     ref = *list;
     *list = NULL;
diff --git a/src/heap.h b/src/heap.h
index 6c4c38b..584718e 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -59,6 +59,17 @@
 typedef AtomicStack<Object*> ObjectStack;
 typedef std::vector<ContinuousSpace*> Spaces;
 
+class AgeCardVisitor {
+ public:
+  byte operator ()(byte card) const {
+    if (card == CardTable::kCardDirty) {
+      return card - 1;
+    } else {
+      return 0;
+    }
+  }
+};
+
 // The ordering of the enum matters, it is used to determine which GCs are run first.
 enum GcType {
   // No Gc
@@ -382,7 +393,7 @@
   void SwapStacks();
 
   // Clear cards and update the mod union table.
-  void ClearCards(TimingLogger& timings);
+  void ProcessCards(TimingLogger& timings);
 
   Spaces spaces_;
 
diff --git a/src/utils.h b/src/utils.h
index d33cc4b..b2b2de9 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -342,10 +342,25 @@
 bool IsValidDexFilename(const std::string& filename);
 bool IsValidOatFilename(const std::string& filename);
 
-class IdentityFunctor {
+class VoidFunctor {
  public:
-  template <typename T>
-  inline T operator () (T t) const { return t; }
+  template <typename A>
+  inline void operator () (A a) const {
+    UNUSED(a);
+  }
+
+  template <typename A, typename B>
+  inline void operator () (A a, B b) const {
+    UNUSED(a);
+    UNUSED(b);
+  }
+
+  template <typename A, typename B, typename C>
+  inline void operator () (A a, B b, C c) const {
+    UNUSED(a);
+    UNUSED(b);
+    UNUSED(c);
+  }
 };
 
 }  // namespace art