Introduce base::FlatSet
A memory-dense alternative to std::set.
The driving use-case is pid tracking (see aosp/1180622) but
it seems to work well in most cases where the set is small.
See comments and links in flat_set.h for design and
performance characteristics.
Bug: 145398368
Test: perfetto_unittests + perfetto_benchmarks
Change-Id: Ie3e57e98228559b06bba62333f9f70fbab485681
diff --git a/Android.bp b/Android.bp
index b722a95..9c26c44 100644
--- a/Android.bp
+++ b/Android.bp
@@ -4080,6 +4080,7 @@
name: "perfetto_src_base_unittests",
srcs: [
"src/base/circular_queue_unittest.cc",
+ "src/base/flat_set_unittest.cc",
"src/base/metatrace_unittest.cc",
"src/base/no_destructor_unittest.cc",
"src/base/optional_unittest.cc",
diff --git a/BUILD b/BUILD
index 4d81a97..60a1501 100644
--- a/BUILD
+++ b/BUILD
@@ -214,6 +214,7 @@
"include/perfetto/ext/base/container_annotations.h",
"include/perfetto/ext/base/event_fd.h",
"include/perfetto/ext/base/file_utils.h",
+ "include/perfetto/ext/base/flat_set.h",
"include/perfetto/ext/base/hash.h",
"include/perfetto/ext/base/lookup_set.h",
"include/perfetto/ext/base/metatrace.h",
diff --git a/gn/perfetto_benchmarks.gni b/gn/perfetto_benchmarks.gni
index f711222..4b0f331 100644
--- a/gn/perfetto_benchmarks.gni
+++ b/gn/perfetto_benchmarks.gni
@@ -16,6 +16,7 @@
perfetto_benchmarks_targets = [
"gn:default_deps",
+ "src/base:benchmarks",
"src/traced/probes/ftrace:benchmarks",
"src/trace_processor/db:benchmarks",
"src/trace_processor/tables:benchmarks",
diff --git a/include/perfetto/ext/base/BUILD.gn b/include/perfetto/ext/base/BUILD.gn
index db82b08..7d76c84 100644
--- a/include/perfetto/ext/base/BUILD.gn
+++ b/include/perfetto/ext/base/BUILD.gn
@@ -20,6 +20,7 @@
"container_annotations.h",
"event_fd.h",
"file_utils.h",
+ "flat_set.h",
"hash.h",
"lookup_set.h",
"metatrace.h",
diff --git a/include/perfetto/ext/base/flat_set.h b/include/perfetto/ext/base/flat_set.h
new file mode 100644
index 0000000..578f20f
--- /dev/null
+++ b/include/perfetto/ext/base/flat_set.h
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * 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
+ *
+ * http://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 INCLUDE_PERFETTO_EXT_BASE_FLAT_SET_H_
+#define INCLUDE_PERFETTO_EXT_BASE_FLAT_SET_H_
+
+#include <algorithm>
+#include <vector>
+
+// A vector-based set::set-like container.
+// It's more cache friendly than std::*set and performs for cases where:
+// 1. A high number of dupes is expected (e.g. pid tracking in ftrace).
+// 2. The working set is small (hundreds of elements).
+
+// Performance characteristics (for uniformly random insertion order):
+// - For smaller insertions (up to ~500), it outperforms both std::set<int> and
+// std::unordered_set<int> by ~3x.
+// - Up until 4k insertions, it is always faster than std::set<int>.
+// - unordered_set<int> is faster with more than 2k insertions.
+// - unordered_set, however, it's less memory efficient and has more caveats
+// (see chromium's base/containers/README.md).
+//
+// See flat_set_benchmark.cc and the charts in go/perfetto-int-set-benchmark.
+
+namespace perfetto {
+namespace base {
+
+template <typename T>
+class FlatSet {
+ public:
+ using value_type = T;
+ using const_pointer = const T*;
+ using iterator = typename std::vector<T>::iterator;
+ using const_iterator = typename std::vector<T>::const_iterator;
+
+ FlatSet() = default;
+
+ // Mainly for tests. Deliberately not marked as "expicit".
+ FlatSet(std::initializer_list<T> initial) : entries_(initial) {
+ std::sort(entries_.begin(), entries_.end());
+ }
+
+ const_iterator find(T value) const {
+ auto entries_end = entries_.end();
+ auto it = std::lower_bound(entries_.begin(), entries_end, value);
+ return (it != entries_end && *it == value) ? it : entries_end;
+ }
+
+ size_t count(T value) const { return find(value) == entries_.end() ? 0 : 1; }
+
+ void insert(T value) {
+ auto entries_end = entries_.end();
+ auto it = std::lower_bound(entries_.begin(), entries_end, value);
+ if (it != entries_end && *it == value)
+ return;
+ // If the value is not found |it| is either end() or the next item strictly
+ // greater than |value|. In both cases we want to insert just before that.
+ entries_.insert(it, std::move(value));
+ }
+
+ size_t erase(T value) {
+ auto it = find(value);
+ if (it == entries_.end())
+ return 0;
+ entries_.erase(it);
+ return 1;
+ }
+
+ void clear() { entries_.clear(); }
+
+ bool empty() const { return entries_.empty(); }
+ void reserve(size_t n) { entries_.reserve(n); }
+ size_t size() const { return entries_.size(); }
+ const_iterator begin() const { return entries_.begin(); }
+ const_iterator end() const { return entries_.end(); }
+
+ private:
+ std::vector<T> entries_;
+};
+
+} // namespace base
+} // namespace perfetto
+
+#endif // INCLUDE_PERFETTO_EXT_BASE_FLAT_SET_H_
diff --git a/src/base/BUILD.gn b/src/base/BUILD.gn
index 0e7a0d0..b6c7343 100644
--- a/src/base/BUILD.gn
+++ b/src/base/BUILD.gn
@@ -122,6 +122,7 @@
sources = [
"circular_queue_unittest.cc",
+ "flat_set_unittest.cc",
"no_destructor_unittest.cc",
"optional_unittest.cc",
"paged_memory_unittest.cc",
@@ -154,3 +155,17 @@
}
}
}
+
+if (enable_perfetto_benchmarks) {
+ source_set("benchmarks") {
+ testonly = true
+ deps = [
+ ":base",
+ "../../gn:benchmark",
+ "../../gn:default_deps",
+ ]
+ sources = [
+ "flat_set_benchmark.cc",
+ ]
+ }
+}
diff --git a/src/base/flat_set_benchmark.cc b/src/base/flat_set_benchmark.cc
new file mode 100644
index 0000000..12e5565
--- /dev/null
+++ b/src/base/flat_set_benchmark.cc
@@ -0,0 +1,64 @@
+// Copyright (C) 2019 The Android Open Source Project
+//
+// 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
+//
+// http://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 <random>
+#include <set>
+#include <unordered_set>
+
+#include <benchmark/benchmark.h>
+
+#include "perfetto/ext/base/flat_set.h"
+
+namespace {
+
+std::vector<int> GetRandData(int num_pids) {
+ std::vector<int> rnd_data;
+ std::minstd_rand0 rng(0);
+ static constexpr int kDistinctValues = 100;
+ for (int i = 0; i < num_pids; i++)
+ rnd_data.push_back(static_cast<int>(rng()) % kDistinctValues);
+ return rnd_data;
+}
+
+bool IsBenchmarkFunctionalOnly() {
+ return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
+}
+
+void BenchmarkArgs(benchmark::internal::Benchmark* b) {
+ if (IsBenchmarkFunctionalOnly()) {
+ b->Arg(64);
+ } else {
+ b->RangeMultiplier(2)->Range(64, 4096);
+ }
+}
+
+} // namespace
+
+template <typename SetType>
+static void BM_SetInsert(benchmark::State& state) {
+ std::vector<int> rnd_data = GetRandData(state.range(0));
+ for (auto _ : state) {
+ SetType iset;
+ for (const int val : rnd_data)
+ iset.insert(val);
+ benchmark::DoNotOptimize(iset);
+ benchmark::DoNotOptimize(iset.begin());
+ benchmark::ClobberMemory();
+ }
+}
+
+using perfetto::base::FlatSet;
+BENCHMARK_TEMPLATE(BM_SetInsert, FlatSet<int>)->Apply(BenchmarkArgs);
+BENCHMARK_TEMPLATE(BM_SetInsert, std::set<int>)->Apply(BenchmarkArgs);
+BENCHMARK_TEMPLATE(BM_SetInsert, std::unordered_set<int>)->Apply(BenchmarkArgs);
diff --git a/src/base/flat_set_unittest.cc b/src/base/flat_set_unittest.cc
new file mode 100644
index 0000000..22a51d3
--- /dev/null
+++ b/src/base/flat_set_unittest.cc
@@ -0,0 +1,106 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * 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
+ *
+ * http://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 "perfetto/ext/base/flat_set.h"
+
+#include <random>
+#include <set>
+
+#include "test/gtest_and_gmock.h"
+
+using testing::ElementsAreArray;
+using testing::UnorderedElementsAre;
+
+namespace perfetto {
+namespace base {
+namespace {
+
+TEST(FlatSetTest, InsertAndLookup) {
+ FlatSet<long> flat_set;
+ for (int i = 0; i < 3; i++) {
+ EXPECT_TRUE(flat_set.empty());
+ EXPECT_EQ(flat_set.size(), 0u);
+ EXPECT_EQ(flat_set.begin(), flat_set.end());
+ EXPECT_FALSE(flat_set.count(42));
+ EXPECT_EQ(flat_set.find(42), flat_set.end());
+ EXPECT_EQ(flat_set.find(42), flat_set.begin());
+
+ flat_set.insert(1);
+ EXPECT_FALSE(flat_set.empty());
+ EXPECT_EQ(flat_set.size(), 1u);
+ {
+ auto it = flat_set.find(1);
+ EXPECT_EQ(it, flat_set.begin());
+ EXPECT_NE(it, flat_set.end());
+ EXPECT_EQ(*it, 1);
+ }
+
+ EXPECT_TRUE(flat_set.count(1));
+ EXPECT_NE(flat_set.begin(), flat_set.end());
+ EXPECT_EQ(std::distance(flat_set.begin(), flat_set.end()), 1);
+
+ flat_set.insert(1);
+ EXPECT_EQ(flat_set.size(), 1u);
+ EXPECT_TRUE(flat_set.count(1));
+ EXPECT_FALSE(flat_set.count(0));
+ EXPECT_FALSE(flat_set.count(-1));
+
+ EXPECT_TRUE(flat_set.erase(1));
+ EXPECT_FALSE(flat_set.count(1));
+ EXPECT_EQ(flat_set.size(), 0u);
+
+ flat_set.insert(7);
+ flat_set.insert(-4);
+ flat_set.insert(11);
+ flat_set.insert(-13);
+ EXPECT_TRUE(flat_set.count(7));
+ EXPECT_TRUE(flat_set.count(-4));
+ EXPECT_TRUE(flat_set.count(11));
+ EXPECT_TRUE(flat_set.count(-13));
+ EXPECT_THAT(flat_set, UnorderedElementsAre(-13, -4, 7, 11));
+
+ EXPECT_TRUE(flat_set.erase(-4));
+ EXPECT_TRUE(flat_set.erase(7));
+ EXPECT_THAT(flat_set, UnorderedElementsAre(-13, 11));
+
+ flat_set.clear();
+ }
+}
+
+TEST(FlatSetTest, GoldenTest) {
+ FlatSet<int> flat_set;
+ std::set<int> gold_set;
+ static std::minstd_rand rng(0);
+ std::uniform_int_distribution<int> int_dist(-200, 200);
+
+ for (int i = 0; i < 10000; i++) {
+ const int val = int_dist(rng);
+ if (i % 3) {
+ flat_set.insert(val);
+ gold_set.insert(val);
+ } else {
+ flat_set.erase(val);
+ gold_set.erase(val);
+ }
+ ASSERT_EQ(flat_set.size(), gold_set.size());
+ }
+
+ EXPECT_THAT(flat_set, ElementsAreArray(gold_set));
+}
+
+} // namespace
+} // namespace base
+} // namespace perfetto