src/set/ibf_sim.c

   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
  19 /**
  20  * @file set/ibf_sim.c
  21  * @brief implementation of simulation for invertible bloom filter
  22  * @author Florian Dold
  23  *
  24  * This code was used for some internal experiments, it is not
  25  * build or shipped as part of the GNUnet system.
  26  */
  27 #include <stdlib.h>
  28 #include <stdio.h>
  29 #include <string.h>
  30
  31 #define MAX_IBF_DECODE 16
  32
  33 /* report average over how many rounds? */
  34 #define ROUNDS 100000
  35
  36 /* enable one of the three below */
  37 // simple fix
  38 #define FIX1 0
  39 // possibly slightly better fix for large IBF_DECODE values
  40 #define FIX2 1
  41
  42 // SIGCOMM algorithm
  43 #define STRATA 0
  44
  45 // print each value?
  46 #define VERBOSE 0
  47 // avoid assembly? (ASM is about 50% faster)
  48 #define SLOW 0
  49
  50 int
  51 main(int argc, char **argv)
  52 {
  53   unsigned int round;
  54   unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
  55   unsigned int i;
  56   int j;
  57   unsigned int r;
  58   unsigned int ret;
  59   unsigned long long total;
  60   unsigned int want;
  61   double predict;
  62
  63   srandom (time (NULL));
  64   total = 0;
  65   want = atoi (argv[1]);
  66   for (round=0;round<ROUNDS;round++)
  67   {
  68     memset (buckets, 0, sizeof (buckets));
  69     for (i=0;i<want;i++)
  70     {
  71       /* FIXME: might want to use 'better' PRNG to avoid
  72          PRNG-induced biases */
  73       r = random ();
  74       if (0 == r)
  75         continue;
  76 #if SLOW
  77       for (j=0;(j < 31) && (0 == (r & (1 << j)));j++) ;
  78 #else
  79       /* use assembly / gcc */
  80       j = __builtin_ffs (r) - 1;
  81 #endif
  82       buckets[j]++;
  83     }
  84     ret = 0;
  85     predict = 0.0;
  86     for (j=31;j >= 0; j--)
  87     {
  88 #if FIX1
  89       /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
  90          get 990/1000 elements on average over 1 million runs; key
  91          idea being to stop short of the 'last' possible IBF as
  92          otherwise a "lowball" per-chance would unduely influence the
  93          result */
  94       if ( (j > 0) &&
  95            (buckets[j - 1] > MAX_IBF_DECODE) )
  96       {
  97         ret *= (1 << (j + 1));
  98         break;
  99       }
 100 #endif
 101 #if FIX2
 102       /* another improvement: don't just always cut off the last one,
 103          but rather try to predict based on all previous values where
 104          that "last" one is; additional prediction can only really
 105          work if MAX_IBF_DECODE is sufficiently high */
 106       if (  (j > 0) &&
 107             ( (buckets[j - 1] > MAX_IBF_DECODE) ||
 108               (predict > MAX_IBF_DECODE) ) )
 109       {
 110         ret *= (1 << (j + 1));
 111         break;
 112       }
 113 #endif
 114 #if STRATA
 115       /* original algorithm, for 1000 elements with IBF-DECODE 8,
 116          I get 920/1000 elements on average over 1 million runs */
 117       if (buckets[j] > MAX_IBF_DECODE)
 118         {
 119           ret *= (1 << (j+1));
 120           break;
 121         }
 122 #endif
 123       ret += buckets[j];
 124       predict = (buckets[j] + 2.0 * predict) / 2.0;
 125     }
 126 #if VERBOSE
 127     fprintf (stderr, "%u ", ret);
 128 #endif
 129     total += ret;
 130   }
 131   fprintf (stderr, "\n");
 132   fprintf (stdout, "average %llu\n", total / ROUNDS);
 133   return 0;
 134 }
 135
 136 /* TODO: should calculate stddev of the results to also be able to
 137    say something about the stability of the results, outside of
 138    large-scale averages -- gaining 8% precision at the expense of
 139    50% additional variance might not be worth it... */