Differential D4621 Diff 14590 src/test/cuckoocache_tests.cpp

Changeset View

Standalone View

src/test/cuckoocache_tests.cpp

Show All 20 Lines
* 3) Results should be treated as a regression test, i.e., did the behavior		* 3) Results should be treated as a regression test, i.e., did the behavior
* 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: uses bytes 0...27 for the key, and bytes 28..31
		* for the value.
		*/
		deadalnixAuthorUnsubmitted Not Done Inline Actions Don't copy bad style. Fix it instead. deadalnix: Don't copy bad style. Fix it instead.
		class ExampleMapElement : public uint256 {
		public:
		class CacheHasher {
		public:
		template <uint8_t hash_select>
		uint32_t operator()(const ExampleMapElement &element) const {
		static_assert(hash_select < 8, "only has 8 hashes available.");
		uint32_t u;
		if (hash_select < 7) {
		std::memcpy(&u, element.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(*(element.begin() + 0) & 0x07) << 29) +
		markblundebergUnsubmitted Done Inline Actions Amusingly, if we just use u=0 for the last hash, all the tests pass fine. In the `cuckoocache_hit_rate_ok` test, this causes the normalized hit rate to drop from 0.989480 to 0.989442, compared to the sigcache's 0.989503. That is basically insignificant though, since changing the test seed makes much larger fluctuations. (In contrast if I zero out the last two hashes then it causes tests to fail.) In other words, we can probably drop to having the cache look at 7 hashes instead of 8. This increases the speed of a read miss by 14%, and the speed of a low-load insertion should see a similar boost since the initial search will be faster. markblundeberg: Amusingly, if we just use u=0 for the last hash, all the tests pass fine. In the…
		(uint32_t(*(element.begin() + 4) & 0x07) << 26) +
		(uint32_t(*(element.begin() + 8) & 0x0f) << 22) +
		(uint32_t(*(element.begin() + 16) & 0x3f) << 16) +
		(uint32_t(*(element.begin() + 20) & 0xff) << 8) +
		(uint32_t(*(element.begin() + 24) & 0xff) << 0);
		}
		return u;
		}
		};
		ExampleMapElement() = default;
		ExampleMapElement(const uint256 &x) {
		std::copy(x.begin(), x.end(), begin());
		}
		deadalnixAuthorUnsubmitted Not Done Inline Actions If this is a KV element, then you really want to pass a key and a value to this instead of filling the value with random garbage. deadalnix: If this is a KV element, then you really want to pass a key and a value to this instead of…
		void setValue(uint32_t v) { std::memcpy(begin() + 28, &v, 4); }
		deadalnixAuthorUnsubmitted Not Done Inline Actions You can then remove the setter. In general, when you end up with both setters (OO style) and getters (functional style) in the same object, you are doing something wrong. If generating variant is still desired, you can have functions such as withValue(...) that generate and return a modified copy. deadalnix: You can then remove the setter. In general, when you end up with both setters (OO style) and…
		uint32_t getValue() {
		uint32_t v;
		std::memcpy(&v, begin() + 28, 4);
		deadalnixAuthorUnsubmitted Not Done Inline Actions I would advice against the use of memcpy. Why not have an std::array<uint8_t, 28> and a uint32_t as member for the element? deadalnix: I would advice against the use of memcpy. Why not have an std::array<uint8_t, 28> and a…
		return v;
		}
		bool operator==(const ExampleMapElement &rhs) const {
		return std::equal(begin(), end() - 4, rhs.begin());
		}
		deadalnixAuthorUnsubmitted Not Done Inline Actions Maybe it is a good idea to actually use a function such as `matchKey(const ExampleMapElement &rhs)` rather than use `operator==` because this is clearly not an equality test. deadalnix: Maybe it is a good idea to actually use a function such as `matchKey(const ExampleMapElement…
		};

/**		/**
* 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
*/		*/
BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) {		BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) {
SeedInsecureRand(true);		SeedInsecureRand(true);
CuckooCache::cache<uint256, SignatureCacheHasher> cc{};		CuckooCache::cache<uint256, SignatureCacheHasher> 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));
}		}

		SeedInsecureRand(true);
		CuckooCache::cache<ExampleMapElement, ExampleMapElement::CacheHasher> cm{};
		cm.setup_bytes(megabytes << 20);
		for (int x = 0; x < 100000; ++x) {
		cm.insert(InsecureRand256());
		}
		for (int x = 0; x < 100000; ++x) {
		BOOST_CHECK(!cm.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>		template <typename Cache>
static double test_cache(size_t megabytes, double load) {		static double test_cache(size_t megabytes, double load) {
▲ Show 20 Lines • Show All 59 Lines • ▼ Show 20 Lines	BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok) {
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);
}		}
		for (double load = 0.1; load < 2; load *= 2) {
		double hits =
		test_cache<CuckooCache::cache<ExampleMapElement,
		ExampleMapElement::CacheHasher>>(
		megabytes, load);
		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> 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(true);
std::vector<uint256> hashes;		std::vector<uint256> hashes;
▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines	template <typename Cache> static void test_cache_erase(size_t megabytes) {
// 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<uint256, SignatureCacheHasher>>(		test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(
megabytes);		megabytes);
		test_cache_erase<
		CuckooCache::cache<ExampleMapElement, ExampleMapElement::CacheHasher>>(
		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 78 Lines • ▼ Show 20 Lines	static void test_cache_erase_parallel(size_t megabytes) {
// 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<		test_cache_erase_parallel<
CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);		CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
		test_cache_erase_parallel<
		CuckooCache::cache<ExampleMapElement, ExampleMapElement::CacheHasher>>(
		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 83 Lines • ▼ Show 20 Lines	template <typename Cache> static void test_cache_generations() {
}		}
// 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<uint256, SignatureCacheHasher>>();		test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
		test_cache_generations<CuckooCache::cache<
		ExampleMapElement, ExampleMapElement::CacheHasher>>();
		}

		BOOST_AUTO_TEST_CASE(map) {
		SeedInsecureRand(true);
		CuckooCache::cache<ExampleMapElement, ExampleMapElement::CacheHasher> cm{};
		cm.setup_bytes(4 << 20);
		for (int x = 0; x < 100000; ++x) {
		ExampleMapElement elem = InsecureRand256();
		uint32_t initvalue = elem.getValue();
		uint32_t newvalue;
		while ((newvalue = InsecureRand32()) == initvalue)
		;
		deadalnixAuthorUnsubmitted Not Done Inline Actions Use `{}` as an empty statement instead. Also, I don't think this is a bit strange and I'm not sure what it is testing. This is potentially looping forever and not really testing that the value we get are working properly, because they are set randomly to begin with, see comments on `ExampleMapElement`. deadalnix: Use `{}` as an empty statement instead. Also, I don't think this is a bit strange and I'm not…

		BOOST_CHECK(!cm.get(elem, false));

		cm.insert(elem);

		elem.setValue(newvalue);
		BOOST_CHECK(cm.get(elem, false));
		BOOST_CHECK(elem.getValue() == initvalue);
		elem.setValue(newvalue);
		cm.insert(elem, false);
		BOOST_CHECK(cm.get(elem, false));
		BOOST_CHECK(elem.getValue() == initvalue);
		elem.setValue(newvalue);
		cm.insert(elem, true);
		BOOST_CHECK(cm.get(elem, false));
		BOOST_CHECK(elem.getValue() == newvalue);
		}
}		}

BOOST_AUTO_TEST_SUITE_END();		BOOST_AUTO_TEST_SUITE_END();