Changeset View
Changeset View
Standalone View
Standalone View
src/test/cuckoocache_tests.cpp
Show All 22 Lines | |||||
* change significantly from what was expected. This can be OK, depending on | * change significantly from what was expected. This can be OK, depending on | ||||
* the nature of the change, but requires updating the tests to reflect the new | * the nature of the change, but requires updating the tests to reflect the new | ||||
* expected behavior. For example improving the hit rate may cause some tests | * expected behavior. For example improving the hit rate may cause some tests | ||||
* using BOOST_CHECK_CLOSE to fail. | * using BOOST_CHECK_CLOSE to fail. | ||||
*/ | */ | ||||
BOOST_AUTO_TEST_SUITE(cuckoocache_tests); | BOOST_AUTO_TEST_SUITE(cuckoocache_tests); | ||||
/** | /** | ||||
* Example key/value element. The key is 28 bytes long and the value 4, for a | |||||
* total of 32 bytes. | |||||
*/ | |||||
struct TestMapElement { | |||||
struct KeyType { | |||||
std::array<uint8_t, 28> data; | |||||
KeyType() = default; | |||||
KeyType(const KeyType &rhs) = default; | |||||
KeyType(const uint256 &k) { | |||||
std::copy(k.begin() + 4, k.end(), data.begin()); | |||||
} | |||||
bool operator==(const KeyType &rhs) const { return rhs.data == data; } | |||||
}; | |||||
private: | |||||
KeyType key; | |||||
uint32_t value; | |||||
public: | |||||
TestMapElement() = default; | |||||
TestMapElement(const TestMapElement &rhs) = default; | |||||
TestMapElement(const uint256 &data) | |||||
: TestMapElement(data, data.GetUint64(0)) {} | |||||
TestMapElement(const KeyType &keyIn, uint32_t valueIn) | |||||
: key(keyIn), value(valueIn) {} | |||||
const KeyType &getKey() const { return key; } | |||||
uint32_t getValue() const { return value; } | |||||
class CacheHasher { | |||||
public: | |||||
template <uint8_t hash_select> | |||||
uint32_t operator()(const KeyType &k) const { | |||||
static_assert(hash_select < 8, "only has 8 hashes available."); | |||||
const auto &d = k.data; | |||||
uint32_t u; | |||||
if (hash_select < 7) { | |||||
std::memcpy(&u, d.begin() + 4 * hash_select, 4); | |||||
} else { | |||||
// We are required to produce 8 subhashes but all key bytes have | |||||
// been used once already. So, we grab a mix of bits from each | |||||
// of the other blobs. We try to ensure more entropy on the | |||||
// higher bits, as these are what primarily get used to | |||||
// determine the index. | |||||
u = (uint32_t(d[0] & 0x07) << 29) + | |||||
(uint32_t(d[4] & 0x07) << 26) + | |||||
(uint32_t(d[8] & 0x0f) << 22) + | |||||
(uint32_t(d[16] & 0x3f) << 16) + | |||||
(uint32_t(d[20] & 0xff) << 8) + | |||||
(uint32_t(d[24] & 0xff) << 0); | |||||
} | |||||
return u; | |||||
} | |||||
}; | |||||
friend class CuckooCache::cache<TestMapElement, CacheHasher>; | |||||
}; | |||||
static_assert(sizeof(TestMapElement) == 32, "TestMapElement must be 32 bytes"); | |||||
// For convenience. | |||||
using CuckooCacheSet = | |||||
CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher>; | |||||
using CuckooCacheMap = | |||||
CuckooCache::cache<TestMapElement, TestMapElement::CacheHasher>; | |||||
using TestMapKey = TestMapElement::KeyType; | |||||
/** | |||||
* Test that no values not inserted into the cache are read out of it. | * Test that no values not inserted into the cache are read out of it. | ||||
* | * | ||||
* There are no repeats in the first 200000 insecure_GetRandHash calls | * There are no repeats in the first 400000 insecure_GetRandHash calls | ||||
*/ | */ | ||||
BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) { | BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) { | ||||
SeedInsecureRand(true); | SeedInsecureRand(true); | ||||
CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher> | CuckooCacheSet cc{}; | ||||
cc{}; | |||||
size_t megabytes = 4; | size_t megabytes = 4; | ||||
cc.setup_bytes(megabytes << 20); | cc.setup_bytes(megabytes << 20); | ||||
for (int x = 0; x < 100000; ++x) { | for (int x = 0; x < 100000; ++x) { | ||||
cc.insert(InsecureRand256()); | cc.insert(InsecureRand256()); | ||||
} | } | ||||
for (int x = 0; x < 100000; ++x) { | for (int x = 0; x < 100000; ++x) { | ||||
BOOST_CHECK(!cc.contains(InsecureRand256(), false)); | BOOST_CHECK(!cc.contains(InsecureRand256(), false)); | ||||
} | } | ||||
CuckooCacheMap cm{}; | |||||
cm.setup_bytes(megabytes << 20); | |||||
for (int x = 0; x < 100000; ++x) { | |||||
cm.insert(TestMapElement(InsecureRand256())); | |||||
} | |||||
for (int x = 0; x < 100000; ++x) { | |||||
BOOST_CHECK(!cm.contains(TestMapKey(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> | template <typename Cache> | ||||
static double test_cache(size_t megabytes, double load) { | 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.reserve(n_insert); | ||||
for (uint32_t i = 0; i < n_insert; ++i) { | for (uint32_t i = 0; i < n_insert; ++i) { | ||||
hashes[i] = InsecureRand256(); | hashes.emplace_back(InsecureRand256()); | ||||
} | } | ||||
/** | /** | ||||
* We make a copy of the hashes because future optimizations of the | * We make a copy of the hashes because future optimizations of the | ||||
* cuckoocache may overwrite the inserted element, so the test is "future | * cuckoocache may overwrite the inserted element, so the test is "future | ||||
* proofed". | * proofed". | ||||
*/ | */ | ||||
std::vector<uint256> hashes_insert_copy = hashes; | std::vector<uint256> hashes_insert_copy = hashes; | ||||
/** Do the insert */ | /** Do the insert */ | ||||
Show All 35 Lines | |||||
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<CuckooCacheSet>(megabytes, load); | ||||
test_cache<CuckooCache::cache<CuckooCache::KeyOnly<uint256>, | BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); | ||||
SignatureCacheHasher>>(megabytes, | } | ||||
load); | |||||
for (double load = 0.1; load < 2; load *= 2) { | |||||
double hits = test_cache<CuckooCacheMap>(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. | ||||
*/ | */ | ||||
▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines | template <typename Cache> static void test_cache_erase(size_t megabytes) { | ||||
BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); | BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); | ||||
// Check that we have a more than 2x better hit rate on stale elements than | // Check that we have a more than 2x better hit rate on stale elements than | ||||
// erased elements. | // erased elements. | ||||
BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); | BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); | ||||
} | } | ||||
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<CuckooCache::KeyOnly<uint256>, | test_cache_erase<CuckooCacheSet>(megabytes); | ||||
SignatureCacheHasher>>(megabytes); | test_cache_erase<CuckooCacheMap>(megabytes); | ||||
} | } | ||||
template <typename Cache> | template <typename Cache> | ||||
static void test_cache_erase_parallel(size_t megabytes) { | 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{}; | ||||
▲ Show 20 Lines • Show All 75 Lines • ▼ Show 20 Lines | static void test_cache_erase_parallel(size_t megabytes) { | ||||
BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); | BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); | ||||
// Check that we have a more than 2x better hit rate on stale elements than | // Check that we have a more than 2x better hit rate on stale elements than | ||||
// erased elements. | // erased elements. | ||||
BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); | BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); | ||||
} | } | ||||
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<CuckooCache::cache<CuckooCache::KeyOnly<uint256>, | test_cache_erase_parallel<CuckooCacheSet>(megabytes); | ||||
SignatureCacheHasher>>( | test_cache_erase_parallel<CuckooCacheMap>(megabytes); | ||||
megabytes); | |||||
} | } | ||||
template <typename Cache> static 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; | ||||
▲ Show 20 Lines • Show All 80 Lines • ▼ Show 20 Lines | for (uint32_t i = 0; i < total; ++i) { | ||||
// (and implicitly, greater than min_hit_rate) | // (and implicitly, greater than min_hit_rate) | ||||
out_of_tight_tolerance += hit < tight_hit_rate; | out_of_tight_tolerance += hit < tight_hit_rate; | ||||
} | } | ||||
// Check that being out of tolerance happens less than | // Check that being out of tolerance happens less than | ||||
// max_rate_less_than_tight_hit_rate of the time | // max_rate_less_than_tight_hit_rate of the time | ||||
BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < | BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < | ||||
max_rate_less_than_tight_hit_rate); | max_rate_less_than_tight_hit_rate); | ||||
} | } | ||||
BOOST_AUTO_TEST_CASE(cuckoocache_generations) { | BOOST_AUTO_TEST_CASE(cuckoocache_generations) { | ||||
test_cache_generations<CuckooCache::cache<CuckooCache::KeyOnly<uint256>, | test_cache_generations<CuckooCacheSet>(); | ||||
SignatureCacheHasher>>(); | test_cache_generations<CuckooCacheMap>(); | ||||
} | |||||
BOOST_AUTO_TEST_CASE(cuckoocache_map_element) { | |||||
// Check the hash is parsed properly. | |||||
uint256 hash = uint256S( | |||||
"baadf00dcafebeef00000000bada550ff1ce00000000000000000000deadc0de"); | |||||
uint256 key = uint256S( | |||||
"baadf00dcafebeef00000000bada550ff1ce00000000000000000000abadba5e"); | |||||
const TestMapElement e(hash); | |||||
BOOST_CHECK_EQUAL(e.getValue(), 0xdeadc0de); | |||||
BOOST_CHECK(e.getKey() == TestMapElement(key).getKey()); | |||||
} | |||||
BOOST_AUTO_TEST_CASE(cuckoocache_map) { | |||||
SeedInsecureRand(true); | |||||
// 4k cache. | |||||
CuckooCacheMap cm{}; | |||||
cm.setup_bytes(4 * 1024); | |||||
for (int x = 0; x < 100000; ++x) { | |||||
const TestMapElement e1(InsecureRand256()); | |||||
const TestMapElement e2(e1.getKey(), e1.getValue() ^ 0xbabe); | |||||
BOOST_CHECK(e1.getKey() == e2.getKey()); | |||||
BOOST_CHECK(e1.getValue() != e2.getValue()); | |||||
// Insert a KV pair in the map and checks that it is effectively | |||||
// inserted. | |||||
BOOST_CHECK(!cm.contains(e1.getKey(), false)); | |||||
cm.insert(e1); | |||||
BOOST_CHECK(cm.contains(e1.getKey(), false)); | |||||
// Check that we recover the proper value from the map. | |||||
TestMapElement e(e1.getKey(), 0); | |||||
BOOST_CHECK(cm.get(e, false)); | |||||
BOOST_CHECK(e.getKey() == e1.getKey()); | |||||
BOOST_CHECK(e.getValue() == e1.getValue()); | |||||
// Insert without replace will not change the value. | |||||
e = e2; | |||||
cm.insert(e2); | |||||
BOOST_CHECK(cm.get(e, false)); | |||||
BOOST_CHECK(e.getKey() == e1.getKey()); | |||||
BOOST_CHECK(e.getValue() == e1.getValue()); | |||||
// Insert and replace. | |||||
cm.insert(e2, true); | |||||
BOOST_CHECK(cm.get(e, false)); | |||||
BOOST_CHECK(e.getKey() == e2.getKey()); | |||||
BOOST_CHECK(e.getValue() == e2.getValue()); | |||||
} | |||||
} | } | ||||
BOOST_AUTO_TEST_SUITE_END(); | BOOST_AUTO_TEST_SUITE_END(); |