09_cachedetect

09_cachedetect.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <time.h>
#include <unistd.h>

#define KB (1024 * sizeof(char))
#define MB (1024 * KB)
#define STACK_LIMIT 

#define CYCLE_COUNT 16
#define DATA_FILE_STACK "data.stack"
#define DATA_FILE_HEAP "data.heap"

struct chain_link {
  struct chain_link *next_link;
};

long get_curr_stack_limit() {
  struct rlimit l;
  getrlimit(RLIMIT_STACK, &l);

  return l.rlim_cur;
}

void begin_profiling(struct tms *t_start) {
  if (times(t_start) == ((clock_t)-1)) {
    fprintf(stderr, "**Error** while getting start time;\n");
    exit(1);
  }
}

double end_profiling_and_get_elapsed_nanosecs(struct tms *t_start, struct tms *t_end) {
  if (times(t_end) == ((clock_t)-1)) {
    fprintf(stderr, "**Error** while getting end time;\n");
    exit(1);
  }

// _SC_CLK_TCK: The frequency of the statistics clock in ticks per second.
#ifndef CLK_TCK
  int CLK_TCK = sysconf(_SC_CLK_TCK);
#endif

  clock_t ticks = t_end->tms_utime - t_start->tms_utime;
  double nanosec = (double)ticks / CLK_TCK * 10E9;

  return nanosec;
}

void fisher_yates_shuffle(long n, long a[]) {
  srand(time(NULL));
  
  for (long i = 0; i < n - 1; i++) {
    long j = i + rand() / (RAND_MAX / (n - i) + 1);
    
    long t = a[j];
    a[j] = a[i];
    a[i] = t;
  }
}

struct chain_link *initialize_and_shuffle_chain(long chain_length, struct chain_link links[]) {
  long *idcs = malloc(chain_length * sizeof(long)); 
  for(int i = 0; i < chain_length; i++) {
    idcs[i] = i;

    links[i].next_link = NULL;
  }

  fisher_yates_shuffle(chain_length, idcs);

  struct chain_link *first_link = &links[idcs[0]];

  struct chain_link *last_link = &links[idcs[chain_length - 1]];
  last_link->next_link = first_link;

  int i, prev_idx, curr_idx;
  for (i = 0; i < chain_length - 1; i++) {
    prev_idx = idcs[i];
    curr_idx = idcs[i + 1];
    links[prev_idx].next_link = &links[curr_idx];
  }

  free(idcs);
  return first_link;
}

void cycle_chain(struct chain_link *first_link) {

    int n_cycle;
    struct chain_link *l;
    for (n_cycle = 0, l = first_link; n_cycle < CYCLE_COUNT; l = l->next_link) {
      if (l->next_link == first_link)
        n_cycle++;
    }
}

double profile_array_access(long chain_length, struct chain_link links[]) {
    struct tms t_start, t_end;

    struct chain_link *first_link = initialize_and_shuffle_chain(chain_length, links);
    if (first_link == NULL) {
      fprintf(stderr, "**Error** during chain building\n");
      exit(1);
    }

    begin_profiling(&t_start);
    cycle_chain(first_link);
    
    double nanosecs = end_profiling_and_get_elapsed_nanosecs(&t_start, &t_end);
    return nanosecs; 
}

int main(int argc, char *argv[]) {
  long stack_limit = get_curr_stack_limit();
 
  FILE *f_stack = fopen(DATA_FILE_STACK, "w");
  FILE *f_heap = fopen(DATA_FILE_HEAP, "w");

  for (long memory_limit = 1 * KB; memory_limit < stack_limit; memory_limit += 250 * KB) {
    long chain_length = memory_limit / sizeof(struct chain_link);
   
    // Profile on stack
    struct chain_link links_on_stack[chain_length];
    double elapsed_ns_stack = profile_array_access(chain_length, links_on_stack);
   
    // Profile on heap
    struct chain_link *links_on_heap = malloc(chain_length * sizeof(struct chain_link));
    double elapsed_ns_heap = profile_array_access(chain_length, links_on_heap);
    free(links_on_heap);

    fprintf(f_stack, "%f\t%f\n", (double)chain_length, elapsed_ns_stack);
    fprintf(f_heap, "%f\t%f\n", (double)chain_length, elapsed_ns_heap);

    fprintf(stderr, "Status: %0.2f %%\n", ((double)memory_limit / (double)stack_limit) * 100.0);
  }

  fclose(f_stack);
  fclose(f_heap);

  return 0;
}