#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cfloat>

double timer(int *arr, int size, int times_o, int times_z) {
    double result = DBL_MAX, temp_result;

    union ticks {
        unsigned long long t64;
        struct s32 {
            long th, tl;
        } t32;
    } start, end;

    //"pre-heating" the cache
    for (int k = 0, j = 0; j < size; j++)
        k = arr[k];


    for (int i = 0; i < times_z; i++) {

        asm("rdtsc\n":"=a"(start.t32.th), "=d"(start.t32.tl));

        for (int k = 0, j = 0; j < size * times_o; j++)
            k = arr[k];

        asm("rdtsc\n":"=a"(end.t32.th), "=d"(end.t32.tl));

        temp_result = (end.t64 - start.t64) / (double) size / times_o;
        if (temp_result < result)
            result = temp_result;
    }

    return result;
}

int *get_direct_array(int size) {
    int *arr = (int *) malloc(size * sizeof(int));

    for (int j = 0; j < size - 1; j++)
        arr[j] = j + 1;
    arr[size - 1] = 0;

    return arr;
}

int *get_reversed_array(int size) {
    int *arr = (int *) malloc(size * sizeof(int));

    for (int j = 0; j < size; j++)
        arr[j] = j - 1;
    arr[0] = size - 1;

    return arr;
}

int *get_random_array(int size) {
    int *arr = (int *) malloc(size * sizeof(int));
    int l, temp;

    srand(time(NULL));

    for (int j = 0; j < size; j++)
        arr[j] = j;

    for (int j = size - 1; j > 0; j--) {
        l = rand() % j;
        temp = arr[l];
        arr[l] = arr[j];
        arr[j] = temp;
    }

    return arr;
}

int main() {
    int size, step;
    int *arr;

    FILE * file = fopen("test.csv", "w");

    const int ATTEMPTS_TO_MEASURE = 10;//10;
    const int ATTEMPTS_TO_PASS = 5;//5;



    const size_t kb1_step = 1024 * 1 / sizeof(int);
    const size_t kb4_step = 1024 * 4 / sizeof(int);
    const size_t kb16_step = 1024 * 32 / sizeof(int);
    const size_t kb128_step = 1024 * 128 / sizeof(int);
    const size_t kb256_step = 1024 * 256 / sizeof(int);

    const size_t kb32 = 1024 * 32 / sizeof(int);//32 KB
    const size_t kb256 = 1024 * 256 / sizeof(int);//256 KB
    const size_t kb8192 = 1024 * 8192 / sizeof(int);//8192 KB

    size = kb4_step;
    while (size <= kb8192){

        if (kb32*4<=size && size<=kb256){
            size+= kb4_step*2;
        }
        else
            size += size/100 + size/1000;
        //size += kb32/100; //8192

        if (size < 1024)
            fprintf(file, "%lf, ", (double) size / 1024 * 4);
        else
            fprintf(file, "%d, ", size / 1024 *4);
        //fprintf(file,"%d, ", size*4);
        arr = get_direct_array(size);
        fprintf(file,"%lf, ", timer(arr, size, ATTEMPTS_TO_PASS, ATTEMPTS_TO_MEASURE));
        free(arr);

        arr = get_reversed_array(size);
        fprintf(file, "%lf, ", timer(arr, size, ATTEMPTS_TO_PASS, ATTEMPTS_TO_MEASURE));
        free(arr);

        arr = get_random_array(size);
        fprintf(file, "%lf\n", timer(arr, size, ATTEMPTS_TO_PASS, ATTEMPTS_TO_MEASURE));
        free(arr);

    }

    fclose(file);
    return 0;
}