Add instrumentation

Track the number of comparisons, swaps, and rotations performed in each
part of the sorting algorithm.

12 files changed, 99 insertions, 8 deletions

diff --git a/Makefile b/Makefile
index 8cf35ad..e1281d1 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-COMMONFLAGS = -Os -pipe -D_XOPEN_SOURCE=500
+COMMONFLAGS = -Os -pipe -D_XOPEN_SOURCE=700
 CFLAGS   = -std=c99
 CXXFLAGS = -std=c++11
 LIBS     = -lm -lrt
diff --git a/bench.c b/bench.c
index 75bf32e..a5da95f 100644
--- a/bench.c
+++ b/bench.c
@@ -5,6 +5,8 @@
 
 #include "testcases.h"
 #include "sorters.h"
+#include "common.h"
+#include "counts.h"
 
 #define CMP_WIDTH  12
 #define MS_WIDTH   6
@@ -33,14 +35,15 @@ int main()
 		for (size_t size = MIN_SIZE; size <= MAX_SIZE; size *= 10) {
 			printf("%-*s ", SORT_WIDTH, size == MIN_SIZE ? s->name : "");
 			for (const struct testcase *t = testcases; t->name; t++) {
-				comparisons = 0;
+				clear_all_counts();
 				t->init(size);
 
 				if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start)) abort();
 				s->func(buffer, size, sizeof(int), t->cmp);
 				if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop)) abort();
 
-				printf("%*lu %*lu ", CMP_WIDTH, comparisons, MS_WIDTH, timediff_ms(&start, &stop));
+				printf("%*lu %*lu ", CMP_WIDTH, counts[CURRENT].compare, MS_WIDTH, timediff_ms(&start, &stop));
+				print_counts();
 				assert_sorted(size, t->cmp);
 			}
 			printf(" %*zu\n", SIZE_WIDTH, size);
diff --git a/common.h b/common.h
index e6c5662..fcdfe3d 100644
--- a/common.h
+++ b/common.h
@@ -11,9 +11,8 @@ size_t binary_search(const char *, char *, size_t, size_t, cmpfun);
 void distribute_buffer(char *, size_t, size_t, size_t, cmpfun);
 void swap(char *, char *, size_t);
 void rotate(char *, size_t, size_t);
+void sorting_network(char *, size_t, size_t, cmpfun);
 
 #define MAX_SORTNET 8
 
-void sorting_network(char *, size_t, size_t, cmpfun);
-
 #endif
diff --git a/counts.c b/counts.c
new file mode 100644
index 0000000..d1f3910
--- /dev/null
+++ b/counts.c
@@ -0,0 +1,38 @@
+#include <stdint.h>
+#include <stdio.h>
+
+#include "counts.h"
+
+struct counts counts[MAX_COUNTS];
+
+static void clear(struct counts *c)
+{
+	*c = (struct counts) {0};
+}
+
+void clear_all_counts(void)
+{
+	for (int i = 0; i < MAX_COUNTS; i++)
+		clear(counts+i);
+}
+
+void clear_accumulator(void)
+{
+	clear(counts);
+}
+
+void add_counts(struct counts *target, struct counts *snapshot)
+{
+	target->compare += counts[CURRENT].compare - snapshot->compare;
+	target->rotate  += counts[CURRENT].rotate  - snapshot->rotate;
+	target->swap    += counts[CURRENT].swap    - snapshot->swap;
+}
+
+void print_counts(void)
+{
+	char *labels[] = {"total", "sortnet", "overlap", "merge", "move buffer", "distribute"};
+	for (int i = 0; i < MAX_COUNTS; i++) {
+		const struct counts *c = counts+i;
+		dprintf(42, "%12s: %10lu cmp, %10lu swap, %10lu rotate\n", labels[i], c->compare, c->swap, c->rotate);
+	}
+}
diff --git a/counts.h b/counts.h
new file mode 100644
index 0000000..46e2e18
--- /dev/null
+++ b/counts.h
@@ -0,0 +1,23 @@
+#ifndef COUNTS_H
+#define COUNTS_H
+
+enum {
+	CURRENT,
+	SORTNET,
+	LAST_OVERLAP,
+	MERGE,
+	MOVE_BUFFER,
+	DISTRIBUTE,
+	MAX_COUNTS
+};
+
+extern struct counts {
+	unsigned long compare, swap, rotate;
+} counts[MAX_COUNTS];
+
+void clear_all_counts(void);
+void clear_accumulator(void);
+void add_counts(struct counts*, struct counts*);
+void print_counts(void);
+
+#endif
diff --git a/distribute.c b/distribute.c
index d2d1eff..7c2b49f 100644
--- a/distribute.c
+++ b/distribute.c
@@ -1,9 +1,12 @@
 #include <stddef.h>
 
 #include "common.h"
+#include "counts.h"
 
 void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
 {
+	struct counts snapshot = counts[CURRENT];
+
 	while (bufnmel && sortnmel) {
 		char  *sorted    = base + bufnmel * width;
 		size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp);
@@ -15,4 +18,6 @@ void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width
 		bufnmel  -= 1;
 		sortnmel -= insertpos;
 	}
+
+	add_counts(counts + DISTRIBUTE, &snapshot);
 }
diff --git a/grailsort.c b/grailsort.c
index 6f63701..9eff4d6 100644
--- a/grailsort.c
+++ b/grailsort.c
@@ -6,6 +6,7 @@
 
 #include "sorters.h"
 #include "common.h"
+#include "counts.h"
 
 static inline void *tail(char *base, size_t nmel, size_t width)
 {
@@ -15,13 +16,19 @@ static inline void *tail(char *base, size_t nmel, size_t width)
 /* get index of last block whose head is less than the previous block's tail */
 static size_t last_overlap(char *base, size_t bcount, size_t bwidth, size_t width, cmpfun cmp)
 {
+	struct counts snapshot = counts[CURRENT];
+
 	for (char *cur = tail(base, bcount, bwidth); --bcount; cur -= bwidth)
 		if (cmp(cur - width, cur) > 0) break;
+
+	add_counts(counts + LAST_OVERLAP, &snapshot);
 	return bcount;
 }
 
 size_t merge(char *buf, char *a, char *b, size_t bufnmel, size_t anmel, size_t bnmel, size_t width, cmpfun cmp)
 {
+	struct counts snapshot = counts[CURRENT];
+
 	while (bnmel) {
 		char *a_tail   = tail(a,   anmel,   width);
 		char *b_tail   = tail(b,   bnmel,   width);
@@ -36,6 +43,8 @@ size_t merge(char *buf, char *a, char *b, size_t bufnmel, size_t anmel, size_t b
 		}
 		bufnmel--;
 	}
+
+	add_counts(counts + MERGE, &snapshot);
 	return anmel;
 }
 
@@ -81,7 +90,10 @@ void grailsort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
 		blocks    = overlap;
 	}
 
+	struct counts snapshot = counts[CURRENT];
 	rotate(base, buf-base + bufnmel*width, buf-base);
+	add_counts(counts + MOVE_BUFFER, &snapshot);
+
 	grailsort(base, bufnmel, width, cmp);
 	distribute_buffer(base, bufnmel, nmel - bufnmel, width, cmp);
 }
diff --git a/rotate.c b/rotate.c
index 5eb7696..1815812 100644
--- a/rotate.c
+++ b/rotate.c
@@ -1,11 +1,14 @@
 #include <stddef.h>
 
 #include "common.h"
+#include "counts.h"
 
 /* rotates left */
 void rotate(char *base, size_t size, size_t shift)
 {
 	int dir = 1;
+
+	counts[CURRENT].rotate++;
 	while (shift) {
 		while (2*shift <= size) {
 			swap(base, base + dir*shift, shift);
diff --git a/sortnet.c b/sortnet.c
index fd99a17..40c78a8 100644
--- a/sortnet.c
+++ b/sortnet.c
@@ -2,6 +2,7 @@
 #include <stdint.h>
 
 #include "common.h"
+#include "counts.h"
 
 static const uint8_t sortnet[][2] = {
 	/* 0: index =  0 */
@@ -30,9 +31,13 @@ static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
 
 void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
 {
+	struct counts snapshot = counts[CURRENT];
+
 	for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
 		char *elem1 = base + sortnet[i][0] * width;
 		char *elem2 = base + sortnet[i][1] * width;
 		if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
 	}
+
+	add_counts(counts + SORTNET, &snapshot);
 }
diff --git a/swap.c b/swap.c
index 626abb0..ecf68e5 100644
--- a/swap.c
+++ b/swap.c
@@ -2,9 +2,12 @@
 #include <stdint.h>
 
 #include "common.h"
+#include "counts.h"
 
 void swap(char *a, char *b, size_t width)
 {
+	counts[CURRENT].swap++;
+
 #ifdef __GNUC__
 	typedef uint32_t __attribute__((__may_alias__)) u32;
 
diff --git a/testcases.c b/testcases.c
index 1a50632..a41cd89 100644
--- a/testcases.c
+++ b/testcases.c
@@ -3,9 +3,10 @@
 #include <stdlib.h>
 
 #include "testcases.h"
+#include "common.h"
+#include "counts.h"
 
 int buffer[MAX_SIZE];
-unsigned long comparisons;
 
 void assert_sorted(size_t size, cmpfun cmp)
 {
@@ -19,7 +20,7 @@ static int compare(const void *a, const void *b)
 	const int *aa = a;
 	const int *bb = b;
 
-	comparisons++;
+	counts[CURRENT].compare++;
 	if (*aa < *bb)
 		return -1;
 	else if (*aa > *bb)
diff --git a/testcases.h b/testcases.h
index fc2ffd9..acb409b 100644
--- a/testcases.h
+++ b/testcases.h
@@ -6,7 +6,6 @@
 #define MAX_SIZE 10000000
 
 extern int buffer[MAX_SIZE];
-extern unsigned long comparisons;
 
 void assert_sorted(size_t size, cmpfun cmp);