diff --git a/build/gen.py b/build/gen.py
index cc6e835..772d090 100755
--- a/build/gen.py
+++ b/build/gen.py
@@ -684,6 +684,7 @@
         'src/gn/analyzer_unittest.cc',
         'src/gn/args_unittest.cc',
         'src/gn/builder_unittest.cc',
+        'src/gn/builder_record_map_unittest.cc',
         'src/gn/c_include_iterator_unittest.cc',
         'src/gn/command_format_unittest.cc',
         'src/gn/commands_unittest.cc',
diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index d1ba662..7e36deb 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -34,7 +34,9 @@
 bool RecursiveFindCycle(const BuilderRecord* search_in,
                         std::vector<const BuilderRecord*>* path) {
   path->push_back(search_in);
-  for (auto* cur : search_in->unresolved_deps()) {
+  BuilderRecordSet unresolved_deps = search_in->GetUnresolvedDeps();
+  for (auto it = unresolved_deps.begin(); it.valid(); ++it) {
+    const BuilderRecord* cur = *it;
     std::vector<const BuilderRecord*>::iterator found =
         std::find(path->begin(), path->end(), cur);
     if (found != path->end()) {
@@ -133,7 +135,7 @@
   std::vector<const BuilderRecord*> result;
   result.reserve(records_.size());
   for (const auto& record : records_)
-    result.push_back(record.second.get());
+    result.push_back(&record);
   return result;
 }
 
@@ -141,9 +143,9 @@
   std::vector<const Item*> result;
   result.reserve(records_.size());
   for (const auto& record : records_) {
-    if (record.second->type() != BuilderRecord::ITEM_UNKNOWN &&
-        record.second->should_generate() && record.second->item()) {
-      result.push_back(record.second->item());
+    if (record.type() != BuilderRecord::ITEM_UNKNOWN &&
+        record.should_generate() && record.item()) {
+      result.push_back(record.item());
     }
   }
 
@@ -154,9 +156,9 @@
   std::vector<const Target*> result;
   result.reserve(records_.size());
   for (const auto& record : records_) {
-    if (record.second->type() == BuilderRecord::ITEM_TARGET &&
-        record.second->should_generate() && record.second->item())
-      result.push_back(record.second->item()->AsTarget());
+    if (record.type() == BuilderRecord::ITEM_TARGET &&
+        record.should_generate() && record.item())
+      result.push_back(record.item()->AsTarget());
   }
   return result;
 }
@@ -167,8 +169,7 @@
 }
 
 BuilderRecord* Builder::GetRecord(const Label& label) {
-  auto found = records_.find(label);
-  return (found != records_.end()) ? found->second.get() : nullptr;
+  return records_.find(label);
 }
 
 bool Builder::CheckForBadItems(Err* err) const {
@@ -183,18 +184,18 @@
   // that below.
   std::vector<const BuilderRecord*> bad_records;
   std::string depstring;
-  for (const auto& record_pair : records_) {
-    const BuilderRecord* src = record_pair.second.get();
-    if (!src->should_generate())
+  for (const auto& src : records_) {
+    if (!src.should_generate())
       continue;  // Skip ungenerated nodes.
 
-    if (!src->resolved()) {
-      bad_records.push_back(src);
+    if (!src.resolved()) {
+      bad_records.push_back(&src);
 
       // Check dependencies.
-      for (auto* dest : src->unresolved_deps()) {
+      BuilderRecordSet unresolved_deps = src.GetUnresolvedDeps();
+      for (const auto* dest : unresolved_deps) {
         if (!dest->item()) {
-          depstring += src->label().GetUserVisibleName(true) + "\n  needs " +
+          depstring += src.label().GetUserVisibleName(true) + "\n  needs " +
                        dest->label().GetUserVisibleName(true) + "\n";
         }
       }
@@ -265,8 +266,9 @@
   // anything they depend on is actually written, the "generate" flag isn't
   // relevant and means extra book keeping. Just force load any deps of this
   // config.
-  for (auto* cur : record->all_deps())
-    ScheduleItemLoadIfNecessary(cur);
+  for (auto it = record->all_deps().begin(); it.valid(); ++it) {
+    ScheduleItemLoadIfNecessary(*it);
+  }
 
   return true;
 }
@@ -303,18 +305,11 @@
                                                 const ParseNode* request_from,
                                                 BuilderRecord::ItemType type,
                                                 Err* err) {
-  BuilderRecord* record = GetRecord(label);
-  if (!record) {
-    // Not seen this record yet, create a new one.
-    auto new_record = std::make_unique<BuilderRecord>(type, label);
-    new_record->set_originally_referenced_from(request_from);
-    record = new_record.get();
-    records_[label] = std::move(new_record);
-    return record;
-  }
+  auto pair = records_.try_emplace(label, request_from, type);
+  BuilderRecord* record = pair.second;
 
-  // Check types.
-  if (record->type() != type) {
+  // Check types, if the record was not just created.
+  if (!pair.first && record->type() != type) {
     std::string msg =
         "The type of " + label.GetUserVisibleName(false) + "\nhere is a " +
         BuilderRecord::GetNameForType(type) + " but was previously seen as a " +
@@ -461,7 +456,8 @@
     return;  // Already set and we're not required to iterate dependencies.
   }
 
-  for (auto* cur : record->all_deps()) {
+  for (auto it = record->all_deps().begin(); it.valid(); ++it) {
+    BuilderRecord* cur = *it;
     if (!cur->should_generate()) {
       ScheduleItemLoadIfNecessary(cur);
       RecursiveSetShouldGenerate(cur, false);
@@ -508,12 +504,10 @@
     resolved_and_generated_callback_(record);
 
   // Recursively update everybody waiting on this item to be resolved.
-  for (BuilderRecord* waiting : record->waiting_on_resolution()) {
-    DCHECK(waiting->unresolved_deps().find(record) !=
-           waiting->unresolved_deps().end());
-    waiting->unresolved_deps().erase(record);
-
-    if (waiting->can_resolve()) {
+  const BuilderRecordSet waiting_deps = record->waiting_on_resolution();
+  for (auto it = waiting_deps.begin(); it.valid(); ++it) {
+    BuilderRecord* waiting = *it;
+    if (waiting->OnResolvedDep(record)) {
       if (!ResolveItem(waiting, err))
         return false;
     }
diff --git a/src/gn/builder.h b/src/gn/builder.h
index bd62c18..4b85824 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -6,10 +6,11 @@
 #define TOOLS_GN_BUILDER_H_
 
 #include <functional>
-#include <map>
 #include <memory>
+#include <unordered_map>
 
 #include "gn/builder_record.h"
+#include "gn/builder_record_map.h"
 #include "gn/label.h"
 #include "gn/label_ptr.h"
 #include "gn/unique_vector.h"
@@ -138,7 +139,7 @@
   // Non owning pointer.
   Loader* loader_;
 
-  std::map<Label, std::unique_ptr<BuilderRecord>> records_;
+  BuilderRecordMap records_;
 
   ResolvedGeneratedCallback resolved_and_generated_callback_;
 
diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index 6325cdc..7849d91 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -6,8 +6,12 @@
 
 #include "gn/item.h"
 
-BuilderRecord::BuilderRecord(ItemType type, const Label& label)
-    : type_(type), label_(label) {}
+BuilderRecord::BuilderRecord(ItemType type,
+                             const Label& label,
+                             const ParseNode* originally_referenced_from)
+    : type_(type),
+      label_(label),
+      originally_referenced_from_(originally_referenced_from) {}
 
 // static
 const char* BuilderRecord::GetNameForType(ItemType type) {
@@ -64,10 +68,25 @@
   all_deps_.insert(record);
 }
 
+bool BuilderRecord::OnResolvedDep(const BuilderRecord* dep) {
+  DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
+  DCHECK(unresolved_count_ > 0);
+  return --unresolved_count_ == 0;
+}
+
+BuilderRecord::BuilderRecordSet BuilderRecord::GetUnresolvedDeps() const {
+  BuilderRecordSet result;
+  for (auto it = all_deps_.begin(); it.valid(); ++it) {
+    BuilderRecord* dep = *it;
+    if (dep->waiting_on_resolution_.contains(const_cast<BuilderRecord*>(this)))
+      result.add(dep);
+  }
+  return result;
+}
+
 void BuilderRecord::AddDep(BuilderRecord* record) {
-  all_deps_.insert(record);
-  if (!record->resolved()) {
-    unresolved_deps_.insert(record);
-    record->waiting_on_resolution_.insert(this);
+  if (all_deps_.add(record) && !record->resolved()) {
+    unresolved_count_ += 1;
+    record->waiting_on_resolution_.add(this);
   }
 }
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index 439893b..28f75fe 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -6,11 +6,11 @@
 #define TOOLS_GN_BUILDER_RECORD_H_
 
 #include <memory>
-#include <set>
 #include <utility>
 
 #include "gn/item.h"
 #include "gn/location.h"
+#include "gn/pointer_set.h"
 
 class ParseNode;
 
@@ -28,7 +28,7 @@
 // the current build (should_generate is false).
 class BuilderRecord {
  public:
-  using BuilderRecordSet = std::set<BuilderRecord*>;
+  using BuilderRecordSet = PointerSet<BuilderRecord>;
 
   enum ItemType {
     ITEM_UNKNOWN,
@@ -38,7 +38,9 @@
     ITEM_POOL
   };
 
-  BuilderRecord(ItemType type, const Label& label);
+  BuilderRecord(ItemType type,
+                const Label& label,
+                const ParseNode* originally_referenced_from);
 
   ItemType type() const { return type_; }
   const Label& label() const { return label_; }
@@ -62,9 +64,6 @@
   const ParseNode* originally_referenced_from() const {
     return originally_referenced_from_;
   }
-  void set_originally_referenced_from(const ParseNode* pn) {
-    originally_referenced_from_ = pn;
-  }
 
   bool should_generate() const { return should_generate_; }
   void set_should_generate(bool sg) { should_generate_ = sg; }
@@ -72,16 +71,21 @@
   bool resolved() const { return resolved_; }
   void set_resolved(bool r) { resolved_ = r; }
 
-  bool can_resolve() const { return item_ && unresolved_deps_.empty(); }
+  bool can_resolve() const { return item_ && unresolved_count_ == 0; }
 
   // All records this one is depending on. Note that this includes gen_deps for
   // targets, which can have cycles.
   BuilderRecordSet& all_deps() { return all_deps_; }
   const BuilderRecordSet& all_deps() const { return all_deps_; }
 
-  // Unresolved records this one is depending on. A subset of all... above.
-  BuilderRecordSet& unresolved_deps() { return unresolved_deps_; }
-  const BuilderRecordSet& unresolved_deps() const { return unresolved_deps_; }
+  // Return the set of unresolved records this one is depend on.
+  // This is a subset of all_deps() above.
+  BuilderRecordSet GetUnresolvedDeps() const;
+
+  // Call this method to notify the record that its dependency |dep| was
+  // just resolved. This returns true to indicate that the current record
+  // should now be resolved.
+  bool OnResolvedDep(const BuilderRecord* dep);
 
   // Records that are waiting on this one to be resolved. This is the other
   // end of the "unresolved deps" arrow.
@@ -95,14 +99,14 @@
 
  private:
   ItemType type_;
+  bool should_generate_ = false;
+  bool resolved_ = false;
   Label label_;
   std::unique_ptr<Item> item_;
   const ParseNode* originally_referenced_from_ = nullptr;
-  bool should_generate_ = false;
-  bool resolved_ = false;
 
+  size_t unresolved_count_ = 0;
   BuilderRecordSet all_deps_;
-  BuilderRecordSet unresolved_deps_;
   BuilderRecordSet waiting_on_resolution_;
 
   BuilderRecord(const BuilderRecord&) = delete;
diff --git a/src/gn/builder_record_map.h b/src/gn/builder_record_map.h
new file mode 100644
index 0000000..58ce712
--- /dev/null
+++ b/src/gn/builder_record_map.h
@@ -0,0 +1,80 @@
+// Copyright 2021 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SRC_GN_BUILDER_RECORD_MAP_H_
+#define SRC_GN_BUILDER_RECORD_MAP_H_
+
+#include "gn/builder_record.h"
+#include "gn/hash_table_base.h"
+
+// This header implements a custom Label -> BuilderRecord map that is critical
+// for performance of the Builder class.
+//
+// Measurements show it performs better than
+// std::unordered_map<Label, BuilderRecord>, which itself performs much better
+// than base::flat_map<Label, BuilderRecord> or std::map<Label, BuilderRecord>
+//
+// NOTE: This only implements the features required by the Builder class.
+//
+
+struct BuilderRecordNode {
+  BuilderRecord* record;
+  bool is_null() const { return !record; }
+  static constexpr bool is_tombstone() { return false; }
+  bool is_valid() const { return !is_null() && !is_tombstone(); }
+  size_t hash_value() const { return record->label().hash(); }
+};
+
+class BuilderRecordMap : public HashTableBase<BuilderRecordNode> {
+ public:
+  using NodeType = BuilderRecordNode;
+
+  ~BuilderRecordMap() {
+    for (auto it = NodeBegin(); it.valid(); ++it) {
+      delete it->record;
+    }
+  }
+
+  // Find BuilderRecord matching |label| or return nullptr.
+  BuilderRecord* find(const Label& label) const {
+    return Lookup(label)->record;
+  }
+
+  // Try to find BuilderRecord matching |label|, and create one if
+  // none is found. result.first will be true to indicate that a new
+  // record was created.
+  std::pair<bool, BuilderRecord*> try_emplace(const Label& label,
+                                              const ParseNode* request_from,
+                                              BuilderRecord::ItemType type) {
+    NodeType* node = Lookup(label);
+    if (node->is_valid()) {
+      return {false, node->record};
+    }
+    BuilderRecord* record = new BuilderRecord(type, label, request_from);
+    node->record = record;
+    UpdateAfterInsert();
+    return {true, record};
+  }
+
+  // Iteration support
+  struct const_iterator : public NodeIterator {
+    const BuilderRecord& operator*() const { return *node_->record; }
+    BuilderRecord& operator*() { return *node_->record; }
+
+    const BuilderRecord* operator->() const { return node_->record; }
+    BuilderRecord* operator->() { return node_->record; }
+  };
+
+  const_iterator begin() const { return {NodeBegin()}; }
+  const_iterator end() const { return {NodeEnd()}; }
+
+ private:
+  NodeType* Lookup(const Label& label) const {
+    return NodeLookup(label.hash(), [&label](const NodeType* node) {
+      return node->record->label() == label;
+    });
+  }
+};
+
+#endif  // SRC_GN_BUILDER_RECORD_MAP_H_
diff --git a/src/gn/builder_record_map_unittest.cc b/src/gn/builder_record_map_unittest.cc
new file mode 100644
index 0000000..b26ed5c
--- /dev/null
+++ b/src/gn/builder_record_map_unittest.cc
@@ -0,0 +1,62 @@
+// Copyright 2021 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+
+#include "gn/builder_record_map.h"
+#include "gn/builder_record.h"
+#include "gn/label.h"
+#include "gn/source_dir.h"
+#include "util/test/test.h"
+
+TEST(BuilderRecordMap, Construction) {
+  const Label kLabel1(SourceDir("//src"), "foo");
+  BuilderRecordMap map;
+  EXPECT_TRUE(map.empty());
+  EXPECT_EQ(0u, map.size());
+  EXPECT_FALSE(map.find(kLabel1));
+}
+
+TEST(BuilderRecordMap, TryEmplace) {
+  const Label kLabel1(SourceDir("//src"), "foo");
+  const Label kLabel2(SourceDir("//src"), "bar");
+  const Label kLabel3(SourceDir("//third_party/src"), "zoo");
+
+  BuilderRecordMap map;
+
+  auto ret = map.try_emplace(kLabel1, nullptr, BuilderRecord::ITEM_TARGET);
+  EXPECT_TRUE(ret.first);
+  EXPECT_TRUE(ret.second);
+  EXPECT_EQ(BuilderRecord::ITEM_TARGET, ret.second->type());
+  EXPECT_EQ(kLabel1, ret.second->label());
+  EXPECT_EQ(ret.second, map.find(kLabel1));
+  EXPECT_EQ(1u, map.size());
+
+  BuilderRecord* record = ret.second;
+  ret = map.try_emplace(kLabel1, nullptr, BuilderRecord::ITEM_CONFIG);
+  EXPECT_FALSE(ret.first);
+  EXPECT_EQ(record, ret.second);
+  EXPECT_EQ(1u, map.size());
+
+  ret = map.try_emplace(kLabel2, nullptr, BuilderRecord::ITEM_CONFIG);
+  EXPECT_TRUE(ret.first);
+  EXPECT_TRUE(ret.second);
+  EXPECT_EQ(2u, map.size());
+  EXPECT_EQ(BuilderRecord::ITEM_CONFIG, ret.second->type());
+  EXPECT_EQ(kLabel2, ret.second->label());
+  EXPECT_EQ(ret.second, map.find(kLabel2));
+
+  ret = map.try_emplace(kLabel3, nullptr, BuilderRecord::ITEM_TOOLCHAIN);
+  EXPECT_TRUE(ret.first);
+  EXPECT_TRUE(ret.second);
+  EXPECT_EQ(3u, map.size());
+  EXPECT_EQ(BuilderRecord::ITEM_TOOLCHAIN, ret.second->type());
+  EXPECT_EQ(kLabel3, ret.second->label());
+  EXPECT_EQ(ret.second, map.find(kLabel3));
+
+  ret = map.try_emplace(kLabel2, nullptr, BuilderRecord::ITEM_CONFIG);
+  EXPECT_FALSE(ret.first);
+
+  EXPECT_EQ(3u, map.size());
+  EXPECT_TRUE(map.find(kLabel1));
+  EXPECT_TRUE(map.find(kLabel2));
+  EXPECT_TRUE(map.find(kLabel3));
+}
diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index 81b9f89..2a354d5 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -138,17 +138,14 @@
 
   // A should have two deps: B and the toolchain. Only B should be unresolved.
   EXPECT_EQ(2u, a_record->all_deps().size());
-  EXPECT_EQ(1u, a_record->unresolved_deps().size());
-  EXPECT_NE(a_record->all_deps().end(),
-            a_record->all_deps().find(toolchain_record));
-  EXPECT_NE(a_record->all_deps().end(), a_record->all_deps().find(b_record));
-  EXPECT_NE(a_record->unresolved_deps().end(),
-            a_record->unresolved_deps().find(b_record));
+  EXPECT_EQ(1u, a_record->GetUnresolvedDeps().size());
+  EXPECT_TRUE(a_record->all_deps().contains(toolchain_record));
+  EXPECT_TRUE(a_record->all_deps().contains(b_record));
+  EXPECT_TRUE(a_record->GetUnresolvedDeps().contains(b_record));
 
   // B should be marked as having A waiting on it.
   EXPECT_EQ(1u, b_record->waiting_on_resolution().size());
-  EXPECT_NE(b_record->waiting_on_resolution().end(),
-            b_record->waiting_on_resolution().find(a_record));
+  EXPECT_TRUE(b_record->waiting_on_resolution().contains(a_record));
 
   // Add the C target.
   Target* c = new Target(&settings_, c_label);
@@ -177,9 +174,9 @@
   EXPECT_TRUE(b_record->resolved());
   EXPECT_TRUE(c_record->resolved());
 
-  EXPECT_TRUE(a_record->unresolved_deps().empty());
-  EXPECT_TRUE(b_record->unresolved_deps().empty());
-  EXPECT_TRUE(c_record->unresolved_deps().empty());
+  EXPECT_TRUE(a_record->GetUnresolvedDeps().empty());
+  EXPECT_TRUE(b_record->GetUnresolvedDeps().empty());
+  EXPECT_TRUE(c_record->GetUnresolvedDeps().empty());
 
   EXPECT_TRUE(a_record->waiting_on_resolution().empty());
   EXPECT_TRUE(b_record->waiting_on_resolution().empty());
diff --git a/src/gn/loader.cc b/src/gn/loader.cc
index c615170..9d46103 100644
--- a/src/gn/loader.cc
+++ b/src/gn/loader.cc
@@ -38,7 +38,7 @@
       : file(f), toolchain_name(tc_name) {}
 
   bool operator<(const LoadID& other) const {
-    if (file.value() == other.file.value())
+    if (file == other.file)
       return toolchain_name < other.toolchain_name;
     return file < other.file;
   }