about summary refs log tree commit diff
path: root/absl/container/internal/raw_hash_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal/raw_hash_set.h')
-rw-r--r--absl/container/internal/raw_hash_set.h19
1 files changed, 14 insertions, 5 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 0c0e5906d206..40bdb71b5203 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -662,7 +662,7 @@ class raw_hash_set {
       allocator_type>::template rebind_traits<value_type>::const_pointer;
 
   // Alias used for heterogeneous lookup functions.
-  // `key_arg<K>` evaluates to `K` when the functors are tranparent and to
+  // `key_arg<K>` evaluates to `K` when the functors are transparent and to
   // `key_type` otherwise. It permits template argument deduction on `K` for the
   // transparent case.
   template <class K>
@@ -1330,8 +1330,7 @@ class raw_hash_set {
   void rehash(size_t n) {
     if (n == 0 && capacity_ == 0) return;
     if (n == 0 && size_ == 0) return destroy_slots();
-    auto m = NormalizeCapacity(std::max(
-        n, static_cast<size_t>(std::ceil(size() / kMaxLoadFactor))));
+    auto m = NormalizeCapacity(std::max(n, NumSlotsFast(size())));
     // n == 0 unconditionally rehashes as per the standard.
     if (n == 0 || m > capacity_) {
       resize(m);
@@ -1339,7 +1338,7 @@ class raw_hash_set {
   }
 
   void reserve(size_t n) {
-    rehash(static_cast<size_t>(std::ceil(n / kMaxLoadFactor)));
+    rehash(NumSlotsFast(n));
   }
 
   // Extension API: support for heterogeneous keys.
@@ -1518,6 +1517,13 @@ class raw_hash_set {
     slot_type&& slot;
   };
 
+  // Computes std::ceil(n / kMaxLoadFactor). Faster than calling std::ceil.
+  static inline size_t NumSlotsFast(size_t n) {
+    return static_cast<size_t>(
+        (n * kMaxLoadFactorDenominator + (kMaxLoadFactorNumerator - 1)) /
+        kMaxLoadFactorNumerator);
+  }
+
   // "erases" the object from the container, except that it doesn't actually
   // destroy the object. It only updates all the metadata of the class.
   // This can be used in conjunction with Policy::transfer to move the object to
@@ -1825,7 +1831,10 @@ class raw_hash_set {
   }
 
   // On average each group has 2 empty slot (for the vectorized case).
-  static constexpr float kMaxLoadFactor = 14.0 / 16.0;
+  static constexpr int64_t kMaxLoadFactorNumerator = 14;
+  static constexpr int64_t kMaxLoadFactorDenominator = 16;
+  static constexpr float kMaxLoadFactor =
+      1.0 * kMaxLoadFactorNumerator / kMaxLoadFactorDenominator;
 
   // TODO(alkis): Investigate removing some of these fields:
   // - ctrl/slots can be derived from each other