cuckoocache_tests.cpp File Reference

#include "cuckoocache.h"
#include "script/sigcache.h"
#include "test/test_pivx.h"
#include "random.h"
#include <thread>
#include <boost/test/unit_test.hpp>

Include dependency graph for cuckoocache_tests.cpp:

Go to the source code of this file.

Functions
	BOOST_AUTO_TEST_SUITE (cuckoocache_tests)
	Test Suite for CuckooCache. More...
	BOOST_AUTO_TEST_CASE (test_cuckoocache_no_fakes)
template<typename Cache >
double	test_cache (size_t megabytes, double load)
	This helper returns the hit rate when megabytes*load worth of entries are inserted into a megabytes sized cache. More...
double	normalize_hit_rate (double hits, double load)
	The normalized hit rate for a given load. More...
	BOOST_AUTO_TEST_CASE (cuckoocache_hit_rate_ok)
	Check the hit rate on loads ranging from 0.1 to 2.0. More...
template<typename Cache >
void	test_cache_erase (size_t megabytes)
	This helper checks that erased elements are preferentially inserted onto and that the hit rate of "fresher" keys is reasonable. More...
	BOOST_AUTO_TEST_CASE (cuckoocache_erase_ok)
template<typename Cache >
void	test_cache_erase_parallel (size_t megabytes)
	BOOST_AUTO_TEST_CASE (cuckoocache_erase_parallel_ok)
template<typename Cache >
void	test_cache_generations ()
	BOOST_AUTO_TEST_CASE (cuckoocache_generations)
	BOOST_AUTO_TEST_SUITE_END ()

Function Documentation

BOOST_AUTO_TEST_CASE() [1/5]

BOOST_AUTO_TEST_CASE

(

cuckoocache_erase_ok

)

Definition at line 179 of file cuckoocache_tests.cpp.

BOOST_AUTO_TEST_CASE() [2/5]

BOOST_AUTO_TEST_CASE

(

cuckoocache_erase_parallel_ok

)

Definition at line 266 of file cuckoocache_tests.cpp.

BOOST_AUTO_TEST_CASE() [3/5]

BOOST_AUTO_TEST_CASE

(

cuckoocache_generations

)

Definition at line 363 of file cuckoocache_tests.cpp.

BOOST_AUTO_TEST_CASE() [4/5]

BOOST_AUTO_TEST_CASE

(

cuckoocache_hit_rate_ok

)

Check the hit rate on loads ranging from 0.1 to 2.0.

Arbitrarily selected Hit Rate threshold that happens to work for this test as a lower bound on performance.

Definition at line 106 of file cuckoocache_tests.cpp.

Here is the call graph for this function:

BOOST_AUTO_TEST_CASE() [5/5]

BOOST_AUTO_TEST_CASE

(

test_cuckoocache_no_fakes

)

Definition at line 34 of file cuckoocache_tests.cpp.

BOOST_AUTO_TEST_SUITE()

BOOST_AUTO_TEST_SUITE

(

cuckoocache_tests

)

Test Suite for CuckooCache.

1) All tests should have a deterministic result (using insecure rand with deterministic seeds) 2) Some test methods are templated to allow for easier testing against new versions / comparing 3) Results should be treated as a regression test, ie, did the behavior 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 expected behavior. For example improving the hit rate may cause some tests using BOOST_CHECK_CLOSE to fail.

BOOST_AUTO_TEST_SUITE_END()

BOOST_AUTO_TEST_SUITE_END

(

)

normalize_hit_rate()

double normalize_hit_rate	(	double	hits,
		double	load
	)

The normalized hit rate for a given load.

The semantics are a little confusing, so please see the below explanation.

Examples:

1) at load 0.5, we expect a perfect hit rate, so we multiply by 1.0 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 normalized hit rate.

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 becomes effectively perfect, ignoring freshness.

Definition at line 100 of file cuckoocache_tests.cpp.

Here is the caller graph for this function:

test_cache()

template<typename Cache >

double test_cache	(	size_t	megabytes,
		double	load
	)

This helper returns the hit rate when megabytes*load worth of entries are inserted into a megabytes sized cache.

We make a copy of the hashes because future optimizations of the cuckoocache may overwrite the inserted element, so the test is "future proofed".

Do the insert

Count the hits

Definition at line 53 of file cuckoocache_tests.cpp.

test_cache_erase()

template<typename Cache >

void test_cache_erase

(

size_t

megabytes

)

This helper checks that erased elements are preferentially inserted onto and that the hit rate of "fresher" keys is reasonable.

We make a copy of the hashes because future optimizations of the cuckoocache may overwrite the inserted element, so the test is "future proofed".

Insert the first half

Erase the first quarter

Insert the second half

elements that we marked erased but that are still there

elements that we did not erase but are older

elements that were most recently inserted

Definition at line 123 of file cuckoocache_tests.cpp.

test_cache_erase_parallel()

template<typename Cache >

void test_cache_erase_parallel

(

size_t

megabytes

)

We make a copy of the hashes because future optimizations of the cuckoocache may overwrite the inserted element, so the test is "future proofed".

Grab lock to make sure we release inserts

Insert the first half

Spin up 3 threads to run contains with erase.

Erase the first quarter

Each thread is emplaced with x copy-by-value

Wait for all threads to finish

Grab lock to make sure we observe erases

Insert the second half

elements that we marked erased but that are still there

elements that we did not erase but are older

elements that were most recently inserted

Definition at line 186 of file cuckoocache_tests.cpp.

test_cache_generations()

template<typename Cache >

void test_cache_generations

(

)

Definition at line 274 of file cuckoocache_tests.cpp.