Function test_cache_generations

src/test/cuckoocache_tests.cpp:286–374

template <typename Cache>
static void test_cache_generations()
{
    // 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
    // 99.9% are less than 1% of the time.
    double min_hit_rate = 0.99;
    double tight_hit_rate = 0.999;
    double max_rate_less_than_tight_hit_rate = 0.01;
    // A cache that meets this specification is therefore shown to have a hit
    // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) +
    // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89%
    // hit rate with low variance.

    // We use deterministic values, but this test has also passed on many
    // iterations with non-deterministic values, so it isn't "overfit" to the
    // specific entropy in FastRandomContext(true) and implementation of the
    // cache.
    local_rand_ctx = FastRandomContext(true);

    // 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
    // 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
    // immediately and never uses the other half.
    struct block_activity {
        std::vector<uint256> reads;
        block_activity(uint32_t n_insert, Cache& c) : reads()
        {
            std::vector<uint256> inserts;
            inserts.resize(n_insert);
            reads.reserve(n_insert / 2);
            for (uint32_t i = 0; i < n_insert; ++i) {
                uint32_t* ptr = (uint32_t*)inserts[i].begin();
                for (uint8_t j = 0; j < 8; ++j)
                    *(ptr++) = local_rand_ctx.rand32();
            }
            for (uint32_t i = 0; i < n_insert / 4; ++i)
                reads.push_back(inserts[i]);
            for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
                reads.push_back(inserts[i]);
            for (auto h : inserts)
                c.insert(h);
        }
    };

    const uint32_t BLOCK_SIZE = 1000;
    // We expect window size 60 to perform reasonably given that each epoch
    // stores 45% of the cache size (~472k).
    const uint32_t WINDOW_SIZE = 60;
    const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
    const double load = 10;
    const size_t megabytes = 4;
    const size_t bytes = megabytes * (1 << 20);
    const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));

    std::vector<block_activity> hashes;
    Cache set{};
    set.setup_bytes(bytes);