minisketchwrapper.cpp raw

   1  // Copyright (c) 2021-present 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 <util/log.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      LogInfo("Using Minisketch implementation number %i", 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
  80