Ton

1
/* 
2
    This file is part of TON Blockchain source code.
3

4
    TON Blockchain is free software; you can redistribute it and/or
5
    modify it under the terms of the GNU General Public License
6
    as published by the Free Software Foundation; either version 2
7
    of the License, or (at your option) any later version.
8

9
    TON Blockchain is distributed in the hope that it will be useful,
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
    GNU General Public License for more details.
13

14
    You should have received a copy of the GNU General Public License
15
    along with TON Blockchain.  If not, see <http://www.gnu.org/licenses/>.
16

17
    In addition, as a special exception, the copyright holders give permission 
18
    to link the code of portions of this program with the OpenSSL library. 
19
    You must obey the GNU General Public License in all respects for all 
20
    of the code used other than OpenSSL. If you modify file(s) with this 
21
    exception, you may extend this exception to your version of the file(s), 
22
    but you are not obligated to do so. If you do not wish to do so, delete this 
23
    exception statement from your version. If you delete this exception statement 
24
    from all source files in the program, then also delete it here.
25

26
    Copyright 2020 Telegram Systems LLP
27
*/
28
#include <iostream>
29
#include "td/utils/Random.h"
30
#include "td/utils/misc.h"
31
#include "block/block.h"
32
#include <getopt.h>
33

34
const int MAX_N = 1000, MAX_K = 100, DEFAULT_K = 7;
35

36
int verbosity;
37
int N, K = DEFAULT_K;
38
long long iterations = 1000000;
39

40
td::uint64 TWL, WL[MAX_N];
41
double W[MAX_N], CW[MAX_N + 1], RW[MAX_N], R0;
42
int A[MAX_N], C[MAX_N];
43
long long TC;
44

45
void gen_vset() {
46
  static std::pair<double, double> H[MAX_N];
47
  double total_wt = 1.;
48
  int hc = 0;
49
  for (int i = 0; i < K; i++) {
50
    CHECK(total_wt > 0);
51
    double inv_wt = 1. / total_wt;
52
    R0 += inv_wt;  // advanced mtcarlo stats
53
    for (int j = 0; j < i; j++) {
54
      RW[A[j]] -= inv_wt;  // advanced mtcarlo stats
55
    }
56
    // double p = drand48() * total_wt;
57
    double p = (double)td::Random::fast_uint64() * total_wt / (1. * (1LL << 32) * (1LL << 32));
58
    for (int h = 0; h < hc; h++) {
59
      if (p < H[h].first) {
60
        break;
61
      }
62
      p += H[h].second;
63
    }
64
    int a = -1, b = N, c;
65
    while (b - a > 1) {
66
      c = ((a + b) >> 1);
67
      if (CW[c] <= p) {
68
        a = c;
69
      } else {
70
        b = c;
71
      }
72
    }
73
    CHECK(a >= 0 && a < N);
74
    CHECK(total_wt >= W[a]);
75
    total_wt -= W[a];
76
    double x = CW[a];
77
    c = hc++;
78
    while (c > 0 && H[c - 1].first > x) {
79
      H[c] = H[c - 1];
80
      --c;
81
    }
82
    H[c].first = x;
83
    H[c].second = W[a];
84
    A[i] = a;
85
    C[a]++;  // simple mtcarlo stats
86
    // std::cout << a << ' ';
87
  }
88
  // std::cout << std::endl;
89
  ++TC;  // simple mtcarlo stats
90
}
91

92
void mt_carlo() {
93
  for (int i = 0; i < N; i++) {
94
    C[i] = 0;
95
    RW[i] = 0.;
96
  }
97
  TC = 0;
98
  R0 = 0.;
99
  std::cout << "running " << iterations << " steps of Monte Carlo simulation\n";
100
  for (long long it = 0; it < iterations; ++it) {
101
    gen_vset();
102
  }
103
  for (int i = 0; i < N; i++) {
104
    RW[i] = W[i] * (RW[i] + R0) / (double)iterations;
105
  }
106
}
107

108
double B[MAX_N];
109

110
void compute_bad_approx() {
111
  static double S[MAX_K + 1];
112
  S[0] = 1.;
113
  for (int i = 1; i <= K; i++) {
114
    S[i] = 0.;
115
  }
116
  for (int i = 0; i < N; i++) {
117
    double p = W[i];
118
    for (int j = K; j > 0; j--) {
119
      S[j] += p * S[j - 1];
120
    }
121
  }
122
  double Sk = S[K];
123
  for (int i = 0; i < N; i++) {
124
    double t = 1., p = W[i];
125
    for (int j = 1; j <= K; j++) {
126
      t = S[j] - p * t;
127
    }
128
    B[i] = 1. - t / Sk;
129
  }
130
}
131

132
void usage() {
133
  std::cout
134
      << "usage: test-weight-distr [-k<shard-val-num>][-m<iterations>][-s<rand-seed>]\nReads the set of validator "
135
         "weights from stdin and emulates validator shard distribution load\n\t-k <shard-val-num>\tSets the number of "
136
         "validators generating each shard\n\t-m <iterations>\tMonte Carlo simulation steps\n";
137
  std::exit(2);
138
}
139

140
int main(int argc, char* const argv[]) {
141
  int i;
142
  int new_verbosity_level = VERBOSITY_NAME(INFO);
143
  // long seed = 0;
144
  while ((i = getopt(argc, argv, "hs:k:m:v:")) != -1) {
145
    switch (i) {
146
      case 'k':
147
        K = td::to_integer<int>(td::Slice(optarg));
148
        CHECK(K > 0 && K <= 100);
149
        break;
150
      case 'm':
151
        iterations = td::to_integer<long long>(td::Slice(optarg));
152
        CHECK(iterations > 0);
153
        break;
154
      case 's':
155
        // seed = td::to_integer<long>(td::Slice(optarg));
156
        // srand48(seed);
157
        break;
158
      case 'v':
159
        new_verbosity_level = VERBOSITY_NAME(FATAL) + (verbosity = td::to_integer<int>(td::Slice(optarg)));
160
        break;
161
      case 'h':
162
        usage();
163
        std::exit(2);
164
      default:
165
        usage();
166
        std::exit(2);
167
    }
168
  }
169
  SET_VERBOSITY_LEVEL(new_verbosity_level);
170
  for (N = 0; N < MAX_N && (std::cin >> WL[N]); N++) {
171
    CHECK(WL[N] > 0);
172
    TWL += WL[N];
173
  }
174
  CHECK(std::cin.eof());
175
  CHECK(N > 0 && TWL > 0 && N <= MAX_N);
176
  K = std::min(K, N);
177
  CHECK(K > 0 && K <= MAX_K);
178
  double acc = 0.;
179
  for (i = 0; i < N; i++) {
180
    CW[i] = acc;
181
    acc += W[i] = (double)WL[i] / (double)TWL;
182
    std::cout << "#" << i << ":\t" << W[i] << std::endl;
183
  }
184
  compute_bad_approx();
185
  mt_carlo();
186
  std::cout << "result of Monte Carlo simulation (" << iterations << " iterations):" << std::endl;
187
  std::cout << "idx\tweight\tmtcarlo1\tmtcarlo2\tapprox\n";
188
  for (i = 0; i < N; i++) {
189
    std::cout << "#" << i << ":\t" << W[i] << '\t' << (double)C[i] / (double)iterations << '\t' << RW[i] << '\t' << B[i]
190
              << std::endl;
191
  }
192
  // same computation, but using a MtCarloComputeShare object
193
  block::MtCarloComputeShare MT(K, N, W, iterations);
194
  std::cout << "-----------------------\n";
195
  for (i = 0; i < N; i++) {
196
    std::cout << '#' << i << ":\t" << MT.weight(i) << '\t' << MT.share(i) << std::endl;
197
  }
198
  return 0;
199
}
200