diff options
| -rw-r--r-- | src/Makefile.am | 2 | ||||
| -rw-r--r-- | src/minisketchwrapper.cpp | 77 | ||||
| -rw-r--r-- | src/minisketchwrapper.h | 17 | ||||
| -rw-r--r-- | src/test/minisketch_tests.cpp | 9 |
4 files changed, 101 insertions, 4 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index f8644280cb..76755f03d2 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -167,6 +167,7 @@ BITCOIN_CORE_H = \ memusage.h \ merkleblock.h \ miner.h \ + minisketchwrapper.h \ net.h \ net_permissions.h \ net_processing.h \ @@ -334,6 +335,7 @@ libbitcoin_server_a_SOURCES = \ init.cpp \ mapport.cpp \ miner.cpp \ + minisketchwrapper.cpp \ net.cpp \ net_processing.cpp \ node/blockstorage.cpp \ diff --git a/src/minisketchwrapper.cpp b/src/minisketchwrapper.cpp new file mode 100644 index 0000000000..fb176fb153 --- /dev/null +++ b/src/minisketchwrapper.cpp @@ -0,0 +1,77 @@ +// Copyright (c) 2021 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <minisketchwrapper.h> + +#include <logging.h> +#include <util/time.h> + +#include <minisketch.h> + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <utility> +#include <vector> + +namespace { + +static constexpr uint32_t BITS = 32; + +uint32_t FindBestImplementation() +{ + std::optional<std::pair<int64_t, uint32_t>> best; + + uint32_t max_impl = Minisketch::MaxImplementation(); + for (uint32_t impl = 0; impl <= max_impl; ++impl) { + std::vector<int64_t> benches; + uint64_t offset = 0; + /* Run a little benchmark with capacity 32, adding 184 entries, and decoding 11 of them once. */ + for (int b = 0; b < 11; ++b) { + if (!Minisketch::ImplementationSupported(BITS, impl)) break; + Minisketch sketch(BITS, impl, 32); + auto start = GetTimeMicros(); + for (uint64_t e = 0; e < 100; ++e) { + sketch.Add(e*1337 + b*13337 + offset); + } + for (uint64_t e = 0; e < 84; ++e) { + sketch.Add(e*1337 + b*13337 + offset); + } + offset += (*sketch.Decode(32))[0]; + auto stop = GetTimeMicros(); + benches.push_back(stop - start); + } + /* Remember which implementation has the best median benchmark time. */ + if (!benches.empty()) { + std::sort(benches.begin(), benches.end()); + if (!best || best->first > benches[5]) { + best = std::make_pair(benches[5], impl); + } + } + } + assert(best.has_value()); + LogPrintf("Using Minisketch implementation number %i\n", best->second); + return best->second; +} + +uint32_t Minisketch32Implementation() +{ + // Fast compute-once idiom. + static uint32_t best = FindBestImplementation(); + return best; +} + +} // namespace + + +Minisketch MakeMinisketch32(size_t capacity) +{ + return Minisketch(BITS, Minisketch32Implementation(), capacity); +} + +Minisketch MakeMinisketch32FP(size_t max_elements, uint32_t fpbits) +{ + return Minisketch::CreateFP(BITS, Minisketch32Implementation(), max_elements, fpbits); +} diff --git a/src/minisketchwrapper.h b/src/minisketchwrapper.h new file mode 100644 index 0000000000..409221de79 --- /dev/null +++ b/src/minisketchwrapper.h @@ -0,0 +1,17 @@ +// Copyright (c) 2021 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_MINISKETCHWRAPPER_H +#define BITCOIN_MINISKETCHWRAPPER_H + +#include <minisketch.h> +#include <cstddef> +#include <cstdint> + +/** Wrapper around Minisketch::Minisketch(32, implementation, capacity). */ +Minisketch MakeMinisketch32(size_t capacity); +/** Wrapper around Minisketch::CreateFP. */ +Minisketch MakeMinisketch32FP(size_t max_elements, uint32_t fpbits); + +#endif // BITCOIN_DBWRAPPER_H diff --git a/src/test/minisketch_tests.cpp b/src/test/minisketch_tests.cpp index 7211ddfaad..6798331936 100644 --- a/src/test/minisketch_tests.cpp +++ b/src/test/minisketch_tests.cpp @@ -3,6 +3,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include <minisketch.h> +#include <minisketchwrapper.h> #include <random.h> #include <test/util/setup_common.h> @@ -24,13 +25,13 @@ BOOST_AUTO_TEST_CASE(minisketch_test) uint32_t start_b = start_a + a_not_b; uint32_t end_b = start_b + both + b_not_a; - Minisketch sketch_a(32, 0, 10); + Minisketch sketch_a = MakeMinisketch32(10); for (uint32_t a = start_a; a < end_a; ++a) sketch_a.Add(a); - Minisketch sketch_b(32, 0, 10); + Minisketch sketch_b = MakeMinisketch32(10); for (uint32_t b = start_b; b < end_b; ++b) sketch_b.Add(b); - Minisketch sketch_ar(32, 0, 10); - Minisketch sketch_br(32, 0, 10); + Minisketch sketch_ar = MakeMinisketch32(10); + Minisketch sketch_br = MakeMinisketch32(10); sketch_ar.Deserialize(sketch_a.Serialize()); sketch_br.Deserialize(sketch_b.Serialize()); |