ibf_sim.c File Reference

#include "platform.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

Include dependency graph for ibf_sim.c:

Go to the source code of this file.

Macros
#define	MAX_IBF_DECODE   16
#define	ROUNDS   100000
#define	FIX1   0
#define	FIX2   1
#define	STRATA   0
#define	VERBOSE   0
#define	SLOW   0

Functions
int	main (int argc, char **argv)

Macro Definition Documentation

MAX_IBF_DECODE

#define MAX_IBF_DECODE   16

Definition at line 34 of file ibf_sim.c.

ROUNDS

#define ROUNDS   100000

Definition at line 37 of file ibf_sim.c.

FIX1

#define FIX1   0

Definition at line 41 of file ibf_sim.c.

FIX2

#define FIX2   1

Definition at line 43 of file ibf_sim.c.

STRATA

#define STRATA   0

Definition at line 46 of file ibf_sim.c.

VERBOSE

#define VERBOSE   0

Definition at line 49 of file ibf_sim.c.

SLOW

#define SLOW   0

Definition at line 51 of file ibf_sim.c.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 54 of file ibf_sim.c.

{
  unsigned int round;
  unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
  unsigned int i;
  int j;
  unsigned int r;
  unsigned int ret;
  unsigned long long total;
  unsigned int want;
  double predict;
 
  srandom (time (NULL));
  total = 0;
  want = atoi (argv[1]);
  for (round = 0; round < ROUNDS; round++)
  {
    memset (buckets, 0, sizeof(buckets));
    for (i = 0; i < want; i++)
    {
      /* FIXME: might want to use 'better' PRNG to avoid
         PRNG-induced biases */
      r = random ();
      if (0 == r)
        continue;
#if SLOW
      for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++)
        ;
#else
      /* use assembly / gcc */
      j = __builtin_ffs (r) - 1;
#endif
      buckets[j]++;
    }
    ret = 0;
    predict = 0.0;
    for (j = 31; j >= 0; j--)
    {
#if FIX1
      /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
         get 990/1000 elements on average over 1 million runs; key
         idea being to stop short of the 'last' possible IBF as
         otherwise a "lowball" per-chance would unduely influence the
         result */if ((j > 0) &&
          (buckets[j - 1] > MAX_IBF_DECODE))
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
#if FIX2
      /* another improvement: don't just always cut off the last one,
         but rather try to predict based on all previous values where
         that "last" one is; additional prediction can only really
         work if MAX_IBF_DECODE is sufficiently high */
      if ((j > 0) &&
          ((buckets[j - 1] > MAX_IBF_DECODE) ||
           (predict > MAX_IBF_DECODE)))
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
#if STRATA
      /* original algorithm, for 1000 elements with IBF-DECODE 8,
         I get 920/1000 elements on average over 1 million runs */
      if (buckets[j] > MAX_IBF_DECODE)
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
      ret += buckets[j];
      predict = (buckets[j] + 2.0 * predict) / 2.0;
    }
#if VERBOSE
    fprintf (stderr, "%u ", ret);
#endif
    total += ret;
  }
  fprintf (stderr, "\n");
  fprintf (stdout, "average %llu\n", total / ROUNDS);
  return 0;
}

References MAX_IBF_DECODE, ret, and ROUNDS.