Change hash table load factors
Changed class table and intern table load factors to query the
runtime. The runtime returns load factors based on whether or not we
are a low ram device.
DescriptorEquals time for class linking goes from 10% -> 1.2% for
compiling GmsCore with interpret only.
Added test.
Bug: 24917584
Change-Id: Iaaf5d2eab1b0c2d188d299e4bc1852cdb3801173
diff --git a/runtime/base/hash_set.h b/runtime/base/hash_set.h
index f2b1cc0..4819f06 100644
--- a/runtime/base/hash_set.h
+++ b/runtime/base/hash_set.h
@@ -127,8 +127,8 @@
using size_type = size_t;
using difference_type = ptrdiff_t;
- static constexpr double kDefaultMinLoadFactor = 0.5;
- static constexpr double kDefaultMaxLoadFactor = 0.9;
+ static constexpr double kDefaultMinLoadFactor = 0.4;
+ static constexpr double kDefaultMaxLoadFactor = 0.7;
static constexpr size_t kMinBuckets = 1000;
// If we don't own the data, this will create a new array which owns the data.
@@ -138,14 +138,18 @@
elements_until_expand_ = 0;
}
- HashSet()
+ HashSet() : HashSet(kDefaultMinLoadFactor, kDefaultMaxLoadFactor) {}
+
+ HashSet(double min_load_factor, double max_load_factor)
: num_elements_(0u),
num_buckets_(0u),
elements_until_expand_(0u),
owns_data_(false),
data_(nullptr),
- min_load_factor_(kDefaultMinLoadFactor),
- max_load_factor_(kDefaultMaxLoadFactor) {
+ min_load_factor_(min_load_factor),
+ max_load_factor_(max_load_factor) {
+ DCHECK_GT(min_load_factor, 0.0);
+ DCHECK_LT(max_load_factor, 1.0);
}
explicit HashSet(const allocator_type& alloc)
@@ -459,6 +463,31 @@
return errors;
}
+ double GetMinLoadFactor() const {
+ return min_load_factor_;
+ }
+
+ double GetMaxLoadFactor() const {
+ return max_load_factor_;
+ }
+
+ // Change the load factor of the hash set. If the current load factor is greater than the max
+ // specified, then we resize the hash table storage.
+ void SetLoadFactor(double min_load_factor, double max_load_factor) {
+ DCHECK_LT(min_load_factor, max_load_factor);
+ DCHECK_GT(min_load_factor, 0.0);
+ DCHECK_LT(max_load_factor, 1.0);
+ min_load_factor_ = min_load_factor;
+ max_load_factor_ = max_load_factor;
+ elements_until_expand_ = NumBuckets() * max_load_factor_;
+ // If the current load factor isn't in the range, then resize to the mean of the minimum and
+ // maximum load factor.
+ const double load_factor = CalculateLoadFactor();
+ if (load_factor > max_load_factor_) {
+ Resize(Size() / ((min_load_factor_ + max_load_factor_) * 0.5));
+ }
+ }
+
private:
T& ElementForIndex(size_t index) {
DCHECK_LT(index, NumBuckets());
diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc
index 6d2c5e0..743e98e 100644
--- a/runtime/base/hash_set_test.cc
+++ b/runtime/base/hash_set_test.cc
@@ -196,6 +196,24 @@
}
}
+TEST_F(HashSetTest, TestLoadFactor) {
+ HashSet<std::string, IsEmptyFnString> hash_set;
+ static constexpr size_t kStringCount = 1000;
+ static constexpr double kEpsilon = 0.01;
+ for (size_t i = 0; i < kStringCount; ++i) {
+ hash_set.Insert(RandomString(i % 10 + 1));
+ }
+ // Check that changing the load factor resizes the table to be within the target range.
+ EXPECT_GE(hash_set.CalculateLoadFactor() + kEpsilon, hash_set.GetMinLoadFactor());
+ EXPECT_LE(hash_set.CalculateLoadFactor() - kEpsilon, hash_set.GetMaxLoadFactor());
+ hash_set.SetLoadFactor(0.1, 0.3);
+ EXPECT_DOUBLE_EQ(0.1, hash_set.GetMinLoadFactor());
+ EXPECT_DOUBLE_EQ(0.3, hash_set.GetMaxLoadFactor());
+ EXPECT_LE(hash_set.CalculateLoadFactor() - kEpsilon, hash_set.GetMaxLoadFactor());
+ hash_set.SetLoadFactor(0.6, 0.8);
+ EXPECT_LE(hash_set.CalculateLoadFactor() - kEpsilon, hash_set.GetMaxLoadFactor());
+}
+
TEST_F(HashSetTest, TestStress) {
HashSet<std::string, IsEmptyFnString> hash_set;
std::unordered_multiset<std::string> std_set;