1  /**********************************************************************
  2   * Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko      *
  3   * Distributed under the MIT software license, see the accompanying   *
  4   * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
  5   **********************************************************************/
  6  
  7  #include "../include/minisketch.h"
  8  #include <string.h>
  9  #include <memory>
 10  #include <vector>
 11  #include <chrono>
 12  #include <random>
 13  #include <set>
 14  #include <algorithm>
 15  
 16  int main(int argc, char** argv) {
 17      if (argc < 1 || argc > 4) {
 18          printf("Usage: %s [syndromes=150] [errors=syndromes] [iters=10]\n", argv[0]);
 19          return 1;
 20      }
 21      int syndromes = argc > 1 ? strtoul(argv[1], NULL, 10) : 150;
 22      int errors = argc > 2 ? strtoul(argv[2], NULL, 10) : syndromes;
 23      int iters = argc > 3 ? strtoul(argv[3], NULL, 10) : 10;
 24      if (syndromes < 0 || syndromes > 1000000) {
 25          printf("Number of syndromes (%i) out of range 0..1000000\n", syndromes);
 26          return 1;
 27      }
 28      if (errors < 0) {
 29          printf("Number of errors (%i) is negative(%i)\n", errors, syndromes);
 30          return 1;
 31      }
 32      if (iters < 0 || iters > 1000000000) {
 33          printf("Number of iterations (%i) out of range 0..1000000000\n", iters);
 34          return 1;
 35      }
 36      uint32_t max_impl = minisketch_implementation_max();
 37      for (int bits = 2; bits <= 64; ++bits) {
 38          if (errors > pow(2.0, bits - 1)) continue;
 39          if (!minisketch_bits_supported(bits)) continue;
 40          printf("recover[ms]\t% 3i\t", bits);
 41          for (uint32_t impl = 0; impl <= max_impl; ++impl) {
 42              std::vector<minisketch*> states;
 43              std::vector<uint64_t> roots(2 * syndromes);
 44              std::random_device rng;
 45              std::uniform_int_distribution<uint64_t> dist(1, (uint64_t(1) << bits) - 1);
 46              states.resize(iters);
 47              std::vector<double> benches;
 48              benches.reserve(iters);
 49              for (int i = 0; i < iters; ++i) {
 50                  states[i] = minisketch_create(bits, impl, syndromes);
 51                  if (!states[i]) break;
 52                  std::set<uint64_t> done;
 53                  for (int j = 0; j < errors; ++j) {
 54                      uint64_t r;
 55                      do {
 56                          r = dist(rng);
 57                      } while (done.count(r));
 58                      done.insert(r);
 59                      minisketch_add_uint64(states[i], r);
 60                  }
 61              }
 62              if (!states[0]) {
 63                  printf("         -\t");
 64              } else {
 65                  for (auto& state : states) {
 66                      auto start = std::chrono::steady_clock::now();
 67                      minisketch_decode(state, 2 * syndromes, roots.data());
 68                      auto stop = std::chrono::steady_clock::now();
 69                      std::chrono::duration<double> dur(stop - start);
 70                      benches.push_back(dur.count());
 71                  }
 72                  std::sort(benches.begin(), benches.end());
 73                  printf("% 10.5f\t", benches[0] * 1000.0);
 74              }
 75              for (auto& state : states) {
 76                  minisketch_destroy(state);
 77              }
 78          }
 79          printf("\n");
 80          printf("create[ns]\t% 3i\t", bits);
 81          for (uint32_t impl = 0; impl <= max_impl; ++impl) {
 82              std::vector<minisketch*> states;
 83              std::random_device rng;
 84              std::uniform_int_distribution<uint64_t> dist;
 85              std::vector<uint64_t> data;
 86              data.resize(errors * 10);
 87              states.resize(iters);
 88              std::vector<double> benches;
 89              benches.reserve(iters);
 90              for (int i = 0; i < iters; ++i) {
 91                  states[i] = minisketch_create(bits, impl, syndromes);
 92              }
 93              for (size_t i = 0; i < data.size(); ++i) {
 94                  data[i] = dist(rng);
 95              }
 96              if (!states[0]) {
 97                  printf("         -\t");
 98              } else {
 99                  for (auto& state : states) {
100                      auto start = std::chrono::steady_clock::now();
101                      for (auto val : data) {
102                          minisketch_add_uint64(state, val);
103                      }
104                      auto stop = std::chrono::steady_clock::now();
105                      std::chrono::duration<double> dur(stop - start);
106                      benches.push_back(dur.count());
107                  }
108                  std::sort(benches.begin(), benches.end());
109                  printf("% 10.5f\t", benches[0] * 1000000000.0 / data.size() / syndromes);
110              }
111              for (auto& state : states) {
112                  minisketch_destroy(state);
113              }
114          }
115          printf("\n");
116      }
117      return 0;
118  }