diff --git a/runtime/Android.mk b/runtime/Android.mk
index ae62d36..4638e78 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -47,6 +47,7 @@
 	file_output_stream.cc \
 	gc/allocator/dlmalloc.cc \
 	gc/accounting/card_table.cc \
+	gc/accounting/gc_allocator.cc \
 	gc/accounting/heap_bitmap.cc \
 	gc/accounting/mod_union_table.cc \
 	gc/accounting/space_bitmap.cc \
diff --git a/runtime/gc/accounting/gc_allocator.cc b/runtime/gc/accounting/gc_allocator.cc
new file mode 100644
index 0000000..aff50df
--- /dev/null
+++ b/runtime/gc/accounting/gc_allocator.cc
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "gc_allocator.h"
+#include "gc/heap.h"
+#include "runtime.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+  void RegisterGCAllocation(size_t bytes) {
+    Runtime::Current()->GetHeap()->RegisterGCAllocation(bytes);
+  }
+
+  void RegisterGCDeAllocation(size_t bytes) {
+    Runtime::Current()->GetHeap()->RegisterGCDeAllocation(bytes);
+  }
+}
+}
+}
diff --git a/runtime/gc/accounting/gc_allocator.h b/runtime/gc/accounting/gc_allocator.h
new file mode 100644
index 0000000..12e16b5
--- /dev/null
+++ b/runtime/gc/accounting/gc_allocator.h
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
+#define ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
+
+#include "gc/allocator/dlmalloc.h"
+#include "utils.h"
+
+#include <cstdlib>
+#include <limits>
+#include <memory>
+
+namespace art {
+namespace gc {
+namespace accounting {
+  void RegisterGCAllocation(size_t bytes);
+  void RegisterGCDeAllocation(size_t bytes);
+
+  static const bool kMeasureGCMemoryOverhead = false;
+
+  template <typename T>
+  class GCAllocatorImpl : public std::allocator<T> {
+  public:
+    typedef typename std::allocator<T>::value_type value_type;
+    typedef typename std::allocator<T>::size_type size_type;
+    typedef typename std::allocator<T>::difference_type difference_type;
+    typedef typename std::allocator<T>::pointer pointer;
+    typedef typename std::allocator<T>::const_pointer const_pointer;
+    typedef typename std::allocator<T>::reference reference;
+    typedef typename std::allocator<T>::const_reference const_reference;
+
+    // Used internally by STL data structures.
+    template <class U>
+    GCAllocatorImpl(const GCAllocatorImpl<U>& alloc) throw() {
+
+    }
+
+    // Used internally by STL data structures.
+    GCAllocatorImpl() throw() {
+
+    }
+
+    // Enables an allocator for objects of one type to allocate storage for objects of another type.
+    // Used internally by STL data structures.
+    template <class U>
+    struct rebind {
+        typedef GCAllocatorImpl<U> other;
+    };
+
+    pointer allocate(size_type n, const_pointer hint = 0) {
+      RegisterGCAllocation(n * sizeof(T));
+      return reinterpret_cast<pointer>(malloc(n * sizeof(T)));
+    }
+
+    template <typename PT>
+    void deallocate(PT p, size_type n) {
+      RegisterGCDeAllocation(n * sizeof(T));
+      free(p);
+    }
+  };
+
+  // C++ doesn't allow template typedefs. This is a workaround template typedef which is
+  // GCAllocatorImpl<T> if kMeasureGCMemoryOverhead is true, std::allocator<T> otherwise.
+  template <typename T>
+  class GCAllocator : public TypeStaticIf<kMeasureGCMemoryOverhead,
+                                          GCAllocatorImpl<T>,
+                                          std::allocator<T> >::value {
+  };
+}
+}
+}
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
diff --git a/runtime/gc/accounting/heap_bitmap-inl.h b/runtime/gc/accounting/heap_bitmap-inl.h
index 5edea95..f6cf2b5 100644
--- a/runtime/gc/accounting/heap_bitmap-inl.h
+++ b/runtime/gc/accounting/heap_bitmap-inl.h
@@ -26,14 +26,14 @@
 template <typename Visitor>
 inline void HeapBitmap::Visit(const Visitor& visitor) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
     bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor, VoidFunctor());
   }
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It2;
+  typedef SpaceSetMapVector::iterator It2;
   DCHECK(discontinuous_space_sets_.begin() !=  discontinuous_space_sets_.end());
   for (It2 it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
diff --git a/runtime/gc/accounting/heap_bitmap.cc b/runtime/gc/accounting/heap_bitmap.cc
index 1bdc978..0462905 100644
--- a/runtime/gc/accounting/heap_bitmap.cc
+++ b/runtime/gc/accounting/heap_bitmap.cc
@@ -24,7 +24,7 @@
 
 void HeapBitmap::ReplaceBitmap(SpaceBitmap* old_bitmap, SpaceBitmap* new_bitmap) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     if (*it == old_bitmap) {
@@ -37,7 +37,7 @@
 
 void HeapBitmap::ReplaceObjectSet(SpaceSetMap* old_set, SpaceSetMap* new_set) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It;
+  typedef SpaceSetMapVector::iterator It;
   for (It it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
     if (*it == old_set) {
@@ -52,7 +52,7 @@
   DCHECK(bitmap != NULL);
 
   // Check for interval overlap.
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
@@ -71,14 +71,14 @@
 
 void HeapBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
     bitmap->Walk(callback, arg);
   }
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It2;
+  typedef SpaceSetMapVector::iterator It2;
   DCHECK(discontinuous_space_sets_.begin() !=  discontinuous_space_sets_.end());
   for (It2 it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
diff --git a/runtime/gc/accounting/heap_bitmap.h b/runtime/gc/accounting/heap_bitmap.h
index 1710579..ada976f 100644
--- a/runtime/gc/accounting/heap_bitmap.h
+++ b/runtime/gc/accounting/heap_bitmap.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_GC_ACCOUNTING_HEAP_BITMAP_H_
 
 #include "base/logging.h"
+#include "gc_allocator.h"
 #include "locks.h"
 #include "space_bitmap.h"
 
@@ -30,6 +31,9 @@
 
 class HeapBitmap {
  public:
+  typedef std::vector<SpaceBitmap*, GCAllocator<SpaceBitmap*> > SpaceBitmapVector;
+  typedef std::vector<SpaceSetMap*, GCAllocator<SpaceSetMap*> > SpaceSetMapVector;
+
   bool Test(const mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
     SpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
     if (LIKELY(bitmap != NULL)) {
@@ -63,7 +67,7 @@
 
   SpaceBitmap* GetContinuousSpaceBitmap(const mirror::Object* obj) {
     // TODO: C++0x auto
-    typedef std::vector<SpaceBitmap*>::iterator It;
+    typedef SpaceBitmapVector::iterator It;
     for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
         it != end; ++it) {
       SpaceBitmap* bitmap = *it;
@@ -76,7 +80,7 @@
 
   SpaceSetMap* GetDiscontinuousSpaceObjectSet(const mirror::Object* obj) {
     // TODO: C++0x auto
-    typedef std::vector<SpaceSetMap*>::iterator It;
+    typedef SpaceSetMapVector::iterator It;
     for (It it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
         it != end; ++it) {
       SpaceSetMap* set = *it;
@@ -112,10 +116,10 @@
   void AddDiscontinuousObjectSet(SpaceSetMap* set);
 
   // Bitmaps covering continuous spaces.
-  std::vector<SpaceBitmap*> continuous_space_bitmaps_;
+  SpaceBitmapVector continuous_space_bitmaps_;
 
   // Sets covering discontinuous spaces.
-  std::vector<SpaceSetMap*> discontinuous_space_sets_;
+  SpaceSetMapVector discontinuous_space_sets_;
 
   friend class art::gc::Heap;
 };
diff --git a/runtime/gc/accounting/mod_union_table.cc b/runtime/gc/accounting/mod_union_table.cc
index b33cbce..718dcf0 100644
--- a/runtime/gc/accounting/mod_union_table.cc
+++ b/runtime/gc/accounting/mod_union_table.cc
@@ -86,7 +86,7 @@
 
 class ModUnionClearCardSetVisitor {
  public:
-  explicit ModUnionClearCardSetVisitor(std::set<byte*>* const cleared_cards)
+  explicit ModUnionClearCardSetVisitor(ModUnionTable::CardSet* const cleared_cards)
     : cleared_cards_(cleared_cards) {
   }
 
@@ -97,7 +97,7 @@
   }
 
  private:
-  std::set<byte*>* const cleared_cards_;
+  ModUnionTable::CardSet* const cleared_cards_;
 };
 
 class ModUnionClearCardVisitor {
diff --git a/runtime/gc/accounting/mod_union_table.h b/runtime/gc/accounting/mod_union_table.h
index d46281c..eb7a754 100644
--- a/runtime/gc/accounting/mod_union_table.h
+++ b/runtime/gc/accounting/mod_union_table.h
@@ -17,6 +17,7 @@
 #ifndef ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 #define ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 
+#include "gc_allocator.h"
 #include "globals.h"
 #include "safe_map.h"
 
@@ -49,6 +50,8 @@
 // cleared between GC phases, reducing the number of dirty cards that need to be scanned.
 class ModUnionTable {
  public:
+  typedef std::set<byte*, std::less<byte*>, GCAllocator<byte*> > CardSet;
+
   explicit ModUnionTable(Heap* heap) : heap_(heap) {}
 
   virtual ~ModUnionTable() {}
@@ -111,10 +114,11 @@
 
  protected:
   // Cleared card array, used to update the mod-union table.
-  std::set<byte*> cleared_cards_;
+  ModUnionTable::CardSet cleared_cards_;
 
   // Maps from dirty cards to their corresponding alloc space references.
-  SafeMap<const byte*, std::vector<const mirror::Object*> > references_;
+  SafeMap<const byte*, std::vector<const mirror::Object*>, std::less<const byte*>,
+    GCAllocator<std::pair<const byte*, std::vector<const mirror::Object*> > > > references_;
 };
 
 // Card caching implementation. Keeps track of which cards we cleared and only this information.
@@ -141,7 +145,7 @@
 
  protected:
   // Cleared card array, used to update the mod-union table.
-  std::set<byte*> cleared_cards_;
+  CardSet cleared_cards_;
 };
 
 }  // namespace accounting
diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h
index 77f93a2..674c262 100644
--- a/runtime/gc/accounting/space_bitmap.h
+++ b/runtime/gc/accounting/space_bitmap.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_H_
 
 #include "locks.h"
+#include "gc_allocator.h"
 #include "globals.h"
 #include "mem_map.h"
 #include "UniquePtr.h"
@@ -205,7 +206,9 @@
 // Like a bitmap except it keeps track of objects using sets.
 class SpaceSetMap {
  public:
-  typedef std::set<const mirror::Object*> Objects;
+  typedef std::set<
+      const mirror::Object*, std::less<const mirror::Object*>,
+      GCAllocator<const mirror::Object*> > Objects;
 
   bool IsEmpty() const {
     return contained_.empty();
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index b6cef58..edc5529 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -90,6 +90,7 @@
       num_bytes_allocated_(0),
       native_bytes_allocated_(0),
       process_state_(PROCESS_STATE_TOP),
+      gc_memory_overhead_(0),
       verify_missing_card_marks_(false),
       verify_system_weaks_(false),
       verify_pre_gc_heap_(false),
@@ -177,7 +178,7 @@
   card_table_.reset(accounting::CardTable::Create(heap_begin, heap_capacity));
   CHECK(card_table_.get() != NULL) << "Failed to create card table";
 
-  image_mod_union_table_.reset(new accounting::ModUnionTableToZygoteAllocspace(this));
+  image_mod_union_table_.reset(new accounting::ModUnionTableCardCache(this));
   CHECK(image_mod_union_table_.get() != NULL) << "Failed to create image mod-union table";
 
   zygote_mod_union_table_.reset(new accounting::ModUnionTableCardCache(this));
@@ -273,6 +274,18 @@
   }
 }
 
+void Heap::RegisterGCAllocation(size_t bytes) {
+  if (this != NULL) {
+    gc_memory_overhead_.fetch_add(bytes);
+  }
+}
+
+void Heap::RegisterGCDeAllocation(size_t bytes) {
+  if (this != NULL) {
+    gc_memory_overhead_.fetch_sub(bytes);
+  }
+}
+
 void Heap::AddDiscontinuousSpace(space::DiscontinuousSpace* space) {
   WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
   DCHECK(space != NULL);
@@ -333,6 +346,7 @@
   }
   os << "Total mutator paused time: " << PrettyDuration(total_paused_time) << "\n";
   os << "Total time waiting for GC to complete: " << PrettyDuration(total_wait_time_) << "\n";
+  os << "Approximate GC data structures memory overhead: " << gc_memory_overhead_;
 }
 
 Heap::~Heap() {
@@ -1128,6 +1142,7 @@
     // Wake anyone who may have been waiting for the GC to complete.
     gc_complete_cond_->Broadcast(self);
   }
+
   // Inform DDMS that a GC completed.
   ATRACE_END();
   Dbg::GcDidFinish();
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 4a043a7..853db93 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -24,6 +24,7 @@
 #include "atomic_integer.h"
 #include "base/timing_logger.h"
 #include "gc/accounting/atomic_stack.h"
+#include "gc/accounting/gc_allocator.h"
 #include "gc/accounting/card_table.h"
 #include "gc/collector/gc_type.h"
 #include "globals.h"
@@ -207,6 +208,10 @@
     return target_utilization_;
   }
 
+  // Data structure memory usage tracking.
+  void RegisterGCAllocation(size_t bytes);
+  void RegisterGCDeAllocation(size_t bytes);
+
   // Set target ideal heap utilization ratio, implements
   // dalvik.system.VMRuntime.setTargetHeapUtilization.
   void SetTargetHeapUtilization(float target);
@@ -556,6 +561,9 @@
   // Current process state, updated by activity manager.
   ProcessState process_state_;
 
+  // Data structure GC overhead.
+  AtomicInteger gc_memory_overhead_;
+
   // Heap verification flags.
   const bool verify_missing_card_marks_;
   const bool verify_system_weaks_;
diff --git a/runtime/gc/space/large_object_space.h b/runtime/gc/space/large_object_space.h
index 09c55ec..8cd5088 100644
--- a/runtime/gc/space/large_object_space.h
+++ b/runtime/gc/space/large_object_space.h
@@ -17,7 +17,7 @@
 #ifndef ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
 #define ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
 
-
+#include "gc/accounting/gc_allocator.h"
 #include "dlmalloc_space.h"
 #include "safe_map.h"
 #include "space.h"
@@ -95,8 +95,10 @@
 
   // Used to ensure mutual exclusion when the allocation spaces data structures are being modified.
   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
-  std::vector<mirror::Object*> large_objects_ GUARDED_BY(lock_);
-  typedef SafeMap<mirror::Object*, MemMap*> MemMaps;
+  std::vector<mirror::Object*,
+      accounting::GCAllocator<mirror::Object*> > large_objects_ GUARDED_BY(lock_);
+  typedef SafeMap<mirror::Object*, MemMap*, std::less<mirror::Object*>,
+      accounting::GCAllocator<std::pair<const mirror::Object*, MemMap*> > > MemMaps;
   MemMaps mem_maps_ GUARDED_BY(lock_);
 };
 
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index dcc172d..4b5202a 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_SAFE_MAP_H_
 
 #include <map>
+#include <memory>
 
 #include "base/logging.h"
 
@@ -25,10 +26,11 @@
 
 // Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular,
 // the implicit insertion of a default-constructed value on failed lookups).
-template <typename K, typename V, typename Comparator = std::less<K> >
+template <typename K, typename V, typename Comparator = std::less<K>,
+          typename Allocator = std::allocator<std::pair<const K, V> > >
 class SafeMap {
  private:
-  typedef SafeMap<K, V, Comparator> Self;
+  typedef SafeMap<K, V, Comparator, Allocator> Self;
 
  public:
   typedef typename ::std::map<K, V, Comparator>::iterator iterator;
@@ -87,7 +89,7 @@
   }
 
  private:
-  ::std::map<K, V, Comparator> map_;
+  ::std::map<K, V, Comparator, Allocator> map_;
 };
 
 template <typename K, typename V, typename Comparator>
diff --git a/runtime/utils.h b/runtime/utils.h
index 72597f5..1c45048 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -107,6 +107,18 @@
   return static_cast<uint32_t>(value >> 32);
 }
 
+// A static if which determines whether to return type A or B based on the condition boolean.
+template <const bool condition, typename A, typename B>
+struct TypeStaticIf {
+  typedef A value;
+};
+
+// Specialization to handle the false case.
+template <typename A, typename B>
+struct TypeStaticIf<false, A,  B> {
+  typedef B value;
+};
+
 template<typename T>
 static inline T RoundDown(T x, int n) {
   CHECK(IsPowerOfTwo(n));