Bitcoin Core  22.99.0
P2P Digital Currency
minisketchwrapper.cpp
Go to the documentation of this file.
1 // Copyright (c) 2021 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
6 
7 #include <logging.h>
8 #include <util/time.h>
9 
10 #include <minisketch.h>
11 
12 #include <algorithm>
13 #include <cstddef>
14 #include <cstdint>
15 #include <optional>
16 #include <utility>
17 #include <vector>
18 
19 namespace node {
20 namespace {
21 
22 static constexpr uint32_t BITS = 32;
23 
24 uint32_t FindBestImplementation()
25 {
26  std::optional<std::pair<int64_t, uint32_t>> best;
27 
28  uint32_t max_impl = Minisketch::MaxImplementation();
29  for (uint32_t impl = 0; impl <= max_impl; ++impl) {
30  std::vector<int64_t> benches;
31  uint64_t offset = 0;
32  /* Run a little benchmark with capacity 32, adding 184 entries, and decoding 11 of them once. */
33  for (int b = 0; b < 11; ++b) {
34  if (!Minisketch::ImplementationSupported(BITS, impl)) break;
35  Minisketch sketch(BITS, impl, 32);
36  auto start = GetTimeMicros();
37  for (uint64_t e = 0; e < 100; ++e) {
38  sketch.Add(e*1337 + b*13337 + offset);
39  }
40  for (uint64_t e = 0; e < 84; ++e) {
41  sketch.Add(e*1337 + b*13337 + offset);
42  }
43  offset += (*sketch.Decode(32))[0];
44  auto stop = GetTimeMicros();
45  benches.push_back(stop - start);
46  }
47  /* Remember which implementation has the best median benchmark time. */
48  if (!benches.empty()) {
49  std::sort(benches.begin(), benches.end());
50  if (!best || best->first > benches[5]) {
51  best = std::make_pair(benches[5], impl);
52  }
53  }
54  }
55  assert(best.has_value());
56  LogPrintf("Using Minisketch implementation number %i\n", best->second);
57  return best->second;
58 }
59 
60 uint32_t Minisketch32Implementation()
61 {
62  // Fast compute-once idiom.
63  static uint32_t best = FindBestImplementation();
64  return best;
65 }
66 
67 } // namespace
68 
69 
70 Minisketch MakeMinisketch32(size_t capacity)
71 {
72  return Minisketch(BITS, Minisketch32Implementation(), capacity);
73 }
74 
75 Minisketch MakeMinisketch32FP(size_t max_elements, uint32_t fpbits)
76 {
77  return Minisketch::CreateFP(BITS, Minisketch32Implementation(), max_elements, fpbits);
78 }
79 } // namespace node
minisketchwrapper.h
assert
assert(!tx.IsCoinBase())
minisketch.h
node::MakeMinisketch32
Minisketch MakeMinisketch32(size_t capacity)
Wrapper around Minisketch::Minisketch(32, implementation, capacity).
Definition: minisketchwrapper.cpp:70
time.h
LogPrintf
#define LogPrintf(...)
Definition: logging.h:187
stop
static RPCHelpMan stop()
Definition: server.cpp:161
node::MakeMinisketch32FP
Minisketch MakeMinisketch32FP(size_t max_elements, uint32_t fpbits)
Wrapper around Minisketch::CreateFP.
Definition: minisketchwrapper.cpp:75
node
Definition: init.h:22
GetTimeMicros
int64_t GetTimeMicros()
Returns the system time (not mockable)
Definition: time.cpp:122