aboutsummaryrefslogtreecommitdiffhomepage
path: root/absl/base/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/base/internal')
-rw-r--r--absl/base/internal/periodic_sampler.cc50
-rw-r--r--absl/base/internal/periodic_sampler.h193
-rw-r--r--absl/base/internal/periodic_sampler_benchmark.cc70
-rw-r--r--absl/base/internal/periodic_sampler_test.cc175
4 files changed, 488 insertions, 0 deletions
diff --git a/absl/base/internal/periodic_sampler.cc b/absl/base/internal/periodic_sampler.cc
new file mode 100644
index 0000000..439745d
--- /dev/null
+++ b/absl/base/internal/periodic_sampler.cc
@@ -0,0 +1,50 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/base/internal/periodic_sampler.h"
+
+#include <atomic>
+
+#include "absl/base/internal/exponential_biased.h"
+
+namespace absl {
+namespace base_internal {
+
+int64_t PeriodicSamplerBase::GetExponentialBiased(int period) noexcept {
+ return rng_.Get(period);
+}
+
+bool PeriodicSamplerBase::SubtleConfirmSample() noexcept {
+ int current_period = period();
+
+ // Deal with period case 0 (always off) and 1 (always on)
+ if (ABSL_PREDICT_FALSE(current_period < 2)) {
+ stride_ = 0;
+ return current_period == 1;
+ }
+
+ // Check if this is the first call to Sample()
+ if (ABSL_PREDICT_FALSE(stride_ == 1)) {
+ stride_ = -1 - GetExponentialBiased(current_period);
+ if (stride_ < -1) {
+ ++stride_;
+ return false;
+ }
+ }
+ stride_ = -1 - GetExponentialBiased(current_period);
+ return true;
+}
+
+} // namespace base_internal
+} // namespace absl
diff --git a/absl/base/internal/periodic_sampler.h b/absl/base/internal/periodic_sampler.h
new file mode 100644
index 0000000..2c0600f
--- /dev/null
+++ b/absl/base/internal/periodic_sampler.h
@@ -0,0 +1,193 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
+#define ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
+
+#include <stdint.h>
+
+#include <atomic>
+
+#include "absl/base/internal/exponential_biased.h"
+#include "absl/base/optimization.h"
+
+namespace absl {
+namespace base_internal {
+
+// PeriodicSamplerBase provides the basic period sampler implementation.
+//
+// This is the base class for the templated PeriodicSampler class, which holds
+// a global std::atomic value identified by a user defined tag, such that
+// each specific PeriodSampler implementation holds its own global period.
+//
+// PeriodicSamplerBase is thread-compatible except where stated otherwise.
+class PeriodicSamplerBase {
+ public:
+ // PeriodicSamplerBase is trivial / copyable / movable / destructible.
+ PeriodicSamplerBase() = default;
+ PeriodicSamplerBase(PeriodicSamplerBase&&) = default;
+ PeriodicSamplerBase(const PeriodicSamplerBase&) = default;
+
+ // Returns true roughly once every `period` calls. This is established by a
+ // randomly picked `stride` that is counted down on each call to `Sample`.
+ // This stride is picked such that the probability of `Sample()` returning
+ // true is 1 in `period`.
+ inline bool Sample() noexcept;
+
+ // The below methods are intended for optimized use cases where the
+ // size of the inlined fast path code is highly important. Applications
+ // should use the `Sample()` method unless they have proof that their
+ // specific use case requires the optimizations offered by these methods.
+ //
+ // An example of such a use case is SwissTable sampling. All sampling checks
+ // are in inlined SwissTable methods, and the number of call sites is huge.
+ // In this case, the inlined code size added to each translation unit calling
+ // SwissTable methods is non-trivial.
+ //
+ // The `SubtleMaybeSample()` function spuriously returns true even if the
+ // function should not be sampled, applications MUST match each call to
+ // 'SubtleMaybeSample()' returning true with a `SubtleConfirmSample()` call,
+ // and use the result of the latter as the sampling decision.
+ // In other words: the code should logically be equivalent to:
+ //
+ // if (SubtleMaybeSample() && SubtleConfirmSample()) {
+ // // Sample this call
+ // }
+ //
+ // In the 'inline-size' optimized case, the `SubtleConfirmSample()` call can
+ // be placed out of line, for example, the typical use case looks as follows:
+ //
+ // // --- frobber.h -----------
+ // void FrobberSampled();
+ //
+ // inline void FrobberImpl() {
+ // // ...
+ // }
+ //
+ // inline void Frobber() {
+ // if (ABSL_PREDICT_FALSE(sampler.SubtleMaybeSample())) {
+ // FrobberSampled();
+ // } else {
+ // FrobberImpl();
+ // }
+ // }
+ //
+ // // --- frobber.cc -----------
+ // void FrobberSampled() {
+ // if (!sampler.SubtleConfirmSample())) {
+ // // Spurious false positive
+ // FrobberImpl();
+ // return;
+ // }
+ //
+ // // Sampled execution
+ // // ...
+ // }
+ inline bool SubtleMaybeSample() noexcept;
+ bool SubtleConfirmSample() noexcept;
+
+ protected:
+ // We explicitly don't use a virtual destructor as this class is never
+ // virtually destroyed, and it keeps the class trivial, which avoids TLS
+ // prologue and epilogue code for our TLS instances.
+ ~PeriodicSamplerBase() = default;
+
+ // Returns the next stride for our sampler.
+ // This function is virtual for testing purposes only.
+ virtual int64_t GetExponentialBiased(int period) noexcept;
+
+ private:
+ // Returns the current period of this sampler. Thread-safe.
+ virtual int period() const noexcept = 0;
+
+ int64_t stride_ = 0;
+ ExponentialBiased rng_;
+};
+
+inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept {
+ // We explicitly count up and not down, as the compiler does not generate
+ // ideal code for counting down. See also https://gcc.godbolt.org/z/FTPDSM
+ //
+ // With `if (ABSL_PREDICT_FALSE(++stride_ < 0))`
+ // add QWORD PTR fs:sampler@tpoff+8, 1
+ // jns .L15
+ // ret
+ //
+ // With `if (ABSL_PREDICT_FALSE(--stride_ > 0))`
+ // mov rax, QWORD PTR fs:sampler@tpoff+8
+ // sub rax, 1
+ // mov QWORD PTR fs:sampler@tpoff+8, rax
+ // test rax, rax
+ // jle .L15
+ // ret
+ // add QWORD PTR fs:sampler@tpoff+8, 1
+ // jns .L15
+ // ret
+ //
+ // --stride >= 0 does work, but makes our logic slightly harder as in that
+ // case we have less convenient zero-init and over-run values.
+ if (ABSL_PREDICT_FALSE(++stride_ < 0)) {
+ return false;
+ }
+ return true;
+}
+
+inline bool PeriodicSamplerBase::Sample() noexcept {
+ return ABSL_PREDICT_FALSE(SubtleMaybeSample()) ? SubtleConfirmSample()
+ : false;
+}
+
+// PeriodicSampler is a concreted periodic sampler implementation.
+// The user provided Tag identifies the implementation, and is required to
+// isolate the global state of this instance from other instances.
+//
+// Typical use case:
+//
+// struct HashTablezTag {};
+// thread_local PeriodicSampler sampler;
+//
+// void HashTableSamplingLogic(...) {
+// if (sampler.Sample()) {
+// HashTableSlowSamplePath(...);
+// }
+// }
+//
+template <typename Tag, int default_period = 0>
+class PeriodicSampler final : public PeriodicSamplerBase {
+ public:
+ ~PeriodicSampler() = default;
+
+ int period() const noexcept final {
+ return period_.load(std::memory_order_relaxed);
+ }
+
+ // Sets the global period for this sampler. Thread-safe.
+ // Setting a period of 0 disables the sampler, i.e., every call to Sample()
+ // will return false. Setting a period of 1 puts the sampler in 'always on'
+ // mode, i.e., every call to Sample() returns true.
+ static void SetGlobalPeriod(int period) {
+ period_.store(period, std::memory_order_relaxed);
+ }
+
+ private:
+ static std::atomic<int> period_;
+};
+
+template <typename Tag, int default_period>
+std::atomic<int> PeriodicSampler<Tag, default_period>::period_(default_period);
+
+} // namespace base_internal
+} // namespace absl
+
+#endif // ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
diff --git a/absl/base/internal/periodic_sampler_benchmark.cc b/absl/base/internal/periodic_sampler_benchmark.cc
new file mode 100644
index 0000000..f87cef7
--- /dev/null
+++ b/absl/base/internal/periodic_sampler_benchmark.cc
@@ -0,0 +1,70 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "benchmark/benchmark.h"
+#include "absl/base/internal/periodic_sampler.h"
+
+namespace absl {
+namespace base_internal {
+namespace {
+
+template <typename Sampler>
+void BM_Sample(Sampler* sampler, benchmark::State& state) {
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(sampler);
+ benchmark::DoNotOptimize(sampler->Sample());
+ }
+}
+
+template <typename Sampler>
+void BM_SampleMinunumInlined(Sampler* sampler, benchmark::State& state) {
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(sampler);
+ if (ABSL_PREDICT_FALSE(sampler->SubtleMaybeSample())) {
+ benchmark::DoNotOptimize(sampler->SubtleConfirmSample());
+ }
+ }
+}
+
+void BM_PeriodicSampler_ShortSample(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_ShortSample);
+
+void BM_PeriodicSampler_LongSample(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024 * 1024> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSample);
+
+void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 1024 * 1024> sampler;
+ BM_SampleMinunumInlined(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined);
+
+void BM_PeriodicSampler_Disabled(benchmark::State& state) {
+ struct Tag {};
+ PeriodicSampler<Tag, 0> sampler;
+ BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_Disabled);
+
+} // namespace
+} // namespace base_internal
+} // namespace absl
diff --git a/absl/base/internal/periodic_sampler_test.cc b/absl/base/internal/periodic_sampler_test.cc
new file mode 100644
index 0000000..1ba6137
--- /dev/null
+++ b/absl/base/internal/periodic_sampler_test.cc
@@ -0,0 +1,175 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/base/internal/periodic_sampler.h"
+
+#include <thread> // NOLINT(build/c++11)
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/attributes.h"
+#include "absl/base/macros.h"
+
+namespace absl {
+namespace base_internal {
+namespace {
+
+using testing::Eq;
+using testing::Return;
+using testing::StrictMock;
+
+class MockPeriodicSampler : public PeriodicSamplerBase {
+ public:
+ virtual ~MockPeriodicSampler() = default;
+
+ MOCK_METHOD(int, period, (), (const, noexcept));
+ MOCK_METHOD(int64_t, GetExponentialBiased, (int), (noexcept));
+};
+
+TEST(PeriodicSamplerBaseTest, Sample) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .WillOnce(Return(1))
+ .WillOnce(Return(2))
+ .WillOnce(Return(3));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, ImmediatelySample) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .WillOnce(Return(0))
+ .WillOnce(Return(1))
+ .WillOnce(Return(2));
+
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disabled) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(0));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, AlwaysOn) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(1));
+
+ EXPECT_TRUE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disable) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).WillOnce(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16)).WillOnce(Return(2));
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(0));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Enable) {
+ StrictMock<MockPeriodicSampler> sampler;
+
+ EXPECT_CALL(sampler, period()).WillOnce(Return(0));
+ EXPECT_FALSE(sampler.Sample());
+
+ EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+ EXPECT_CALL(sampler, GetExponentialBiased(16))
+ .Times(2)
+ .WillRepeatedly(Return(2));
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_TRUE(sampler.Sample());
+
+ EXPECT_FALSE(sampler.Sample());
+ EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerTest, ConstructConstInit) {
+ struct Tag {};
+ ABSL_CONST_INIT static PeriodicSampler<Tag> sampler;
+ (void)sampler;
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod0) {
+ struct Tag {};
+ PeriodicSampler<Tag> sampler;
+ EXPECT_THAT(sampler.period(), Eq(0));
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod) {
+ struct Tag {};
+ PeriodicSampler<Tag, 100> sampler;
+ EXPECT_THAT(sampler.period(), Eq(100));
+}
+
+TEST(PeriodicSamplerTest, SetGlobalPeriod) {
+ struct Tag1 {};
+ struct Tag2 {};
+ PeriodicSampler<Tag1, 25> sampler1;
+ PeriodicSampler<Tag2, 50> sampler2;
+
+ EXPECT_THAT(sampler1.period(), Eq(25));
+ EXPECT_THAT(sampler2.period(), Eq(50));
+
+ std::thread thread([] {
+ PeriodicSampler<Tag1, 25> sampler1;
+ PeriodicSampler<Tag2, 50> sampler2;
+ EXPECT_THAT(sampler1.period(), Eq(25));
+ EXPECT_THAT(sampler2.period(), Eq(50));
+ sampler1.SetGlobalPeriod(10);
+ sampler2.SetGlobalPeriod(20);
+ });
+ thread.join();
+
+ EXPECT_THAT(sampler1.period(), Eq(10));
+ EXPECT_THAT(sampler2.period(), Eq(20));
+}
+
+} // namespace
+} // namespace base_internal
+} // namespace absl
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-19 17:12:02 +0000