diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9491ef6..2d220fc 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -17,7 +17,6 @@
 #include "graph_checker.h"
 
 #include <algorithm>
-#include <map>
 #include <string>
 #include <sstream>
 
@@ -32,19 +31,19 @@
   current_block_ = block;
 
   // Check consistency with respect to predecessors of `block`.
-  ArenaSafeMap<HBasicBlock*, size_t> predecessors_count(
-      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
-  for (HBasicBlock* p : block->GetPredecessors()) {
-    auto it = predecessors_count.find(p);
-    if (it != predecessors_count.end()) {
-      ++it->second;
-    } else {
-      predecessors_count.Put(p, 1u);
+  // Note: Counting duplicates with a sorted vector uses up to 6x less memory
+  // than ArenaSafeMap<HBasicBlock*, size_t>.
+  ArenaVector<HBasicBlock*> sorted_predecessors(
+      block->GetPredecessors().begin(),
+      block->GetPredecessors().end(),
+      GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
+  std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
+  for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) {
+    HBasicBlock* p = *it++;
+    size_t p_count_in_block_predecessors = 1u;
+    for (; it != end && *it == p; ++it) {
+      ++p_count_in_block_predecessors;
     }
-  }
-  for (auto& pc : predecessors_count) {
-    HBasicBlock* p = pc.first;
-    size_t p_count_in_block_predecessors = pc.second;
     size_t block_count_in_p_successors =
         std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block);
     if (p_count_in_block_predecessors != block_count_in_p_successors) {
@@ -57,19 +56,19 @@
   }
 
   // Check consistency with respect to successors of `block`.
-  ArenaSafeMap<HBasicBlock*, size_t> successors_count(
-      std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
-  for (HBasicBlock* s : block->GetSuccessors()) {
-    auto it = successors_count.find(s);
-    if (it != successors_count.end()) {
-      ++it->second;
-    } else {
-      successors_count.Put(s, 1u);
+  // Note: Counting duplicates with a sorted vector uses up to 6x less memory
+  // than ArenaSafeMap<HBasicBlock*, size_t>.
+  ArenaVector<HBasicBlock*> sorted_successors(
+      block->GetSuccessors().begin(),
+      block->GetSuccessors().end(),
+      GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
+  std::sort(sorted_successors.begin(), sorted_successors.end());
+  for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) {
+    HBasicBlock* s = *it++;
+    size_t s_count_in_block_successors = 1u;
+    for (; it != end && *it == s; ++it) {
+      ++s_count_in_block_successors;
     }
-  }
-  for (auto& sc : successors_count) {
-    HBasicBlock* s = sc.first;
-    size_t s_count_in_block_successors = sc.second;
     size_t block_count_in_s_predecessors =
         std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block);
     if (s_count_in_block_successors != block_count_in_s_predecessors) {