Differential D4621 Diff 14724 src/test/cuckoocache_tests.cpp

Changeset 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 200000 insecure_GetRandHash calls
		markblundebergUnsubmitted Not Done Inline Actions note that (since not re-seeded) this does 400000 calls. markblundeberg: note that (since not re-seeded) this does 400000 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));
		markblundebergUnsubmitted Not Done Inline Actions It's interesting that this manages to have 100000 successive inserts. Without any erases, the epoch system does allow the table to get pretty full. I tried setting this to 2 million iterations and it only fails 7 times. markblundeberg: It's interesting that this manages to have 100000 successive inserts. Without any erases, the…
		deadalnixAuthorUnsubmitted Done Inline Actions With each element having 8 positions, it's not that incredible. deadalnix: With each element having 8 positions, it's not that incredible.

		// 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();