1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
/* Finding items in a keyed list the way TPC-C's stock is found (docs/research/109):
* bench-seek ITEMS OPERATIONS
* A list of ITEMS items, five number fields, keyed by the first (keys 1..ITEMS);
* then OPERATIONS random keys, four ways: a seek alone; a seek and three
* fields read; and three fields read and each changed (journaled); the same
* with a share every 30 changes, as a snapshot a save takes. Prints ns each,
* and the machine's latency to memory (a random pointer chase over 64 MiB). */
#include "module-list.h"
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static uint64_t now_ns(void) {
struct timespec t;
clock_gettime(CLOCK_MONOTONIC, &t);
return (uint64_t)t.tv_sec * 1000000000u + (uint64_t)t.tv_nsec;
}
static uint64_t state = 0x9e3779b97f4a7c15u;
static uint64_t next(void) {
state ^= state << 13, state ^= state >> 7, state ^= state << 17;
return state;
}
int main(int argc, char **argv) {
size_t items = argc > 1 ? strtoull(argv[1], NULL, 10) : 100000, operations = argc > 2 ? strtoull(argv[2], NULL, 10) : 2000000;
static const uint8_t numbers[5] = {0};
PureList *list = pure_list_new(5, numbers);
if (!list || pure_list_keyed(list, 0) != PURE_OK) return 1;
for (size_t i = 0; i < items; ++i) {
PureCell cells[5] = {{.num = (double)(i + 1)}, {.num = 50}, {.num = 0}, {.num = 0}, {.num = 0}};
if (pure_list_insert(list, i, cells, NULL) != PURE_OK) return 1;
}
pure_list_journal(list, true);
double sink = 0;
const char *names[4] = {"seek", "seek+3 reads", "seek+3 reads+3 changes", "same, a share each 30"};
for (int way = 0; way < 4; ++way) {
PureRetired retired = {0};
PureList *copy = NULL;
uint64_t epoch = 0;
uint64_t began = now_ns();
for (size_t op = 0; op < operations; ++op) {
bool found;
size_t at = pure_list_seek(list, 0, (PureCell){.num = (double)(next() % items + 1)}, &found);
if (way == 0) { sink += (double)at; continue; }
for (unsigned f = 1; f <= 3; ++f) {
double value = pure_list_get(list, at, f).num;
sink += value;
if (way >= 2) pure_list_set(list, at, f, (PureCell){.num = value + 1}, NULL);
}
if (way >= 2 && op % 64 == 63) pure_list_forget(list, 0);
if (way == 3 && op % 30 == 29) {
if (copy) {
pure_list_free(copy);
pure_retired_reuse(&retired, &list, 1);
}
copy = pure_list_share(list, &retired, ++epoch);
}
}
uint64_t took = now_ns() - began;
if (copy) pure_list_free(copy);
pure_retired_free(&retired);
printf("%-26s %7.1f ns\n", names[way], (double)took / (double)operations);
}
/* The latency to memory: a random cycle through 64 MiB of pointers. */
size_t slots = (64u << 20) / sizeof(size_t);
size_t *chain = malloc(slots * sizeof(*chain)), *order = malloc(slots * sizeof(*order));
for (size_t i = 0; i < slots; ++i) order[i] = i;
for (size_t i = slots - 1; i > 0; --i) { size_t j = next() % (i + 1), t = order[i]; order[i] = order[j]; order[j] = t; }
for (size_t i = 0; i < slots; ++i) chain[order[i]] = order[(i + 1) % slots];
size_t at = order[0];
uint64_t began = now_ns();
for (size_t i = 0; i < 4000000; ++i) at = chain[at];
printf("%-26s %7.1f ns\n", "memory latency", (double)(now_ns() - began) / 4000000.0);
sink += (double)at;
fprintf(stderr, "%g\n", sink);
pure_list_free(list);
return 0;
}
|
