core/performance/Main.cpp

#include "data/HashMap.hpp"
#include "data/ProbingHashMap.hpp"
#include "test/Test.hpp"
#include "utils/Clock.hpp"
#include "utils/Random.hpp"

using Millis = Core::Clock::Nanos;

struct Timer {
    Core::Clock::Nanos nanos;

    Timer() {
        CORE_TEST_ERROR(Core::Clock::getNanos(nanos));
    }

    Core::Clock::Nanos get() const {
        Core::Clock::Nanos nanos2 = 0;
        CORE_TEST_ERROR(Core::Clock::getNanos(nanos2));
        return nanos2 - nanos;
    }
};

template<typename Map>
static Core::Clock::Nanos testSearch(const Map& m) {
    Timer t;
    volatile int sum = 0;
    for(int i = 0; i < 10000; i++) {
        for(int k = -5000; k < 5000; k++) {
            const int* s = m.search(i + k);
            if(s != nullptr) {
                sum = sum + *s;
            }
        }
    }
    return t.get();
}

template<typename Map>
static Core::Clock::Nanos testEmptySearch(const Map& m) {
    Timer t;
    volatile int sum = 0;
    for(int i = 0; i < 100'000'000; i++) {
        const int* s = m.search(-i);
        if(s != nullptr) {
            sum = sum + *s;
        }
    }
    return t.get();
}

template<typename Map>
static void fillOrder(Map& m) {
    for(int i = 0; i < 10000; i++) {
        CORE_TEST_ERROR(m.add(i, i * i));
    }
}

template<typename Map>
static void fillChaos(Map& m) {
    Core::Random random(0);
    for(int i = 0; i < 10000; i++) {
        int r = random.next(0, 9999);
        CORE_TEST_ERROR(m.add(r, r * r));
    }
}

template<typename Map>
static Millis average(Map& m, Core::Clock::Nanos (*f)(const Map&), int n) {
    Core::Clock::Nanos sum = 0;
    for(int i = 0; i < n; i++) {
        sum += f(m);
    }
    return sum / (n * 1'000'000);
}

static void order(int n) {
    Core::HashMap<int, int> m;
    Core::ProbingHashMap<int, int> m2;
    fillOrder(m);
    fillOrder(m2);
    CORE_LOG_INFO("Order Chaining | Order Probing");
    CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
                  average(m2, testSearch, n));
    CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
                  average(m2, testEmptySearch, n));
}

static void chaos(int n) {
    Core::HashMap<int, int> m;
    Core::ProbingHashMap<int, int> m2;
    fillChaos(m);
    fillChaos(m2);
    CORE_LOG_INFO("Order Chaining | Order Probing");
    CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
                  average(m2, testSearch, n));
    CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
                  average(m2, testEmptySearch, n));
}

static void testProbing(int n) {
    Core::ProbingHashMap<int, int> m;
    Core::ProbingHashMap<int, int> m2;
    fillOrder(m);
    fillChaos(m2);
    CORE_LOG_INFO("Order | Chaos");
    CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
                  average(m2, testSearch, n));
    CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
                  average(m2, testEmptySearch, n));
}

int main() {
    (void)order;
    (void)chaos;
    (void)testProbing;
    order(3);
    chaos(3);
    // testProbing(3);
    Core::Test::finalize();
    return 0;
}