Bitcoin Core  22.99.0
P2P Digital Currency
Functions
cuckoocache_tests.cpp File Reference
#include <cuckoocache.h>
#include <random.h>
#include <script/sigcache.h>
#include <test/util/setup_common.h>
#include <boost/test/unit_test.hpp>
#include <deque>
#include <mutex>
#include <shared_mutex>
#include <thread>
#include <vector>
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 >
static 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...
 
static 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 1.6. More...
 
template<typename Cache >
static 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 >
static void test_cache_erase_parallel (size_t megabytes)
 
 BOOST_AUTO_TEST_CASE (cuckoocache_erase_parallel_ok)
 
template<typename Cache >
static 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 180 of file cuckoocache_tests.cpp.

◆ BOOST_AUTO_TEST_CASE() [2/5]

BOOST_AUTO_TEST_CASE ( cuckoocache_erase_parallel_ok  )

Definition at line 269 of file cuckoocache_tests.cpp.

◆ BOOST_AUTO_TEST_CASE() [3/5]

BOOST_AUTO_TEST_CASE ( cuckoocache_generations  )

Definition at line 366 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 1.6.

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

Definition at line 107 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 36 of file cuckoocache_tests.cpp.

Here is the call graph for this function:

◆ 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, i.e., 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()

static double normalize_hit_rate ( double  hits,
double  load 
)
static

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 101 of file cuckoocache_tests.cpp.

Here is the caller graph for this function:

◆ test_cache()

template<typename Cache >
static double test_cache ( size_t  megabytes,
double  load 
)
static

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 54 of file cuckoocache_tests.cpp.

Here is the call graph for this function:

◆ test_cache_erase()

template<typename Cache >
static void test_cache_erase ( size_t  megabytes)
static

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 as erased but are still there

elements that we did not erase but are older

elements that were most recently inserted

Definition at line 124 of file cuckoocache_tests.cpp.

Here is the call graph for this function:

◆ test_cache_erase_parallel()

template<typename Cache >
static void test_cache_erase_parallel ( size_t  megabytes)
static

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 187 of file cuckoocache_tests.cpp.

Here is the call graph for this function:

◆ test_cache_generations()

template<typename Cache >
static void test_cache_generations ( )
static

Definition at line 277 of file cuckoocache_tests.cpp.

Here is the call graph for this function: