burnit.cpp

// ---------------------------------------------------------------------------
// burnit.cpp
// author: David Ryan
// ---------------------------------------------------------------------------

#include <chrono>
#include <ctime>
#include <iostream>
#include <bitset>
#include <map>
#include <cstring>
#include <cmath>
#include <vector>
#include <thread>
#include <memory>

using namespace std;
using namespace std::chrono;

const uint64_t DEFAULT_UPPER_LIMIT = 10'000'000LLU;

class BitArray
{
    uint32_t *array;
    size_t arrSize;

    inline static size_t arraySize(size_t size)
    {
        return (size >> 5) + ((size & 31) > 0);
    }

    inline static size_t index(size_t n)
    {
        return (n >> 5);
    }

    inline static uint32_t getSubindex(size_t n, uint32_t d)
    {
        return d & uint32_t(uint32_t(0x01) << (n % 32));
    }

    inline void setFalseSubindex(size_t n, uint32_t &d)
    {
        d &= ~uint32_t(uint32_t(0x01) << (n % (8 * sizeof(uint32_t))));
    }

public:
    explicit BitArray(size_t size) : arrSize(size)
    {
        array = new uint32_t[arraySize(size)];
        std::memset(array, 0xFF, (size >> 3) + ((size & 7) > 0));
    }

    ~BitArray() { delete[] array; }

    bool get(size_t n) const
    {
        return getSubindex(n, array[index(n)]);
    }

    static constexpr uint32_t rol(uint32_t x, uint32_t n)
    {
        return (x << n) | (x >> (32 - n));
    }

    void setFlagsFalse(size_t n, size_t skip)
    {
        auto rolling_mask = ~uint32_t(1 << n % 32);
        auto roll_bits = skip % 32;
        while (n < arrSize)
        {
            array[index(n)] &= rolling_mask;
            n += skip;
            rolling_mask = rol(rolling_mask, roll_bits);
        }
    }

    inline size_t size() const { return arrSize; }
};

// prime_sieve
//
// Represents the data comprising the sieve (an array of N bits, where N is the upper limit prime being tested)
// as well as the code needed to eliminate non-primes from its array, which you perform by calling runSieve.

class prime_sieve
{
private:
    BitArray Bits; // Sieve data, where 1==prime, 0==not

public:
    prime_sieve(uint64_t n) : Bits(n) // Initialize all to true (potential primes)
    {
    }

    ~prime_sieve()
    {
    }

    // runSieve
    //
    // Scan the array for the next factor (>2) that hasn't yet been eliminated from the array, and then
    // walk through the array crossing off every multiple of that factor.

    void runSieve()
    {
        uint64_t factor = 3;
        uint64_t q = (int)sqrt(Bits.size());

        while (factor <= q)
        {
            for (uint64_t num = factor; num < Bits.size(); num += 2)
            {
                if (Bits.get(num))
                {
                    factor = num;
                    break;
                }
            }
            Bits.setFlagsFalse(factor * factor, factor + factor);

            factor += 2;
        }
    }

    void printResults(double duration, size_t passes, size_t threads) const
    {

        cout << "==========" << "\n"
        << "COMPLEATED" << "\n"
        << "==========" << "\n"
        << "Passes: " << passes << ", "
             << "Threads: " << threads << ", "
             << "Time: " << duration << ", "
             << "Average: " << duration / passes  << ", "
             << "Limit: " << Bits.size()
             << "\n";
    }
};

int main(int argc, char **argv)
{
    vector<string> args(argv + 1, argv + argc); // From first to last argument in the argv array
    uint64_t ullLimitRequested = 0;
    auto cThreadsRequested = 0;
    auto cSecondsRequested = 0;
    auto keepGoing = false;

    // Process command-line args

    for (auto i = args.begin(); i != args.end(); ++i)
    {
        if (*i == "-h" || *i == "--help")
        {
            cout << "Syntax: " << argv[0] << " [-t,--threads threads] [-s,--seconds seconds] [-l,--limit limit] [-k,-keepgoing] [-h] " << endl;
            return 0;
        }
        else if (*i == "-t" || *i == "--threads")
        {
            i++;
            cThreadsRequested = (i == args.end()) ? 0 : max(1, atoi(i->c_str()));
        }
        else if (*i == "-s" || *i == "--seconds")
        {
            i++;
            cSecondsRequested = (i == args.end()) ? 0 : max(1, atoi(i->c_str()));
        }
        else if (*i == "-l" || *i == "--limit")
        {
            i++;
            ullLimitRequested = (i == args.end()) ? 0LL : max((long long)1, atoll(i->c_str()));
        }
        else if (*i == "-k" || *i == "--keepgoing")
        {
            keepGoing = true;
        }
        else
        {
            fprintf(stderr, "Unknown argument: %s", i->c_str());
            return 0;
        }
    }

    auto cPasses = 0;
    auto cSeconds = (cSecondsRequested ? cSecondsRequested : 5);
    auto cThreads = (cThreadsRequested ? cThreadsRequested : thread::hardware_concurrency());
    auto llUpperLimit = (ullLimitRequested ? ullLimitRequested : DEFAULT_UPPER_LIMIT);

    if (keepGoing)
    {
        printf("Computing primes to %llu on %d thread%s until exited with ^c (ctrl c).\n",
               (unsigned long long)llUpperLimit,
               cThreads,
               cThreads == 1 ? "" : "s");
    }
    else
    {

        printf("Computing primes to %llu on %d thread%s for %d second%s.\n",
               (unsigned long long)llUpperLimit,
               cThreads,
               cThreads == 1 ? "" : "s",
               cSeconds,
               cSeconds == 1 ? "" : "s");
    }
    double duration;

    auto tStart = steady_clock::now();
    std::thread threads[cThreads];
    uint64_t l_passes[cThreads];
    for (unsigned int i = 0; i < cThreads; i++)
        threads[i] = std::thread([i, keepGoing, cSeconds, &l_passes, &tStart](size_t llUpperLimit)
                                 {
                                     l_passes[i] = 0;
                                     if (keepGoing)
                                     {
                                         while (true)
                                         {
                                             prime_sieve(llUpperLimit).runSieve();
                                             ++l_passes[i];
                                         }
                                     }
                                     else
                                     {
                                         while (duration_cast<seconds>(steady_clock::now() - tStart).count() < cSeconds)
                                         {
                                             prime_sieve(llUpperLimit).runSieve();
                                             ++l_passes[i];
                                         }
                                     }
                                 },
                                 llUpperLimit);
    for (auto i = 0; i < cThreads; i++)
    {
        threads[i].join();
        cPasses += l_passes[i];
    }
    auto tEnd = steady_clock::now() - tStart;
    duration = duration_cast<microseconds>(tEnd).count() / 1000000.0;

    prime_sieve checkSieve(llUpperLimit);

    checkSieve.runSieve();

    checkSieve.printResults(duration, cPasses, cThreads);

    return 0;
}