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  
 5  #include <node/minisketchwrapper.h>
 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<SteadyClock::duration, uint32_t>> best;
27  
28      uint32_t max_impl = Minisketch::MaxImplementation();
29      for (uint32_t impl = 0; impl <= max_impl; ++impl) {
30          std::vector<SteadyClock::duration> 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 = SteadyClock::now();
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 = SteadyClock::now();
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