diff --git a/src/atomic_integer.h b/src/atomic_integer.h
index adf3e77..22cc7b4 100644
--- a/src/atomic_integer.h
+++ b/src/atomic_integer.h
@@ -71,6 +71,10 @@
   int32_t operator -- () {
     return android_atomic_dec(&value_) - 1;
   }
+
+  int CompareAndSwap(int expected_value, int new_value) {
+    return android_atomic_cas(expected_value, new_value, &value_);
+  }
  private:
   int32_t value_;
 };
diff --git a/src/barrier_test.cc b/src/barrier_test.cc
index 43b279e..7b31e29 100644
--- a/src/barrier_test.cc
+++ b/src/barrier_test.cc
@@ -24,9 +24,9 @@
 #include "UniquePtr.h"
 
 namespace art {
-class CheckWaitClosure : public Closure {
+class CheckWaitTask : public Task {
  public:
-  CheckWaitClosure(Barrier* barrier, AtomicInteger* count1, AtomicInteger* count2,
+  CheckWaitTask(Barrier* barrier, AtomicInteger* count1, AtomicInteger* count2,
                    AtomicInteger* count3)
       : barrier_(barrier),
         count1_(count1),
@@ -44,6 +44,9 @@
     barrier_->Wait(self);
     ++*count3_;
     LOG(INFO) << "After barrier 2 " << self;
+  }
+
+  virtual void Finalize() {
     delete this;
   }
  private:
@@ -69,7 +72,7 @@
   AtomicInteger count2 = 0;
   AtomicInteger count3 = 0;
   for (int32_t i = 0; i < num_threads; ++i) {
-    thread_pool.AddTask(self, new CheckWaitClosure(&barrier, &count1, &count2, &count3));
+    thread_pool.AddTask(self, new CheckWaitTask(&barrier, &count1, &count2, &count3));
   }
   thread_pool.StartWorkers(self);
   barrier.Increment(self, num_threads);
@@ -91,9 +94,9 @@
   EXPECT_EQ(num_threads, count3);
 }
 
-class CheckPassClosure : public Closure {
+class CheckPassTask : public Task {
  public:
-  CheckPassClosure(Barrier* barrier, AtomicInteger* count, size_t subtasks)
+  CheckPassTask(Barrier* barrier, AtomicInteger* count, size_t subtasks)
       : barrier_(barrier),
         count_(count),
         subtasks_(subtasks) {
@@ -106,6 +109,9 @@
       // Pass through to next subtask.
       barrier_->Pass(self);
     }
+  }
+
+  void Finalize() {
     delete this;
   }
  private:
@@ -123,7 +129,7 @@
   const int32_t num_tasks = num_threads * 4;
   const int32_t num_sub_tasks = 128;
   for (int32_t i = 0; i < num_tasks; ++i) {
-    thread_pool.AddTask(self, new CheckPassClosure(&barrier, &count, num_sub_tasks));
+    thread_pool.AddTask(self, new CheckPassTask(&barrier, &count, num_sub_tasks));
   }
   thread_pool.StartWorkers(self);
   const int32_t expected_total_tasks = num_sub_tasks * num_tasks;
diff --git a/src/class_linker.cc b/src/class_linker.cc
index dc86aed..ce9b37b 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -240,6 +240,7 @@
   SirtRef<Class>
       java_lang_Class(self, down_cast<Class*>(heap->AllocObject(self, NULL, sizeof(ClassClass))));
   CHECK(java_lang_Class.get() != NULL);
+  Class::SetClassClass(java_lang_Class.get());
   java_lang_Class->SetClass(java_lang_Class.get());
   java_lang_Class->SetClassSize(sizeof(ClassClass));
   // AllocClass(Class*) can now be used
@@ -972,11 +973,12 @@
   Object* dex_caches_object = space->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
   ObjectArray<DexCache>* dex_caches = dex_caches_object->AsObjectArray<DexCache>();
 
+  ObjectArray<Class>* class_roots =
+      space->GetImageHeader().GetImageRoot(ImageHeader::kClassRoots)->AsObjectArray<Class>();
+
   // Special case of setting up the String class early so that we can test arbitrary objects
   // as being Strings or not
-  Class* java_lang_String = space->GetImageHeader().GetImageRoot(ImageHeader::kClassRoots)
-      ->AsObjectArray<Class>()->Get(kJavaLangString);
-  String::SetClass(java_lang_String);
+  String::SetClass(class_roots->Get(kJavaLangString));
 
   CHECK_EQ(oat_file->GetOatHeader().GetDexFileCount(),
            static_cast<uint32_t>(dex_caches->GetLength()));
@@ -1004,9 +1006,8 @@
   }
 
   // reinit class_roots_
-  Object* class_roots_object =
-      heap->GetImageSpace()->GetImageHeader().GetImageRoot(ImageHeader::kClassRoots);
-  class_roots_ = class_roots_object->AsObjectArray<Class>();
+  Class::SetClassClass(class_roots->Get(kJavaLangClass));
+  class_roots_ = class_roots;
 
   // reinit array_iftable_ from any array class instance, they should be ==
   array_iftable_ = GetClassRoot(kObjectArrayClass)->GetIfTable();
@@ -1112,6 +1113,7 @@
 
 
 ClassLinker::~ClassLinker() {
+  Class::ResetClass();
   String::ResetClass();
   Field::ResetClass();
   AbstractMethod::ResetClasses();
diff --git a/src/common_test.h b/src/common_test.h
index 67d2266..f564bbd 100644
--- a/src/common_test.h
+++ b/src/common_test.h
@@ -388,6 +388,10 @@
     compiler_.reset(new Compiler(compiler_backend, instruction_set, true, 2, false, image_classes_.get(),
                                  true, true));
 
+    // Create the heap thread pool so that the GC runs in parallel for tests. Normally, the thread
+    // pool is created by the runtime.
+    runtime_->GetHeap()->CreateThreadPool();
+
     runtime_->GetHeap()->VerifyHeap();  // Check for heap corruption before the test
   }
 
diff --git a/src/compiler.cc b/src/compiler.cc
index b096912..4c9860c 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -993,7 +993,7 @@
     self->AssertNoPendingException();
     CHECK_GT(work_units, 0U);
 
-    std::vector<Closure*> closures(work_units);
+    std::vector<ForAllClosure*> closures(work_units);
     for (size_t i = 0; i < work_units; ++i) {
       closures[i] = new ForAllClosure(this, begin + i, end, callback, work_units);
       thread_pool_->AddTask(self, closures[i]);
@@ -1006,13 +1006,11 @@
 
     // Wait for all the worker threads to finish.
     thread_pool_->Wait(self);
-
-    STLDeleteElements(&closures);
   }
 
  private:
 
-  class ForAllClosure : public Closure {
+  class ForAllClosure : public Task {
    public:
     ForAllClosure(CompilationContext* context, size_t begin, size_t end, Callback* callback,
                   size_t stripe)
@@ -1031,6 +1029,10 @@
         self->AssertNoPendingException();
       }
     }
+
+    virtual void Finalize() {
+      delete this;
+    }
    private:
     CompilationContext* const context_;
     const size_t begin_;
diff --git a/src/gc/heap_bitmap.h b/src/gc/heap_bitmap.h
index 1610df8..666fcc7 100644
--- a/src/gc/heap_bitmap.h
+++ b/src/gc/heap_bitmap.h
@@ -38,9 +38,9 @@
         EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
       SpaceBitmap* bitmap = GetSpaceBitmap(obj);
       if (LIKELY(bitmap != NULL)) {
-        return bitmap->Clear(obj);
+        bitmap->Clear(obj);
       } else {
-        return large_objects_->Clear(obj);
+        large_objects_->Clear(obj);
       }
     }
 
diff --git a/src/gc/mark_sweep.cc b/src/gc/mark_sweep.cc
index e93eb1a..4662cf6 100644
--- a/src/gc/mark_sweep.cc
+++ b/src/gc/mark_sweep.cc
@@ -41,8 +41,17 @@
 
 namespace art {
 
+// Performance options.
+static const bool kParallelMarkStack = true;
+static const bool kDisableFinger = true;
 static const bool kUseMarkStackPrefetch = true;
 
+// Profiling and information flags.
+static const bool kCountClassesMarked = false;
+static const bool kProfileLargeObjects = false;
+static const bool kMeasureOverhead = false;
+static const bool kCountTasks = false;
+
 class SetFingerVisitor {
  public:
   SetFingerVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
@@ -71,17 +80,20 @@
       cleared_reference_list_(NULL),
       freed_bytes_(0), freed_objects_(0),
       class_count_(0), array_count_(0), other_count_(0),
-      gc_barrier_(new Barrier) {
+      large_object_test_(0), large_object_mark_(0),
+      classes_marked_(0), overhead_time_(0),
+      work_chunks_created_(0), work_chunks_deleted_(0),
+      gc_barrier_(new Barrier),
+      large_object_lock_("large object lock") {
   DCHECK(mark_stack_ != NULL);
 }
 
 void MarkSweep::Init() {
+  java_lang_Class_ = Class::GetJavaLangClass();
+  CHECK(java_lang_Class_ != NULL);
   heap_ = Runtime::Current()->GetHeap();
   mark_stack_->Reset();
-  // TODO: C++0x auto
   FindDefaultMarkBitmap();
-  // TODO: if concurrent, enable card marking in compiler
-  // TODO: check that the mark bitmap is entirely clear.
   // Mark any concurrent roots as dirty since we need to scan them at least once during this GC.
   Runtime::Current()->DirtyRoots();
 }
@@ -99,7 +111,7 @@
   LOG(FATAL) << "Could not find a default mark bitmap";
 }
 
-inline void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
+inline void MarkSweep::MarkObjectNonNull(const Object* obj, bool check_finger) {
   DCHECK(obj != NULL);
 
   if (obj >= immune_begin_ && obj < immune_end_) {
@@ -109,32 +121,21 @@
 
   // Try to take advantage of locality of references within a space, failing this find the space
   // the hard way.
-  if (UNLIKELY(!current_mark_bitmap_->HasAddress(obj))) {
+  SpaceBitmap* object_bitmap = current_mark_bitmap_;
+  if (UNLIKELY(!object_bitmap->HasAddress(obj))) {
     SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj);
     if (new_bitmap != NULL) {
-      current_mark_bitmap_ = new_bitmap;
+      object_bitmap = new_bitmap;
     } else {
-      LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace();
-      SpaceSetMap* large_objects = large_object_space->GetMarkObjects();
-      if (!large_objects->Test(obj)) {
-        if (!large_object_space->Contains(obj)) {
-          LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces";
-          LOG(ERROR) << "Attempting see if it's a bad root";
-          VerifyRoots();
-          LOG(FATAL) << "Can't mark bad root";
-        }
-        large_objects->Set(obj);
-        // Don't need to check finger since large objects never have any object references.
-      }
-      // TODO: Improve clarity of control flow in this function?
+      MarkLargeObject(obj);
       return;
     }
   }
 
   // This object was not previously marked.
-  if (!current_mark_bitmap_->Test(obj)) {
-    current_mark_bitmap_->Set(obj);
-    if (check_finger && obj < finger_) {
+  if (!object_bitmap->Test(obj)) {
+    object_bitmap->Set(obj);
+    if (kDisableFinger || (check_finger && obj < finger_)) {
       // Do we need to expand the mark stack?
       if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) {
         std::vector<Object*> temp;
@@ -150,6 +151,57 @@
   }
 }
 
+// Rare case, probably not worth inlining since it will increase instruction cache miss rate.
+bool MarkSweep::MarkLargeObject(const Object* obj) {
+  LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace();
+  SpaceSetMap* large_objects = large_object_space->GetMarkObjects();
+  if (kProfileLargeObjects) {
+    ++large_object_test_;
+  }
+  if (UNLIKELY(!large_objects->Test(obj))) {
+    if (!large_object_space->Contains(obj)) {
+      LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces";
+      LOG(ERROR) << "Attempting see if it's a bad root";
+      VerifyRoots();
+      LOG(FATAL) << "Can't mark bad root";
+    }
+    if (kProfileLargeObjects) {
+      ++large_object_mark_;
+    }
+    large_objects->Set(obj);
+    // Don't need to check finger since large objects never have any object references.
+    return true;
+  }
+  return false;
+}
+
+inline bool MarkSweep::MarkObjectParallel(const Object* obj) {
+  DCHECK(obj != NULL);
+
+  if (obj >= immune_begin_ && obj < immune_end_) {
+    DCHECK(IsMarked(obj));
+    return false;
+  }
+
+  // Try to take advantage of locality of references within a space, failing this find the space
+  // the hard way.
+  SpaceBitmap* object_bitmap = current_mark_bitmap_;
+  if (UNLIKELY(!object_bitmap->HasAddress(obj))) {
+    SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj);
+    if (new_bitmap != NULL) {
+      object_bitmap = new_bitmap;
+    } else {
+      // TODO: Remove the Thread::Current here?
+      // TODO: Convert this to some kind of atomic marking?
+      MutexLock mu(Thread::Current(), large_object_lock_);
+      return MarkLargeObject(obj);
+    }
+  }
+
+  // Return true if the object was not previously marked.
+  return !object_bitmap->AtomicTestAndSet(obj);
+}
+
 // Used to mark objects when recursing.  Recursion is done by moving
 // the finger across the bitmaps in address order and marking child
 // objects.  Any newly-marked objects whose addresses are lower than
@@ -157,22 +209,22 @@
 // need to be added to the mark stack.
 void MarkSweep::MarkObject(const Object* obj) {
   if (obj != NULL) {
-    MarkObject0(obj, true);
+    MarkObjectNonNull(obj, true);
   }
 }
 
-void MarkSweep::MarkObjectVisitor(const Object* root, void* arg) {
+void MarkSweep::MarkObjectCallback(const Object* root, void* arg) {
   DCHECK(root != NULL);
   DCHECK(arg != NULL);
   MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
-  mark_sweep->MarkObject0(root, false);
+  mark_sweep->MarkObjectNonNull(root, false);
 }
 
 void MarkSweep::ReMarkObjectVisitor(const Object* root, void* arg) {
   DCHECK(root != NULL);
   DCHECK(arg != NULL);
   MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
-  mark_sweep->MarkObject0(root, true);
+  mark_sweep->MarkObjectNonNull(root, true);
 }
 
 void MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg,
@@ -201,15 +253,15 @@
 
 // Marks all objects in the root set.
 void MarkSweep::MarkRoots() {
-  Runtime::Current()->VisitNonConcurrentRoots(MarkObjectVisitor, this);
+  Runtime::Current()->VisitNonConcurrentRoots(MarkObjectCallback, this);
 }
 
 void MarkSweep::MarkNonThreadRoots() {
-  Runtime::Current()->VisitNonThreadRoots(MarkObjectVisitor, this);
+  Runtime::Current()->VisitNonThreadRoots(MarkObjectCallback, this);
 }
 
 void MarkSweep::MarkConcurrentRoots() {
-  Runtime::Current()->VisitConcurrentRoots(MarkObjectVisitor, this);
+  Runtime::Current()->VisitConcurrentRoots(MarkObjectCallback, this);
 }
 
 class CheckObjectVisitor {
@@ -259,26 +311,26 @@
   alloc_space->mark_bitmap_.reset(live_bitmap);
 }
 
-class ScanImageRootVisitor {
+class ScanObjectVisitor {
  public:
-  ScanImageRootVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
+  ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
+
   }
 
-  void operator ()(const Object* root) const
+  void operator ()(const Object* obj) const
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    DCHECK(root != NULL);
-    mark_sweep_->ScanObject(root);
+    mark_sweep_->ScanObject(obj);
   }
 
  private:
   MarkSweep* const mark_sweep_;
 };
 
-void MarkSweep::ScanGrayObjects(bool update_finger) {
+void MarkSweep::ScanGrayObjects() {
   const Spaces& spaces = heap_->GetSpaces();
   CardTable* card_table = heap_->GetCardTable();
-  ScanImageRootVisitor image_root_visitor(this);
+  ScanObjectVisitor visitor(this);
   SetFingerVisitor finger_visitor(this);
   // TODO: C++ 0x auto
   for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
@@ -287,11 +339,7 @@
     byte* end = space->End();
     // Image spaces are handled properly since live == marked for them.
     SpaceBitmap* mark_bitmap = space->GetMarkBitmap();
-    if (update_finger) {
-      card_table->Scan(mark_bitmap, begin, end, image_root_visitor, finger_visitor);
-    } else {
-      card_table->Scan(mark_bitmap, begin, end, image_root_visitor, IdentityFunctor());
-    }
+    card_table->Scan(mark_bitmap, begin, end, visitor, IdentityFunctor());
   }
 }
 
@@ -330,22 +378,6 @@
   }
 }
 
-class ScanObjectVisitor {
- public:
-  ScanObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
-
-  }
-
-  void operator ()(const Object* obj) const
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-    mark_sweep_->ScanObject(obj);
-  }
-
- private:
-  MarkSweep* const mark_sweep_;
-};
-
 // Populates the mark stack based on the set of marked objects and
 // recursively marks until the mark stack is emptied.
 void MarkSweep::RecursiveMark(bool partial, TimingLogger& timings) {
@@ -358,12 +390,11 @@
   CHECK(cleared_reference_list_ == NULL);
 
   const Spaces& spaces = heap_->GetSpaces();
-
   SetFingerVisitor set_finger_visitor(this);
   ScanObjectVisitor scan_visitor(this);
   for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
     ContinuousSpace* space = *it;
-    if (space->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect ||
+    if ((!kDisableFinger && space->GetGcRetentionPolicy() == kGcRetentionPolicyAlwaysCollect) ||
         (!partial && space->GetGcRetentionPolicy() == kGcRetentionPolicyFullCollect)
         ) {
       current_mark_bitmap_ = space->GetMarkBitmap();
@@ -386,7 +417,7 @@
 
 void MarkSweep::RecursiveMarkCards(CardTable* card_table, const std::vector<byte*>& cards,
                                    TimingLogger& timings) {
-  ScanImageRootVisitor image_root_visitor(this);
+  ScanObjectVisitor image_root_visitor(this);
   SetFingerVisitor finger_visitor(this);
   const size_t card_count = cards.size();
   SpaceBitmap* active_bitmap = NULL;
@@ -399,14 +430,16 @@
     }
     if (active_bitmap == NULL || !active_bitmap->HasAddress(start_obj)) {
       active_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(start_obj);
-#ifndef NDEBUG
-      if (active_bitmap == NULL) {
+      if (kIsDebugBuild && active_bitmap == NULL) {
         GetHeap()->DumpSpaces();
         LOG(FATAL) << "Object " << reinterpret_cast<const void*>(start_obj);
       }
-#endif
     }
-    active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor);
+    if (kDisableFinger) {
+      active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, IdentityFunctor());
+    } else {
+      active_bitmap->VisitMarkedRange(begin, end, image_root_visitor, finger_visitor);
+    }
   }
   timings.AddSplit("RecursiveMarkCards");
   ProcessMarkStack();
@@ -419,8 +452,8 @@
       !reinterpret_cast<MarkSweep*>(arg)->GetHeap()->GetLiveBitmap()->Test(object);
 }
 
-void MarkSweep::RecursiveMarkDirtyObjects(bool update_finger) {
-  ScanGrayObjects(update_finger);
+void MarkSweep::RecursiveMarkDirtyObjects() {
+  ScanGrayObjects();
   ProcessMarkStack();
 }
 
@@ -539,7 +572,7 @@
     DCHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc)
         << thread->GetState();
     WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
-    thread->VisitRoots(MarkSweep::MarkObjectVisitor, mark_sweep_);
+    thread->VisitRoots(MarkSweep::MarkObjectCallback, mark_sweep_);
     mark_sweep_->GetBarrier().Pass(self);
   }
 
@@ -561,8 +594,6 @@
 }
 
 void MarkSweep::SweepCallback(size_t num_ptrs, Object** ptrs, void* arg) {
-  size_t freed_objects = num_ptrs;
-  size_t freed_bytes = 0;
   SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
   MarkSweep* mark_sweep = context->mark_sweep;
   Heap* heap = mark_sweep->GetHeap();
@@ -572,17 +603,9 @@
   // Use a bulk free, that merges consecutive objects before freeing or free per object?
   // Documentation suggests better free performance with merging, but this may be at the expensive
   // of allocation.
-  // TODO: investigate performance
-  static const bool kUseFreeList = true;
-  if (kUseFreeList) {
-    // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
-    freed_bytes += space->FreeList(self, num_ptrs, ptrs);
-  } else {
-    for (size_t i = 0; i < num_ptrs; ++i) {
-      freed_bytes += space->Free(self, ptrs[i]);
-    }
-  }
-
+  size_t freed_objects = num_ptrs;
+  // AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
+  size_t freed_bytes = space->FreeList(self, num_ptrs, ptrs);
   heap->RecordFree(freed_objects, freed_bytes);
   mark_sweep->freed_objects_ += freed_objects;
   mark_sweep->freed_bytes_ += freed_bytes;
@@ -606,7 +629,6 @@
 
   // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark
   // bitmap, resulting in occasional frees of Weaks which are still in use.
-  // TODO: Fix when sweeping weaks works properly with mutators unpaused + allocation list.
   SweepSystemWeaksArray(allocations);
   logger.AddSplit("SweepSystemWeaks");
 
@@ -656,12 +678,13 @@
   logger.AddSplit("Reset stack");
 }
 
-void MarkSweep::Sweep(bool partial, bool swap_bitmaps) {
+void MarkSweep::Sweep(TimingLogger& timings, bool partial, bool swap_bitmaps) {
   DCHECK(mark_stack_->IsEmpty());
 
   // If we don't swap bitmaps then newly allocated Weaks go into the live bitmap but not mark
   // bitmap, resulting in occasional frees of Weaks which are still in use.
   SweepSystemWeaks();
+  timings.AddSplit("SweepSystemWeaks");
 
   const Spaces& spaces = heap_->GetSpaces();
   SweepCallbackContext scc;
@@ -693,6 +716,7 @@
       }
     }
   }
+  timings.AddSplit("Sweep");
 }
 
 void MarkSweep::SweepLargeObjects(bool swap_bitmaps) {
@@ -721,53 +745,6 @@
   GetHeap()->RecordFree(freed_objects, freed_bytes);
 }
 
-// Scans instance fields.
-inline void MarkSweep::ScanInstanceFields(const Object* obj) {
-  DCHECK(obj != NULL);
-  Class* klass = obj->GetClass();
-  DCHECK(klass != NULL);
-  ScanFields(obj, klass->GetReferenceInstanceOffsets(), false);
-}
-
-// Scans static storage on a Class.
-inline void MarkSweep::ScanStaticFields(const Class* klass) {
-  DCHECK(klass != NULL);
-  ScanFields(klass, klass->GetReferenceStaticOffsets(), true);
-}
-
-inline void MarkSweep::ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static) {
-  if (ref_offsets != CLASS_WALK_SUPER) {
-    // Found a reference offset bitmap.  Mark the specified offsets.
-    while (ref_offsets != 0) {
-      const size_t right_shift = CLZ(ref_offsets);
-      MemberOffset byte_offset = CLASS_OFFSET_FROM_CLZ(right_shift);
-      const Object* ref = obj->GetFieldObject<const Object*>(byte_offset, false);
-      MarkObject(ref);
-      ref_offsets ^= CLASS_HIGH_BIT >> right_shift;
-    }
-  } else {
-    // There is no reference offset bitmap.  In the non-static case,
-    // walk up the class inheritance hierarchy and find reference
-    // offsets the hard way. In the static case, just consider this
-    // class.
-    for (const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
-         klass != NULL;
-         klass = is_static ? NULL : klass->GetSuperClass()) {
-      size_t num_reference_fields = (is_static
-                                     ? klass->NumReferenceStaticFields()
-                                     : klass->NumReferenceInstanceFields());
-      for (size_t i = 0; i < num_reference_fields; ++i) {
-        Field* field = (is_static
-                        ? klass->GetStaticField(i)
-                        : klass->GetInstanceField(i));
-        MemberOffset field_offset = field->GetOffset();
-        const Object* ref = obj->GetFieldObject<const Object*>(field_offset, false);
-        MarkObject(ref);
-      }
-    }
-  }
-}
-
 void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
   const Spaces& spaces = heap_->GetSpaces();
   // TODO: C++0x auto
@@ -812,32 +789,6 @@
   }
 }
 
-// Scans the header, static field references, and interface pointers
-// of a class object.
-inline void MarkSweep::ScanClass(const Object* obj) {
-#ifndef NDEBUG
-  ++class_count_;
-#endif
-  ScanInstanceFields(obj);
-  ScanStaticFields(obj->AsClass());
-}
-
-// Scans the header of all array objects.  If the array object is
-// specialized to a reference type, scans the array data as well.
-inline void MarkSweep::ScanArray(const Object* obj) {
-#ifndef NDEBUG
-  ++array_count_;
-#endif
-  MarkObject(obj->GetClass());
-  if (obj->IsObjectArray()) {
-    const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
-    for (int32_t i = 0; i < array->GetLength(); ++i) {
-      const Object* element = array->GetWithoutChecks(i);
-      MarkObject(element);
-    }
-  }
-}
-
 // Process the "referent" field in a java.lang.ref.Reference.  If the
 // referent has not yet been marked, put it on the appropriate list in
 // the gcHeap for later processing.
@@ -860,49 +811,205 @@
       list = &phantom_reference_list_;
     }
     DCHECK(list != NULL) << PrettyClass(klass) << " " << std::hex << klass->GetAccessFlags();
+    // TODO: One lock per list?
     heap_->EnqueuePendingReference(obj, list);
   }
 }
 
-// Scans the header and field references of a data object.  If the
-// scanned object is a reference subclass, it is scheduled for later
-// processing.
-inline void MarkSweep::ScanOther(const Object* obj) {
-#ifndef NDEBUG
-  ++other_count_;
-#endif
-  ScanInstanceFields(obj);
-  if (obj->GetClass()->IsReferenceClass()) {
-    DelayReferenceReferent(const_cast<Object*>(obj));
-  }
-}
-
 void MarkSweep::ScanRoot(const Object* obj) {
   ScanObject(obj);
 }
 
+class MarkObjectVisitor {
+ public:
+  MarkObjectVisitor(MarkSweep* const mark_sweep) : mark_sweep_(mark_sweep) {
+  }
+
+  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_) {
+    mark_sweep_->MarkObject(ref);
+  }
+
+ private:
+  MarkSweep* const mark_sweep_;
+};
+
 // Scans an object reference.  Determines the type of the reference
 // and dispatches to a specialized scanning routine.
 void MarkSweep::ScanObject(const Object* obj) {
-  DCHECK(obj != NULL);
-  DCHECK(obj->GetClass() != NULL);
-#ifndef NDEBUG
-  if (!IsMarked(obj)) {
-    heap_->DumpSpaces();
-    LOG(FATAL) << "Scanning unmarked object " << reinterpret_cast<const void*>(obj);
+  MarkObjectVisitor visitor(this);
+  ScanObjectVisit(obj, visitor);
+}
+
+class MarkStackChunk : public Task {
+public:
+  MarkStackChunk(ThreadPool* thread_pool, MarkSweep* mark_sweep, Object** begin, Object** end)
+      : mark_sweep_(mark_sweep),
+        thread_pool_(thread_pool),
+        index_(0),
+        length_(0),
+        output_(NULL) {
+    length_ = end - begin;
+    if (begin != end) {
+      // Cost not significant since we only do this for the initial set of mark stack chunks.
+      memcpy(data_, begin, length_ * sizeof(*begin));
+    }
+    if (kCountTasks) {
+      ++mark_sweep_->work_chunks_created_;
+    }
   }
-#endif
-  if (obj->IsClass()) {
-    ScanClass(obj);
-  } else if (obj->IsArrayInstance()) {
-    ScanArray(obj);
-  } else {
-    ScanOther(obj);
+
+  ~MarkStackChunk() {
+    DCHECK(output_ == NULL || output_->length_ == 0);
+    DCHECK_GE(index_, length_);
+    delete output_;
+    if (kCountTasks) {
+      ++mark_sweep_->work_chunks_deleted_;
+    }
   }
+
+  MarkSweep* const mark_sweep_;
+  ThreadPool* const thread_pool_;
+  static const size_t max_size = 1 * KB;
+  // Index of which object we are scanning. Only needs to be atomic if we are doing work stealing.
+  size_t index_;
+  // Input / output mark stack. We add newly marked references to data_ until length reaches
+  // max_size. This is an optimization so that less tasks are created.
+  // TODO: Investigate using a bounded buffer FIFO.
+  Object* data_[max_size];
+  // How many elements in data_ we need to scan.
+  size_t length_;
+  // Output block, newly marked references get added to the ouput block so that another thread can
+  // scan them.
+  MarkStackChunk* output_;
+
+  class MarkObjectParallelVisitor {
+   public:
+    MarkObjectParallelVisitor(MarkStackChunk* chunk_task) : chunk_task_(chunk_task) {
+
+    }
+
+    void operator ()(const Object* /* obj */, const Object* ref,
+                     const MemberOffset& /* offset */, bool /* is_static */) const {
+      if (ref != NULL && chunk_task_->mark_sweep_->MarkObjectParallel(ref)) {
+        chunk_task_->MarkStackPush(ref);
+      }
+    }
+
+   private:
+    MarkStackChunk* const chunk_task_;
+  };
+
+  // Push an object into the block.
+  // Don't need to use atomic ++ since we only one thread is writing to an output block at any
+  // given time.
+  void Push(Object* obj) {
+    data_[length_++] = obj;
+  }
+
+  void MarkStackPush(const Object* obj) {
+    if (static_cast<size_t>(length_) < max_size) {
+      Push(const_cast<Object*>(obj));
+    } else {
+      // Internal buffer is full, push to a new buffer instead.
+      if (UNLIKELY(output_ == NULL)) {
+        AllocateOutputChunk();
+      } else if (UNLIKELY(static_cast<size_t>(output_->length_) == max_size)) {
+        // Output block is full, queue it up for processing and obtain a new block.
+        EnqueueOutput();
+        AllocateOutputChunk();
+      }
+      output_->Push(const_cast<Object*>(obj));
+    }
+  }
+
+  void ScanObject(Object* obj) {
+    mark_sweep_->ScanObjectVisit(obj, MarkObjectParallelVisitor(this));
+  }
+
+  void EnqueueOutput() {
+    if (output_ != NULL) {
+      uint64_t start = 0;
+      if (kMeasureOverhead) {
+        start = NanoTime();
+      }
+      thread_pool_->AddTask(Thread::Current(), output_);
+      output_ = NULL;
+      if (kMeasureOverhead) {
+        mark_sweep_->overhead_time_ += NanoTime() - start;
+      }
+    }
+  }
+
+  void AllocateOutputChunk() {
+    uint64_t start = 0;
+    if (kMeasureOverhead) {
+      start = NanoTime();
+    }
+    output_ = new MarkStackChunk(thread_pool_, mark_sweep_, NULL, NULL);
+    if (kMeasureOverhead) {
+      mark_sweep_->overhead_time_ += NanoTime() - start;
+    }
+  }
+
+  void Finalize() {
+    EnqueueOutput();
+    delete this;
+  }
+
+  // Scans all of the objects
+  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]);
+        }
+      }
+      Object* obj = data_[index];
+      DCHECK(obj != NULL);
+      ScanObject(obj);
+    }
+  }
+};
+
+void MarkSweep::ProcessMarkStackParallel() {
+  CHECK(kDisableFinger) << "parallel mark stack processing cannot work when finger is enabled";
+  Thread* self = Thread::Current();
+  ThreadPool* thread_pool = GetHeap()->GetThreadPool();
+  // Split the current mark stack up into work tasks.
+  const size_t num_threads = thread_pool->GetThreadCount();
+  const size_t stack_size = mark_stack_->Size();
+  const size_t chunk_size =
+      std::min((stack_size + num_threads - 1) / num_threads,
+               static_cast<size_t>(MarkStackChunk::max_size));
+  size_t index = 0;
+  for (size_t i = 0; i < num_threads || index < stack_size; ++i) {
+    Object** begin = &mark_stack_->Begin()[std::min(stack_size, index)];
+    Object** end = &mark_stack_->Begin()[std::min(stack_size, index + chunk_size)];
+    index += chunk_size;
+    thread_pool->AddTask(self, new MarkStackChunk(thread_pool, this, begin, end));
+  }
+  thread_pool->StartWorkers(self);
+  mark_stack_->Reset();
+  thread_pool->Wait(self, true);
+  //LOG(INFO) << "Idle wait time " << PrettyDuration(thread_pool->GetWaitTime());
+  CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked";
 }
 
 // Scan anything that's on the mark stack.
 void MarkSweep::ProcessMarkStack() {
+  ThreadPool* thread_pool = GetHeap()->GetThreadPool();
+  if (kParallelMarkStack && thread_pool != NULL && thread_pool->GetThreadCount() > 0) {
+    ProcessMarkStackParallel();
+    return;
+  }
+
   if (kUseMarkStackPrefetch) {
     const size_t fifo_size = 4;
     const size_t fifo_mask = fifo_size - 1;
@@ -1096,13 +1203,31 @@
 }
 
 MarkSweep::~MarkSweep() {
-#ifndef NDEBUG
-  VLOG(heap) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ << " other=" << other_count_;
-#endif
+  if (class_count_ != 0 || array_count_ != 0 || other_count_ != 0) {
+    LOG(INFO) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_
+               << " other=" << other_count_;
+  }
+
+  if (kCountTasks) {
+    LOG(INFO) << "Total number of work chunks allocated: " << work_chunks_created_;
+  }
+
+  if (kMeasureOverhead) {
+    LOG(INFO) << "Overhead time " << PrettyDuration(overhead_time_);
+  }
+
+  if (kProfileLargeObjects) {
+    LOG(INFO) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_;
+  }
+
+  if (kCountClassesMarked) {
+    LOG(INFO) << "Classes marked " << classes_marked_;
+  }
+
   // Ensure that the mark stack is empty.
   CHECK(mark_stack_->IsEmpty());
 
-  // Clear all of the alloc spaces' mark bitmaps.
+  // Clear all of the spaces' mark bitmaps.
   const Spaces& spaces = heap_->GetSpaces();
   // TODO: C++0x auto
   for (Spaces::const_iterator it = spaces.begin(); it != spaces.end(); ++it) {
diff --git a/src/gc/mark_sweep.h b/src/gc/mark_sweep.h
index d64439f..f510943 100644
--- a/src/gc/mark_sweep.h
+++ b/src/gc/mark_sweep.h
@@ -35,6 +35,7 @@
 class ModUnionTableBitmap;
 class Object;
 class TimingLogger;
+class MarkStackChunk;
 
 class MarkSweep {
  public:
@@ -80,9 +81,8 @@
   void UnBindBitmaps()
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
-  // Builds a mark stack with objects on dirty cards and recursively mark
-  // until it empties.
-  void RecursiveMarkDirtyObjects(bool update_finger)
+  // Builds a mark stack with objects on dirty cards and recursively mark until it empties.
+  void RecursiveMarkDirtyObjects()
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -111,7 +111,7 @@
   }
 
   // Sweeps unmarked objects to complete the garbage collection.
-  void Sweep(bool partial, bool swap_bitmaps)
+  void Sweep(TimingLogger& timings, bool partial, bool swap_bitmaps)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   // Sweeps unmarked objects to complete the garbage collection.
@@ -136,6 +136,41 @@
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+  template <typename MarkVisitor>
+  void ScanObjectVisit(const Object* obj, const MarkVisitor& visitor)
+      NO_THREAD_SAFETY_ANALYSIS {
+    DCHECK(obj != NULL);
+    if (kIsDebugBuild && !IsMarked(obj)) {
+      heap_->DumpSpaces();
+      LOG(FATAL) << "Scanning unmarked object " << obj;
+    }
+    Class* klass = obj->GetClass();
+    DCHECK(klass != NULL);
+    if (klass == java_lang_Class_) {
+      DCHECK_EQ(klass->GetClass(), java_lang_Class_);
+      if (kCountScannedTypes) {
+        ++class_count_;
+      }
+      VisitClassReferences(klass, obj, visitor);
+    } else if (klass->IsArrayClass()) {
+      if (kCountScannedTypes) {
+        ++array_count_;
+      }
+      visitor(obj, klass, Object::ClassOffset(), false);
+      if (klass->IsObjectArrayClass()) {
+        VisitObjectArrayReferences(obj->AsObjectArray<Object>(), visitor);
+      }
+    } else {
+      if (kCountScannedTypes) {
+        ++other_count_;
+      }
+      VisitOtherReferences(klass, obj, visitor);
+      if (klass->IsReferenceClass()) {
+        DelayReferenceReferent(const_cast<Object*>(obj));
+      }
+    }
+  }
+
   void SetFinger(Object* new_finger) {
     finger_ = new_finger;
   }
@@ -181,16 +216,29 @@
                             Locks::mutator_lock_) {
     DCHECK(obj != NULL);
     DCHECK(obj->GetClass() != NULL);
-    if (obj->IsClass()) {
-      VisitClassReferences(obj, visitor);
-    } else if (obj->IsArrayInstance()) {
-      VisitArrayReferences(obj, visitor);
+
+    Class* klass = obj->GetClass();
+    DCHECK(klass != NULL);
+    if (klass == Class::GetJavaLangClass()) {
+      DCHECK_EQ(klass->GetClass(), Class::GetJavaLangClass());
+      VisitClassReferences(klass, obj, visitor);
     } else {
-      VisitOtherReferences(obj, visitor);
+      if (klass->IsArrayClass()) {
+        visitor(obj, klass, Object::ClassOffset(), false);
+        if (klass->IsObjectArrayClass()) {
+          VisitObjectArrayReferences(obj->AsObjectArray<Object>(), visitor);
+        }
+      } else {
+        VisitOtherReferences(klass, obj, visitor);
+      }
     }
   }
 
-  static void MarkObjectVisitor(const Object* root, void* arg)
+  static void MarkObjectCallback(const Object* root, void* arg)
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
+
+  // Marks an object.
+  void MarkObject(const Object* obj)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   Barrier& GetBarrier();
@@ -216,14 +264,15 @@
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  // Marks an object.
-  void MarkObject(const Object* obj)
+  void MarkObjectNonNull(const Object* obj, bool check_finger)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
-  // Yuck.
-  void MarkObject0(const Object* obj, bool check_finger)
+  bool MarkLargeObject(const Object* obj)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
+  // Returns true if we need to add obj to a mark stack.
+  bool MarkObjectParallel(const Object* obj) NO_THREAD_SAFETY_ANALYSIS;
+
   static void ScanBitmapCallback(Object* obj, void* finger, void* arg)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -241,11 +290,6 @@
   void CheckObject(const Object* obj)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_);
 
-  // Grays references in instance fields.
-  void ScanInstanceFields(const Object* obj)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   // Verify the roots of the heap and print out information related to any invalid roots.
   // Called in MarkObject, so may we may not hold the mutator lock.
   void VerifyRoots()
@@ -258,32 +302,23 @@
       NO_THREAD_SAFETY_ANALYSIS;
 
   template <typename Visitor>
-  static void VisitInstanceFieldsReferences(const Object* obj, const Visitor& visitor)
+  static void VisitInstanceFieldsReferences(const Class* klass, const Object* obj,
+                                            const Visitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
     DCHECK(obj != NULL);
-    Class* klass = obj->GetClass();
     DCHECK(klass != NULL);
     VisitFieldsReferences(obj, klass->GetReferenceInstanceOffsets(), false, visitor);
   }
 
-  // Blackens a class object.
-  void ScanClass(const Object* obj)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
-
+  // Visit the header, static field references, and interface pointers of a class object.
   template <typename Visitor>
-  static void VisitClassReferences(const Object* obj, const Visitor& visitor)
+  static void VisitClassReferences(const Class* klass, const Object* obj,
+                                   const Visitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
-    VisitInstanceFieldsReferences(obj, visitor);
+    VisitInstanceFieldsReferences(klass, obj, visitor);
     VisitStaticFieldsReferences(obj->AsClass(), visitor);
   }
 
-  // Grays references in static fields.
-  void ScanStaticFields(const Class* klass)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   template <typename Visitor>
   static void VisitStaticFieldsReferences(const Class* klass, const Visitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
@@ -291,11 +326,6 @@
     VisitFieldsReferences(klass, klass->GetReferenceStaticOffsets(), true, visitor);
   }
 
-  // Used by ScanInstanceFields and ScanStaticFields
-  void ScanFields(const Object* obj, uint32_t ref_offsets, bool is_static)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   template <typename Visitor>
   static void VisitFieldsReferences(const Object* obj, uint32_t ref_offsets, bool is_static,
                              const Visitor& visitor)
@@ -333,37 +363,30 @@
     }
   }
 
-  // Grays references in an array.
-  void ScanArray(const Object* obj)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
+  // Visit all of the references in an object array.
   template <typename Visitor>
-  static void VisitArrayReferences(const Object* obj, const Visitor& visitor)
+  static void VisitObjectArrayReferences(const ObjectArray<Object>* array,
+                                         const Visitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
-    visitor(obj, obj->GetClass(), Object::ClassOffset(), false);
-    if (obj->IsObjectArray()) {
-      const ObjectArray<Object>* array = obj->AsObjectArray<Object>();
-      for (int32_t i = 0; i < array->GetLength(); ++i) {
-        const Object* element = array->GetWithoutChecks(i);
-        size_t width = sizeof(Object*);
-        visitor(obj, element, MemberOffset(i * width + Array::DataOffset(width).Int32Value()), false);
-      }
+    const int32_t length = array->GetLength();
+    for (int32_t i = 0; i < length; ++i) {
+      const Object* element = array->GetWithoutChecks(i);
+      const size_t width = sizeof(Object*);
+      MemberOffset offset = MemberOffset(i * width + Array::DataOffset(width).Int32Value());
+      visitor(array, element, offset, false);
     }
   }
 
-  void ScanOther(const Object* obj)
-      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
+  // Visits the header and field references of a data object.
   template <typename Visitor>
-  static void VisitOtherReferences(const Object* obj, const Visitor& visitor)
+  static void VisitOtherReferences(const Class* klass, const Object* obj,
+                                   const Visitor& visitor)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
-    return VisitInstanceFieldsReferences(obj, visitor);
+    return VisitInstanceFieldsReferences(klass, obj, visitor);
   }
 
   // Blackens objects grayed during a garbage collection.
-  void ScanGrayObjects(bool update_finger)
+  void ScanGrayObjects()
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
   // Schedules an unmarked object for reference processing.
@@ -375,6 +398,10 @@
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
+  void ProcessMarkStackParallel()
+      EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
   void EnqueueFinalizerReferences(Object** ref)
       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -396,9 +423,15 @@
   void SweepJniWeakGlobals(Heap::IsMarkedTester is_marked, void* arg)
       SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
 
+  // Whether or not we count how many of each type of object were scanned.
+  static const bool kCountScannedTypes = false;
+
   // Current space, we check this space first to avoid searching for the appropriate space for an object.
   SpaceBitmap* current_mark_bitmap_;
 
+  // Cache java.lang.Class for optimization.
+  Class* java_lang_Class_;
+
   ObjectStack* mark_stack_;
 
   Heap* heap_;
@@ -410,23 +443,25 @@
   Object* immune_end_;
 
   Object* soft_reference_list_;
-
   Object* weak_reference_list_;
-
   Object* finalizer_reference_list_;
-
   Object* phantom_reference_list_;
-
   Object* cleared_reference_list_;
 
-  size_t freed_bytes_;
-  size_t freed_objects_;
-
-  size_t class_count_;
-  size_t array_count_;
-  size_t other_count_;
+  AtomicInteger freed_bytes_;
+  AtomicInteger freed_objects_;
+  AtomicInteger class_count_;
+  AtomicInteger array_count_;
+  AtomicInteger other_count_;
+  AtomicInteger large_object_test_;
+  AtomicInteger large_object_mark_;
+  AtomicInteger classes_marked_;
+  AtomicInteger overhead_time_;
+  AtomicInteger work_chunks_created_;
+  AtomicInteger work_chunks_deleted_;
 
   UniquePtr<Barrier> gc_barrier_;
+  Mutex large_object_lock_;
 
   friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table.
   friend class CheckBitmapVisitor;
@@ -443,6 +478,8 @@
   friend class ModUnionScanImageRootVisitor;
   friend class ScanBitmapVisitor;
   friend class ScanImageRootVisitor;
+  friend class MarkStackChunk;
+  friend class FifoMarkStackChunk;
 
   DISALLOW_COPY_AND_ASSIGN(MarkSweep);
 };
diff --git a/src/gc/space_bitmap.h b/src/gc/space_bitmap.h
index 885491f..25fd538 100644
--- a/src/gc/space_bitmap.h
+++ b/src/gc/space_bitmap.h
@@ -22,6 +22,8 @@
 #include <stdint.h>
 #include <vector>
 
+#include "cutils/atomic.h"
+#include "cutils/atomic-inline.h"
 #include "UniquePtr.h"
 #include "globals.h"
 #include "logging.h"
@@ -64,12 +66,32 @@
     return static_cast<uintptr_t>(kWordHighBitMask) >> ((offset_ / kAlignment) % kBitsPerWord);
   }
 
-  inline void Set(const Object* obj) {
-    Modify(obj, true);
+  inline bool Set(const Object* obj) {
+    return Modify(obj, true);
   }
 
-  inline void Clear(const Object* obj) {
-    Modify(obj, false);
+  inline bool Clear(const Object* obj) {
+    return Modify(obj, false);
+  }
+
+  // Returns true if the object was previously marked.
+  inline bool AtomicTestAndSet(const Object* obj) {
+    uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
+    DCHECK_GE(addr, heap_begin_);
+    const uintptr_t offset = addr - heap_begin_;
+    const size_t index = OffsetToIndex(offset);
+    const word mask = OffsetToMask(offset);
+    word* const address = &bitmap_begin_[index];
+    DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
+    word old_word;
+    do {
+      old_word = *address;
+      // Fast path: The bit is already set.
+      if ((old_word & mask) != 0) {
+        return true;
+      }
+    } while (UNLIKELY(android_atomic_cas(old_word, old_word | mask, address) != 0));
+    return false;
   }
 
   void Clear();
@@ -229,6 +251,12 @@
   std::string GetName() const;
   void SetName(const std::string& name);
 
+  const void* GetObjectWordAddress(const Object* obj) const {
+    uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
+    const uintptr_t offset = addr - heap_begin_;
+    const size_t index = OffsetToIndex(offset);
+    return &bitmap_begin_[index];
+  }
  private:
   // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
   // however, we document that this is expected on heap_end_
@@ -237,18 +265,21 @@
         heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
         name_(name) {}
 
-  inline void Modify(const Object* obj, bool do_set) {
+  inline bool Modify(const Object* obj, bool do_set) {
     uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
     DCHECK_GE(addr, heap_begin_);
     const uintptr_t offset = addr - heap_begin_;
     const size_t index = OffsetToIndex(offset);
     const word mask = OffsetToMask(offset);
     DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
+    word* address = &bitmap_begin_[index];
+    word old_word = *address;
     if (do_set) {
-      bitmap_begin_[index] |= mask;
+      *address = old_word | mask;
     } else {
-      bitmap_begin_[index] &= ~mask;
+      *address = old_word & ~mask;
     }
+    return (old_word & mask) != 0;
   }
 
   // Backing storage for bitmap.
diff --git a/src/heap.cc b/src/heap.cc
index d12d20e..b4cf4a9 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -45,6 +45,7 @@
 
 namespace art {
 
+static const bool kDumpGcPerformanceOnShutdown = false;
 const double Heap::kDefaultTargetUtilization = 0.5;
 
 static bool GenerateImage(const std::string& image_file_name) {
@@ -282,6 +283,11 @@
   gc_complete_cond_.reset(new ConditionVariable("GC complete condition variable",
                                                 *gc_complete_lock_));
 
+  // Create the reference queue lock, this is required so for parrallel object scanning in the GC.
+  reference_queue_lock_.reset(new Mutex("reference queue lock"));
+
+  CHECK(max_allowed_footprint_ != 0);
+
   // Set up the cumulative timing loggers.
   for (size_t i = static_cast<size_t>(kGcTypeSticky); i < static_cast<size_t>(kGcTypeMax);
        ++i) {
@@ -296,6 +302,17 @@
   }
 }
 
+void Heap::CreateThreadPool() {
+  // TODO: Make sysconf(_SC_NPROCESSORS_CONF) be a helper function?
+  // Use the number of processors - 1 since the thread doing the GC does work while its waiting for
+  // workers to complete.
+  thread_pool_.reset(new ThreadPool(sysconf(_SC_NPROCESSORS_CONF) - 1));
+}
+
+void Heap::DeleteThreadPool() {
+  thread_pool_.reset(NULL);
+}
+
 // Sort spaces based on begin address
 struct SpaceSorter {
   bool operator ()(const ContinuousSpace* a, const ContinuousSpace* b) const {
@@ -369,6 +386,10 @@
 }
 
 Heap::~Heap() {
+  if (kDumpGcPerformanceOnShutdown) {
+    DumpGcPerformanceInfo();
+  }
+
   // If we don't reset then the mark stack complains in it's destructor.
   allocation_stack_->Reset();
   live_stack_->Reset();
@@ -947,12 +968,11 @@
   // We need to do partial GCs every now and then to avoid the heap growing too much and
   // fragmenting.
   if (gc_type == kGcTypeSticky && ++sticky_gc_count_ > partial_gc_frequency_) {
-    gc_type = kGcTypePartial;
+    gc_type = have_zygote_space_ ? kGcTypePartial : kGcTypeFull;
   }
   if (gc_type != kGcTypeSticky) {
     sticky_gc_count_ = 0;
   }
-
   if (concurrent_gc_) {
     CollectGarbageConcurrentMarkSweepPlan(self, gc_type, gc_cause, clear_soft_references);
   } else {
@@ -1049,9 +1069,6 @@
     mark_sweep.MarkConcurrentRoots();
     timings.AddSplit("MarkRoots");
 
-    // Roots are marked on the bitmap and the mark_stack is empty.
-    DCHECK(mark_stack_->IsEmpty());
-
     UpdateAndMarkModUnion(&mark_sweep, timings, gc_type);
 
     if (gc_type != kGcTypeSticky) {
@@ -1079,15 +1096,14 @@
     mark_sweep.ProcessReferences(clear_soft_references);
     timings.AddSplit("ProcessReferences");
 
-#ifndef NDEBUG
-    // Verify that we only reach marked objects from the image space
-    mark_sweep.VerifyImageRoots();
-    timings.AddSplit("VerifyImageRoots");
-#endif
+    if (kIsDebugBuild) {
+      // Verify that we only reach marked objects from the image space
+      mark_sweep.VerifyImageRoots();
+      timings.AddSplit("VerifyImageRoots");
+    }
 
     if (gc_type != kGcTypeSticky) {
-      mark_sweep.Sweep(gc_type == kGcTypePartial, false);
-      timings.AddSplit("Sweep");
+      mark_sweep.Sweep(timings, gc_type == kGcTypePartial, false);
       mark_sweep.SweepLargeObjects(false);
       timings.AddSplit("SweepLargeObjects");
     } else {
@@ -1098,15 +1114,12 @@
 
     // Unbind the live and mark bitmaps.
     mark_sweep.UnBindBitmaps();
-
-    const bool swap = true;
-    if (swap) {
-      if (gc_type == kGcTypeSticky) {
-        SwapLargeObjects();
-      } else {
-        SwapBitmaps(gc_type);
-      }
+    if (gc_type == kGcTypeSticky) {
+      SwapLargeObjects();
+    } else {
+      SwapBitmaps(gc_type);
     }
+    timings.AddSplit("SwapBitmaps");
 
     if (verify_system_weaks_) {
       mark_sweep.VerifySystemWeaks();
@@ -1600,9 +1613,6 @@
       ClearCards(timings);
     }
 
-    // Roots are marked on the bitmap and the mark_stack is empty.
-    DCHECK(mark_stack_->IsEmpty());
-
     if (verify_mod_union_table_) {
       ReaderMutexLock reader_lock(self, *Locks::heap_bitmap_lock_);
       zygote_mod_union_table_->Update();
@@ -1657,7 +1667,7 @@
       timings.AddSplit("ReMarkRoots");
 
       // Scan dirty objects, this is only required if we are not doing concurrent GC.
-      mark_sweep.RecursiveMarkDirtyObjects(false);
+      mark_sweep.RecursiveMarkDirtyObjects();
       timings.AddSplit("RecursiveMarkDirtyObjects");
     }
 
@@ -1721,8 +1731,7 @@
       // TODO: this lock shouldn't be necessary (it's why we did the bitmap flip above).
       if (gc_type != kGcTypeSticky) {
         WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
-        mark_sweep.Sweep(gc_type == kGcTypePartial, false);
-        timings.AddSplit("Sweep");
+        mark_sweep.Sweep(timings, gc_type == kGcTypePartial, false);
         mark_sweep.SweepLargeObjects(false);
         timings.AddSplit("SweepLargeObjects");
       } else {
@@ -1740,14 +1749,12 @@
 
       // Swap the live and mark bitmaps for each space which we modified space. This is an
       // optimization that enables us to not clear live bits inside of the sweep.
-      const bool swap = true;
-      if (swap) {
-        if (gc_type == kGcTypeSticky) {
-          SwapLargeObjects();
-        } else {
-          SwapBitmaps(gc_type);
-        }
+      if (gc_type == kGcTypeSticky) {
+        SwapLargeObjects();
+      } else {
+        SwapBitmaps(gc_type);
       }
+      timings.AddSplit("SwapBitmaps");
     }
 
     if (verify_system_weaks_) {
@@ -1850,7 +1857,7 @@
 void Heap::GrowForUtilization() {
   // We know what our utilization is at this moment.
   // This doesn't actually resize any memory. It just lets the heap grow more when necessary.
-  size_t target_size = num_bytes_allocated_ / Heap::GetTargetHeapUtilization();
+  size_t target_size = num_bytes_allocated_ / GetTargetHeapUtilization();
   if (target_size > num_bytes_allocated_ + max_free_) {
     target_size = num_bytes_allocated_ + max_free_;
   } else if (target_size < num_bytes_allocated_ + min_free_) {
@@ -1870,7 +1877,6 @@
 }
 
 void Heap::ClearGrowthLimit() {
-  WaitForConcurrentGcToComplete(Thread::Current());
   alloc_space_->ClearGrowthLimit();
 }
 
@@ -1922,6 +1928,8 @@
   DCHECK(ref != NULL);
   DCHECK(list != NULL);
 
+  // TODO: Remove this lock, use atomic stacks for storing references.
+  MutexLock mu(Thread::Current(), *reference_queue_lock_);
   if (*list == NULL) {
     ref->SetFieldObject(reference_pendingNext_offset_, ref, false);
     *list = ref;
@@ -1937,6 +1945,9 @@
   DCHECK(*list != NULL);
   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_);
   if (*list == head) {
     ref = *list;
     *list = NULL;
diff --git a/src/heap.h b/src/heap.h
index 8ed5881..6c4c38b 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -31,6 +31,7 @@
 #include "offsets.h"
 #include "safe_map.h"
 #include "timing_logger.h"
+#include "thread_pool.h"
 
 #define VERIFY_OBJECT_ENABLED 0
 
@@ -312,6 +313,13 @@
   // GC performance measuring
   void DumpGcPerformanceInfo();
 
+  // Thread pool.
+  void CreateThreadPool();
+  void DeleteThreadPool();
+  ThreadPool* GetThreadPool() {
+    return thread_pool_.get();
+  }
+
  private:
   // Allocates uninitialized storage. Passing in a null space tries to place the object in the
   // large object space.
@@ -408,6 +416,9 @@
   Mutex* gc_complete_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
   UniquePtr<ConditionVariable> gc_complete_cond_ GUARDED_BY(gc_complete_lock_);
 
+  // Reference queue lock
+  UniquePtr<Mutex> reference_queue_lock_;
+
   // True while the garbage collector is running.
   volatile bool is_gc_running_ GUARDED_BY(gc_complete_lock_);
 
@@ -450,6 +461,9 @@
   const bool verify_post_gc_heap_;
   const bool verify_mod_union_table_;
 
+  // Parallel GC data structures.
+  UniquePtr<ThreadPool> thread_pool_;
+
   // After how many GCs we force to do a partial GC instead of sticky mark bits GC.
   const size_t partial_gc_frequency_;
 
diff --git a/src/mutex.cc b/src/mutex.cc
index e2044d6..1cdbc4d 100644
--- a/src/mutex.cc
+++ b/src/mutex.cc
@@ -758,7 +758,6 @@
 void ConditionVariable::Wait(Thread* self) {
   DCHECK(self == NULL || self == Thread::Current());
   guard_.AssertExclusiveHeld(self);
-  guard_.CheckSafeToWait(self);
   unsigned int old_recursion_count = guard_.recursion_count_;
 #if ART_USE_FUTEXES
   int32_t cur_state = state_;
@@ -794,7 +793,6 @@
 void ConditionVariable::TimedWait(Thread* self, int64_t ms, int32_t ns) {
   DCHECK(self == NULL || self == Thread::Current());
   guard_.AssertExclusiveHeld(self);
-  guard_.CheckSafeToWait(self);
   unsigned int old_recursion_count = guard_.recursion_count_;
 #if ART_USE_FUTEXES
   // Record the original end time so that if the futex call fails we can recompute the appropriate
diff --git a/src/object.cc b/src/object.cc
index 9a4588a..cebbb2a 100644
--- a/src/object.cc
+++ b/src/object.cc
@@ -733,6 +733,19 @@
   RegisterNative(self, Runtime::Current()->GetJniDlsymLookupStub()->GetData());
 }
 
+Class* Class::java_lang_Class_ = NULL;
+
+void Class::SetClassClass(Class* java_lang_Class) {
+  CHECK(java_lang_Class_ == NULL) << java_lang_Class_ << " " << java_lang_Class;
+  CHECK(java_lang_Class != NULL);
+  java_lang_Class_ = java_lang_Class;
+}
+
+void Class::ResetClass() {
+  CHECK(java_lang_Class_ != NULL);
+  java_lang_Class_ = NULL;
+}
+
 void Class::SetStatus(Status new_status) {
   CHECK(new_status > GetStatus() || new_status == kStatusError || !Runtime::Current()->IsStarted())
       << PrettyClass(this) << " " << GetStatus() << " -> " << new_status;
diff --git a/src/object.h b/src/object.h
index 79df4e2..efd456e 100644
--- a/src/object.h
+++ b/src/object.h
@@ -1521,6 +1521,10 @@
     return !IsPrimitive() && !IsInterface() && !IsAbstract();
   }
 
+  bool IsObjectArrayClass() const {
+    return GetComponentType() != NULL && !GetComponentType()->IsPrimitive();
+  }
+
   // Creates a raw object instance but does not invoke the default constructor.
   Object* AllocObject(Thread* self) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
@@ -2008,6 +2012,15 @@
     SetField32(OFFSET_OF_OBJECT_MEMBER(Class, dex_type_idx_), type_idx, false);
   }
 
+  static Class* GetJavaLangClass() {
+    DCHECK(java_lang_Class_ != NULL);
+    return java_lang_Class_;
+  }
+
+  // Can't call this SetClass or else gets called instead of Object::SetClass in places.
+  static void SetClassClass(Class* java_lang_Class);
+  static void ResetClass();
+
  private:
   void SetVerifyErrorClass(Class* klass) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     CHECK(klass != NULL) << PrettyClass(this);
@@ -2127,6 +2140,9 @@
   // Location of first static field.
   uint32_t fields_[0];
 
+  // java.lang.Class
+  static Class* java_lang_Class_;
+
   friend struct ClassOffsets;  // for verifying offset information
   DISALLOW_IMPLICIT_CONSTRUCTORS(Class);
 };
diff --git a/src/runtime.cc b/src/runtime.cc
index 79d1fb2..3fa3123 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -115,6 +115,8 @@
 }
 
 Runtime::~Runtime() {
+  heap_->DeleteThreadPool();
+
   Thread* self = Thread::Current();
   {
     MutexLock mu(self, *Locks::runtime_shutdown_lock_);
@@ -696,6 +698,9 @@
 void Runtime::DidForkFromZygote() {
   is_zygote_ = false;
 
+  // Create the thread pool.
+  heap_->CreateThreadPool();
+
   StartSignalCatcher();
 
   // Start the JDWP thread. If the command-line debugger flags specified "suspend=y",
@@ -1030,7 +1035,9 @@
 }
 
 void Runtime::DirtyRoots() {
+  CHECK(intern_table_ != NULL);
   intern_table_->Dirty();
+  CHECK(class_linker_ != NULL);
   class_linker_->Dirty();
 }
 
diff --git a/src/thread_pool.cc b/src/thread_pool.cc
index ba53113..26c83d2 100644
--- a/src/thread_pool.cc
+++ b/src/thread_pool.cc
@@ -1,3 +1,4 @@
+#include "casts.h"
 #include "runtime.h"
 #include "stl_util.h"
 #include "thread.h"
@@ -24,9 +25,10 @@
 
 void ThreadPoolWorker::Run() {
   Thread* self = Thread::Current();
-  Closure* task = NULL;
+  Task* task = NULL;
   while ((task = thread_pool_->GetTask(self)) != NULL) {
     task->Run(self);
+    task->Finalize();
   }
 }
 
@@ -40,7 +42,7 @@
   return NULL;
 }
 
-void ThreadPool::AddTask(Thread* self, Closure* task){
+void ThreadPool::AddTask(Thread* self, Task* task){
   MutexLock mu(self, task_queue_lock_);
   tasks_.push_back(task);
   // If we have any waiters, signal one.
@@ -49,14 +51,6 @@
   }
 }
 
-void ThreadPool::AddThread(size_t stack_size) {
-  threads_.push_back(
-      new ThreadPoolWorker(
-          this,
-          StringPrintf("Thread pool worker %d", static_cast<int>(GetThreadCount())),
-          stack_size));
-}
-
 ThreadPool::ThreadPool(size_t num_threads)
   : task_queue_lock_("task queue lock"),
     task_queue_condition_("task queue condition", task_queue_lock_),
@@ -65,7 +59,8 @@
     shutting_down_(false),
     waiting_count_(0) {
   while (GetThreadCount() < num_threads) {
-    AddThread(ThreadPoolWorker::kDefaultStackSize);
+    const std::string name = StringPrintf("Thread pool worker %zu", GetThreadCount());
+    threads_.push_back(new ThreadPoolWorker(this, name, ThreadPoolWorker::kDefaultStackSize));
   }
 }
 
@@ -75,9 +70,9 @@
     MutexLock mu(self, task_queue_lock_);
     // Tell any remaining workers to shut down.
     shutting_down_ = true;
-    android_memory_barrier();
     // Broadcast to everyone waiting.
     task_queue_condition_.Broadcast(self);
+    completion_condition_.Broadcast(self);
   }
   // Wait for the threads to finish.
   STLDeleteElements(&threads_);
@@ -86,22 +81,21 @@
 void ThreadPool::StartWorkers(Thread* self) {
   MutexLock mu(self, task_queue_lock_);
   started_ = true;
-  android_memory_barrier();
   task_queue_condition_.Broadcast(self);
+  start_time_ = NanoTime();
+  total_wait_time_ = 0;
 }
 
 void ThreadPool::StopWorkers(Thread* self) {
   MutexLock mu(self, task_queue_lock_);
   started_ = false;
-  android_memory_barrier();
 }
 
-Closure* ThreadPool::GetTask(Thread* self) {
+Task* ThreadPool::GetTask(Thread* self) {
   MutexLock mu(self, task_queue_lock_);
-  while (!shutting_down_) {
-    if (started_ && !tasks_.empty()) {
-      Closure* task = tasks_.front();
-      tasks_.pop_front();
+  while (!IsShuttingDown()) {
+    Task* task = TryGetTaskLocked(self);
+    if (task != NULL) {
       return task;
     }
 
@@ -110,7 +104,10 @@
       // We may be done, lets broadcast to the completion condition.
       completion_condition_.Broadcast(self);
     }
+    const uint64_t wait_start = NanoTime();
     task_queue_condition_.Wait(self);
+    const uint64_t wait_end = NanoTime();
+    total_wait_time_ += wait_end - std::max(wait_start, start_time_);
     waiting_count_--;
   }
 
@@ -118,12 +115,151 @@
   return NULL;
 }
 
-void ThreadPool::Wait(Thread* self) {
+Task* ThreadPool::TryGetTask(Thread* self) {
   MutexLock mu(self, task_queue_lock_);
+  return TryGetTaskLocked(self);
+}
+
+Task* ThreadPool::TryGetTaskLocked(Thread* self) {
+  if (started_ && !tasks_.empty()) {
+    Task* task = tasks_.front();
+    tasks_.pop_front();
+    return task;
+  }
+  return NULL;
+}
+
+void ThreadPool::Wait(Thread* self, bool do_work) {
+  Task* task = NULL;
+  while ((task = TryGetTask(self)) != NULL) {
+    task->Run(self);
+    task->Finalize();
+  }
+
   // Wait until each thread is waiting and the task list is empty.
-  while (waiting_count_ != GetThreadCount() || !tasks_.empty()) {
+  MutexLock mu(self, task_queue_lock_);
+  while (!shutting_down_ && (waiting_count_ != GetThreadCount() || !tasks_.empty())) {
     completion_condition_.Wait(self);
   }
 }
 
+size_t ThreadPool::GetTaskCount(Thread* self){
+  MutexLock mu(self, task_queue_lock_);
+  return tasks_.size();
+}
+
+WorkStealingWorker::WorkStealingWorker(ThreadPool* thread_pool, const std::string& name,
+                                       size_t stack_size)
+    : ThreadPoolWorker(thread_pool, name, stack_size),
+      task_(NULL) {
+
+}
+
+void WorkStealingWorker::Run() {
+  Thread* self = Thread::Current();
+  Task* task = NULL;
+  WorkStealingThreadPool* thread_pool = down_cast<WorkStealingThreadPool*>(thread_pool_);
+  while ((task = thread_pool_->GetTask(self)) != NULL) {
+    WorkStealingTask* stealing_task = down_cast<WorkStealingTask*>(task);
+
+    {
+      CHECK(task_ == NULL);
+      MutexLock mu(self, thread_pool->work_steal_lock_);
+      // Register that we are running the task
+      ++stealing_task->ref_count_;
+      task_ = stealing_task;
+    }
+    stealing_task->Run(self);
+    // Mark ourselves as not running a task so that nobody tries to steal from us.
+    // There is a race condition that someone starts stealing from us at this point. This is okay
+    // due to the reference counting.
+    task_ = NULL;
+
+    bool finalize;
+
+    // Steal work from tasks until there is none left to steal. Note: There is a race, but
+    // all that happens when the race occurs is that we steal some work instead of processing a
+    // task from the queue.
+    while (thread_pool->GetTaskCount(self) == 0) {
+      WorkStealingTask* steal_from_task  = NULL;
+
+      {
+        MutexLock mu(self, thread_pool->work_steal_lock_);
+        // Try finding a task to steal from.
+        steal_from_task = thread_pool->FindTaskToStealFrom(self);
+        if (steal_from_task != NULL) {
+          CHECK_NE(stealing_task, steal_from_task)
+              << "Attempting to steal from completed self task";
+          steal_from_task->ref_count_++;
+        } else {
+          break;
+        }
+      }
+
+      if (steal_from_task != NULL) {
+        // Task which completed earlier is going to steal some work.
+        stealing_task->StealFrom(self, steal_from_task);
+
+        {
+          // We are done stealing from the task, lets decrement its reference count.
+          MutexLock mu(self, thread_pool->work_steal_lock_);
+          finalize = !--steal_from_task->ref_count_;
+        }
+
+        if (finalize) {
+          steal_from_task->Finalize();
+        }
+      }
+    }
+
+    {
+      MutexLock mu(self, thread_pool->work_steal_lock_);
+      // If nobody is still referencing task_ we can finalize it.
+      finalize = !--stealing_task->ref_count_;
+    }
+
+    if (finalize) {
+      stealing_task->Finalize();
+    }
+  }
+}
+
+WorkStealingWorker::~WorkStealingWorker() {
+
+}
+
+WorkStealingThreadPool::WorkStealingThreadPool(size_t num_threads)
+    : ThreadPool(0),
+      work_steal_lock_("work stealing lock"),
+      steal_index_(0) {
+  while (GetThreadCount() < num_threads) {
+    const std::string name = StringPrintf("Work stealing worker %zu", GetThreadCount());
+    threads_.push_back(new WorkStealingWorker(this, name, ThreadPoolWorker::kDefaultStackSize));
+  }
+}
+
+WorkStealingTask* WorkStealingThreadPool::FindTaskToStealFrom(Thread* self) {
+  const size_t thread_count = GetThreadCount();
+  for (size_t i = 0; i < thread_count; ++i) {
+    // TODO: Use CAS instead of lock.
+    ++steal_index_;
+    if (steal_index_ >= thread_count) {
+      steal_index_-= thread_count;
+    }
+
+    WorkStealingWorker* worker = down_cast<WorkStealingWorker*>(threads_[steal_index_]);
+    WorkStealingTask* task = worker->task_;
+    if (task) {
+      // Not null, we can probably steal from this worker.
+      return task;
+    }
+  }
+  // Couldn't find something to steal.
+  return NULL;
+}
+
+WorkStealingThreadPool::~WorkStealingThreadPool() {
+
+}
+
 }  // namespace art
diff --git a/src/thread_pool.h b/src/thread_pool.h
index 1d0f85d..c8f6056 100644
--- a/src/thread_pool.h
+++ b/src/thread_pool.h
@@ -20,14 +20,20 @@
 #include <deque>
 #include <vector>
 
+#include "closure.h"
 #include "locks.h"
 #include "../src/mutex.h"
 
 namespace art {
 
-class Closure;
 class ThreadPool;
 
+class Task : public Closure {
+public:
+  // Called when references reaches 0.
+  virtual void Finalize() { }
+};
+
 class ThreadPoolWorker {
  public:
   static const size_t kDefaultStackSize = 1 * MB;
@@ -38,10 +44,10 @@
 
   virtual ~ThreadPoolWorker();
 
- private:
+ protected:
   ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name, size_t stack_size);
   static void* Callback(void* arg) LOCKS_EXCLUDED(Locks::mutator_lock_);
-  void Run();
+  virtual void Run();
 
   ThreadPool* thread_pool_;
   const std::string name_;
@@ -67,20 +73,33 @@
 
   // Add a new task, the first available started worker will process it. Does not delete the task
   // after running it, it is the caller's responsibility.
-  void AddTask(Thread* self, Closure* task);
+  void AddTask(Thread* self, Task* task);
 
   ThreadPool(size_t num_threads);
   virtual ~ThreadPool();
 
   // Wait for all tasks currently on queue to get completed.
-  void Wait(Thread* self);
+  void Wait(Thread* self, bool do_work = true);
 
- private:
-  // Add a new task.
-  void AddThread(size_t stack_size);
+  size_t GetTaskCount(Thread* self);
 
+  // Returns the total amount of workers waited for tasks.
+  uint64_t GetWaitTime() const {
+    return total_wait_time_;
+  }
+
+ protected:
   // Get a task to run, blocks if there are no tasks left
-  Closure* GetTask(Thread* self);
+  virtual Task* GetTask(Thread* self);
+
+  // Try to get a task, returning NULL if there is none available.
+  Task* TryGetTask(Thread* self);
+  Task* TryGetTaskLocked(Thread* self) EXCLUSIVE_LOCKS_REQUIRED(task_queue_lock_);
+
+  // Are we shutting down?
+  bool IsShuttingDown() const EXCLUSIVE_LOCKS_REQUIRED(task_queue_lock_) {
+    return shutting_down_;
+  }
 
   Mutex task_queue_lock_;
   ConditionVariable task_queue_condition_ GUARDED_BY(task_queue_lock_);
@@ -89,14 +108,71 @@
   volatile bool shutting_down_ GUARDED_BY(task_queue_lock_);
   // How many worker threads are waiting on the condition.
   volatile size_t waiting_count_ GUARDED_BY(task_queue_lock_);
-  std::deque<Closure*> tasks_ GUARDED_BY(task_queue_lock_);
+  std::deque<Task*> tasks_ GUARDED_BY(task_queue_lock_);
   // TODO: make this immutable/const?
   std::vector<ThreadPoolWorker*> threads_;
+  // Work balance detection.
+  uint64_t start_time_ GUARDED_BY(task_queue_lock_);
+  uint64_t total_wait_time_;
 
   friend class ThreadPoolWorker;
+  friend class WorkStealingWorker;
   DISALLOW_COPY_AND_ASSIGN(ThreadPool);
 };
 
+class WorkStealingTask : public Task {
+ public:
+  WorkStealingTask() : ref_count_(0) {
+
+  }
+
+  size_t GetRefCount() const {
+    return ref_count_;
+  }
+
+  virtual void StealFrom(Thread* self, WorkStealingTask* source) = 0;
+
+ private:
+  // How many people are referencing this task.
+  size_t ref_count_;
+
+  friend class WorkStealingWorker;
+};
+
+class WorkStealingWorker : public ThreadPoolWorker {
+ public:
+  virtual ~WorkStealingWorker();
+
+  bool IsRunningTask() const {
+    return task_ != NULL;
+  }
+
+ protected:
+  WorkStealingTask* task_;
+
+  WorkStealingWorker(ThreadPool* thread_pool, const std::string& name, size_t stack_size);
+  virtual void Run();
+
+  friend class WorkStealingThreadPool;
+  DISALLOW_COPY_AND_ASSIGN(WorkStealingWorker);
+};
+
+class WorkStealingThreadPool : public ThreadPool {
+ public:
+  WorkStealingThreadPool(size_t num_threads);
+  virtual ~WorkStealingThreadPool();
+
+ private:
+  Mutex work_steal_lock_;
+  // Which thread we are stealing from (round robin).
+  size_t steal_index_;
+
+  // Find a task to steal from
+  WorkStealingTask* FindTaskToStealFrom(Thread* self) EXCLUSIVE_LOCKS_REQUIRED(work_steal_lock_);
+
+  friend class WorkStealingWorker;
+};
+
 }  // namespace art
 
 #endif  // ART_SRC_THREAD_POOL_H_
diff --git a/src/thread_pool_test.cc b/src/thread_pool_test.cc
index 783f786..bac6002 100644
--- a/src/thread_pool_test.cc
+++ b/src/thread_pool_test.cc
@@ -23,9 +23,9 @@
 
 namespace art {
 
-class CountClosure : public Closure {
+class CountTask : public Task {
  public:
-  CountClosure(AtomicInteger* count) : count_(count) {
+  CountTask(AtomicInteger* count) : count_(count) {
 
   }
 
@@ -34,6 +34,9 @@
     usleep(100);
     // Increment the counter which keeps track of work completed.
     ++*count_;
+  }
+
+  void Finalize() {
     delete this;
   }
 
@@ -55,7 +58,7 @@
   AtomicInteger count = 0;
   static const int32_t num_tasks = num_threads * 4;
   for (int32_t i = 0; i < num_tasks; ++i) {
-    thread_pool.AddTask(self, new CountClosure(&count));
+    thread_pool.AddTask(self, new CountTask(&count));
   }
   thread_pool.StartWorkers(self);
   // Wait for tasks to complete.
@@ -70,7 +73,7 @@
   AtomicInteger count = 0;
   static const int32_t num_tasks = num_threads * 4;
   for (int32_t i = 0; i < num_tasks; ++i) {
-    thread_pool.AddTask(self, new CountClosure(&count));
+    thread_pool.AddTask(self, new CountTask(&count));
   }
   usleep(200);
   // Check that no threads started prematurely.
@@ -80,15 +83,15 @@
   usleep(200);
   thread_pool.StopWorkers(self);
   AtomicInteger bad_count = 0;
-  thread_pool.AddTask(self, new CountClosure(&bad_count));
+  thread_pool.AddTask(self, new CountTask(&bad_count));
   usleep(200);
   // Ensure that the task added after the workers were stopped doesn't get run.
   EXPECT_EQ(0, bad_count);
 }
 
-class TreeClosure : public Closure {
+class TreeTask : public Task {
  public:
-  TreeClosure(ThreadPool* const thread_pool, AtomicInteger* count, int depth)
+  TreeTask(ThreadPool* const thread_pool, AtomicInteger* count, int depth)
       : thread_pool_(thread_pool),
         count_(count),
         depth_(depth) {
@@ -97,11 +100,14 @@
 
   void Run(Thread* self) {
     if (depth_ > 1) {
-      thread_pool_->AddTask(self, new TreeClosure(thread_pool_, count_, depth_ - 1));
-      thread_pool_->AddTask(self, new TreeClosure(thread_pool_, count_, depth_ - 1));
+      thread_pool_->AddTask(self, new TreeTask(thread_pool_, count_, depth_ - 1));
+      thread_pool_->AddTask(self, new TreeTask(thread_pool_, count_, depth_ - 1));
     }
     // Increment the counter which keeps track of work completed.
     ++*count_;
+  }
+
+  void Finalize() {
     delete this;
   }
 
@@ -117,7 +123,7 @@
   ThreadPool thread_pool(num_threads);
   AtomicInteger count = 0;
   static const int depth = 8;
-  thread_pool.AddTask(self, new TreeClosure(&thread_pool, &count, depth));
+  thread_pool.AddTask(self, new TreeTask(&thread_pool, &count, depth));
   thread_pool.StartWorkers(self);
   thread_pool.Wait(self);
   EXPECT_EQ((1 << depth) - 1, count);