Page MenuHomePhabricator
Differential D7970 Diff 24771 src/test/cuckoocache_tests.cpp

Changeset View

Standalone View

View Options

src/test/cuckoocache_tests.cpp

Show First 20 Lines • Show All 101 Lines • ▼ Show 20 Lines
using TestMapKey = TestMapElement::KeyType; 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 400000 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(SeedRand::ZEROS);
CuckooCacheSet cc{}; CuckooCacheSet 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));
Show All 10 Lines
}; };
/** /**
* 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(SeedRand::ZEROS);
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.reserve(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.emplace_back(InsecureRand256()); hashes.emplace_back(InsecureRand256());
▲ Show 20 Lines • Show All 59 Lines • ▼ Show 20 Lines
} }
/** /**
* 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> static 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(SeedRand::ZEROS);
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) {
hashes[i] = InsecureRand256(); hashes[i] = InsecureRand256();
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 LinesBOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) {
size_t megabytes = 4; size_t megabytes = 4;
test_cache_erase<CuckooCacheSet>(megabytes); test_cache_erase<CuckooCacheSet>(megabytes);
test_cache_erase<CuckooCacheMap>(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(SeedRand::ZEROS);
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) {
hashes[i] = InsecureRand256(); hashes[i] = InsecureRand256();
▲ Show 20 Lines • Show All 93 Lines • ▼ Show 20 Linestemplate <typename Cache> static void test_cache_generations() {
// min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% ==
// 99.89% // 99.89%
// hit rate with low variance. // hit rate with low variance.
// We use deterministic values, but this test has also passed on many // We use deterministic values, but this test has also passed on many
// iterations with non-deterministic values, so it isn't "overfit" to the // iterations with non-deterministic values, so it isn't "overfit" to the
// specific entropy in FastRandomContext(true) and implementation of the // specific entropy in FastRandomContext(true) and implementation of the
// cache. // cache.
SeedInsecureRand(true); SeedInsecureRand(SeedRand::ZEROS);
// block_activity models a chunk of network activity. n_insert elements are // block_activity models a chunk of network activity. n_insert elements are
// added to the cache. The first and last n/4 are stored for removal later // added to the cache. The first and last n/4 are stored for removal later
// and the middle n/2 are not stored. This models a network which uses half // and the middle n/2 are not stored. This models a network which uses half
// the signatures of recently (since the last block) added transactions // the signatures of recently (since the last block) added transactions
// immediately and never uses the other half. // immediately and never uses the other half.
struct block_activity { struct block_activity {
std::vector<uint256> reads; std::vector<uint256> reads;
▲ Show 20 Lines • Show All 78 Lines • ▼ Show 20 Lines uint256 key = uint256S(
"baadf00dcafebeef00000000bada550ff1ce00000000000000000000abadba5e"); "baadf00dcafebeef00000000bada550ff1ce00000000000000000000abadba5e");
const TestMapElement e(hash); const TestMapElement e(hash);
BOOST_CHECK_EQUAL(e.getValue(), 0xdeadc0de); BOOST_CHECK_EQUAL(e.getValue(), 0xdeadc0de);
BOOST_CHECK(e.getKey() == TestMapElement(key).getKey()); BOOST_CHECK(e.getKey() == TestMapElement(key).getKey());
} }
BOOST_AUTO_TEST_CASE(cuckoocache_map) { BOOST_AUTO_TEST_CASE(cuckoocache_map) {
SeedInsecureRand(true); SeedInsecureRand(SeedRand::ZEROS);
// 4k cache. // 4k cache.
CuckooCacheMap cm{}; CuckooCacheMap cm{};
cm.setup_bytes(4 * 1024); cm.setup_bytes(4 * 1024);
for (int x = 0; x < 100000; ++x) { for (int x = 0; x < 100000; ++x) {
const TestMapElement e1(InsecureRand256()); const TestMapElement e1(InsecureRand256());
const TestMapElement e2(e1.getKey(), e1.getValue() ^ 0xbabe); const TestMapElement e2(e1.getKey(), e1.getValue() ^ 0xbabe);
Show All 32 Lines