aboutsummaryrefslogtreecommitdiff
path: root/lab6_malloclab/fcyc.c
diff options
context:
space:
mode:
Diffstat (limited to 'lab6_malloclab/fcyc.c')
-rw-r--r--lab6_malloclab/fcyc.c251
1 files changed, 251 insertions, 0 deletions
diff --git a/lab6_malloclab/fcyc.c b/lab6_malloclab/fcyc.c
new file mode 100644
index 0000000..7b62622
--- /dev/null
+++ b/lab6_malloclab/fcyc.c
@@ -0,0 +1,251 @@
+/*
+ * fcyc.c - Estimate the time (in CPU cycles) used by a function f
+ *
+ * Copyright (c) 2002, R. Bryant and D. O'Hallaron, All rights reserved.
+ * May not be used, modified, or copied without permission.
+ *
+ * Uses the cycle timer routines in clock.c to estimate the
+ * the time in CPU cycles for a function f.
+ */
+#include <stdlib.h>
+#include <sys/times.h>
+#include <stdio.h>
+
+#include "fcyc.h"
+#include "clock.h"
+
+/* Default values */
+#define K 3 /* Value of K in K-best scheme */
+#define MAXSAMPLES 20 /* Give up after MAXSAMPLES */
+#define EPSILON 0.01 /* K samples should be EPSILON of each other*/
+#define COMPENSATE 0 /* 1-> try to compensate for clock ticks */
+#define CLEAR_CACHE 0 /* Clear cache before running test function */
+#define CACHE_BYTES (1<<19) /* Max cache size in bytes */
+#define CACHE_BLOCK 32 /* Cache block size in bytes */
+
+static int kbest = K;
+static int maxsamples = MAXSAMPLES;
+static double epsilon = EPSILON;
+static int compensate = COMPENSATE;
+static int clear_cache = CLEAR_CACHE;
+static int cache_bytes = CACHE_BYTES;
+static int cache_block = CACHE_BLOCK;
+
+static int *cache_buf = NULL;
+
+static double *values = NULL;
+static int samplecount = 0;
+
+/* for debugging only */
+#define KEEP_VALS 0
+#define KEEP_SAMPLES 0
+
+#if KEEP_SAMPLES
+static double *samples = NULL;
+#endif
+
+/*
+ * init_sampler - Start new sampling process
+ */
+static void init_sampler()
+{
+ if (values)
+ free(values);
+ values = (double*) calloc(kbest, sizeof(double));
+#if KEEP_SAMPLES
+ if (samples)
+ free(samples);
+ /* Allocate extra for wraparound analysis */
+ samples = calloc(maxsamples+kbest, sizeof(double));
+#endif
+ samplecount = 0;
+}
+
+/*
+ * add_sample - Add new sample
+ */
+static void add_sample(double val)
+{
+ int pos = 0;
+ if (samplecount < kbest) {
+ pos = samplecount;
+ values[pos] = val;
+ } else if (val < values[kbest-1]) {
+ pos = kbest-1;
+ values[pos] = val;
+ }
+#if KEEP_SAMPLES
+ samples[samplecount] = val;
+#endif
+ samplecount++;
+ /* Insertion sort */
+ while (pos > 0 && values[pos-1] > values[pos]) {
+ double temp = values[pos-1];
+ values[pos-1] = values[pos];
+ values[pos] = temp;
+ pos--;
+ }
+}
+
+/*
+ * has_converged- Have kbest minimum measurements converged within epsilon?
+ */
+static int has_converged()
+{
+ return
+ (samplecount >= kbest) &&
+ ((1 + epsilon)*values[0] >= values[kbest-1]);
+}
+
+/*
+ * clear - Code to clear cache
+ */
+static volatile int sink = 0;
+
+static void clear()
+{
+ int x = sink;
+ int *cptr, *cend;
+ int incr = cache_block/sizeof(int);
+ if (!cache_buf) {
+ cache_buf = (int *) malloc(cache_bytes);
+ if (!cache_buf) {
+ fprintf(stderr, "Fatal error. Malloc returned null when trying to clear cache\n");
+ exit(1);
+ }
+ }
+ cptr = (int *) cache_buf;
+ cend = cptr + cache_bytes/sizeof(int);
+ while (cptr < cend) {
+ x += *cptr;
+ cptr += incr;
+ }
+ sink = x;
+}
+
+/*
+ * fcyc - Use K-best scheme to estimate the running time of function f
+ */
+double fcyc(test_funct f, void *argp)
+{
+ double result;
+ init_sampler();
+ if (compensate) {
+ do {
+ double cyc;
+ if (clear_cache)
+ clear();
+ start_comp_counter();
+ f(argp);
+ cyc = get_comp_counter();
+ add_sample(cyc);
+ } while (!has_converged() && samplecount < maxsamples);
+ } else {
+ do {
+ double cyc;
+ if (clear_cache)
+ clear();
+ start_counter();
+ f(argp);
+ cyc = get_counter();
+ add_sample(cyc);
+ } while (!has_converged() && samplecount < maxsamples);
+ }
+#ifdef DEBUG
+ {
+ int i;
+ printf(" %d smallest values: [", kbest);
+ for (i = 0; i < kbest; i++)
+ printf("%.0f%s", values[i], i==kbest-1 ? "]\n" : ", ");
+ }
+#endif
+ result = values[0];
+#if !KEEP_VALS
+ free(values);
+ values = NULL;
+#endif
+ return result;
+}
+
+
+/*************************************************************
+ * Set the various parameters used by the measurement routines
+ ************************************************************/
+
+/*
+ * set_fcyc_clear_cache - When set, will run code to clear cache
+ * before each measurement.
+ * Default = 0
+ */
+void set_fcyc_clear_cache(int clear)
+{
+ clear_cache = clear;
+}
+
+/*
+ * set_fcyc_cache_size - Set size of cache to use when clearing cache
+ * Default = 1<<19 (512KB)
+ */
+void set_fcyc_cache_size(int bytes)
+{
+ if (bytes != cache_bytes) {
+ cache_bytes = bytes;
+ if (cache_buf) {
+ free(cache_buf);
+ cache_buf = NULL;
+ }
+ }
+}
+
+/*
+ * set_fcyc_cache_block - Set size of cache block
+ * Default = 32
+ */
+void set_fcyc_cache_block(int bytes) {
+ cache_block = bytes;
+}
+
+
+/*
+ * set_fcyc_compensate- When set, will attempt to compensate for
+ * timer interrupt overhead
+ * Default = 0
+ */
+void set_fcyc_compensate(int compensate_arg)
+{
+ compensate = compensate_arg;
+}
+
+/*
+ * set_fcyc_k - Value of K in K-best measurement scheme
+ * Default = 3
+ */
+void set_fcyc_k(int k)
+{
+ kbest = k;
+}
+
+/*
+ * set_fcyc_maxsamples - Maximum number of samples attempting to find
+ * K-best within some tolerance.
+ * When exceeded, just return best sample found.
+ * Default = 20
+ */
+void set_fcyc_maxsamples(int maxsamples_arg)
+{
+ maxsamples = maxsamples_arg;
+}
+
+/*
+ * set_fcyc_epsilon - Tolerance required for K-best
+ * Default = 0.01
+ */
+void set_fcyc_epsilon(double epsilon_arg)
+{
+ epsilon = epsilon_arg;
+}
+
+
+
+
+