Assignment 6 - Templates - Autograder (W.I.P)

test_complexity.cpp

#include "papi.h"
#include "set.hpp"
#include <iostream>
#include <string>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <omp.h>
#include <cstdlib>
#include <functional>
#include <cassert>
#include <fstream>

template <typename SimpleSetImpl>
void test_simple_set(std::string fname, std::function<SimpleSetImpl(int)> createFn) {
    #pragma omp critical
    std::cout << "Running test for " << fname << " on thread #" << PAPI_thread_id() << std::endl;

    int eventset = PAPI_NULL;
    int ret = PAPI_create_eventset(&eventset);
    if (ret != PAPI_OK) {
        std::cerr << "PAPI could not create eventset!" << std::endl;
        exit(-1);
    }
    ret = PAPI_add_event(eventset, PAPI_TOT_INS);
    if (ret != PAPI_OK) {
        std::cerr << "PAPI could not add to eventset!" << std::endl;
        exit(-1);
    }

    std::ofstream fout(fname, std::ofstream::out | std::ofstream::trunc);

    long long insertInstrs, removeInstrs, containInstrs = 0;
    PAPI_start(eventset);
    
    std::srand(time(nullptr));

    int M = 1;
    int N = 1024 * 64;

    for (int n = M; n <= N; n += 10) {    
        SimpleSetImpl R = createFn(n);    
        std::vector<int> iterationSpace;
        for (int i = 0; i < n; i++) {
            iterationSpace.push_back(i);
        }
        #ifdef AUTOGRADER_RANDOMIZE_ITERATION
        std::random_shuffle(iterationSpace.begin(), iterationSpace.end());
        #endif
        // Insertion
        PAPI_reset(eventset);
        for(int i : iterationSpace) {
            R += i;
        }
        PAPI_read(eventset, &insertInstrs);

        // Contains
        PAPI_reset(eventset);
        for (int i : iterationSpace) {
            bool ret = R.contains(i);
            if (!ret) {
                fout << n << ", NaN, NaN, NaN" << std::endl;
                std::cerr << "Failed on " << fname << "! Contains(" << i << ")..." << std::endl;
                break;
            }
        }
        PAPI_read(eventset, &containInstrs);

        // Remove
        PAPI_reset(eventset);
        for (int i : iterationSpace) {
            R -= i;
        }
        PAPI_read(eventset, &removeInstrs);

        // Skip the first 1% as it appears to cause some weird outliers in the data, likely due to warmup of cache.
        // Weird thing is that we create a new object in each iteration of the loop, yet it is consistently bad.
        if (n < (N * 0.01)) continue;
        fout << n << ", " << insertInstrs / n << ", " << containInstrs / n << ", " << removeInstrs / n << std::endl;
    }
    
    PAPI_stop(eventset, &insertInstrs);
}

template <typename RangeSetImpl>
void test_range_set(std::string fname, std::function<RangeSetImpl(int)> createFn) {
    #pragma omp critical
    std::cout << "Running test for " << fname << " on thread #" << PAPI_thread_id() << std::endl;

    int eventset = PAPI_NULL;
    int ret = PAPI_create_eventset(&eventset);
    if (ret != PAPI_OK) {
        std::cerr << "PAPI could not create eventset!" << std::endl;
        exit(-1);
    }
    ret = PAPI_add_event(eventset, PAPI_TOT_INS);
    if (ret != PAPI_OK) {
        std::cerr << "PAPI could not add to eventset!" << std::endl;
        exit(-1);
    }

    std::ofstream fout(fname, std::ofstream::out | std::ofstream::trunc);
    long long insertInstrs, removeInstrs, containInstrs = 0;
    PAPI_start(eventset);
    
    std::srand(time(nullptr));

    int M = 1;
    int N = 1024;
    for (int n = M; n <= N; n += 1) {    
        RangeSetImpl R = createFn(n);    
        std::vector<int> iterationSpace;
        for (int i = 0; i < n; i++) {
            iterationSpace.push_back(i);
        }
        #ifdef AUTOGRADER_RANDOMIZE_ITERATION
        std::random_shuffle(iterationSpace.begin(), iterationSpace.end());
        #endif

        // Insertion
        PAPI_reset(eventset);
        for (int i : iterationSpace) {            
            R += range<int>(i * 64, true, (i + 1) * 64, false);
        }
        PAPI_read(eventset, &insertInstrs);

        // Contains
        PAPI_reset(eventset);
        for (int i : iterationSpace) {
            // Midpoint between ranges inserted above
            bool ret = R.contains((int) (i * 64 + (i + 1) * 64) / 2);
            if (!ret) {
                fout << n << ", NaN, NaN, NaN" << std::endl;
                std::cerr << "Failed on " << fname << "! Contains(" << (i * 64 + (i + 1) * 64) / 2 << ")..." << std::endl;
                break;
            }
        }
        PAPI_read(eventset, &containInstrs);

        // Remove
        PAPI_reset(eventset);
        for (int i : iterationSpace) {
            R -= range<int>(i * 64, true, (i + 1) * 64, false);
        }
        PAPI_read(eventset, &removeInstrs);

        // Skip the first 1% as it appears to cause some weird outliers in the data, likely due to warmup of cache.
        // Weird thing is that we create a new object in each iteration of the loop, yet it is consistently bad.
        if (n < (N * 0.01)) continue;
        fout << n << ", " << insertInstrs / n << ", " << containInstrs / n << ", " << removeInstrs / n << std::endl;
    }
    
    PAPI_stop(eventset, &insertInstrs);
}

int main(void) {
    PAPI_library_init(PAPI_VER_CURRENT);

    int ret = PAPI_thread_init([] (void) -> unsigned long { return omp_get_thread_num(); });
    if (ret != PAPI_OK) {
        std::cerr << "PAPI could not initialize thread support!" << std::endl;
        exit(-1);
    }
    // Bound the time for running these tests by running them in parallel.
    #pragma omp parallel sections
    {
        #pragma omp section
        {
            PAPI_register_thread();
            test_simple_set<std_simple_set<int>>("std_simple_set.dat", [] (int n) { return std_simple_set<int>(); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_range_set<std_range_set<int>>("std_range_set.dat", [] (int n) { return std_range_set<int>(); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_range_set<carray_range_set<int>>("carray_range_set.dat", [] (int n) { return carray_range_set<int>(0, n * 64 + 1); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_simple_set<carray_simple_set<int>>("carray_simple_set.dat", [] (int n) { return carray_simple_set<int>(0, n + 1); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_range_set<hashed_range_set<int>>("hashed_range_set.dat", [] (int n) { return hashed_range_set<int>(n + 1); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_simple_set<hashed_simple_set<int>>("hashed_simple_set.dat", [] (int n) { return hashed_simple_set<int>(2 * n); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_range_set<bin_search_range_set<int>>("bin_search_range_set.dat", [] (int n) { return bin_search_range_set<int>(n + 1); });
        }
        #pragma omp section
        {
            PAPI_register_thread();
            test_simple_set<bin_search_simple_set<int>>("bin_search_simple_set.dat", [] (int n) { return bin_search_simple_set<int>(n + 1); });
        }
    }
}

time_complexity_plotter.py

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

fig = plt.figure(figsize=(10, 4))
fig.subplots_adjust(hspace=0.4, wspace=0.4)
curr_row = 0

def plot(name):
    global curr_row
    xs = []
    ys = []
    zs = []
    ws = []
    with open(name + ".dat") as f:
        skipped = False
        for line in f.readlines():
            if skipped == False:
                skipped = True
                continue
            x,y,z,w = line.strip().split(',') 
            xs.append(int(x))
            ys.append(int(y))
            zs.append(int(z))
            ws.append(int(w))

    # Nothing? So slow that not even a _single_ iteration failed?!
    if len(xs) == 0:
        print(name + ".dat was empty!")
        return

    ax = fig.add_subplot(1,3, 1)
    ax.set_title(name + ".(+=)")
    ax.set_ylabel("Processor Instructions")
    ax.set_xlabel("Number of Operations")
    plt.plot(xs, ys)
    plt.ylim(int(min(ys) * 0.5), int(max(ys) * 1.5))
    ax2 = fig.add_subplot(1,3,2)
    ax2.set_title(name + ".contains")
    ax2.set_ylabel("Processor Instructions")
    ax2.set_xlabel("Number of Operations")
    plt.ylim(int(min(zs) * 0.5), int(max(zs) * 1.5))
    plt.plot(xs, zs)
    ax3 = fig.add_subplot(1,3,3)
    ax3.set_title(name + ".(-=)")
    ax3.set_ylabel("Processor Instructions")
    ax3.set_xlabel("Number of Operations")
    plt.ylim(int(min(ws) * 0.5), int(max(ws) * 1.5))
    plt.plot(xs, ws)
    plt.savefig(name + '.png')
    curr_row += 1
    fig.clf()


plot("std_simple_set")
plot("std_range_set")
plot("carray_simple_set")
plot("carray_range_set")
plot("bin_search_simple_set")
plot("bin_search_range_set")
plot("hashed_simple_set")
plot("hashed_range_set")

#plt.tight_layout()
plt.show()