diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index e5c8c47..f2e77e2 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -32,11 +32,9 @@
 
   // Check consistency with respect to predecessors of `block`.
   // 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));
+  // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
+  ArenaVector<HBasicBlock*>& sorted_predecessors = blocks_storage_;
+  sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end());
   std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
   for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) {
     HBasicBlock* p = *it++;
@@ -57,11 +55,9 @@
 
   // Check consistency with respect to successors of `block`.
   // 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));
+  // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
+  ArenaVector<HBasicBlock*>& sorted_successors = blocks_storage_;
+  sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end());
   std::sort(sorted_successors.begin(), sorted_successors.end());
   for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) {
     HBasicBlock* s = *it++;
@@ -811,10 +807,11 @@
               phi->GetRegNumber(),
               type_str.str().c_str()));
         } else {
-          ArenaBitVector visited(GetGraph()->GetArena(),
-                                 0,
-                                 /* expandable */ true,
-                                 kArenaAllocGraphChecker);
+          // If we get here, make sure we allocate all the necessary storage at once
+          // because the BitVector reallocation strategy has very bad worst-case behavior.
+          ArenaBitVector& visited = visited_storage_;
+          visited.SetBit(GetGraph()->GetCurrentInstructionId());
+          visited.ClearAllBits();
           if (!IsConstantEquivalent(phi, other_phi, &visited)) {
             AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
                                   "are not equivalents of constants.",
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 27d5621..a536b30 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -33,7 +33,9 @@
       seen_ids_(graph->GetArena(),
                 graph->GetCurrentInstructionId(),
                 false,
-                kArenaAllocGraphChecker) {}
+                kArenaAllocGraphChecker),
+      blocks_storage_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)),
+      visited_storage_(graph->GetArena(), 0u, true, kArenaAllocGraphChecker) {}
 
   // Check the whole graph (in reverse post-order).
   void Run() {
@@ -102,6 +104,10 @@
   const char* const dump_prefix_;
   ArenaBitVector seen_ids_;
 
+  // To reduce the total arena memory allocation, we reuse the same storage.
+  ArenaVector<HBasicBlock*> blocks_storage_;
+  ArenaBitVector visited_storage_;
+
   DISALLOW_COPY_AND_ASSIGN(GraphChecker);
 };