lru: new implementation and also interface

The implementation is now similar to set-associative caches
that x86 CPU use.  Also the API is changed a bit, leading to
slight simplification of our use patterns.

2 files changed, 70 insertions, 27 deletions

diff --git a/bench/bench.mk b/bench/bench.mk
index b1defbd9..dfd06ee7 100644
--- a/bench/bench.mk
+++ b/bench/bench.mk
@@ -27,9 +27,9 @@ $(foreach bench,$(bench_BIN),$(eval $(call make_bench,$(bench))))
 .PHONY: bench bench-clean
 bench-clean: $(foreach bench,$(bench_BIN),$(bench)-clean)
 bench: $(foreach bench,$(bench_BIN),bench/$(bench))
-	# Test LRU with increasing overfill, misses should increase ~ linearly
-	@./bench/bench_lru 22 bench/bench_lru_set1.tsv - 65536 # fill = 1
-	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 32768 # fill = 2
-	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 16384 # fill = 4
-	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 8192  # fill = 8
-	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 4096  # fill = 16
\ No newline at end of file
+	@echo "Test LRU with increasing overfill, misses should increase ~ linearly" >&2
+	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 65536 # fill ~ 1
+	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 32768 # fill ~ 2
+	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 16384 # fill ~ 4
+	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 8192  # fill ~ 8
+	@./bench/bench_lru 23 bench/bench_lru_set1.tsv - 4096  # fill ~ 16
diff --git a/bench/bench_lru.c b/bench/bench_lru.c
index ec549174..1befb776 100644
--- a/bench/bench_lru.c
+++ b/bench/bench_lru.c
@@ -17,6 +17,7 @@
 #include <math.h>
 #include <stdlib.h>
 #include <stdint.h>
+#include <stdio.h>
 #include <sys/time.h>
 #include <unistd.h>
 
@@ -26,17 +27,25 @@
 
 typedef kr_nsrep_lru_t lru_bench_t;
 
+#define p_out(...) do { \
+	printf(__VA_ARGS__); \
+	fflush(stdout); \
+	} while (0)
+#define p_err(...) fprintf(stderr, __VA_ARGS__)
 
-static int die(const char *cause) {
+static int die(const char *cause)
+{
 	fprintf(stderr, "%s: %s\n", cause, strerror(errno));
 	exit(1);
 }
 
-static void time_get(struct timeval *tv) {
+static void time_get(struct timeval *tv)
+{
 	if (gettimeofday(tv, NULL))
 		die("gettimeofday");
 }
-static void time_print_diff(struct timeval *tv, size_t op_count) {
+static void time_print_diff(struct timeval *tv, size_t op_count)
+{
 	struct timeval now;
 	time_get(&now);
 	now.tv_sec -= tv->tv_sec;
@@ -48,11 +57,16 @@ static void time_print_diff(struct timeval *tv, size_t op_count) {
 
 	size_t speed = round((double)(op_count) / 1000
 		/ (now.tv_sec + (double)(now.tv_usec)/1000000));
-	printf("\t%ld.%06d s, \t %zd kop/s\n", now.tv_sec, (int)now.tv_usec, speed);
+
+	p_out("%ld.%06d", now.tv_sec, (int)now.tv_usec);
+	p_err(" s"); p_out(","); p_err("\t");
+	p_out("%zd", speed);
+	p_err(" kops/s"); p_out(","); p_err("\n");
 }
 
 /// initialize seed for random()
-static int ssrandom(char *s) {
+static int ssrandom(char *s)
+{
 	if (*s == '-') { // initialize from time
 		struct timeval now;
 		time_get(&now);
@@ -75,7 +89,8 @@ struct key {
 };
 
 /// read lines from a file and reorder them randomly
-static struct key * read_lines(const char *fname, size_t *count) {
+static struct key * read_lines(const char *fname, size_t *count, char **pfree)
+{
 	// read the file at once
 	int fd = open(fname, O_RDONLY);
 	if (fd < 0)
@@ -85,6 +100,7 @@ static struct key * read_lines(const char *fname, size_t *count) {
 		die("stat");
 	size_t flen = (size_t)st.st_size;
 	char *fbuf = malloc(flen + 1);
+	*pfree = fbuf;
 	if (fbuf == NULL)
 		die("malloc");
 	if (read(fd, fbuf, flen) < 0)
@@ -101,7 +117,11 @@ static struct key * read_lines(const char *fname, size_t *count) {
 		}
 	*count = lines;
 	size_t avg_len = (flen + 1) / lines - 1;
-	printf("%zu lines read, average length %zu\n", lines, avg_len);
+
+	p_err("lines read: ");
+	p_out("%zu,", lines);
+	p_err("\taverage length ");
+	p_out("%zu,", avg_len);
 
 	struct key *result = calloc(lines, sizeof(struct key));
 	result[0].chars = fbuf;
@@ -137,26 +157,33 @@ static struct key * read_lines(const char *fname, size_t *count) {
 	#define lru_get_try lru_get
 #endif
 
-static void usage(const char *progname) {
-	fprintf(stderr, "usage: %s <log_count> <input> <seed> [lru_size]\n"
-		"The seed must be at least 12 characters or \"-\".\n" , progname);
+static void usage(const char *progname)
+{
+	p_err("usage: %s <log_count> <input> <seed> [lru_size]\n", progname);
+	p_err("The seed must be at least 12 characters or \"-\".\n"
+		"Standard output contains csv-formatted lines.\n");
 	exit(1);
 }
 
-int main(int argc, char ** argv) {
+
+int main(int argc, char ** argv)
+{
 	if (argc != 4 && argc != 5)
 		usage(argv[0]);
 	if (ssrandom(argv[3]) < 0)
 		usage(argv[0]);
 
+	p_out("\n");
 	size_t key_count;
-	struct key *keys = read_lines(argv[2], &key_count);
+	char *data_to_free = NULL;
+	struct key *keys = read_lines(argv[2], &key_count, &data_to_free);
 	size_t run_count;
 	{
 		size_t run_log = atoi(argv[1]);
 		assert(run_log < 64);
 		run_count = 1ULL << run_log;
-		printf("test run length: 2^%zd\n", run_log);
+		p_err("\ntest run length:\t2^");
+		p_out("%zd,", run_log);
 	}
 
 	struct timeval time;
@@ -164,7 +191,7 @@ int main(int argc, char ** argv) {
 
 	lru_bench_t *lru;
 	#ifdef lru_create
-		lru_create(&lru, lru_size, NULL);
+		lru_create(&lru, lru_size, NULL, NULL);
 	#else
 		lru = malloc(lru_size(lru_bench_t, lru_size));
 		if (lru)
@@ -172,12 +199,19 @@ int main(int argc, char ** argv) {
 	#endif
 	if (!lru)
 		die("malloc");
-	printf("LRU size:\t%d\n", lru_size);
+	p_err("\nLRU capacity:\t");
+	p_out("%d,",
+		#ifdef lru_capacity
+			lru_capacity(lru) // report real capacity, if provided
+		#else
+			lru_size
+		#endif
+		);
 
 	size_t miss = 0;
+	p_err("\nload everything:\t");
 	time_get(&time);
-	printf("load everything:");
-	for (size_t i = 0, ki = key_count; i < run_count; ++i, --ki) {
+	for (size_t i = 0, ki = key_count - 1; i < run_count; ++i, --ki) {
 		unsigned *r = lru_get_new(lru, keys[ki].chars, keys[ki].len);
 		if (!r || *r == 0)
 			++miss;
@@ -187,12 +221,14 @@ int main(int argc, char ** argv) {
 			ki = key_count;
 	}
 	time_print_diff(&time, run_count);
-	printf("LRU misses:\t%zd%%\n", (miss * 100 + 50) / run_count);
+	p_err("LRU misses [%%]:\t");
+	p_out("%zd,",(miss * 100 + 50) / run_count);
+	p_err("\n");
 
 	unsigned accum = 0; // compute something to make sure compiler can't remove code
+	p_err("search everything:\t");
 	time_get(&time);
-	printf("search everything:");
-	for (size_t i = 0, ki = key_count; i < run_count; ++i, --ki) {
+	for (size_t i = 0, ki = key_count - 1; i < run_count; ++i, --ki) {
 		unsigned *r = lru_get_try(lru, keys[ki].chars, keys[ki].len);
 		if (r)
 			accum += *r;
@@ -200,7 +236,14 @@ int main(int argc, char ** argv) {
 			ki = key_count;
 	}
 	time_print_diff(&time, run_count);
-	printf("ignore: %u\n", accum);
+	p_err("ignore: %u\n", accum);
+
+	// free memory, at least with new LRU
+	#ifdef lru_create
+		lru_free(lru);
+	#endif
+	free(keys);
+	free(data_to_free);
 
 	return 0;
 }