Last active
December 29, 2018 16:17
-
-
Save gnuvince/10bebabb464e6d6b8e9bac189ae3bedc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <err.h> | |
#include <inttypes.h> | |
#include <stdint.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <sys/time.h> | |
#define CACHE_LINES 64 | |
const char *PROG_NAME; | |
void usage(void) { | |
fprintf(stderr, | |
"usage: %s <array-fast | array-slow | linked-list> <size>\n", | |
PROG_NAME); | |
exit(1); | |
} | |
/* Get current time in micro-seconds */ | |
int64_t timestamp(void) { | |
struct timeval tv; | |
if (gettimeofday(&tv, NULL) != 0) | |
errx(1, "gettimeofday"); | |
return tv.tv_sec * 1000000 + tv.tv_usec; | |
} | |
/* Caller responsible for calling `free()`. */ | |
int64_t* array_init(size_t size) { | |
int64_t t1 = timestamp(); | |
int64_t *elems; | |
/* Initialize an array [1, 2, 1, 2, 1, 2, ...] of length `size`. */ | |
{ | |
elems = malloc(sizeof(*elems) * size); | |
if (elems == NULL) | |
errx(1, "malloc"); | |
for (size_t i = 0; i < size; ++i) { | |
elems[i] = 1 + (i % 2); | |
} | |
} | |
int64_t t2 = timestamp(); | |
fprintf(stderr, "initialization: %" PRId64 " us\n", t2-t1); | |
return elems; | |
} | |
void array_fast(size_t size) { | |
int64_t *elems = array_init(size); | |
/* Compute sum element-by-element sequentially. */ | |
{ | |
int64_t t1 = timestamp(); | |
int64_t sum = 0; | |
for (size_t i = 0; i < size; ++i) | |
sum += elems[i]; | |
int64_t t2 = timestamp(); | |
fprintf(stderr, "sum (%" PRId64 "): %" PRId64 " us\n", sum, t2-t1); | |
} | |
free(elems); | |
} | |
void array_slow(size_t size) { | |
int64_t *elems = array_init(size); | |
/* Compute sum element-by-element, but with cache-line-sized gaps | |
* between array accesses. */ | |
{ | |
int64_t t1 = timestamp(); | |
int64_t sum = 0; | |
for (size_t j = 0; j < CACHE_LINES; ++j) | |
for (size_t i = j; i < size; i += CACHE_LINES) | |
sum += elems[i]; | |
int64_t t2 = timestamp(); | |
fprintf(stderr, "sum (%" PRId64 "): %" PRId64 " us\n", sum, t2-t1); | |
} | |
free(elems); | |
} | |
void linked_list(size_t size) { | |
} | |
int main(int argc, char **argv) { | |
PROG_NAME = argv[0]; | |
if (argc < 3) | |
usage(); | |
size_t size = atoll(argv[2]); | |
if (strcmp(argv[1], "array-fast") == 0) | |
array_fast(size); | |
else if (strcmp(argv[1], "array-slow") == 0) | |
array_slow(size); | |
else if (strcmp(argv[1], "array-unrolled") == 0) | |
array_slow(size); | |
else if (strcmp(argv[1], "linked-list") == 0) | |
linked_list(size); | |
else | |
usage(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment