GNUnet  0.10.x
ibf_sim.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2013 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32 
33 #define MAX_IBF_DECODE 16
34 
35 /* report average over how many rounds? */
36 #define ROUNDS 100000
37 
38 /* enable one of the three below */
39 // simple fix
40 #define FIX1 0
41 // possibly slightly better fix for large IBF_DECODE values
42 #define FIX2 1
43 
44 // SIGCOMM algorithm
45 #define STRATA 0
46 
47 // print each value?
48 #define VERBOSE 0
49 // avoid assembly? (ASM is about 50% faster)
50 #define SLOW 0
51 
52 int
53 main(int argc, char **argv)
54 {
55  unsigned int round;
56  unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
57  unsigned int i;
58  int j;
59  unsigned int r;
60  unsigned int ret;
61  unsigned long long total;
62  unsigned int want;
63  double predict;
64 
65  srandom(time(NULL));
66  total = 0;
67  want = atoi(argv[1]);
68  for (round = 0; round < ROUNDS; round++)
69  {
70  memset(buckets, 0, sizeof(buckets));
71  for (i = 0; i < want; i++)
72  {
73  /* FIXME: might want to use 'better' PRNG to avoid
74  PRNG-induced biases */
75  r = random();
76  if (0 == r)
77  continue;
78 #if SLOW
79  for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++)
80  ;
81 #else
82  /* use assembly / gcc */
83  j = __builtin_ffs(r) - 1;
84 #endif
85  buckets[j]++;
86  }
87  ret = 0;
88  predict = 0.0;
89  for (j = 31; j >= 0; j--)
90  {
91 #if FIX1
92  /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
93  get 990/1000 elements on average over 1 million runs; key
94  idea being to stop short of the 'last' possible IBF as
95  otherwise a "lowball" per-chance would unduely influence the
96  result */
97  if ((j > 0) &&
98  (buckets[j - 1] > MAX_IBF_DECODE))
99  {
100  ret *= (1 << (j + 1));
101  break;
102  }
103 #endif
104 #if FIX2
105  /* another improvement: don't just always cut off the last one,
106  but rather try to predict based on all previous values where
107  that "last" one is; additional prediction can only really
108  work if MAX_IBF_DECODE is sufficiently high */
109  if ((j > 0) &&
110  ((buckets[j - 1] > MAX_IBF_DECODE) ||
111  (predict > MAX_IBF_DECODE)))
112  {
113  ret *= (1 << (j + 1));
114  break;
115  }
116 #endif
117 #if STRATA
118  /* original algorithm, for 1000 elements with IBF-DECODE 8,
119  I get 920/1000 elements on average over 1 million runs */
120  if (buckets[j] > MAX_IBF_DECODE)
121  {
122  ret *= (1 << (j + 1));
123  break;
124  }
125 #endif
126  ret += buckets[j];
127  predict = (buckets[j] + 2.0 * predict) / 2.0;
128  }
129 #if VERBOSE
130  fprintf(stderr, "%u ", ret);
131 #endif
132  total += ret;
133  }
134  fprintf(stderr, "\n");
135  fprintf(stdout, "average %llu\n", total / ROUNDS);
136  return 0;
137 }
138 
139 /* TODO: should calculate stddev of the results to also be able to
140  say something about the stability of the results, outside of
141  large-scale averages -- gaining 8% precision at the expense of
142  50% additional variance might not be worth it... */
#define ROUNDS
Definition: ibf_sim.c:36
static int ret
Final status code.
Definition: gnunet-arm.c:89
#define MAX_IBF_DECODE
Definition: ibf_sim.c:33
int main(int argc, char **argv)
Definition: ibf_sim.c:53