diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/bigtab.c | 15 | ||||
| -rw-r--r-- | src/main.c | 151 | ||||
| -rw-r--r-- | src/new.c | 24 | ||||
| -rw-r--r-- | src/new32.c | 24 | ||||
| -rw-r--r-- | src/null.c | 4 | ||||
| -rw-r--r-- | src/ref.c | 12 |
6 files changed, 230 insertions, 0 deletions
diff --git a/src/bigtab.c b/src/bigtab.c new file mode 100644 index 0000000..483ded7 --- /dev/null +++ b/src/bigtab.c @@ -0,0 +1,15 @@ +int ref2(int i, int x, int y); +static short table[730][3][244]; + +void bigtab_init(void) +{ + for (int i = 0; i < 729; i++) + for (int x = 0; x < 3; x++) + for (int y = 243; y > 0; y /= 3) + table[i][x][y] = ref2(i, x, y); +} + +int bigtab(int i, int x, int y) +{ + return table[i][x][y]; +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..8d82af5 --- /dev/null +++ b/src/main.c @@ -0,0 +1,151 @@ +#include <stdlib.h> +#include <stdio.h> +#include <stdint.h> +#include <sys/random.h> +#include <time.h> +#include <math.h> + +#define COUNT(x) (sizeof(x) / sizeof(x[0])) + +static uint64_t nclock(void) +{ + struct timespec ts; + clock_gettime(CLOCK_MONOTONIC_RAW, &ts); + return (uint64_t)ts.tv_sec * 1000000000 + ts.tv_nsec; +} + +int null(int i, int x, int y); +int ref1(int i, int x, int y); +int ref2(int i, int x, int y); +int new(int i, int x, int y); +int new32(int i, int x, int y); +void bigtab_init(void); +int bigtab(int i, int x, int y); + +struct solfunc { + const char *name; + int (*func)(int, int, int); + + double T, dT; + double adj_T, adj_dT; +}; + +static struct solfunc solfuncs[ ] = { + {"null", null}, + {"ref1", ref1}, + {"ref2", ref2}, + {"bigtab", bigtab}, + {"new", new}, + {"new32", new32} +}; + +#define PASSES 5 + +static void benchmark(void) +{ + const int ys[] = {243, 81, 27, 9, 3, 1}; + const size_t size = 20*1000*1000; + int seed; + struct { int i, x, y, r; } *data; + struct solfunc *fastest = NULL; + + getrandom(&seed, sizeof(seed), 0); + srand(seed); + + data = malloc(sizeof(*data) * size); + if (!data) { + fprintf(stderr, "out of memory\n"); + exit(2); + } + + printf("benchmarking %zu solutions: ", COUNT(solfuncs)); + + for (size_t j = 0; j < size; j++) { + data[j].i = rand() % 729; + data[j].x = rand() % 3; + data[j].y = ys[rand() % 6]; + } + + for (size_t i = 0; i < COUNT(solfuncs); i++) { + struct solfunc *sf = solfuncs + i; + double ts[PASSES], var; + + printf("%zu", i + 1); + + for (size_t j = 0; j < PASSES; j++) { + uint64_t t0; + + fflush(stdout); + + t0 = nclock(); + for (size_t k = 0; k < size; k++) + data[k].r = sf->func(data[k].i, data[k].x, + data[k].y); + ts[j] = (nclock() - t0) * 1.0e-9; + ts[j] *= 1.0e9 / size; + + printf("."); + } + + sf->T = 0.0f; + for (size_t j = 0; j < PASSES; j++) + sf->T += ts[j]; + sf->T /= PASSES; + + var = 0.0f; + for (size_t j = 0; j < PASSES; j++) + var += pow(ts[j] - sf->T, 2.0); + sf->dT = sqrt(var) / sqrt(PASSES); + } + + printf("\n"); + + for (size_t i = 1; i < COUNT(solfuncs); i++) { + struct solfunc *sf = solfuncs + i; + + sf->adj_T = sf->T - solfuncs[0].T; + sf->adj_dT = sqrt(pow(sf->dT, 2) + pow(solfuncs[0].dT, 2)); + + if (!fastest || sf->T < fastest->T) { + fastest = sf; + fastest->T = sf->T; + } + } + + for (size_t i = 0; i < COUNT(solfuncs); i++) { + struct solfunc *sf = solfuncs + i; + + printf("%7s %.2f ± %.2f", sf->name, sf->T, sf->dT); + if (i > 0) { + printf(" %.2f ± %.2f", sf->adj_T, sf->adj_dT); + printf(" (x %.3f)", sf->T / fastest->T); + } + puts(""); + } +} + +int main(void) +{ + bigtab_init(); + + for (int j = 2; j < COUNT(solfuncs); j++) { + struct solfunc *sf = solfuncs + j; + + for (int i = 0; i < 729; i++) + for (int x = 0; x < 3; x++) + for (int y = 243; y > 0; y /= 3) { + int ref, res; + + ref = ref1(i, x, y); + + if ((res = sf->func(i, x, y)) != ref) { + printf("\n%s fails for %i/%i/%i: got %i, expected %i\n", + sf->name, i, x, y, res, ref); + return 1; + } + } + } + + benchmark(); + return 0; +}
\ No newline at end of file diff --git a/src/new.c b/src/new.c new file mode 100644 index 0000000..3bdd6d0 --- /dev/null +++ b/src/new.c @@ -0,0 +1,24 @@ +#include <stdint.h> + +static const uint64_t divtab[244] = { + [1] = 0xffffffff + 1l, + [3] = 0x55555555 + 1l, + [9] = 0x1c71c71c + 1l, + [27] = 0x097b425e + 1l, + [81] = 0x0329161f + 1l, + [243] = 0x010db20a + 1l +}; + +#define FASTDIV(n, C) (((n) * (C)) >> 32) +#define FASTMOD(n, d, C) ((n) - (d) * FASTDIV((n), (C))) + +int new(int i, int x, int y) +{ + uint64_t A, B, C; + + A = FASTDIV(i, divtab[y]); + B = FASTMOD(A, 3, divtab[3]); + C = FASTMOD(A + (uint64_t)x, 3, divtab[3]); + + return i + (C - B) * y; +} diff --git a/src/new32.c b/src/new32.c new file mode 100644 index 0000000..9136115 --- /dev/null +++ b/src/new32.c @@ -0,0 +1,24 @@ +#include <stdint.h> + +static const unsigned int divtab[244] = { + [1] = 0xffff + 1l, + [3] = 0x5555 + 1l, + [9] = 0x1c71 + 1l, + [27] = 0x097b + 1l, + [81] = 0x0329 + 1l, + [243] = 0x010d + 1l +}; + +#define FASTDIV(n, C) (((n) * (C)) >> 16) +#define FASTMOD(n, d, C) ((n) - (d) * FASTDIV((n), (C))) + +int new32(int i, int x, int y) +{ + int A, B, C; + + A = FASTDIV(i, divtab[y]); + B = FASTMOD(A, 3, divtab[3]); + C = FASTMOD(A + x, 3, divtab[3]); + + return i + (C - B) * y; +} diff --git a/src/null.c b/src/null.c new file mode 100644 index 0000000..4474c1a --- /dev/null +++ b/src/null.c @@ -0,0 +1,4 @@ +int null(int i, int x, int y) +{ + return 0; +}
\ No newline at end of file diff --git a/src/ref.c b/src/ref.c new file mode 100644 index 0000000..3589b13 --- /dev/null +++ b/src/ref.c @@ -0,0 +1,12 @@ +// This is the original code posted on IOTA's Discord. +int ref1(int i, int x, int y) +{ + return i % y + ((((i / y) + x) % 3) + (i / (y * 3)) * 3) * y; +} + +// A simplified version posted by someone on IOTA's Discord (not exactly sure +// who posted it first). +int ref2(int i, int x, int y) +{ + return i + (((i / y) + x) % 3 - ((i / y) % 3)) * y; +}
\ No newline at end of file |