Skip to content

Instantly share code, notes, and snippets.

@gnuvince gnuvince/sob.c
Last active Dec 29, 2018

Embed
What would you like to do?
#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
You can’t perform that action at this time.