primes benchmark

primes_benchmark.cc

// clang++ -Wall -std=c++11 primes_benchmark.cc -o primes_benchmark -O3 && ./primes_benchmark

#include <cassert>
#include <chrono>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <utility>

template <typename T>
class PrimesGenerator
{
public:
    virtual bool isPrime(const T& n) = 0;
};

template <typename T>
class TrialDivisonPrimesGenerator : public PrimesGenerator<T>
{

    std::unordered_set<T> primes;
    T maxN;

public:
    TrialDivisonPrimesGenerator()
        : primes({2})
        , maxN(2)
    {
    }

    virtual bool isPrime(const T& n) override
    {
        if (n <= maxN)
        {
            return primes.find(n) != primes.end();
        }

        maxN = n;
        primes.reserve(maxN);

        for (T i = 2; i * i <= n; ++i)
        {
            if (n % i == 0)
            {
                return false;
            }
        }

        primes.insert(n);
        return true;
    }

};

template <typename T>
class SievePrimesGenerator : public PrimesGenerator<T>
{

    std::unordered_set<T> primes;
    T maxN;

public:
    SievePrimesGenerator()
        : maxN(0)
    {
    }

    virtual bool isPrime(const T& n) override
    {
        if (n > maxN)
        {
            initPrimesWithSieve(n);
        }
        return primes.find(n) != primes.end();
    }

private:
    void initPrimesWithSieve(const T n)
    {
        maxN = n;

        std::unordered_set<T> sieve;
        sieve.reserve(maxN);

        primes.reserve(maxN);

        for (T i = 2; i <= n; ++i)
        {
            if (sieve.find(i) == sieve.end())
            {
                for (T j = i * i; j <= n; j += i)
                {
                    sieve.insert(j);
                }

                primes.insert(i);
            }
        }
    }

};

template <typename T>
void testGenerator(PrimesGenerator<T>& generator)
{
    assert(generator.isPrime(0) == false);
    assert(generator.isPrime(1) == false);
    assert(generator.isPrime(2) == true);
    assert(generator.isPrime(3) == true);
    assert(generator.isPrime(4) == false);
    assert(generator.isPrime(5) == true);
    assert(generator.isPrime(6) == false);
    assert(generator.isPrime(7) == true);
    assert(generator.isPrime(8) == false);
    assert(generator.isPrime(9) == false);
    assert(generator.isPrime(10) == false);
    assert(generator.isPrime(11) == true);
    assert(generator.isPrime(12) == false);
    assert(generator.isPrime(13) == true);
    assert(generator.isPrime(14) == false);
    assert(generator.isPrime(999983) == true);
    assert(generator.isPrime(999982) == false);
}

template <typename T>
void testCompareTwoGenerators(PrimesGenerator<T>& a, PrimesGenerator<T>& b, T maxN)
{
    for (T n = 0; n <= maxN; ++n)
    {
        assert(a.isPrime(n) == b.isPrime(n));
    }
}

template <typename T>
using TestCase = std::pair<std::string, std::function<void(PrimesGenerator<T>&)>>;

template <typename T>
void benchmarkTest(PrimesGenerator<T>& generator, const TestCase<T>& testCase)
{
    std::cout << "  Running benchmark \"" << testCase.first << "\"... ";
    std::cout.flush();

    const auto startTime = std::chrono::high_resolution_clock::now();

    testCase.second(generator);

    const auto endTime = std::chrono::high_resolution_clock::now();
    const auto deltaTime = endTime - startTime;
    const auto deltaTimeMs = std::chrono::duration_cast<std::chrono::milliseconds>(deltaTime).count();

    std::cout << deltaTimeMs << " ms" << std::endl;
}

template <typename T>
void runSanityTests(const T n)
{
    std::cout << " Running sanity checks ... ";
    std::cout.flush();

    {
        TrialDivisonPrimesGenerator<T> trialDivisonGen;
        testGenerator<T>(trialDivisonGen);
    }
    {
        SievePrimesGenerator<T> sieveGen;
        testGenerator<T>(sieveGen);
    }
    {
        TrialDivisonPrimesGenerator<T> trialDivisonGen;
        SievePrimesGenerator<T> sieveGen;
        testCompareTwoGenerators<T>(trialDivisonGen, sieveGen, n);
    }

    std::cout << "ok" << std::endl;
}

template <typename T>
void runBenchmarkTests(const T n)
{
    const std::vector<TestCase<T>> testCases = {
        std::make_pair(
            "n .. 1",
            [=](PrimesGenerator<T>& generator)
            {
                for (T i = n; i >= 1; --i)
                {
                    volatile bool x = generator.isPrime(i);
                    (void) x;
                }
            }
        )/*,
        std::make_pair(
            "1 .. n",
            [=](PrimesGenerator<T>& generator)
            {
                for (T i = 1; i <= n; ++i)
                {
                    volatile bool x = generator.isPrime(i);
                    (void) x;
                }
            }
        )*/
    };

    std::cout << " TrialDivisonPrimesGenerator" << std::endl;
    for (const auto& t : testCases)
    {
        TrialDivisonPrimesGenerator<T> trialDivisonGen;
        benchmarkTest<T>(trialDivisonGen, t);
    }

    std::cout << " SievePrimesGenerator" << std::endl;
    for (const auto& t : testCases)
    {
        SievePrimesGenerator<T> sieveGen;
        benchmarkTest<T>(sieveGen, t);
    }
}

template <typename T>
void runAllTests()
{
    for (const T& n: {1000, 10000, 100000, 1000000})
    {
        std::cout << "n=" << n << std::endl;

        //runSanityTests<T>(n);
        runBenchmarkTests<T>(n);

        std::cout << std::endl;
    }
}

int main()
{
    runAllTests<int64_t>();
    return 0;
}