diff options
author | Christian Grothoff <christian@grothoff.org> | 2020-08-16 20:46:39 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2020-08-16 20:46:39 +0200 |
commit | be0475f2a583d203465d3091ff933806a5ace613 (patch) | |
tree | cbb1ad1a27cd91a6ff1ccb8025595cbe4c15972a /src/setu/gnunet-setu-ibf-profiler.c | |
parent | f1f40feb2beb5c036da0e2b93c433b09b920e0b4 (diff) | |
download | gnunet-be0475f2a583d203465d3091ff933806a5ace613.tar.gz gnunet-be0475f2a583d203465d3091ff933806a5ace613.zip |
split of set union from set service (preliminary)
Diffstat (limited to 'src/setu/gnunet-setu-ibf-profiler.c')
-rw-r--r-- | src/setu/gnunet-setu-ibf-profiler.c | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/src/setu/gnunet-setu-ibf-profiler.c b/src/setu/gnunet-setu-ibf-profiler.c new file mode 100644 index 000000000..944b63d30 --- /dev/null +++ b/src/setu/gnunet-setu-ibf-profiler.c | |||
@@ -0,0 +1,308 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2012 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 | |||
21 | /** | ||
22 | * @file set/gnunet-set-ibf-profiler.c | ||
23 | * @brief tool for profiling the invertible bloom filter implementation | ||
24 | * @author Florian Dold | ||
25 | */ | ||
26 | |||
27 | #include "platform.h" | ||
28 | #include "gnunet_util_lib.h" | ||
29 | |||
30 | #include "ibf.h" | ||
31 | |||
32 | static unsigned int asize = 10; | ||
33 | static unsigned int bsize = 10; | ||
34 | static unsigned int csize = 10; | ||
35 | static unsigned int hash_num = 4; | ||
36 | static unsigned int ibf_size = 80; | ||
37 | |||
38 | /* FIXME: add parameter for this */ | ||
39 | static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK; | ||
40 | |||
41 | static struct GNUNET_CONTAINER_MultiHashMap *set_a; | ||
42 | static struct GNUNET_CONTAINER_MultiHashMap *set_b; | ||
43 | /* common elements in a and b */ | ||
44 | static struct GNUNET_CONTAINER_MultiHashMap *set_c; | ||
45 | |||
46 | static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode; | ||
47 | |||
48 | static struct InvertibleBloomFilter *ibf_a; | ||
49 | static struct InvertibleBloomFilter *ibf_b; | ||
50 | |||
51 | |||
52 | static void | ||
53 | register_hashcode (struct GNUNET_HashCode *hash) | ||
54 | { | ||
55 | struct GNUNET_HashCode replicated; | ||
56 | struct IBF_Key key; | ||
57 | |||
58 | key = ibf_key_from_hashcode (hash); | ||
59 | ibf_hashcode_from_key (key, &replicated); | ||
60 | (void) GNUNET_CONTAINER_multihashmap_put ( | ||
61 | key_to_hashcode, | ||
62 | &replicated, | ||
63 | GNUNET_memdup (hash, sizeof *hash), | ||
64 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | ||
65 | } | ||
66 | |||
67 | |||
68 | static void | ||
69 | iter_hashcodes (struct IBF_Key key, | ||
70 | GNUNET_CONTAINER_MulitHashMapIteratorCallback iter, | ||
71 | void *cls) | ||
72 | { | ||
73 | struct GNUNET_HashCode replicated; | ||
74 | |||
75 | ibf_hashcode_from_key (key, &replicated); | ||
76 | GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode, | ||
77 | &replicated, | ||
78 | iter, | ||
79 | cls); | ||
80 | } | ||
81 | |||
82 | |||
83 | static int | ||
84 | insert_iterator (void *cls, const struct GNUNET_HashCode *key, void *value) | ||
85 | { | ||
86 | struct InvertibleBloomFilter *ibf = cls; | ||
87 | |||
88 | ibf_insert (ibf, ibf_key_from_hashcode (key)); | ||
89 | return GNUNET_YES; | ||
90 | } | ||
91 | |||
92 | |||
93 | static int | ||
94 | remove_iterator (void *cls, const struct GNUNET_HashCode *key, void *value) | ||
95 | { | ||
96 | struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls; | ||
97 | |||
98 | /* if remove fails, there just was a collision with another key */ | ||
99 | (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL); | ||
100 | return GNUNET_YES; | ||
101 | } | ||
102 | |||
103 | |||
104 | static void | ||
105 | run (void *cls, | ||
106 | char *const *args, | ||
107 | const char *cfgfile, | ||
108 | const struct GNUNET_CONFIGURATION_Handle *cfg) | ||
109 | { | ||
110 | struct GNUNET_HashCode id; | ||
111 | struct IBF_Key ibf_key; | ||
112 | int i; | ||
113 | int side; | ||
114 | int res; | ||
115 | struct GNUNET_TIME_Absolute start_time; | ||
116 | struct GNUNET_TIME_Relative delta_time; | ||
117 | |||
118 | set_a = | ||
119 | GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)), | ||
120 | GNUNET_NO); | ||
121 | set_b = | ||
122 | GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)), | ||
123 | GNUNET_NO); | ||
124 | set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize), | ||
125 | GNUNET_NO); | ||
126 | |||
127 | key_to_hashcode = | ||
128 | GNUNET_CONTAINER_multihashmap_create (((asize + bsize + csize == 0) | ||
129 | ? 1 | ||
130 | : (asize + bsize + csize)), | ||
131 | GNUNET_NO); | ||
132 | |||
133 | printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n", | ||
134 | hash_num, | ||
135 | ibf_size, | ||
136 | asize, | ||
137 | bsize, | ||
138 | csize); | ||
139 | |||
140 | i = 0; | ||
141 | while (i < asize) | ||
142 | { | ||
143 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
144 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
145 | continue; | ||
146 | GNUNET_break (GNUNET_OK == | ||
147 | GNUNET_CONTAINER_multihashmap_put ( | ||
148 | set_a, | ||
149 | &id, | ||
150 | NULL, | ||
151 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
152 | register_hashcode (&id); | ||
153 | i++; | ||
154 | } | ||
155 | i = 0; | ||
156 | while (i < bsize) | ||
157 | { | ||
158 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
159 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
160 | continue; | ||
161 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) | ||
162 | continue; | ||
163 | GNUNET_break (GNUNET_OK == | ||
164 | GNUNET_CONTAINER_multihashmap_put ( | ||
165 | set_b, | ||
166 | &id, | ||
167 | NULL, | ||
168 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
169 | register_hashcode (&id); | ||
170 | i++; | ||
171 | } | ||
172 | i = 0; | ||
173 | while (i < csize) | ||
174 | { | ||
175 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
176 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
177 | continue; | ||
178 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) | ||
179 | continue; | ||
180 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id)) | ||
181 | continue; | ||
182 | GNUNET_break (GNUNET_OK == | ||
183 | GNUNET_CONTAINER_multihashmap_put ( | ||
184 | set_c, | ||
185 | &id, | ||
186 | NULL, | ||
187 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
188 | register_hashcode (&id); | ||
189 | i++; | ||
190 | } | ||
191 | |||
192 | ibf_a = ibf_create (ibf_size, hash_num); | ||
193 | ibf_b = ibf_create (ibf_size, hash_num); | ||
194 | if ((NULL == ibf_a) || (NULL == ibf_b)) | ||
195 | { | ||
196 | /* insufficient memory */ | ||
197 | GNUNET_break (0); | ||
198 | GNUNET_SCHEDULER_shutdown (); | ||
199 | return; | ||
200 | } | ||
201 | |||
202 | |||
203 | printf ("generated sets\n"); | ||
204 | |||
205 | start_time = GNUNET_TIME_absolute_get (); | ||
206 | |||
207 | GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a); | ||
208 | GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b); | ||
209 | GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a); | ||
210 | GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b); | ||
211 | |||
212 | delta_time = GNUNET_TIME_absolute_get_duration (start_time); | ||
213 | |||
214 | printf ("encoded in: %s\n", | ||
215 | GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); | ||
216 | |||
217 | ibf_subtract (ibf_a, ibf_b); | ||
218 | |||
219 | |||
220 | start_time = GNUNET_TIME_absolute_get (); | ||
221 | |||
222 | for (i = 0; i <= asize + bsize; i++) | ||
223 | { | ||
224 | res = ibf_decode (ibf_a, &side, &ibf_key); | ||
225 | if (GNUNET_SYSERR == res) | ||
226 | { | ||
227 | printf ("decode failed, %u/%u elements left\n", | ||
228 | GNUNET_CONTAINER_multihashmap_size (set_a) | ||
229 | + GNUNET_CONTAINER_multihashmap_size (set_b), | ||
230 | asize + bsize); | ||
231 | return; | ||
232 | } | ||
233 | if (GNUNET_NO == res) | ||
234 | { | ||
235 | if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) && | ||
236 | (0 == GNUNET_CONTAINER_multihashmap_size (set_a))) | ||
237 | { | ||
238 | delta_time = GNUNET_TIME_absolute_get_duration (start_time); | ||
239 | printf ("decoded successfully in: %s\n", | ||
240 | GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); | ||
241 | } | ||
242 | else | ||
243 | { | ||
244 | printf ("decode missed elements (should never happen)\n"); | ||
245 | } | ||
246 | return; | ||
247 | } | ||
248 | |||
249 | if (side == 1) | ||
250 | iter_hashcodes (ibf_key, remove_iterator, set_a); | ||
251 | if (side == -1) | ||
252 | iter_hashcodes (ibf_key, remove_iterator, set_b); | ||
253 | } | ||
254 | printf ("cyclic IBF, %u/%u elements left\n", | ||
255 | GNUNET_CONTAINER_multihashmap_size (set_a) | ||
256 | + GNUNET_CONTAINER_multihashmap_size (set_b), | ||
257 | asize + bsize); | ||
258 | } | ||
259 | |||
260 | |||
261 | int | ||
262 | main (int argc, char **argv) | ||
263 | { | ||
264 | struct GNUNET_GETOPT_CommandLineOption options[] = { | ||
265 | GNUNET_GETOPT_option_uint ('A', | ||
266 | "asize", | ||
267 | NULL, | ||
268 | gettext_noop ("number of element in set A-B"), | ||
269 | &asize), | ||
270 | |||
271 | GNUNET_GETOPT_option_uint ('B', | ||
272 | "bsize", | ||
273 | NULL, | ||
274 | gettext_noop ("number of element in set B-A"), | ||
275 | &bsize), | ||
276 | |||
277 | GNUNET_GETOPT_option_uint ('C', | ||
278 | "csize", | ||
279 | NULL, | ||
280 | gettext_noop ( | ||
281 | "number of common elements in A and B"), | ||
282 | &csize), | ||
283 | |||
284 | GNUNET_GETOPT_option_uint ('k', | ||
285 | "hash-num", | ||
286 | NULL, | ||
287 | gettext_noop ("hash num"), | ||
288 | &hash_num), | ||
289 | |||
290 | GNUNET_GETOPT_option_uint ('s', | ||
291 | "ibf-size", | ||
292 | NULL, | ||
293 | gettext_noop ("ibf size"), | ||
294 | &ibf_size), | ||
295 | |||
296 | GNUNET_GETOPT_OPTION_END | ||
297 | }; | ||
298 | |||
299 | GNUNET_PROGRAM_run2 (argc, | ||
300 | argv, | ||
301 | "gnunet-consensus-ibf", | ||
302 | "help", | ||
303 | options, | ||
304 | &run, | ||
305 | NULL, | ||
306 | GNUNET_YES); | ||
307 | return 0; | ||
308 | } | ||