diff --git a/common/simple_linked_hash_map.h b/common/simple_linked_hash_map.h
index c99585e..b7488eb 100644
--- a/common/simple_linked_hash_map.h
+++ b/common/simple_linked_hash_map.h
@@ -212,7 +212,8 @@
     return std::make_pair(last, true);
   }
 
-  size_type size() const { return list_.size(); }
+  // Derive size_ from map_, as list::size might be O(N).
+  size_type size() const { return map_.size(); }
 
   template <typename... Args>
   std::pair<iterator, bool> emplace(Args&&... args) {