common: pass-through hash for integer and pointer keys; RangeSet::Intersects

Common::unordered_map/set defaulted to std::hash, a byte-wise FNV-1a on MSVC for
integers and pointers, which boost's flat containers then mix again: the GPU thread's
page maps (shader and query cache invalidation, per inline upload) spent ~1% in it.
Integer and pointer keys now go through as they are and boost mixes them.
BufferCache::IsRegionGpuModified visited every GPU-written range inside the query just
to answer yes or no; without per-fence downloads those ranges stay fragmented and it was
~4% of title 1's GPU thread (inline uploads). RangeSet::Intersects answers with one
lookup. Inline uploads: 10.5% -> 7.5% of the GPU thread.

5 files changed, 39 insertions, 2 deletions

diff --git a/src/common/container/unordered_map.h b/src/common/container/unordered_map.h
index 7d9e49fd80..c4d4a72663 100644
--- a/src/common/container/unordered_map.h
+++ b/src/common/container/unordered_map.h
@@ -9,7 +9,7 @@
 
 namespace Common {
 
-template <class Key, class T, class Hash = std::hash<Key>, class Pred = std::equal_to<Key>,
+template <class Key, class T, class Hash = FastHash<Key>, class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<std::pair<const Key, T>>>
 using unordered_map = boost::unordered::unordered_flat_map<Key, T, Hash, Pred, Allocator>;
 
diff --git a/src/common/container/unordered_set.h b/src/common/container/unordered_set.h
index 54d71406a1..690c33286f 100644
--- a/src/common/container/unordered_set.h
+++ b/src/common/container/unordered_set.h
@@ -9,7 +9,7 @@
 
 namespace Common {
 
-template <class Key, class Hash = std::hash<Key>, class Pred = std::equal_to<Key>,
+template <class Key, class Hash = FastHash<Key>, class Pred = std::equal_to<Key>,
           class Allocator = std::allocator<Key>>
 using unordered_set = boost::unordered::unordered_flat_set<Key, Hash, Pred, Allocator>;
 
diff --git a/src/common/container_hash.h b/src/common/container_hash.h
index d7477f7e4f..f06f69ad8b 100644
--- a/src/common/container_hash.h
+++ b/src/common/container_hash.h
@@ -19,6 +19,28 @@
 
 namespace Common {
 
+/// The default hash of Common::unordered_map/set. std::hash of an integer or a pointer is a
+/// byte-wise FNV-1a on MSVC, and boost's flat containers mix a hash that does not say it
+/// avalanches anyway: pass those keys through (the GPU thread's page maps looked keys up
+/// tens of thousands of times a second with it). Other keys keep std::hash.
+template <class Key>
+struct FastHash : std::hash<Key> {};
+
+template <class Key>
+    requires std::is_integral_v<Key>
+struct FastHash<Key> {
+    std::size_t operator()(Key key) const noexcept {
+        return static_cast<std::size_t>(key);
+    }
+};
+
+template <class T>
+struct FastHash<T*> {
+    std::size_t operator()(T* pointer) const noexcept {
+        return reinterpret_cast<std::size_t>(pointer);
+    }
+};
+
 namespace detail {
 
 template <typename T>
diff --git a/src/common/range_sets.h b/src/common/range_sets.h
index f8fcee4837..e5cb53b058 100644
--- a/src/common/range_sets.h
+++ b/src/common/range_sets.h
@@ -26,6 +26,9 @@ public:
     void Clear();
     bool Empty() const;
 
+    /// Whether any range overlaps [base_address, base_address + size): one lookup.
+    bool Intersects(AddressType base_address, size_t size) const;
+
     template <typename Func>
     void ForEach(Func&& func) const;
 
diff --git a/src/common/range_sets.inc b/src/common/range_sets.inc
index 57b07d05f6..aeda7bc351 100644
--- a/src/common/range_sets.inc
+++ b/src/common/range_sets.inc
@@ -221,6 +221,18 @@ bool RangeSet<AddressType>::Empty() const {
 }
 
 template <typename AddressType>
+bool RangeSet<AddressType>::Intersects(AddressType base_address, size_t size) const {
+    const auto& set = m_impl->m_ranges_set;
+    if (set.empty() || size == 0) {
+        return false;
+    }
+    const AddressType end_address = base_address + static_cast<AddressType>(size);
+    // The first range not entirely below the query; it overlaps when it starts before its end.
+    const auto it = set.lower_bound(typename RangeSetImpl::IntervalType{base_address, end_address});
+    return it != set.end() && it->lower() < end_address;
+}
+
+template <typename AddressType>
 template <typename Func>
 void RangeSet<AddressType>::ForEach(Func&& func) const {
     m_impl->ForEach(std::move(func));