diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | bench.c | 7 | ||||
| -rw-r--r-- | common.h | 3 | ||||
| -rw-r--r-- | counts.c | 38 | ||||
| -rw-r--r-- | counts.h | 23 | ||||
| -rw-r--r-- | distribute.c | 5 | ||||
| -rw-r--r-- | grailsort.c | 12 | ||||
| -rw-r--r-- | rotate.c | 3 | ||||
| -rw-r--r-- | sortnet.c | 5 | ||||
| -rw-r--r-- | swap.c | 3 | ||||
| -rw-r--r-- | testcases.c | 5 | ||||
| -rw-r--r-- | testcases.h | 1 |
12 files changed, 99 insertions, 8 deletions
@@ -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 @@ -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); @@ -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); } @@ -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); @@ -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); } @@ -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); |