9 #include <boost/test/unit_test.hpp>
13 #include <shared_mutex>
42 for (
int x = 0; x < 100000; ++x) {
45 for (
int x = 0; x < 100000; ++x) {
53 template <
typename Cache>
57 std::vector<uint256> hashes;
59 size_t bytes = megabytes * (1 << 20);
60 set.setup_bytes(bytes);
61 uint32_t n_insert =
static_cast<uint32_t
>(load * (bytes /
sizeof(
uint256)));
62 hashes.resize(n_insert);
63 for (uint32_t i = 0; i < n_insert; ++i) {
64 uint32_t* ptr = (uint32_t*)hashes[i].begin();
65 for (uint8_t j = 0; j < 8; ++j)
72 std::vector<uint256> hashes_insert_copy = hashes;
74 for (
const uint256& h : hashes_insert_copy)
79 count += set.contains(h,
false);
80 double hit_rate = ((double)
count) / ((double)n_insert);
103 return hits * std::max(load, 1.0);
112 double HitRateThresh = 0.98;
113 size_t megabytes = 4;
114 for (
double load = 0.1; load < 2; load *= 2) {
115 double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes, load);
123 template <
typename Cache>
128 std::vector<uint256> hashes;
130 size_t bytes = megabytes * (1 << 20);
131 set.setup_bytes(bytes);
132 uint32_t n_insert =
static_cast<uint32_t
>(load * (bytes /
sizeof(
uint256)));
133 hashes.resize(n_insert);
134 for (uint32_t i = 0; i < n_insert; ++i) {
135 uint32_t* ptr = (uint32_t*)hashes[i].begin();
136 for (uint8_t j = 0; j < 8; ++j)
143 std::vector<uint256> hashes_insert_copy = hashes;
146 for (uint32_t i = 0; i < (n_insert / 2); ++i)
147 set.insert(hashes_insert_copy[i]);
149 for (uint32_t i = 0; i < (n_insert / 4); ++i)
152 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
153 set.insert(hashes_insert_copy[i]);
156 size_t count_erased_but_contained = 0;
158 size_t count_stale = 0;
160 size_t count_fresh = 0;
162 for (uint32_t i = 0; i < (n_insert / 4); ++i)
163 count_erased_but_contained += set.contains(hashes[i],
false);
164 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
165 count_stale += set.contains(hashes[i],
false);
166 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
167 count_fresh += set.contains(hashes[i],
false);
169 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
170 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
171 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
177 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
182 size_t megabytes = 4;
183 test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
186 template <
typename Cache>
191 std::vector<uint256> hashes;
193 size_t bytes = megabytes * (1 << 20);
194 set.setup_bytes(bytes);
195 uint32_t n_insert =
static_cast<uint32_t
>(load * (bytes /
sizeof(
uint256)));
196 hashes.resize(n_insert);
197 for (uint32_t i = 0; i < n_insert; ++i) {
198 uint32_t* ptr = (uint32_t*)hashes[i].begin();
199 for (uint8_t j = 0; j < 8; ++j)
206 std::vector<uint256> hashes_insert_copy = hashes;
207 std::shared_mutex mtx;
211 std::unique_lock<std::shared_mutex> l(mtx);
213 for (uint32_t i = 0; i < (n_insert / 2); ++i)
214 set.insert(hashes_insert_copy[i]);
219 std::vector<std::thread> threads;
221 for (uint32_t x = 0; x < 3; ++x)
224 threads.emplace_back([&, x] {
225 std::shared_lock<std::shared_mutex> l(mtx);
226 size_t ntodo = (n_insert/4)/3;
227 size_t start = ntodo*x;
228 size_t end = ntodo*(x+1);
229 for (uint32_t i = start; i < end; ++i) {
230 bool contains = set.contains(hashes[i],
true);
237 for (std::thread& t : threads)
240 std::unique_lock<std::shared_mutex> l(mtx);
242 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
243 set.insert(hashes_insert_copy[i]);
246 size_t count_erased_but_contained = 0;
248 size_t count_stale = 0;
250 size_t count_fresh = 0;
252 for (uint32_t i = 0; i < (n_insert / 4); ++i)
253 count_erased_but_contained += set.contains(hashes[i],
false);
254 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
255 count_stale += set.contains(hashes[i],
false);
256 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
257 count_fresh += set.contains(hashes[i],
false);
259 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
260 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
261 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
267 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
271 size_t megabytes = 4;
272 test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
276 template <
typename Cache>
282 double min_hit_rate = 0.99;
283 double tight_hit_rate = 0.999;
284 double max_rate_less_than_tight_hit_rate = 0.01;
301 struct block_activity {
302 std::vector<uint256> reads;
303 block_activity(uint32_t n_insert, Cache& c) : reads()
305 std::vector<uint256> inserts;
306 inserts.resize(n_insert);
307 reads.reserve(n_insert / 2);
308 for (uint32_t i = 0; i < n_insert; ++i) {
309 uint32_t* ptr = (uint32_t*)inserts[i].begin();
310 for (uint8_t j = 0; j < 8; ++j)
313 for (uint32_t i = 0; i < n_insert / 4; ++i)
314 reads.push_back(inserts[i]);
315 for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
316 reads.push_back(inserts[i]);
317 for (
const auto& h : inserts)
322 const uint32_t BLOCK_SIZE = 1000;
325 const uint32_t WINDOW_SIZE = 60;
326 const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
327 const double load = 10;
328 const size_t megabytes = 4;
329 const size_t bytes = megabytes * (1 << 20);
330 const uint32_t n_insert =
static_cast<uint32_t
>(load * (bytes /
sizeof(
uint256)));
332 std::vector<block_activity> hashes;
334 set.setup_bytes(bytes);
335 hashes.reserve(n_insert / BLOCK_SIZE);
336 std::deque<block_activity> last_few;
337 uint32_t out_of_tight_tolerance = 0;
338 uint32_t total = n_insert / BLOCK_SIZE;
342 for (uint32_t i = 0; i < total; ++i) {
343 if (last_few.size() == WINDOW_SIZE)
344 last_few.pop_front();
345 last_few.emplace_back(BLOCK_SIZE, set);
347 for (
auto& act : last_few)
348 for (uint32_t
k = 0;
k < POP_AMOUNT; ++
k) {
349 count += set.contains(act.reads.back(),
true);
350 act.reads.pop_back();
355 double hit = (double(
count)) / (last_few.size() * POP_AMOUNT);
360 out_of_tight_tolerance += hit < tight_hit_rate;
364 BOOST_CHECK(
double(out_of_tight_tolerance) /
double(total) < max_rate_less_than_tight_hit_rate);
368 test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();