From be0475f2a583d203465d3091ff933806a5ace613 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Sun, 16 Aug 2020 20:46:39 +0200 Subject: split of set union from set service (preliminary) --- src/setu/gnunet-setu-ibf-profiler.c | 308 ++++++++++++++++++++++++++++++++++++ 1 file changed, 308 insertions(+) create mode 100644 src/setu/gnunet-setu-ibf-profiler.c (limited to 'src/setu/gnunet-setu-ibf-profiler.c') 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 @@ +/* + This file is part of GNUnet. + Copyright (C) 2012 GNUnet e.V. + + GNUnet is free software: you can redistribute it and/or modify it + under the terms of the GNU Affero General Public License as published + by the Free Software Foundation, either version 3 of the License, + or (at your option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see . + + SPDX-License-Identifier: AGPL3.0-or-later + */ + +/** + * @file set/gnunet-set-ibf-profiler.c + * @brief tool for profiling the invertible bloom filter implementation + * @author Florian Dold + */ + +#include "platform.h" +#include "gnunet_util_lib.h" + +#include "ibf.h" + +static unsigned int asize = 10; +static unsigned int bsize = 10; +static unsigned int csize = 10; +static unsigned int hash_num = 4; +static unsigned int ibf_size = 80; + +/* FIXME: add parameter for this */ +static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK; + +static struct GNUNET_CONTAINER_MultiHashMap *set_a; +static struct GNUNET_CONTAINER_MultiHashMap *set_b; +/* common elements in a and b */ +static struct GNUNET_CONTAINER_MultiHashMap *set_c; + +static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode; + +static struct InvertibleBloomFilter *ibf_a; +static struct InvertibleBloomFilter *ibf_b; + + +static void +register_hashcode (struct GNUNET_HashCode *hash) +{ + struct GNUNET_HashCode replicated; + struct IBF_Key key; + + key = ibf_key_from_hashcode (hash); + ibf_hashcode_from_key (key, &replicated); + (void) GNUNET_CONTAINER_multihashmap_put ( + key_to_hashcode, + &replicated, + GNUNET_memdup (hash, sizeof *hash), + GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); +} + + +static void +iter_hashcodes (struct IBF_Key key, + GNUNET_CONTAINER_MulitHashMapIteratorCallback iter, + void *cls) +{ + struct GNUNET_HashCode replicated; + + ibf_hashcode_from_key (key, &replicated); + GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode, + &replicated, + iter, + cls); +} + + +static int +insert_iterator (void *cls, const struct GNUNET_HashCode *key, void *value) +{ + struct InvertibleBloomFilter *ibf = cls; + + ibf_insert (ibf, ibf_key_from_hashcode (key)); + return GNUNET_YES; +} + + +static int +remove_iterator (void *cls, const struct GNUNET_HashCode *key, void *value) +{ + struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls; + + /* if remove fails, there just was a collision with another key */ + (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL); + return GNUNET_YES; +} + + +static void +run (void *cls, + char *const *args, + const char *cfgfile, + const struct GNUNET_CONFIGURATION_Handle *cfg) +{ + struct GNUNET_HashCode id; + struct IBF_Key ibf_key; + int i; + int side; + int res; + struct GNUNET_TIME_Absolute start_time; + struct GNUNET_TIME_Relative delta_time; + + set_a = + GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)), + GNUNET_NO); + set_b = + GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)), + GNUNET_NO); + set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize), + GNUNET_NO); + + key_to_hashcode = + GNUNET_CONTAINER_multihashmap_create (((asize + bsize + csize == 0) + ? 1 + : (asize + bsize + csize)), + GNUNET_NO); + + printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n", + hash_num, + ibf_size, + asize, + bsize, + csize); + + i = 0; + while (i < asize) + { + GNUNET_CRYPTO_hash_create_random (random_quality, &id); + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) + continue; + GNUNET_break (GNUNET_OK == + GNUNET_CONTAINER_multihashmap_put ( + set_a, + &id, + NULL, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + register_hashcode (&id); + i++; + } + i = 0; + while (i < bsize) + { + GNUNET_CRYPTO_hash_create_random (random_quality, &id); + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) + continue; + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) + continue; + GNUNET_break (GNUNET_OK == + GNUNET_CONTAINER_multihashmap_put ( + set_b, + &id, + NULL, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + register_hashcode (&id); + i++; + } + i = 0; + while (i < csize) + { + GNUNET_CRYPTO_hash_create_random (random_quality, &id); + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) + continue; + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) + continue; + if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id)) + continue; + GNUNET_break (GNUNET_OK == + GNUNET_CONTAINER_multihashmap_put ( + set_c, + &id, + NULL, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + register_hashcode (&id); + i++; + } + + ibf_a = ibf_create (ibf_size, hash_num); + ibf_b = ibf_create (ibf_size, hash_num); + if ((NULL == ibf_a) || (NULL == ibf_b)) + { + /* insufficient memory */ + GNUNET_break (0); + GNUNET_SCHEDULER_shutdown (); + return; + } + + + printf ("generated sets\n"); + + start_time = GNUNET_TIME_absolute_get (); + + GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a); + GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b); + GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a); + GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b); + + delta_time = GNUNET_TIME_absolute_get_duration (start_time); + + printf ("encoded in: %s\n", + GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); + + ibf_subtract (ibf_a, ibf_b); + + + start_time = GNUNET_TIME_absolute_get (); + + for (i = 0; i <= asize + bsize; i++) + { + res = ibf_decode (ibf_a, &side, &ibf_key); + if (GNUNET_SYSERR == res) + { + printf ("decode failed, %u/%u elements left\n", + GNUNET_CONTAINER_multihashmap_size (set_a) + + GNUNET_CONTAINER_multihashmap_size (set_b), + asize + bsize); + return; + } + if (GNUNET_NO == res) + { + if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) && + (0 == GNUNET_CONTAINER_multihashmap_size (set_a))) + { + delta_time = GNUNET_TIME_absolute_get_duration (start_time); + printf ("decoded successfully in: %s\n", + GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); + } + else + { + printf ("decode missed elements (should never happen)\n"); + } + return; + } + + if (side == 1) + iter_hashcodes (ibf_key, remove_iterator, set_a); + if (side == -1) + iter_hashcodes (ibf_key, remove_iterator, set_b); + } + printf ("cyclic IBF, %u/%u elements left\n", + GNUNET_CONTAINER_multihashmap_size (set_a) + + GNUNET_CONTAINER_multihashmap_size (set_b), + asize + bsize); +} + + +int +main (int argc, char **argv) +{ + struct GNUNET_GETOPT_CommandLineOption options[] = { + GNUNET_GETOPT_option_uint ('A', + "asize", + NULL, + gettext_noop ("number of element in set A-B"), + &asize), + + GNUNET_GETOPT_option_uint ('B', + "bsize", + NULL, + gettext_noop ("number of element in set B-A"), + &bsize), + + GNUNET_GETOPT_option_uint ('C', + "csize", + NULL, + gettext_noop ( + "number of common elements in A and B"), + &csize), + + GNUNET_GETOPT_option_uint ('k', + "hash-num", + NULL, + gettext_noop ("hash num"), + &hash_num), + + GNUNET_GETOPT_option_uint ('s', + "ibf-size", + NULL, + gettext_noop ("ibf size"), + &ibf_size), + + GNUNET_GETOPT_OPTION_END + }; + + GNUNET_PROGRAM_run2 (argc, + argv, + "gnunet-consensus-ibf", + "help", + options, + &run, + NULL, + GNUNET_YES); + return 0; +} -- cgit v1.2.3