1 // Copyright 2023 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 //
5 // This is a framework to measure the memory overhead of different containers.
6 // Under the hood, it works by logging allocations and frees using an allocator
7 // hook.
8 //
9 // Since the free callback does not report a size, and the allocator hooks run
10 // in the middle of allocation, the logger simply takes the simplest approach
11 // and logs out the raw data, relying on analyze_containers_memory_usage.py to
12 // turn the raw output into useful numbers.
13 //
14 // The output of consists of m (number of different key/value combinations being
15 // tested) x n (number of different map types being tested) sections:
16 //
17 // <key type 1> -> <value type 1>
18 // ===== <map type 1> =====
19 // iteration 0
20 // alloc <address 1> size <size 1>
21 // iteration 1
22 // alloc <address 2> size <size 2>
23 // free <address 1>
24 // iteration 2
25 // alloc <address 3> size <size 3>
26 // free <address 2>
27 // ...
28 // ...
29 // ...
30 // ===== <map type n>
31 // iteration 0
32 // alloc <address 1000> size <size 1000>
33 // iteration 1
34 // alloc <address 1001> size <size 1001>
35 // free <address 1000>
36 // iteration 2
37 // alloc <address 1002> size <size 1002>
38 // free <address 1001>
39 // ...
40 // ...
41 // ...
42 // <key type m> -> <value type m>
43 // ===== <map type 1> =====
44 // ...
45 // ...
46 // ===== <map type n> =====
47 //
48 // Alternate output strategies are possible, but most of them are worse/more
49 // complex, and do not eliminate the postprocessing step.
50
51 #include <array>
52 #include <atomic>
53 #include <charconv>
54 #include <limits>
55 #include <map>
56 #include <optional>
57 #include <string>
58 #include <unordered_map>
59 #include <utility>
60
61 #include "base/allocator/dispatcher/dispatcher.h"
62 #include "base/allocator/dispatcher/notification_data.h"
63 #include "base/containers/flat_map.h"
64 #include "base/logging.h"
65 #include "base/strings/safe_sprintf.h"
66 #include "base/unguessable_token.h"
67 #include "base/values.h"
68 #include "third_party/abseil-cpp/absl/container/btree_map.h"
69 #include "third_party/abseil-cpp/absl/container/flat_hash_map.h"
70 #include "third_party/abseil-cpp/absl/container/node_hash_map.h"
71
72 namespace {
73
74 std::atomic<bool> log_allocs_and_frees;
75
76 struct AllocationLogger {
77 public:
OnAllocation__anon3106819c0111::AllocationLogger78 void OnAllocation(
79 const base::allocator::dispatcher::AllocationNotificationData&
80 allocation_data) {
81 if (log_allocs_and_frees.load(std::memory_order_acquire)) {
82 char buffer[128];
83 // Assume success; ignore return value.
84 base::strings::SafeSPrintf(buffer, "alloc address %p size %d\n",
85 allocation_data.address(),
86 allocation_data.size());
87 RAW_LOG(INFO, buffer);
88 }
89 }
90
OnFree__anon3106819c0111::AllocationLogger91 void OnFree(
92 const base::allocator::dispatcher::FreeNotificationData& free_data) {
93 if (log_allocs_and_frees.load(std::memory_order_acquire)) {
94 char buffer[128];
95 // Assume success; ignore return value.
96 base::strings::SafeSPrintf(buffer, "freed address %p\n",
97 free_data.address());
98 RAW_LOG(INFO, buffer);
99 }
100 }
101
Install__anon3106819c0111::AllocationLogger102 static void Install() {
103 static AllocationLogger logger;
104 base::allocator::dispatcher::Dispatcher::GetInstance().InitializeForTesting(
105 &logger);
106 }
107 };
108
109 class ScopedLogAllocAndFree {
110 public:
ScopedLogAllocAndFree()111 ScopedLogAllocAndFree() {
112 log_allocs_and_frees.store(true, std::memory_order_release);
113 }
114
~ScopedLogAllocAndFree()115 ~ScopedLogAllocAndFree() {
116 log_allocs_and_frees.store(false, std::memory_order_release);
117 }
118 };
119
120 // Measures the memory usage for a container with type `Container` from 0 to
121 // 6857 elements, using `inserter` to insert a single element at a time.
122 // `inserter` should be a functor that takes a `Container& container` as its
123 // first parameter and a `size_t current_index` as its second parameter.
124 //
125 // Note that `inserter` can't use `base::FunctionRef` since the inserter is
126 // passed through several layers before actually being instantiated below in
127 // this function.
128 template <typename Container, typename Inserter>
MeasureOneContainer(const Inserter & inserter)129 void MeasureOneContainer(const Inserter& inserter) {
130 char buffer[128];
131
132 RAW_LOG(INFO, "iteration 0");
133 // Record any initial allocations made by an empty container.
134 std::optional<ScopedLogAllocAndFree> base_size_logger;
135 base_size_logger.emplace();
136 Container c;
137 base_size_logger.reset();
138 // As a hack, also log out sizeof(c) since the initial base size of the
139 // container should be counted too. The exact placeholder used for the address
140 // (in this case "(stack)") isn't important as long as it will not have a
141 // corresponding free line logged for it.
142 base::strings::SafeSPrintf(buffer, "alloc address (stack) size %d",
143 sizeof(c));
144 RAW_LOG(INFO, buffer);
145
146 // Swisstables resizes the backing store around 6858 elements.
147 for (size_t i = 1; i <= 6857; ++i) {
148 base::strings::SafeSPrintf(buffer, "iteration %d", i);
149 RAW_LOG(INFO, buffer);
150 inserter(c, i);
151 }
152 }
153
154 // Measures the memory usage for all the container types under test. `inserter`
155 // is used to insert a single element at a time into the tested container.
156 template <typename K, typename V, typename Inserter>
Measure(const Inserter & inserter)157 void Measure(const Inserter& inserter) {
158 using Hasher = std::conditional_t<std::is_same_v<base::UnguessableToken, K>,
159 base::UnguessableTokenHash, std::hash<K>>;
160
161 RAW_LOG(INFO, "===== base::flat_map =====");
162 MeasureOneContainer<base::flat_map<K, V>>(inserter);
163 RAW_LOG(INFO, "===== std::map =====");
164 MeasureOneContainer<std::map<K, V>>(inserter);
165 RAW_LOG(INFO, "===== std::unordered_map =====");
166 MeasureOneContainer<std::unordered_map<K, V, Hasher>>(inserter);
167 RAW_LOG(INFO, "===== absl::btree_map =====");
168 MeasureOneContainer<absl::btree_map<K, V>>(inserter);
169 RAW_LOG(INFO, "===== absl::flat_hash_map =====");
170 MeasureOneContainer<absl::flat_hash_map<K, V, Hasher>>(inserter);
171 RAW_LOG(INFO, "===== absl::node_hash_map =====");
172 MeasureOneContainer<absl::node_hash_map<K, V, Hasher>>(inserter);
173 }
174
175 } // namespace
176
main()177 int main() {
178 AllocationLogger::Install();
179
180 RAW_LOG(INFO, "int -> int");
181 Measure<int, int>([](auto& container, size_t i) {
182 ScopedLogAllocAndFree scoped_logging;
183 container.insert({i, 0});
184 });
185 RAW_LOG(INFO, "int -> void*");
186 Measure<int, void*>([](auto& container, size_t i) {
187 ScopedLogAllocAndFree scoped_logging;
188 container.insert({i, nullptr});
189 });
190 RAW_LOG(INFO, "int -> std::string");
191 Measure<int, std::string>([](auto& container, size_t i) {
192 ScopedLogAllocAndFree scoped_logging;
193 container.insert({i, ""});
194 });
195 RAW_LOG(INFO, "size_t -> int");
196 Measure<size_t, int>([](auto& container, size_t i) {
197 ScopedLogAllocAndFree scoped_logging;
198 container.insert({i, 0});
199 });
200 RAW_LOG(INFO, "size_t -> void*");
201 Measure<size_t, void*>([](auto& container, size_t i) {
202 ScopedLogAllocAndFree scoped_logging;
203 container.insert({i, nullptr});
204 });
205 RAW_LOG(INFO, "size_t -> std::string");
206 Measure<size_t, std::string>([](auto& container, size_t i) {
207 ScopedLogAllocAndFree scoped_logging;
208 container.insert({i, ""});
209 });
210 RAW_LOG(INFO, "std::string -> std::string");
211 Measure<std::string, std::string>([](auto& container, size_t i) {
212 std::string key;
213 key.resize(std::numeric_limits<size_t>::digits10 + 1);
214 auto result = std::to_chars(&key.front(), &key.back(), i);
215 key.resize(result.ptr - &key.front());
216 ScopedLogAllocAndFree scoped_logging;
217 container.insert({key, ""});
218 });
219 RAW_LOG(INFO, "base::UnguessableToken -> void*");
220 Measure<base::UnguessableToken, void*>([](auto& container, size_t i) {
221 auto token = base::UnguessableToken::Create();
222 ScopedLogAllocAndFree scoped_logging;
223 container.insert({token, nullptr});
224 });
225 RAW_LOG(INFO, "base::UnguessableToken -> base::Value");
226 Measure<base::UnguessableToken, base::Value>([](auto& container, size_t i) {
227 auto token = base::UnguessableToken::Create();
228 base::Value value;
229 ScopedLogAllocAndFree scoped_logging;
230 container.insert({token, std::move(value)});
231 });
232 RAW_LOG(INFO, "base::UnguessableToken -> std::array<std::string, 4>");
233 Measure<base::UnguessableToken, std::array<std::string, 4>>(
234 [](auto& container, size_t i) {
235 auto token = base::UnguessableToken::Create();
236 ScopedLogAllocAndFree scoped_logging;
237 container.insert({token, {}});
238 });
239 RAW_LOG(INFO, "base::UnguessableToken -> std::array<std::string, 8>");
240 Measure<base::UnguessableToken, std::array<std::string, 8>>(
241 [](auto& container, size_t i) {
242 auto token = base::UnguessableToken::Create();
243 ScopedLogAllocAndFree scoped_logging;
244 container.insert({token, {}});
245 });
246 RAW_LOG(INFO, "base::UnguessableToken -> std::array<std::string, 16>");
247 Measure<base::UnguessableToken, std::array<std::string, 16>>(
248 [](auto& container, size_t i) {
249 auto token = base::UnguessableToken::Create();
250 ScopedLogAllocAndFree scoped_logging;
251 container.insert({token, {}});
252 });
253
254 return 0;
255 }
256