Do hashtablez sampling on the first insertion into an empty SOO hashtable.

When sampling triggers, we skip SOO and allocate a backing array. We must do this because the HashtablezInfoHandle is part of the heap allocation (along with the control bytes and slots). By default, we sample 1 in ~1024 hashtables when sampling is enabled. This will impact performance because (a) we won't benefit from SOO so we would have worse data locality (more cache/TLB misses), and (b) the backing array capacity will be 3 instead of 1 so (b.1) we skip the rehash after the second insertion and (b.2) we potentially waste up to two slots worth of memory.

We also add an soo_capacity field to HashtablezInfo to allow for distinguishing which sampled tables may otherwise have been SOO - this will allow us to know approximately what fraction of tables are in SOO mode.

PiperOrigin-RevId: 617252334
Change-Id: Ib48b7a4870bd74ea3ba923ed8f350a3b75dbb7d3

1 files changed, 35 insertions, 14 deletions

diff --git a/absl/container/internal/hashtablez_sampler_test.cc b/absl/container/internal/hashtablez_sampler_test.cc
index 8ebb08da..a80f530d 100644
--- a/absl/container/internal/hashtablez_sampler_test.cc
+++ b/absl/container/internal/hashtablez_sampler_test.cc
@@ -15,8 +15,12 @@
 #include "absl/container/internal/hashtablez_sampler.h"
 
 #include <atomic>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
 #include <limits>
 #include <random>
+#include <vector>
 
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
@@ -67,7 +71,7 @@ std::vector<size_t> GetSizes(HashtablezSampler* s) {
 HashtablezInfo* Register(HashtablezSampler* s, size_t size) {
   const int64_t test_stride = 123;
   const size_t test_element_size = 17;
-  auto* info = s->Register(test_stride, test_element_size);
+  auto* info = s->Register(test_stride, test_element_size, /*soo_capacity=*/0);
   assert(info != nullptr);
   info->size.store(size);
   return info;
@@ -79,7 +83,8 @@ TEST(HashtablezInfoTest, PrepareForSampling) {
   const size_t test_element_size = 17;
   HashtablezInfo info;
   absl::MutexLock l(&info.init_mu);
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/1);
 
   EXPECT_EQ(info.capacity.load(), 0);
   EXPECT_EQ(info.size.load(), 0);
@@ -94,6 +99,7 @@ TEST(HashtablezInfoTest, PrepareForSampling) {
   EXPECT_GE(info.create_time, test_start);
   EXPECT_EQ(info.weight, test_stride);
   EXPECT_EQ(info.inline_element_size, test_element_size);
+  EXPECT_EQ(info.soo_capacity, 1);
 
   info.capacity.store(1, std::memory_order_relaxed);
   info.size.store(1, std::memory_order_relaxed);
@@ -106,7 +112,8 @@ TEST(HashtablezInfoTest, PrepareForSampling) {
   info.max_reserve.store(1, std::memory_order_relaxed);
   info.create_time = test_start - absl::Hours(20);
 
-  info.PrepareForSampling(test_stride * 2, test_element_size);
+  info.PrepareForSampling(test_stride * 2, test_element_size,
+                          /*soo_capacity_value=*/0);
   EXPECT_EQ(info.capacity.load(), 0);
   EXPECT_EQ(info.size.load(), 0);
   EXPECT_EQ(info.num_erases.load(), 0);
@@ -120,6 +127,7 @@ TEST(HashtablezInfoTest, PrepareForSampling) {
   EXPECT_EQ(info.weight, 2 * test_stride);
   EXPECT_EQ(info.inline_element_size, test_element_size);
   EXPECT_GE(info.create_time, test_start);
+  EXPECT_EQ(info.soo_capacity, 0);
 }
 
 TEST(HashtablezInfoTest, RecordStorageChanged) {
@@ -127,7 +135,8 @@ TEST(HashtablezInfoTest, RecordStorageChanged) {
   absl::MutexLock l(&info.init_mu);
   const int64_t test_stride = 21;
   const size_t test_element_size = 19;
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/0);
   RecordStorageChangedSlow(&info, 17, 47);
   EXPECT_EQ(info.size.load(), 17);
   EXPECT_EQ(info.capacity.load(), 47);
@@ -141,7 +150,8 @@ TEST(HashtablezInfoTest, RecordInsert) {
   absl::MutexLock l(&info.init_mu);
   const int64_t test_stride = 25;
   const size_t test_element_size = 23;
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/0);
   EXPECT_EQ(info.max_probe_length.load(), 0);
   RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
   EXPECT_EQ(info.max_probe_length.load(), 6);
@@ -165,7 +175,8 @@ TEST(HashtablezInfoTest, RecordErase) {
   const size_t test_element_size = 29;
   HashtablezInfo info;
   absl::MutexLock l(&info.init_mu);
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/1);
   EXPECT_EQ(info.num_erases.load(), 0);
   EXPECT_EQ(info.size.load(), 0);
   RecordInsertSlow(&info, 0x0000FF00, 6 * kProbeLength);
@@ -174,6 +185,7 @@ TEST(HashtablezInfoTest, RecordErase) {
   EXPECT_EQ(info.size.load(), 0);
   EXPECT_EQ(info.num_erases.load(), 1);
   EXPECT_EQ(info.inline_element_size, test_element_size);
+  EXPECT_EQ(info.soo_capacity, 1);
 }
 
 TEST(HashtablezInfoTest, RecordRehash) {
@@ -181,7 +193,8 @@ TEST(HashtablezInfoTest, RecordRehash) {
   const size_t test_element_size = 31;
   HashtablezInfo info;
   absl::MutexLock l(&info.init_mu);
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/0);
   RecordInsertSlow(&info, 0x1, 0);
   RecordInsertSlow(&info, 0x2, kProbeLength);
   RecordInsertSlow(&info, 0x4, kProbeLength);
@@ -201,6 +214,7 @@ TEST(HashtablezInfoTest, RecordRehash) {
   EXPECT_EQ(info.num_erases.load(), 0);
   EXPECT_EQ(info.num_rehashes.load(), 1);
   EXPECT_EQ(info.inline_element_size, test_element_size);
+  EXPECT_EQ(info.soo_capacity, 0);
 }
 
 TEST(HashtablezInfoTest, RecordReservation) {
@@ -208,7 +222,8 @@ TEST(HashtablezInfoTest, RecordReservation) {
   absl::MutexLock l(&info.init_mu);
   const int64_t test_stride = 35;
   const size_t test_element_size = 33;
-  info.PrepareForSampling(test_stride, test_element_size);
+  info.PrepareForSampling(test_stride, test_element_size,
+                          /*soo_capacity_value=*/0);
   RecordReservationSlow(&info, 3);
   EXPECT_EQ(info.max_reserve.load(), 3);
 
@@ -229,7 +244,8 @@ TEST(HashtablezSamplerTest, SmallSampleParameter) {
 
   for (int i = 0; i < 1000; ++i) {
     SamplingState next_sample = {0, 0};
-    HashtablezInfo* sample = SampleSlow(next_sample, test_element_size);
+    HashtablezInfo* sample = SampleSlow(next_sample, test_element_size,
+                                        /*soo_capacity=*/0);
     EXPECT_GT(next_sample.next_sample, 0);
     EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride);
     EXPECT_NE(sample, nullptr);
@@ -244,7 +260,8 @@ TEST(HashtablezSamplerTest, LargeSampleParameter) {
 
   for (int i = 0; i < 1000; ++i) {
     SamplingState next_sample = {0, 0};
-    HashtablezInfo* sample = SampleSlow(next_sample, test_element_size);
+    HashtablezInfo* sample = SampleSlow(next_sample, test_element_size,
+                                        /*soo_capacity=*/0);
     EXPECT_GT(next_sample.next_sample, 0);
     EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride);
     EXPECT_NE(sample, nullptr);
@@ -260,7 +277,8 @@ TEST(HashtablezSamplerTest, Sample) {
   int64_t total = 0;
   double sample_rate = 0.0;
   for (int i = 0; i < 1000000; ++i) {
-    HashtablezInfoHandle h = Sample(test_element_size);
+    HashtablezInfoHandle h = Sample(test_element_size,
+                                    /*soo_capacity=*/0);
     ++total;
     if (h.IsSampled()) {
       ++num_sampled;
@@ -275,7 +293,8 @@ TEST(HashtablezSamplerTest, Handle) {
   auto& sampler = GlobalHashtablezSampler();
   const int64_t test_stride = 41;
   const size_t test_element_size = 39;
-  HashtablezInfoHandle h(sampler.Register(test_stride, test_element_size));
+  HashtablezInfoHandle h(sampler.Register(test_stride, test_element_size,
+                                          /*soo_capacity=*/0));
   auto* info = HashtablezInfoHandlePeer::GetInfo(&h);
   info->hashes_bitwise_and.store(0x12345678, std::memory_order_relaxed);
 
@@ -358,11 +377,13 @@ TEST(HashtablezSamplerTest, MultiThreaded) {
       std::vector<HashtablezInfo*> infoz;
       while (!stop.HasBeenNotified()) {
         if (infoz.empty()) {
-          infoz.push_back(sampler.Register(sampling_stride, elt_size));
+          infoz.push_back(sampler.Register(sampling_stride, elt_size,
+                                           /*soo_capacity=*/0));
         }
         switch (std::uniform_int_distribution<>(0, 2)(gen)) {
           case 0: {
-            infoz.push_back(sampler.Register(sampling_stride, elt_size));
+            infoz.push_back(sampler.Register(sampling_stride, elt_size,
+                                             /*soo_capacity=*/0));
             break;
           }
           case 1: {