diff options
Diffstat (limited to 'src/set/ibf_sim.c')
-rw-r--r-- | src/set/ibf_sim.c | 116 |
1 files changed, 58 insertions, 58 deletions
diff --git a/src/set/ibf_sim.c b/src/set/ibf_sim.c index 02b675f4a..226a9d751 100644 --- a/src/set/ibf_sim.c +++ b/src/set/ibf_sim.c | |||
@@ -50,7 +50,7 @@ | |||
50 | #define SLOW 0 | 50 | #define SLOW 0 |
51 | 51 | ||
52 | int | 52 | int |
53 | main(int argc, char **argv) | 53 | main (int argc, char **argv) |
54 | { | 54 | { |
55 | unsigned int round; | 55 | unsigned int round; |
56 | unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31 | 56 | unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31 |
@@ -62,77 +62,77 @@ main(int argc, char **argv) | |||
62 | unsigned int want; | 62 | unsigned int want; |
63 | double predict; | 63 | double predict; |
64 | 64 | ||
65 | srandom(time(NULL)); | 65 | srandom (time (NULL)); |
66 | total = 0; | 66 | total = 0; |
67 | want = atoi(argv[1]); | 67 | want = atoi (argv[1]); |
68 | for (round = 0; round < ROUNDS; round++) | 68 | for (round = 0; round < ROUNDS; round++) |
69 | { | ||
70 | memset (buckets, 0, sizeof(buckets)); | ||
71 | for (i = 0; i < want; i++) | ||
69 | { | 72 | { |
70 | memset(buckets, 0, sizeof(buckets)); | 73 | /* FIXME: might want to use 'better' PRNG to avoid |
71 | for (i = 0; i < want; i++) | 74 | PRNG-induced biases */ |
72 | { | 75 | r = random (); |
73 | /* FIXME: might want to use 'better' PRNG to avoid | 76 | if (0 == r) |
74 | PRNG-induced biases */ | 77 | continue; |
75 | r = random(); | ||
76 | if (0 == r) | ||
77 | continue; | ||
78 | #if SLOW | 78 | #if SLOW |
79 | for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++) | 79 | for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++) |
80 | ; | 80 | ; |
81 | #else | 81 | #else |
82 | /* use assembly / gcc */ | 82 | /* use assembly / gcc */ |
83 | j = __builtin_ffs(r) - 1; | 83 | j = __builtin_ffs (r) - 1; |
84 | #endif | 84 | #endif |
85 | buckets[j]++; | 85 | buckets[j]++; |
86 | } | 86 | } |
87 | ret = 0; | 87 | ret = 0; |
88 | predict = 0.0; | 88 | predict = 0.0; |
89 | for (j = 31; j >= 0; j--) | 89 | for (j = 31; j >= 0; j--) |
90 | { | 90 | { |
91 | #if FIX1 | 91 | #if FIX1 |
92 | /* improved algorithm, for 1000 elements with IBF-DECODE 8, I | 92 | /* improved algorithm, for 1000 elements with IBF-DECODE 8, I |
93 | get 990/1000 elements on average over 1 million runs; key | 93 | get 990/1000 elements on average over 1 million runs; key |
94 | idea being to stop short of the 'last' possible IBF as | 94 | idea being to stop short of the 'last' possible IBF as |
95 | otherwise a "lowball" per-chance would unduely influence the | 95 | otherwise a "lowball" per-chance would unduely influence the |
96 | result */ | 96 | result */ |
97 | if ((j > 0) && | 97 | if ((j > 0) && |
98 | (buckets[j - 1] > MAX_IBF_DECODE)) | 98 | (buckets[j - 1] > MAX_IBF_DECODE)) |
99 | { | 99 | { |
100 | ret *= (1 << (j + 1)); | 100 | ret *= (1 << (j + 1)); |
101 | break; | 101 | break; |
102 | } | 102 | } |
103 | #endif | 103 | #endif |
104 | #if FIX2 | 104 | #if FIX2 |
105 | /* another improvement: don't just always cut off the last one, | 105 | /* another improvement: don't just always cut off the last one, |
106 | but rather try to predict based on all previous values where | 106 | but rather try to predict based on all previous values where |
107 | that "last" one is; additional prediction can only really | 107 | that "last" one is; additional prediction can only really |
108 | work if MAX_IBF_DECODE is sufficiently high */ | 108 | work if MAX_IBF_DECODE is sufficiently high */ |
109 | if ((j > 0) && | 109 | if ((j > 0) && |
110 | ((buckets[j - 1] > MAX_IBF_DECODE) || | 110 | ((buckets[j - 1] > MAX_IBF_DECODE) || |
111 | (predict > MAX_IBF_DECODE))) | 111 | (predict > MAX_IBF_DECODE))) |
112 | { | 112 | { |
113 | ret *= (1 << (j + 1)); | 113 | ret *= (1 << (j + 1)); |
114 | break; | 114 | break; |
115 | } | 115 | } |
116 | #endif | 116 | #endif |
117 | #if STRATA | 117 | #if STRATA |
118 | /* original algorithm, for 1000 elements with IBF-DECODE 8, | 118 | /* original algorithm, for 1000 elements with IBF-DECODE 8, |
119 | I get 920/1000 elements on average over 1 million runs */ | 119 | I get 920/1000 elements on average over 1 million runs */ |
120 | if (buckets[j] > MAX_IBF_DECODE) | 120 | if (buckets[j] > MAX_IBF_DECODE) |
121 | { | 121 | { |
122 | ret *= (1 << (j + 1)); | 122 | ret *= (1 << (j + 1)); |
123 | break; | 123 | break; |
124 | } | 124 | } |
125 | #endif | 125 | #endif |
126 | ret += buckets[j]; | 126 | ret += buckets[j]; |
127 | predict = (buckets[j] + 2.0 * predict) / 2.0; | 127 | predict = (buckets[j] + 2.0 * predict) / 2.0; |
128 | } | 128 | } |
129 | #if VERBOSE | 129 | #if VERBOSE |
130 | fprintf(stderr, "%u ", ret); | 130 | fprintf (stderr, "%u ", ret); |
131 | #endif | 131 | #endif |
132 | total += ret; | 132 | total += ret; |
133 | } | 133 | } |
134 | fprintf(stderr, "\n"); | 134 | fprintf (stderr, "\n"); |
135 | fprintf(stdout, "average %llu\n", total / ROUNDS); | 135 | fprintf (stdout, "average %llu\n", total / ROUNDS); |
136 | return 0; | 136 | return 0; |
137 | } | 137 | } |
138 | 138 | ||