summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--bench.c7
-rw-r--r--common.h3
-rw-r--r--counts.c38
-rw-r--r--counts.h23
-rw-r--r--distribute.c5
-rw-r--r--grailsort.c12
-rw-r--r--rotate.c3
-rw-r--r--sortnet.c5
-rw-r--r--swap.c3
-rw-r--r--testcases.c5
-rw-r--r--testcases.h1
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);