1 | /* |
2 | * Copyright 2017-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <cstddef> |
20 | #include <cstring> |
21 | #include <limits> |
22 | #include <memory> |
23 | #include <ostream> |
24 | #include <vector> |
25 | |
26 | #include <folly/Demangle.h> |
27 | #include <folly/Function.h> |
28 | #include <folly/container/detail/F14Policy.h> |
29 | #include <folly/container/detail/F14Table.h> |
30 | |
31 | namespace folly { |
32 | namespace f14 { |
33 | |
34 | struct Histo { |
35 | std::vector<std::size_t> const& data; |
36 | }; |
37 | |
38 | std::ostream& operator<<(std::ostream& xo, Histo const& histo) { |
39 | xo << "[" ; |
40 | size_t sum = 0; |
41 | for (auto v : histo.data) { |
42 | sum += v; |
43 | } |
44 | size_t partial = 0; |
45 | for (size_t i = 0; i < histo.data.size(); ++i) { |
46 | if (i > 0) { |
47 | xo << ", " ; |
48 | } |
49 | partial += histo.data[i]; |
50 | if (histo.data[i] > 0) { |
51 | xo << i << ": " << histo.data[i] << " (" |
52 | << (static_cast<double>(partial) * 100.0 / sum) << "%)" ; |
53 | } |
54 | } |
55 | xo << "]" ; |
56 | return xo; |
57 | } |
58 | |
59 | void accumulate( |
60 | std::vector<std::size_t>& a, |
61 | std::vector<std::size_t> const& d) { |
62 | if (a.size() < d.size()) { |
63 | a.resize(d.size()); |
64 | } |
65 | for (std::size_t i = 0; i < d.size(); ++i) { |
66 | a[i] += d[i]; |
67 | } |
68 | } |
69 | |
70 | double expectedProbe(std::vector<std::size_t> const& probeLengths) { |
71 | std::size_t sum = 0; |
72 | std::size_t count = 0; |
73 | for (std::size_t i = 1; i < probeLengths.size(); ++i) { |
74 | sum += i * probeLengths[i]; |
75 | count += probeLengths[i]; |
76 | } |
77 | return static_cast<double>(sum) / static_cast<double>(count); |
78 | } |
79 | |
80 | // Returns i such that probeLengths elements 0 to i (inclusive) account |
81 | // for at least 99% of the samples. |
82 | std::size_t p99Probe(std::vector<std::size_t> const& probeLengths) { |
83 | std::size_t count = 0; |
84 | for (std::size_t i = 1; i < probeLengths.size(); ++i) { |
85 | count += probeLengths[i]; |
86 | } |
87 | std::size_t rv = probeLengths.size(); |
88 | std::size_t suffix = 0; |
89 | while ((suffix + probeLengths[rv - 1]) * 100 <= count) { |
90 | --rv; |
91 | } |
92 | return rv; |
93 | } |
94 | |
95 | struct MoveOnlyTestInt { |
96 | int x; |
97 | bool destroyed{false}; |
98 | |
99 | MoveOnlyTestInt() noexcept : x(0) {} |
100 | /* implicit */ MoveOnlyTestInt(int x0) : x(x0) {} |
101 | MoveOnlyTestInt(MoveOnlyTestInt&& rhs) noexcept : x(rhs.x) {} |
102 | MoveOnlyTestInt(MoveOnlyTestInt const&) = delete; |
103 | MoveOnlyTestInt& operator=(MoveOnlyTestInt&& rhs) noexcept { |
104 | x = rhs.x; |
105 | destroyed = rhs.destroyed; |
106 | return *this; |
107 | } |
108 | MoveOnlyTestInt& operator=(MoveOnlyTestInt const&) = delete; |
109 | |
110 | ~MoveOnlyTestInt() { |
111 | destroyed = true; |
112 | } |
113 | |
114 | bool operator==(MoveOnlyTestInt const& rhs) const { |
115 | return x == rhs.x && destroyed == rhs.destroyed; |
116 | } |
117 | bool operator!=(MoveOnlyTestInt const& rhs) const { |
118 | return !(*this == rhs); |
119 | } |
120 | }; |
121 | |
122 | // Tracked is implicitly constructible across tags |
123 | struct Counts { |
124 | uint64_t copyConstruct{0}; |
125 | uint64_t moveConstruct{0}; |
126 | uint64_t copyConvert{0}; |
127 | uint64_t moveConvert{0}; |
128 | uint64_t copyAssign{0}; |
129 | uint64_t moveAssign{0}; |
130 | uint64_t defaultConstruct{0}; |
131 | uint64_t destroyed{0}; |
132 | |
133 | explicit Counts( |
134 | uint64_t copConstr = 0, |
135 | uint64_t movConstr = 0, |
136 | uint64_t copConv = 0, |
137 | uint64_t movConv = 0, |
138 | uint64_t copAssign = 0, |
139 | uint64_t movAssign = 0, |
140 | uint64_t def = 0, |
141 | uint64_t destr = 0) |
142 | : copyConstruct{copConstr}, |
143 | moveConstruct{movConstr}, |
144 | copyConvert{copConv}, |
145 | moveConvert{movConv}, |
146 | copyAssign{copAssign}, |
147 | moveAssign{movAssign}, |
148 | defaultConstruct{def}, |
149 | destroyed{destr} {} |
150 | |
151 | int64_t liveCount() const { |
152 | return copyConstruct + moveConstruct + copyConvert + moveConvert + |
153 | defaultConstruct - destroyed; |
154 | } |
155 | |
156 | // dist ignores destroyed count |
157 | uint64_t dist(Counts const& rhs) const { |
158 | auto d = [](uint64_t x, uint64_t y) { return (x - y) * (x - y); }; |
159 | return d(copyConstruct, rhs.copyConstruct) + |
160 | d(moveConstruct, rhs.moveConstruct) + d(copyConvert, rhs.copyConvert) + |
161 | d(moveConvert, rhs.moveConvert) + d(copyAssign, rhs.copyAssign) + |
162 | d(moveAssign, rhs.moveAssign) + |
163 | d(defaultConstruct, rhs.defaultConstruct); |
164 | } |
165 | |
166 | bool operator==(Counts const& rhs) const { |
167 | return dist(rhs) == 0 && destroyed == rhs.destroyed; |
168 | } |
169 | bool operator!=(Counts const& rhs) const { |
170 | return !(*this == rhs); |
171 | } |
172 | }; |
173 | |
174 | std::ostream& operator<<(std::ostream& xo, Counts const& counts) { |
175 | xo << "[" ; |
176 | std::string glue = "" ; |
177 | if (counts.copyConstruct > 0) { |
178 | xo << glue << counts.copyConstruct << " copy" ; |
179 | glue = ", " ; |
180 | } |
181 | if (counts.moveConstruct > 0) { |
182 | xo << glue << counts.moveConstruct << " move" ; |
183 | glue = ", " ; |
184 | } |
185 | if (counts.copyConvert > 0) { |
186 | xo << glue << counts.copyConvert << " copy convert" ; |
187 | glue = ", " ; |
188 | } |
189 | if (counts.moveConvert > 0) { |
190 | xo << glue << counts.moveConvert << " move convert" ; |
191 | glue = ", " ; |
192 | } |
193 | if (counts.copyAssign > 0) { |
194 | xo << glue << counts.copyAssign << " copy assign" ; |
195 | glue = ", " ; |
196 | } |
197 | if (counts.moveAssign > 0) { |
198 | xo << glue << counts.moveAssign << " move assign" ; |
199 | glue = ", " ; |
200 | } |
201 | if (counts.defaultConstruct > 0) { |
202 | xo << glue << counts.defaultConstruct << " default construct" ; |
203 | glue = ", " ; |
204 | } |
205 | if (counts.destroyed > 0) { |
206 | xo << glue << counts.destroyed << " destroyed" ; |
207 | glue = ", " ; |
208 | } |
209 | xo << "]" ; |
210 | return xo; |
211 | } |
212 | |
213 | thread_local Counts sumCounts{}; |
214 | |
215 | template <int Tag> |
216 | struct Tracked { |
217 | static_assert(Tag <= 5, "Need to extend Tracked<Tag> in F14TestUtil.h" ); |
218 | |
219 | static thread_local Counts counts; |
220 | |
221 | uint64_t val_; |
222 | |
223 | Tracked() : val_{0} { |
224 | sumCounts.defaultConstruct++; |
225 | counts.defaultConstruct++; |
226 | } |
227 | /* implicit */ Tracked(uint64_t const& val) : val_{val} { |
228 | sumCounts.copyConvert++; |
229 | counts.copyConvert++; |
230 | } |
231 | /* implicit */ Tracked(uint64_t&& val) : val_{val} { |
232 | sumCounts.moveConvert++; |
233 | counts.moveConvert++; |
234 | } |
235 | Tracked(Tracked const& rhs) : val_{rhs.val_} { |
236 | sumCounts.copyConstruct++; |
237 | counts.copyConstruct++; |
238 | } |
239 | Tracked(Tracked&& rhs) noexcept : val_{rhs.val_} { |
240 | sumCounts.moveConstruct++; |
241 | counts.moveConstruct++; |
242 | } |
243 | Tracked& operator=(Tracked const& rhs) { |
244 | val_ = rhs.val_; |
245 | sumCounts.copyAssign++; |
246 | counts.copyAssign++; |
247 | return *this; |
248 | } |
249 | Tracked& operator=(Tracked&& rhs) noexcept { |
250 | val_ = rhs.val_; |
251 | sumCounts.moveAssign++; |
252 | counts.moveAssign++; |
253 | return *this; |
254 | } |
255 | |
256 | template <int T> |
257 | /* implicit */ Tracked(Tracked<T> const& rhs) : val_{rhs.val_} { |
258 | sumCounts.copyConvert++; |
259 | counts.copyConvert++; |
260 | } |
261 | |
262 | template <int T> |
263 | /* implicit */ Tracked(Tracked<T>&& rhs) : val_{rhs.val_} { |
264 | sumCounts.moveConvert++; |
265 | counts.moveConvert++; |
266 | } |
267 | |
268 | ~Tracked() { |
269 | sumCounts.destroyed++; |
270 | counts.destroyed++; |
271 | } |
272 | |
273 | bool operator==(Tracked const& rhs) const { |
274 | return val_ == rhs.val_; |
275 | } |
276 | bool operator!=(Tracked const& rhs) const { |
277 | return !(*this == rhs); |
278 | } |
279 | }; |
280 | |
281 | template <int Tag> |
282 | struct TransparentTrackedHash { |
283 | using is_transparent = void; |
284 | |
285 | size_t operator()(Tracked<Tag> const& tracked) const { |
286 | return tracked.val_ ^ Tag; |
287 | } |
288 | size_t operator()(uint64_t v) const { |
289 | return v ^ Tag; |
290 | } |
291 | }; |
292 | |
293 | template <int Tag> |
294 | struct TransparentTrackedEqual { |
295 | using is_transparent = void; |
296 | |
297 | uint64_t unwrap(Tracked<Tag> const& v) const { |
298 | return v.val_; |
299 | } |
300 | uint64_t unwrap(uint64_t v) const { |
301 | return v; |
302 | } |
303 | |
304 | template <typename A, typename B> |
305 | bool operator()(A const& lhs, B const& rhs) const { |
306 | return unwrap(lhs) == unwrap(rhs); |
307 | } |
308 | }; |
309 | |
310 | template <> |
311 | thread_local Counts Tracked<0>::counts{}; |
312 | template <> |
313 | thread_local Counts Tracked<1>::counts{}; |
314 | template <> |
315 | thread_local Counts Tracked<2>::counts{}; |
316 | template <> |
317 | thread_local Counts Tracked<3>::counts{}; |
318 | template <> |
319 | thread_local Counts Tracked<4>::counts{}; |
320 | template <> |
321 | thread_local Counts Tracked<5>::counts{}; |
322 | |
323 | thread_local size_t testAllocatedMemorySize{0}; |
324 | thread_local size_t testAllocatedBlockCount{0}; |
325 | thread_local size_t testAllocationCount{0}; |
326 | thread_local size_t testAllocationMaxCount{ |
327 | std::numeric_limits<std::size_t>::max()}; |
328 | |
329 | inline void limitTestAllocations(std::size_t allocationsBeforeException = 0) { |
330 | testAllocationMaxCount = testAllocationCount + allocationsBeforeException; |
331 | } |
332 | |
333 | inline void unlimitTestAllocations() { |
334 | testAllocationMaxCount = std::numeric_limits<std::size_t>::max(); |
335 | } |
336 | |
337 | inline void resetTracking() { |
338 | sumCounts = Counts{}; |
339 | Tracked<0>::counts = Counts{}; |
340 | Tracked<1>::counts = Counts{}; |
341 | Tracked<2>::counts = Counts{}; |
342 | Tracked<3>::counts = Counts{}; |
343 | Tracked<4>::counts = Counts{}; |
344 | Tracked<5>::counts = Counts{}; |
345 | testAllocatedMemorySize = 0; |
346 | testAllocatedBlockCount = 0; |
347 | testAllocationCount = 0; |
348 | testAllocationMaxCount = std::numeric_limits<std::size_t>::max(); |
349 | } |
350 | |
351 | template <class T> |
352 | class SwapTrackingAlloc { |
353 | public: |
354 | using Alloc = std::allocator<T>; |
355 | using value_type = typename Alloc::value_type; |
356 | |
357 | using pointer = typename Alloc::pointer; |
358 | using const_pointer = typename Alloc::const_pointer; |
359 | using reference = typename Alloc::reference; |
360 | using const_reference = typename Alloc::const_reference; |
361 | using size_type = typename Alloc::size_type; |
362 | |
363 | using propagate_on_container_swap = std::true_type; |
364 | using propagate_on_container_copy_assignment = std::true_type; |
365 | using propagate_on_container_move_assignment = std::true_type; |
366 | |
367 | SwapTrackingAlloc() {} |
368 | |
369 | template <class U> |
370 | SwapTrackingAlloc(SwapTrackingAlloc<U> const& other) noexcept |
371 | : a_(other.a_), t_(other.t_) {} |
372 | |
373 | template <class U> |
374 | SwapTrackingAlloc& operator=(SwapTrackingAlloc<U> const& other) noexcept { |
375 | a_ = other.a_; |
376 | t_ = other.t_; |
377 | return *this; |
378 | } |
379 | |
380 | template <class U> |
381 | SwapTrackingAlloc(SwapTrackingAlloc<U>&& other) noexcept |
382 | : a_(std::move(other.a_)), t_(std::move(other.t_)) {} |
383 | |
384 | template <class U> |
385 | SwapTrackingAlloc& operator=(SwapTrackingAlloc<U>&& other) noexcept { |
386 | a_ = std::move(other.a_); |
387 | t_ = std::move(other.t_); |
388 | return *this; |
389 | } |
390 | |
391 | T* allocate(size_t n) { |
392 | if (testAllocationCount >= testAllocationMaxCount) { |
393 | throw std::bad_alloc(); |
394 | } |
395 | ++testAllocationCount; |
396 | testAllocatedMemorySize += n * sizeof(T); |
397 | ++testAllocatedBlockCount; |
398 | std::size_t = |
399 | std::max<std::size_t>(1, sizeof(std::size_t) / sizeof(T)); |
400 | T* p = a_.allocate(extra + n); |
401 | std::memcpy(p, &n, sizeof(std::size_t)); |
402 | return p + extra; |
403 | } |
404 | void deallocate(T* p, size_t n) { |
405 | testAllocatedMemorySize -= n * sizeof(T); |
406 | --testAllocatedBlockCount; |
407 | std::size_t = |
408 | std::max<std::size_t>(1, sizeof(std::size_t) / sizeof(T)); |
409 | std::size_t check; |
410 | std::memcpy(&check, p - extra, sizeof(std::size_t)); |
411 | FOLLY_SAFE_CHECK(check == n, "" ); |
412 | a_.deallocate(p - extra, n + extra); |
413 | } |
414 | |
415 | private: |
416 | std::allocator<T> a_; |
417 | folly::f14::Tracked<0> t_; |
418 | |
419 | template <class U> |
420 | friend class SwapTrackingAlloc; |
421 | }; |
422 | |
423 | template <class T> |
424 | void swap(SwapTrackingAlloc<T>&, SwapTrackingAlloc<T>&) { |
425 | // For argument dependent lookup: |
426 | // This function will be called if the custom swap functions of F14 containers |
427 | // are used. Otherwise, std::swap() will do 1 move construct and 2 move |
428 | // assigns which will get tracked by t_. |
429 | } |
430 | |
431 | template <class T1, class T2> |
432 | bool operator==(SwapTrackingAlloc<T1> const&, SwapTrackingAlloc<T2> const&) { |
433 | return true; |
434 | } |
435 | |
436 | template <class T1, class T2> |
437 | bool operator!=(SwapTrackingAlloc<T1> const&, SwapTrackingAlloc<T2> const&) { |
438 | return false; |
439 | } |
440 | |
441 | std::ostream& operator<<(std::ostream& xo, F14TableStats const& stats) { |
442 | using f14::Histo; |
443 | |
444 | xo << "{ " << std::endl; |
445 | xo << " policy: " |
446 | #if FOLLY_HAS_RTTI |
447 | << folly::demangle(stats.policy) |
448 | #else |
449 | << "unknown (RTTI not availabe)" |
450 | #endif |
451 | << std::endl; |
452 | xo << " size: " << stats.size << std::endl; |
453 | xo << " valueSize: " << stats.valueSize << std::endl; |
454 | xo << " bucketCount: " << stats.bucketCount << std::endl; |
455 | xo << " chunkCount: " << stats.chunkCount << std::endl; |
456 | xo << " chunkOccupancyHisto" << Histo{stats.chunkOccupancyHisto} |
457 | << std::endl; |
458 | xo << " chunkOutboundOverflowHisto" |
459 | << Histo{stats.chunkOutboundOverflowHisto} << std::endl; |
460 | xo << " chunkHostedOverflowHisto" << Histo{stats.chunkHostedOverflowHisto} |
461 | << std::endl; |
462 | xo << " keyProbeLengthHisto" << Histo{stats.keyProbeLengthHisto} |
463 | << std::endl; |
464 | xo << " missProbeLengthHisto" << Histo{stats.missProbeLengthHisto} |
465 | << std::endl; |
466 | xo << " totalBytes: " << stats.totalBytes << std::endl; |
467 | xo << " valueBytes: " << (stats.size * stats.valueSize) << std::endl; |
468 | xo << " overheadBytes: " << stats.overheadBytes << std::endl; |
469 | if (stats.size > 0) { |
470 | xo << " overheadBytesPerKey: " |
471 | << (static_cast<double>(stats.overheadBytes) / |
472 | static_cast<double>(stats.size)) |
473 | << std::endl; |
474 | } |
475 | xo << "}" ; |
476 | return xo; |
477 | } |
478 | |
479 | template <class T> |
480 | class GenericAlloc { |
481 | public: |
482 | using value_type = T; |
483 | |
484 | using pointer = T*; |
485 | using const_pointer = T const*; |
486 | using reference = T&; |
487 | using const_reference = T const&; |
488 | using size_type = std::size_t; |
489 | |
490 | using propagate_on_container_swap = std::true_type; |
491 | using propagate_on_container_copy_assignment = std::true_type; |
492 | using propagate_on_container_move_assignment = std::true_type; |
493 | |
494 | using AllocBytesFunc = folly::Function<void*(std::size_t)>; |
495 | using DeallocBytesFunc = folly::Function<void(void*, std::size_t)>; |
496 | |
497 | GenericAlloc() = delete; |
498 | |
499 | template <typename A, typename D> |
500 | GenericAlloc(A&& alloc, D&& dealloc) |
501 | : alloc_{std::make_shared<AllocBytesFunc>(std::forward<A>(alloc))}, |
502 | dealloc_{std::make_shared<DeallocBytesFunc>(std::forward<D>(dealloc))} { |
503 | } |
504 | |
505 | template <class U> |
506 | GenericAlloc(GenericAlloc<U> const& other) noexcept |
507 | : alloc_{other.alloc_}, dealloc_{other.dealloc_} {} |
508 | |
509 | template <class U> |
510 | GenericAlloc& operator=(GenericAlloc<U> const& other) noexcept { |
511 | alloc_ = other.alloc_; |
512 | dealloc_ = other.dealloc_; |
513 | return *this; |
514 | } |
515 | |
516 | template <class U> |
517 | GenericAlloc(GenericAlloc<U>&& other) noexcept |
518 | : alloc_(std::move(other.alloc_)), dealloc_(std::move(other.dealloc_)) {} |
519 | |
520 | template <class U> |
521 | GenericAlloc& operator=(GenericAlloc<U>&& other) noexcept { |
522 | alloc_ = std::move(other.alloc_); |
523 | dealloc_ = std::move(other.dealloc_); |
524 | return *this; |
525 | } |
526 | |
527 | T* allocate(size_t n) { |
528 | return static_cast<T*>((*alloc_)(n * sizeof(T))); |
529 | } |
530 | void deallocate(T* p, size_t n) { |
531 | (*dealloc_)(static_cast<void*>(p), n * sizeof(T)); |
532 | } |
533 | |
534 | template <typename U> |
535 | bool operator==(GenericAlloc<U> const& rhs) const { |
536 | return alloc_ == rhs.alloc_; |
537 | } |
538 | |
539 | template <typename U> |
540 | bool operator!=(GenericAlloc<U> const& rhs) const { |
541 | return !(*this == rhs); |
542 | } |
543 | |
544 | private: |
545 | std::shared_ptr<AllocBytesFunc> alloc_; |
546 | std::shared_ptr<DeallocBytesFunc> dealloc_; |
547 | |
548 | template <class U> |
549 | friend class GenericAlloc; |
550 | }; |
551 | |
552 | template <typename T> |
553 | class GenericEqual { |
554 | public: |
555 | using EqualFunc = folly::Function<bool(T const&, T const&)>; |
556 | |
557 | GenericEqual() = delete; |
558 | |
559 | template <typename E> |
560 | GenericEqual(E&& equal) |
561 | : equal_{std::make_shared<EqualFunc>(std::forward<E>(equal))} {} |
562 | |
563 | bool operator()(T const& lhs, T const& rhs) const { |
564 | return (*equal_)(lhs, rhs); |
565 | } |
566 | |
567 | private: |
568 | std::shared_ptr<EqualFunc> equal_; |
569 | }; |
570 | |
571 | template <typename T> |
572 | class GenericHasher { |
573 | public: |
574 | using HasherFunc = folly::Function<std::size_t(T const&)>; |
575 | |
576 | GenericHasher() = delete; |
577 | |
578 | template <typename H> |
579 | GenericHasher(H&& hasher) |
580 | : hasher_{std::make_shared<HasherFunc>(std::forward<H>(hasher))} {} |
581 | |
582 | std::size_t operator()(T const& val) const { |
583 | return (*hasher_)(val); |
584 | } |
585 | |
586 | private: |
587 | std::shared_ptr<HasherFunc> hasher_; |
588 | }; |
589 | |
590 | } // namespace f14 |
591 | } // namespace folly |
592 | |
593 | namespace std { |
594 | template <> |
595 | struct hash<folly::f14::MoveOnlyTestInt> { |
596 | std::size_t operator()(folly::f14::MoveOnlyTestInt const& val) const { |
597 | return val.x; |
598 | } |
599 | }; |
600 | |
601 | template <int Tag> |
602 | struct hash<folly::f14::Tracked<Tag>> { |
603 | size_t operator()(folly::f14::Tracked<Tag> const& tracked) const { |
604 | return tracked.val_ ^ Tag; |
605 | } |
606 | }; |
607 | |
608 | } // namespace std |
609 | |