Changeset View
Changeset View
Standalone View
Standalone View
src/test/cuckoocache_tests.cpp
Show First 20 Lines • Show All 42 Lines • ▼ Show 20 Lines | for (int x = 0; x < 100000; ++x) { | ||||
BOOST_CHECK(!cc.contains(InsecureRand256(), false)); | BOOST_CHECK(!cc.contains(InsecureRand256(), false)); | ||||
} | } | ||||
}; | }; | ||||
/** | /** | ||||
* This helper returns the hit rate when megabytes*load worth of entries are | * This helper returns the hit rate when megabytes*load worth of entries are | ||||
* inserted into a megabytes sized cache | * inserted into a megabytes sized cache | ||||
*/ | */ | ||||
template <typename Cache> double test_cache(size_t megabytes, double load) { | template <typename Cache> | ||||
static double test_cache(size_t megabytes, double load) { | |||||
SeedInsecureRand(true); | SeedInsecureRand(true); | ||||
std::vector<uint256> hashes; | std::vector<uint256> hashes; | ||||
Cache set{}; | Cache set{}; | ||||
size_t bytes = megabytes * (1 << 20); | size_t bytes = megabytes * (1 << 20); | ||||
set.setup_bytes(bytes); | set.setup_bytes(bytes); | ||||
uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | ||||
hashes.resize(n_insert); | hashes.resize(n_insert); | ||||
for (uint32_t i = 0; i < n_insert; ++i) { | for (uint32_t i = 0; i < n_insert; ++i) { | ||||
Show All 33 Lines | |||||
* 2) at load 2.0, we expect to see half the entries, so a perfect hit rate | * 2) at load 2.0, we expect to see half the entries, so a perfect hit rate | ||||
* would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the | * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the | ||||
* normalized hit rate. | * normalized hit rate. | ||||
* | * | ||||
* This is basically the right semantics, but has a bit of a glitch depending on | * This is basically the right semantics, but has a bit of a glitch depending on | ||||
* how you measure around load 1.0 as after load 1.0 your normalized hit rate | * how you measure around load 1.0 as after load 1.0 your normalized hit rate | ||||
* becomes effectively perfect, ignoring freshness. | * becomes effectively perfect, ignoring freshness. | ||||
*/ | */ | ||||
double normalize_hit_rate(double hits, double load) { | static double normalize_hit_rate(double hits, double load) { | ||||
return hits * std::max(load, 1.0); | return hits * std::max(load, 1.0); | ||||
} | } | ||||
/** Check the hit rate on loads ranging from 0.1 to 2.0 */ | /** Check the hit rate on loads ranging from 0.1 to 2.0 */ | ||||
BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok) { | BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok) { | ||||
/** | /** | ||||
* Arbitrarily selected Hit Rate threshold that happens to work for this | * Arbitrarily selected Hit Rate threshold that happens to work for this | ||||
* test as a lower bound on performance. | * test as a lower bound on performance. | ||||
*/ | */ | ||||
double HitRateThresh = 0.98; | double HitRateThresh = 0.98; | ||||
size_t megabytes = 4; | size_t megabytes = 4; | ||||
for (double load = 0.1; load < 2; load *= 2) { | for (double load = 0.1; load < 2; load *= 2) { | ||||
double hits = | double hits = | ||||
test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>( | test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>( | ||||
megabytes, load); | megabytes, load); | ||||
BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); | BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); | ||||
} | } | ||||
} | } | ||||
/** This helper checks that erased elements are preferentially inserted onto and | /** This helper checks that erased elements are preferentially inserted onto and | ||||
* that the hit rate of "fresher" keys is reasonable*/ | * that the hit rate of "fresher" keys is reasonable*/ | ||||
template <typename Cache> void test_cache_erase(size_t megabytes) { | template <typename Cache> static void test_cache_erase(size_t megabytes) { | ||||
double load = 1; | double load = 1; | ||||
SeedInsecureRand(true); | SeedInsecureRand(true); | ||||
std::vector<uint256> hashes; | std::vector<uint256> hashes; | ||||
Cache set{}; | Cache set{}; | ||||
size_t bytes = megabytes * (1 << 20); | size_t bytes = megabytes * (1 << 20); | ||||
set.setup_bytes(bytes); | set.setup_bytes(bytes); | ||||
uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | ||||
hashes.resize(n_insert); | hashes.resize(n_insert); | ||||
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines | |||||
} | } | ||||
BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) { | BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) { | ||||
size_t megabytes = 4; | size_t megabytes = 4; | ||||
test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>( | test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>( | ||||
megabytes); | megabytes); | ||||
} | } | ||||
template <typename Cache> void test_cache_erase_parallel(size_t megabytes) { | template <typename Cache> | ||||
static void test_cache_erase_parallel(size_t megabytes) { | |||||
double load = 1; | double load = 1; | ||||
SeedInsecureRand(true); | SeedInsecureRand(true); | ||||
std::vector<uint256> hashes; | std::vector<uint256> hashes; | ||||
Cache set{}; | Cache set{}; | ||||
size_t bytes = megabytes * (1 << 20); | size_t bytes = megabytes * (1 << 20); | ||||
set.setup_bytes(bytes); | set.setup_bytes(bytes); | ||||
uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); | ||||
hashes.resize(n_insert); | hashes.resize(n_insert); | ||||
▲ Show 20 Lines • Show All 76 Lines • ▼ Show 20 Lines | |||||
} | } | ||||
BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok) { | BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok) { | ||||
size_t megabytes = 4; | size_t megabytes = 4; | ||||
test_cache_erase_parallel< | test_cache_erase_parallel< | ||||
CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes); | CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes); | ||||
} | } | ||||
template <typename Cache> void test_cache_generations() { | template <typename Cache> static void test_cache_generations() { | ||||
// This test checks that for a simulation of network activity, the fresh hit | // This test checks that for a simulation of network activity, the fresh hit | ||||
// rate is never below 99%, and the number of times that it is worse than | // rate is never below 99%, and the number of times that it is worse than | ||||
// 99.9% are less than 1% of the time. | // 99.9% are less than 1% of the time. | ||||
double min_hit_rate = 0.99; | double min_hit_rate = 0.99; | ||||
double tight_hit_rate = 0.999; | double tight_hit_rate = 0.999; | ||||
double max_rate_less_than_tight_hit_rate = 0.01; | double max_rate_less_than_tight_hit_rate = 0.01; | ||||
// A cache that meets this specification is therefore shown to have a hit | // A cache that meets this specification is therefore shown to have a hit | ||||
// rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) | // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) | ||||
▲ Show 20 Lines • Show All 91 Lines • Show Last 20 Lines |