diff options
Diffstat (limited to 'research/experiments/008-tree-store-edit-cost')
5 files changed, 912 insertions, 0 deletions
diff --git a/research/experiments/008-tree-store-edit-cost/2026-09-25-ext4-linux-aarch64.json b/research/experiments/008-tree-store-edit-cost/2026-09-25-ext4-linux-aarch64.json new file mode 100644 index 0000000..708346f --- /dev/null +++ b/research/experiments/008-tree-store-edit-cost/2026-09-25-ext4-linux-aarch64.json @@ -0,0 +1,346 @@ +{ + "device": "/dev/mmcblk0p2", + "filesystem": "ext4", + "machine": "aarch64", + "kernel": "6.18.39+rpt-rpi-2712", + "compiler": "cc (Debian 14.2.0-19) 14.2.0", + "edits_per_scenario": 32, + "results": [ + { + "store": "flat", + "op": "insert-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 9.305, + "edit_p90_ms": 20.037, + "edit_max_ms": 154.578, + "write_call_bytes_per_edit": 296, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 312, + "whole_read_median_ms": 0.008, + "read_checksum": 7776 + }, + { + "store": "paged", + "op": "insert-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.463, + "edit_p90_ms": 11.859, + "edit_max_ms": 64.024, + "write_call_bytes_per_edit": 296, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 312, + "whole_read_median_ms": 0.01, + "read_checksum": 7776 + }, + { + "store": "tree", + "op": "insert-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.343, + "edit_p90_ms": 11.553, + "edit_max_ms": 65.974, + "write_call_bytes_per_edit": 432, + "device_write_bytes_per_edit": 32768, + "store_file_bytes_after": 12272, + "whole_read_median_ms": 0.011, + "read_checksum": 7776 + }, + { + "store": "flat", + "op": "delete-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.506, + "edit_p90_ms": 10.021, + "edit_max_ms": 65.646, + "write_call_bytes_per_edit": 263, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 248, + "whole_read_median_ms": 0.008, + "read_checksum": 6720 + }, + { + "store": "paged", + "op": "delete-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.344, + "edit_p90_ms": 9.873, + "edit_max_ms": 65.228, + "write_call_bytes_per_edit": 263, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 248, + "whole_read_median_ms": 0.01, + "read_checksum": 6720 + }, + { + "store": "tree", + "op": "delete-middle", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 6.933, + "edit_p90_ms": 10.713, + "edit_max_ms": 11.529, + "write_call_bytes_per_edit": 399, + "device_write_bytes_per_edit": 32768, + "store_file_bytes_after": 11216, + "whole_read_median_ms": 0.011, + "read_checksum": 6720 + }, + { + "store": "flat", + "op": "replace-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.321, + "edit_p90_ms": 9.878, + "edit_max_ms": 27.943, + "write_call_bytes_per_edit": 280, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 280, + "whole_read_median_ms": 0.008, + "read_checksum": 6944 + }, + { + "store": "paged", + "op": "replace-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.409, + "edit_p90_ms": 9.723, + "edit_max_ms": 62.134, + "write_call_bytes_per_edit": 280, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 280, + "whole_read_median_ms": 0.01, + "read_checksum": 6944 + }, + { + "store": "tree", + "op": "replace-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 9.141, + "edit_p90_ms": 16.762, + "edit_max_ms": 62.869, + "write_call_bytes_per_edit": 416, + "device_write_bytes_per_edit": 32768, + "store_file_bytes_after": 11744, + "whole_read_median_ms": 0.011, + "read_checksum": 6944 + }, + { + "store": "flat", + "op": "append-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 9.068, + "edit_p90_ms": 10.062, + "edit_max_ms": 62.784, + "write_call_bytes_per_edit": 296, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 312, + "whole_read_median_ms": 0.012, + "read_checksum": 7984 + }, + { + "store": "paged", + "op": "append-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 8.613, + "edit_p90_ms": 10.037, + "edit_max_ms": 59.767, + "write_call_bytes_per_edit": 296, + "device_write_bytes_per_edit": 16384, + "store_file_bytes_after": 312, + "whole_read_median_ms": 0.015, + "read_checksum": 7984 + }, + { + "store": "tree", + "op": "append-end", + "document_bytes": 256, + "edits": 32, + "edit_median_ms": 6.468, + "edit_p90_ms": 11.041, + "edit_max_ms": 61.441, + "write_call_bytes_per_edit": 432, + "device_write_bytes_per_edit": 32768, + "store_file_bytes_after": 12272, + "whole_read_median_ms": 0.017, + "read_checksum": 7984 + }, + { + "store": "flat", + "op": "insert-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 78.508, + "edit_p90_ms": 82.768, + "edit_max_ms": 83.984, + "write_call_bytes_per_edit": 1048616, + "device_write_bytes_per_edit": 1064960, + "store_file_bytes_after": 1048632, + "whole_read_median_ms": 0.102, + "read_checksum": 28574496 + }, + { + "store": "paged", + "op": "insert-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 86.573, + "edit_p90_ms": 103.801, + "edit_max_ms": 108.102, + "write_call_bytes_per_edit": 1065528, + "device_write_bytes_per_edit": 1081344, + "store_file_bytes_after": 1065528, + "whole_read_median_ms": 0.07, + "read_checksum": 28574496 + }, + { + "store": "tree", + "op": "insert-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 8.58, + "edit_p90_ms": 16.685, + "edit_max_ms": 64.33, + "write_call_bytes_per_edit": 2732, + "device_write_bytes_per_edit": 35328, + "store_file_bytes_after": 1138480, + "whole_read_median_ms": 0.262, + "read_checksum": 28574496 + }, + { + "store": "flat", + "op": "delete-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 78.755, + "edit_p90_ms": 81.697, + "edit_max_ms": 86.715, + "write_call_bytes_per_edit": 1048583, + "device_write_bytes_per_edit": 1060352, + "store_file_bytes_after": 1048568, + "whole_read_median_ms": 0.065, + "read_checksum": 28573440 + }, + { + "store": "paged", + "op": "delete-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 85.293, + "edit_p90_ms": 93.573, + "edit_max_ms": 108.718, + "write_call_bytes_per_edit": 1049136, + "device_write_bytes_per_edit": 1064960, + "store_file_bytes_after": 1049136, + "whole_read_median_ms": 0.077, + "read_checksum": 28573440 + }, + { + "store": "tree", + "op": "delete-middle", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 8.512, + "edit_p90_ms": 11.869, + "edit_max_ms": 14.455, + "write_call_bytes_per_edit": 4907, + "device_write_bytes_per_edit": 37376, + "store_file_bytes_after": 1208072, + "whole_read_median_ms": 0.229, + "read_checksum": 28573440 + }, + { + "store": "flat", + "op": "replace-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 79.202, + "edit_p90_ms": 86.6, + "edit_max_ms": 90.952, + "write_call_bytes_per_edit": 1048600, + "device_write_bytes_per_edit": 1064960, + "store_file_bytes_after": 1048600, + "whole_read_median_ms": 0.063, + "read_checksum": 28573664 + }, + { + "store": "paged", + "op": "replace-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 13.959, + "edit_p90_ms": 23.871, + "edit_max_ms": 69.901, + "write_call_bytes_per_edit": 16944, + "device_write_bytes_per_edit": 32768, + "store_file_bytes_after": 1573424, + "whole_read_median_ms": 0.074, + "read_checksum": 28573664 + }, + { + "store": "tree", + "op": "replace-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 6.488, + "edit_p90_ms": 8.209, + "edit_max_ms": 60.301, + "write_call_bytes_per_edit": 4912, + "device_write_bytes_per_edit": 37376, + "store_file_bytes_after": 1208232, + "whole_read_median_ms": 0.37, + "read_checksum": 28573664 + }, + { + "store": "flat", + "op": "append-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 77.885, + "edit_p90_ms": 86.005, + "edit_max_ms": 89.824, + "write_call_bytes_per_edit": 1048616, + "device_write_bytes_per_edit": 1064960, + "store_file_bytes_after": 1048632, + "whole_read_median_ms": 0.062, + "read_checksum": 28574704 + }, + { + "store": "paged", + "op": "append-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 86.039, + "edit_p90_ms": 102.765, + "edit_max_ms": 121.611, + "write_call_bytes_per_edit": 1065528, + "device_write_bytes_per_edit": 1081344, + "store_file_bytes_after": 1065528, + "whole_read_median_ms": 0.07, + "read_checksum": 28574704 + }, + { + "store": "tree", + "op": "append-end", + "document_bytes": 1048576, + "edits": 32, + "edit_median_ms": 8.473, + "edit_p90_ms": 11.691, + "edit_max_ms": 60.672, + "write_call_bytes_per_edit": 2716, + "device_write_bytes_per_edit": 35328, + "store_file_bytes_after": 1137960, + "whole_read_median_ms": 0.225, + "read_checksum": 28574704 + } + ] +} diff --git a/research/experiments/008-tree-store-edit-cost/2026-09-25-tui-ext4-linux-aarch64.json b/research/experiments/008-tree-store-edit-cost/2026-09-25-tui-ext4-linux-aarch64.json new file mode 100644 index 0000000..6bea961 --- /dev/null +++ b/research/experiments/008-tree-store-edit-cost/2026-09-25-tui-ext4-linux-aarch64.json @@ -0,0 +1,285 @@ +{ + "platform": "Linux-6.18.39+rpt-rpi-2712-aarch64-with-glibc2.41", + "filesystem": "/dev/mmcblk0p2 ext4", + "document_bytes": 1048576, + "rounds": 3, + "edits_per_session": 8, + "median_ms": { + "replace": { + "flat": 86.32, + "paged": 21.31, + "tree": 16.97 + }, + "append": { + "flat": 84.59, + "paged": 93.29, + "tree": 16.6 + } + }, + "binaries": { + "flat": { + "cli_sha256": "f69c7580104b873e0736d7503dcbbcbb6b180adf54920e6ba741d363262867b8", + "tui_sha256": "644980089e65e9db01ecdd21c4edf8a0ae7fe248114340b3b691e6c283e5e5b4" + }, + "paged": { + "cli_sha256": "233311ee133bc1d5299963f4523131dac542d71013cb825f8a4eaa48de813ee8", + "tui_sha256": "77169c79a800881e901e5b1bba938543eed5f3f1f0914799e56c0635859af2d1" + }, + "tree": { + "cli_sha256": "c0c783a1b30a1f8e88bfe9a09b6ae124f596bf6239b802e4aec5e56f374714b9", + "tui_sha256": "8030475c663b09791a5fa24bad2f8498f652d4361a6734a737b3c6a22e4659aa" + } + }, + "runs": { + "replace": { + "flat": [ + { + "samples_ns": [ + 83883854, + 32709073, + 121001564, + 92289945, + 96340473, + 90943269, + 47708564, + 89206225 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 85403197, + 33045701, + 71709920, + 88249419, + 87284740, + 30588422, + 86124025, + 86515579 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 85907991, + 52699698, + 36407605, + 91580804, + 91115363, + 96859361, + 91057308, + 30358535 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + } + ], + "paged": [ + { + "samples_ns": [ + 21286170, + 21523669, + 20435102, + 21175041, + 24219650, + 19863957, + 21457280, + 20223807 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 20820044, + 18812854, + 22029072, + 19884550, + 21458169, + 21256596, + 25127069, + 73009317 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 21277781, + 23763283, + 18573541, + 21452318, + 21336634, + 75828726, + 18893984, + 21467613 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + } + ], + "tree": [ + { + "samples_ns": [ + 16691108, + 17111328, + 15930836, + 17254197, + 16401425, + 16596591, + 17847323, + 18489726 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 16340445, + 18211228, + 12615914, + 17297716, + 17568492, + 16601387, + 17259642, + 15886466 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + }, + { + "samples_ns": [ + 17321808, + 16796238, + 16831978, + 15132138, + 17392253, + 12584915, + 17342679, + 17423900 + ], + "body_sha256": "1acbea9ad5e6321b7e4f8b3f85450d99cb2d82b655820160dcd18bcaae58e00f" + } + ] + }, + "append": { + "flat": [ + { + "samples_ns": [ + 85268681, + 58706620, + 80969562, + 30847551, + 88231013, + 85485051, + 29563059, + 88786509 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 58646271, + 30913440, + 89689432, + 85278758, + 33291979, + 86740285, + 83913915, + 90844368 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 51920946, + 28831473, + 85487720, + 85906421, + 85835644, + 32848520, + 85315555, + 82713850 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + } + ], + "paged": [ + { + "samples_ns": [ + 91333586, + 37920058, + 92091377, + 63703624, + 95308984, + 40485355, + 99081866, + 93075370 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 96352460, + 93512017, + 65222596, + 38763552, + 98852258, + 131612999, + 138169789, + 131450371 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 40996002, + 93012356, + 63056206, + 93559778, + 37065306, + 98450597, + 112059339, + 111368899 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + } + ], + "tree": [ + { + "samples_ns": [ + 15267508, + 17113014, + 17454104, + 16570055, + 69532029, + 15171139, + 18091600, + 11101536 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 19964902, + 14639290, + 16407186, + 17425161, + 15285638, + 18012231, + 15061398, + 17329272 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + }, + { + "samples_ns": [ + 17466771, + 16352390, + 16629406, + 15132064, + 18861503, + 11662162, + 16306335, + 17256958 + ], + "body_sha256": "bd42946a8dafa764907691fbebfd981ef4b012fbcbf5c25beab7d6b1c8d0cc30" + } + ] + } + } +} diff --git a/research/experiments/008-tree-store-edit-cost/bench.c b/research/experiments/008-tree-store-edit-cost/bench.c new file mode 100644 index 0000000..f16f8db --- /dev/null +++ b/research/experiments/008-tree-store-edit-cost/bench.c @@ -0,0 +1,104 @@ +/* Durable edit cost of one selected byte store, through its public API only. + * Built once per store source; the store directory must be on the device + * being measured (not tmpfs, where fsync is free). */ +#define _POSIX_C_SOURCE 200809L +#include "store.h" +#include <dirent.h> +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/stat.h> +#include <time.h> + +static double now_ms(void) { + struct timespec t; + clock_gettime(CLOCK_MONOTONIC, &t); + return (double)t.tv_sec * 1e3 + (double)t.tv_nsec / 1e6; +} + +/* Linux accounting: wchar is bytes passed to write calls, write_bytes is + * bytes this process caused to be sent to the block layer. */ +static uint64_t io_field(const char *name) { + FILE *file = fopen("/proc/self/io", "r"); + char line[128]; + uint64_t value = 0; + size_t length = strlen(name); + while (file && fgets(line, sizeof(line), file)) + if (!strncmp(line, name, length) && line[length] == ':') value = strtoull(line + length + 1, NULL, 10); + if (file) fclose(file); + return value; +} + +static uint64_t store_bytes(const char *path) { + DIR *directory = opendir(path); + struct dirent *entry; + uint64_t total = 0; + char name[4096]; + while (directory && (entry = readdir(directory))) { + struct stat info; + snprintf(name, sizeof(name), "%s/%s", path, entry->d_name); + if (!stat(name, &info) && S_ISREG(info.st_mode)) total += (uint64_t)info.st_size; + } + if (directory) closedir(directory); + return total; +} + +static int compare(const void *a, const void *b) { + double x = *(const double *)a, y = *(const double *)b; + return (x > y) - (x < y); +} + +int main(int argc, char **argv) { + if (argc != 6) { + fputs("bench STORE_NAME DIRECTORY SIZE insert-middle|delete-middle|replace-end|append-end COUNT\n", stderr); + return 2; + } + const char *name = argv[1], *path = argv[2], *op = argv[4]; + size_t size = strtoull(argv[3], NULL, 10), count = strtoull(argv[5], NULL, 10); + unsigned char *body = malloc(size + 1); + double *samples = malloc(count * sizeof(*samples)), reads[16]; + if (!body || !samples || pure_store_init(path) != PURE_OK) return 1; + for (size_t i = 0; i < size; ++i) body[i] = (unsigned char)('a' + i % 26); + int64_t revision; + if (pure_store_put(path, "doc", 0, (PureSpan){body, size}, &revision) != PURE_OK) return 1; + size_t length = size; + uint64_t wchar = io_field("wchar"), device = io_field("write_bytes"); + for (size_t i = 0; i < count; ++i) { + size_t offset, remove, insert; + if (!strcmp(op, "insert-middle")) { offset = length / 2; remove = 0; insert = 1; } + else if (!strcmp(op, "delete-middle")) { offset = length / 2; remove = 1; insert = 0; } + else if (!strcmp(op, "replace-end")) { offset = length - 1; remove = 1; insert = 1; } + else if (!strcmp(op, "append-end")) { offset = length; remove = 0; insert = 1; } + else return 2; + unsigned char byte = (unsigned char)('A' + i % 26); + double start = now_ms(); + PureResult result = pure_store_splice(path, "doc", revision, offset, remove, + (PureSpan){&byte, insert}, PURE_OBJECT_LIMIT, &revision); + samples[i] = now_ms() - start; + if (result != PURE_OK) { fprintf(stderr, "splice failed: %d\n", (int)result); return 1; } + length = length - remove + insert; + } + wchar = io_field("wchar") - wchar; + device = io_field("write_bytes") - device; + uint64_t checksum = 0; + for (size_t i = 0; i < 16; ++i) { + PureStoredView view; + double start = now_ms(); + if (pure_store_get(path, "doc", PURE_OBJECT_LIMIT, &view) != PURE_OK || view.body.size != length) return 1; + for (size_t k = 0; k < view.body.size; k += 64) checksum += view.body.data[k]; + pure_store_release(&view); + reads[i] = now_ms() - start; + } + qsort(samples, count, sizeof(*samples), compare); + qsort(reads, 16, sizeof(*reads), compare); + printf("{\"store\":\"%s\",\"op\":\"%s\",\"document_bytes\":%zu,\"edits\":%zu," + "\"edit_median_ms\":%.3f,\"edit_p90_ms\":%.3f,\"edit_max_ms\":%.3f," + "\"write_call_bytes_per_edit\":%" PRIu64 ",\"device_write_bytes_per_edit\":%" PRIu64 "," + "\"store_file_bytes_after\":%" PRIu64 ",\"whole_read_median_ms\":%.3f,\"read_checksum\":%" PRIu64 "}\n", + name, op, size, count, samples[count / 2], samples[count * 9 / 10], samples[count - 1], + wchar / count, device / count, store_bytes(path), reads[8], checksum); + free(samples); + free(body); + return 0; +} diff --git a/research/experiments/008-tree-store-edit-cost/run.py b/research/experiments/008-tree-store-edit-cost/run.py new file mode 100755 index 0000000..1b9dfa8 --- /dev/null +++ b/research/experiments/008-tree-store-edit-cost/run.py @@ -0,0 +1,49 @@ +#!/usr/bin/env python3 +"""Build bench.c against each selected store and time durable edits on disk.""" +import argparse +import json +import platform +import shutil +import subprocess +from pathlib import Path + +HERE = Path(__file__).resolve().parent +CONNECTIONS = HERE.parents[2] / 'prototypes' / 'connections' +STORES = {'flat': 'store.c', 'paged': 'store-paged.c', 'tree': 'store-tree.c'} +OPS = ['insert-middle', 'delete-middle', 'replace-end', 'append-end'] + + +def main(): + parser = argparse.ArgumentParser() + parser.add_argument('--work', type=Path, default=CONNECTIONS / 'build' / 'bench-tree-cost') + parser.add_argument('--count', type=int, default=32) + parser.add_argument('--sizes', default='256,1048576') + parser.add_argument('--output', type=Path) + args = parser.parse_args() + shutil.rmtree(args.work, ignore_errors=True) + args.work.mkdir(parents=True) + source = subprocess.check_output(['findmnt', '-n', '-T', str(args.work), '-o', 'SOURCE,FSTYPE'], text=True).split() + assert source[1] != 'tmpfs', 'fsync is free on tmpfs; choose a real device' + results = [] + for name, store in STORES.items(): + binary = args.work / f'bench-{name}' + subprocess.run(['cc', '-std=c17', '-O2', '-Wall', '-Wextra', '-Werror', f'-I{CONNECTIONS}', + str(HERE / 'bench.c'), str(CONNECTIONS / store), '-o', str(binary)], check=True) + for size in map(int, args.sizes.split(',')): + for op in OPS: + for name in STORES: # interleave stores within each scenario + directory = args.work / f'{name}-{op}-{size}' + line = subprocess.check_output([str(args.work / f'bench-{name}'), name, str(directory), + str(size), op, str(args.count)], text=True) + results.append(json.loads(line)) + print(line.strip(), flush=True) + shutil.rmtree(directory) + report = {'device': source[0], 'filesystem': source[1], 'machine': platform.machine(), + 'kernel': platform.release(), 'compiler': subprocess.check_output(['cc', '--version'], text=True).splitlines()[0], + 'edits_per_scenario': args.count, 'results': results} + if args.output: + args.output.write_text(json.dumps(report, indent=2) + '\n') + + +if __name__ == '__main__': + main() diff --git a/research/experiments/008-tree-store-edit-cost/tui.py b/research/experiments/008-tree-store-edit-cost/tui.py new file mode 100755 index 0000000..78c6ce0 --- /dev/null +++ b/research/experiments/008-tree-store-edit-cost/tui.py @@ -0,0 +1,128 @@ +#!/usr/bin/env python3 +"""Ctrl+S to completed frame in the real native terminal editor, per store. + +Same method as 006 (full draft comparison, runtime, durable store and redraw), +with two edit shapes: replacing the final character (same size) and typing one +new character at the end (the document grows, as ordinary typing does).""" +import argparse +import fcntl +import hashlib +import json +import os +from pathlib import Path +import platform +import pty +import select +import statistics +import struct +import subprocess +import tempfile +import termios +import time + + +def run(*args): + return subprocess.run([str(arg) for arg in args], check=True, capture_output=True, timeout=30) + + +def frame(master, process): + output = bytearray() + deadline = time.monotonic() + 15 + while time.monotonic() < deadline: + if select.select([master], [], [], 0.5)[0]: + output.extend(os.read(master, 65536)) + if b'\x1b[?25h' in output: + return bytes(output) + if process.poll() is not None: + break + raise AssertionError((process.poll(), output[-1000:])) + + +def one_session(cli, tui, root, size, edits, shape): + root.mkdir(parents=True) + store = root / 'store' + body = b'A' * size + initial = root / 'initial.bin' + initial.write_bytes(body) + assert json.loads(run(cli, '--store', store, 'edit', 'document', 0, 0, 0, initial).stdout)['revision'] == '1' + master, slave = pty.openpty() + fcntl.ioctl(slave, termios.TIOCSWINSZ, struct.pack('HHHH', 24, 80, 0, 0)) + process = subprocess.Popen([str(tui), '--store', str(store), 'document'], + stdin=slave, stdout=slave, stderr=slave, + env={**os.environ, 'LANG': 'C.UTF-8', 'LC_ALL': 'C.UTF-8'}) + samples, expected_body = [], bytearray(body) + try: + assert b'Pure | document' in frame(master, process) + for index in range(edits): + character = b'B' if index % 2 == 0 else b'C' + if shape == 'replace': + os.write(master, b'\x7f') + frame(master, process) + expected_body[-1:] = character + position = size - 1 + else: + expected_body += character + position = size + index + os.write(master, character) + frame(master, process) + start = time.perf_counter_ns() + os.write(master, b'\x13') + shown = frame(master, process) + samples.append(time.perf_counter_ns() - start) + assert f'Saved 1-byte edit at byte {position}'.encode() in shown, shown[-1500:] + assert f'revision {index + 2}'.encode() in shown, shown[-1500:] + os.write(master, b'\x11') + process.wait(timeout=8) + assert process.returncode == 0 + finally: + if process.poll() is None: + process.kill() + process.wait(timeout=5) + os.close(master) + os.close(slave) + final = run(cli, '--store', store, 'show', 'document') + assert final.stdout == bytes(expected_body) + assert json.loads(final.stderr)['revision'] == str(edits + 1) + return {'samples_ns': samples, 'body_sha256': hashlib.sha256(final.stdout).hexdigest()} + + +def main(): + parser = argparse.ArgumentParser(description=__doc__) + parser.add_argument('--store', nargs=3, action='append', metavar=('NAME', 'CLI', 'TUI'), required=True) + parser.add_argument('--scratch-parent', type=Path, required=True) + parser.add_argument('--size', type=int, default=1_048_576) + parser.add_argument('--rounds', type=int, default=3) + parser.add_argument('--edits', type=int, default=8) + parser.add_argument('--output', type=Path) + args = parser.parse_args() + binaries = {name: (Path(cli).resolve(), Path(tui).resolve()) for name, cli, tui in args.store} + parent = args.scratch_parent.resolve() + parent.mkdir(parents=True, exist_ok=True) + filesystem = run('findmnt', '-T', parent, '-no', 'SOURCE,FSTYPE').stdout.decode().strip() + assert 'tmpfs' not in filesystem, 'fsync is free on tmpfs' + raw = {shape: {name: [] for name in binaries} for shape in ('replace', 'append')} + with tempfile.TemporaryDirectory(prefix='pure-tree-save-', dir=parent) as directory: + root = Path(directory) + for shape in raw: + for round_number in range(args.rounds): + names = list(binaries) + order = names[round_number % len(names):] + names[:round_number % len(names)] + for name in order: + cli, tui = binaries[name] + raw[shape][name].append(one_session(cli, tui, root / f'{shape}-{round_number}-{name}', + args.size, args.edits, shape)) + medians = {shape: {name: round(statistics.median(s for session in sessions for s in session['samples_ns']) / 1e6, 2) + for name, sessions in stores.items()} for shape, stores in raw.items()} + result = {'platform': platform.platform(), 'filesystem': filesystem, 'document_bytes': args.size, + 'rounds': args.rounds, 'edits_per_session': args.edits, 'median_ms': medians, + 'binaries': {name: {'cli_sha256': hashlib.sha256(cli.read_bytes()).hexdigest(), + 'tui_sha256': hashlib.sha256(tui.read_bytes()).hexdigest()} + for name, (cli, tui) in binaries.items()}, + 'runs': raw} + if args.output: + args.output.write_text(json.dumps(result, indent=2) + '\n') + print(json.dumps({'filesystem': filesystem, 'median_ms': medians})) + + +if __name__ == '__main__': + main() |