From 6c5df17a302e99dec62aa749ffc30745cc7679a4 Mon Sep 17 00:00:00 2001 From: David Monniaux Date: Sat, 19 Jan 2019 13:33:57 +0100 Subject: quicksort --- test/monniaux/cycles.h | 26 ++++++++++++++++++++ test/monniaux/mod_int_mat/int_mat_run.c | 28 +--------------------- test/monniaux/quicksort/Makefile | 40 +++++++++++++++++++++++++++++++ test/monniaux/quicksort/quicksort.c | 42 +++++++++++++++++++++++++++++++++ test/monniaux/quicksort/quicksort.h | 7 ++++++ test/monniaux/quicksort/quicksort_run.c | 22 +++++++++++++++++ 6 files changed, 138 insertions(+), 27 deletions(-) create mode 100644 test/monniaux/cycles.h create mode 100644 test/monniaux/quicksort/Makefile create mode 100644 test/monniaux/quicksort/quicksort.c create mode 100644 test/monniaux/quicksort/quicksort.h create mode 100644 test/monniaux/quicksort/quicksort_run.c (limited to 'test/monniaux') diff --git a/test/monniaux/cycles.h b/test/monniaux/cycles.h new file mode 100644 index 00000000..212e65fc --- /dev/null +++ b/test/monniaux/cycles.h @@ -0,0 +1,26 @@ +typedef uint64_t cycle_t; + +#ifdef __K1C__ +#include +static inline void cycle_count_config(void) +{ + /* config pmc for cycle count */ + uint64_t pmc_value = __builtin_k1_get(K1_SFR_PMC); + + pmc_value &= ~(0xfULL); + __builtin_k1_set(K1_SFR_PMC, pmc_value); +} + +static inline uint64_t get_cycle(void) +{ + return __builtin_k1_get(K1_SFR_PM0); +} +#else +static inline void cycle_count_config(void) { } +#ifdef __x86_64__ +#include +static inline cycle_t get_cycle(void) { return __rdtsc(); } +#else +static inline cycle_t get_cycle(void) { return 0; } +#endif +#endif diff --git a/test/monniaux/mod_int_mat/int_mat_run.c b/test/monniaux/mod_int_mat/int_mat_run.c index 42cb54fb..f3955345 100644 --- a/test/monniaux/mod_int_mat/int_mat_run.c +++ b/test/monniaux/mod_int_mat/int_mat_run.c @@ -3,33 +3,7 @@ #include #include #include "modint.h" - -typedef uint64_t cycle_t; - -#ifdef __K1C__ -#include -static inline void cycle_count_config(void) -{ - /* config pmc for cycle count */ - uint64_t pmc_value = __builtin_k1_get(K1_SFR_PMC); - - pmc_value &= ~(0xfULL); - __builtin_k1_set(K1_SFR_PMC, pmc_value); -} - -static inline uint64_t get_cycle(void) -{ - return __builtin_k1_get(K1_SFR_PM0); -} -#else -static inline void cycle_count_config(void) { } -#ifdef __x86_64__ -#include -static inline cycle_t get_cycle(void) { return __rdtsc(); } -#else -static inline cycle_t get_cycle(void) { return 0; } -#endif -#endif +#include "../cycles.h" int main() { const unsigned m = 40, n = 21, p = 30; diff --git a/test/monniaux/quicksort/Makefile b/test/monniaux/quicksort/Makefile new file mode 100644 index 00000000..1d8913dd --- /dev/null +++ b/test/monniaux/quicksort/Makefile @@ -0,0 +1,40 @@ +CFLAGS=-Wall -O3 +K1C_CC=k1-mbr-gcc +K1C_CFLAGS=-Wall -O3 -std=c99 +K1C_CCOMP=../../../ccomp +K1C_CCOMPFLAGS=-Wall -O3 -D__thread= -D__int128=int + +PRODUCTS=quicksort.host quicksort.gcc.k1c.out quicksort.ccomp.k1c.out quicksort.ccomp.k1c.s quicksort.gcc.k1c.s quicksort.gcc.k1c quicksort.ccomp.k1c + +all: $(PRODUCTS) + +%.gcc.k1c.s: %.c + $(K1C_CC) $(K1C_CFLAGS) -S $< -o $@ + +%.gcc.k1c.o: %.gcc.k1c.s + $(K1C_CC) $(K1C_CFLAGS) -c $< -o $@ + +%.ccomp.k1c.s: %.c + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) -S $< -o $@ + +%.ccomp.k1c.o: %.ccomp.k1c.s + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) -c $< -o $@ + +quicksort.host: quicksort.c quicksort_run.c quicksort.h + $(CC) $(CFLAGS) quicksort.c quicksort_run.c -o $@ + +quicksort.gcc.k1c.s quicksort.ccomp.k1c.s quicksort_run.gcc.k1c.s: quicksort.h + +quicksort.gcc.k1c: quicksort.gcc.k1c.o quicksort_run.gcc.k1c.o + $(K1C_CC) $(K1C_CFLAGS) $+ -o $@ + +quicksort.ccomp.k1c: quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) $+ -o $@ + +%.k1c.out: %.k1c + k1-cluster --cycle-based -- $< | tee $@ + +clean: + $(RM) -f $(PRODUCTS) quicksort.gcc.k1c.o quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o + +.PHONY: clean diff --git a/test/monniaux/quicksort/quicksort.c b/test/monniaux/quicksort/quicksort.c new file mode 100644 index 00000000..de04bf2d --- /dev/null +++ b/test/monniaux/quicksort/quicksort.c @@ -0,0 +1,42 @@ +#include "quicksort.h" + +/* Rosetta Code */ +void quicksort(data *A, int len) { + if (len < 2) return; + + data pivot = A[len / 2]; + + int i, j; + for (i = 0, j = len - 1; ; i++, j--) { + while (A[i] < pivot) i++; + while (A[j] > pivot) j--; + + if (i >= j) break; + + data temp = A[i]; + A[i] = A[j]; + A[j] = temp; + } + + quicksort(A, i); + quicksort(A + i, len - i); +} + +data data_random(void) { + static uint64_t next = 1325997111; + next = next * 1103515245 + 12345; + return next; +} + +void data_vec_random(data *a, unsigned len) { + for(unsigned i=0; i a[i+1]) return false; + } + return true; +} diff --git a/test/monniaux/quicksort/quicksort.h b/test/monniaux/quicksort/quicksort.h new file mode 100644 index 00000000..cc73e7c3 --- /dev/null +++ b/test/monniaux/quicksort/quicksort.h @@ -0,0 +1,7 @@ +#include +#include + +typedef uint64_t data; +void quicksort(data *A, int len); +void data_vec_random(data *a, unsigned len); +bool data_vec_is_sorted(const data *a, unsigned len); diff --git a/test/monniaux/quicksort/quicksort_run.c b/test/monniaux/quicksort/quicksort_run.c new file mode 100644 index 00000000..c269cc48 --- /dev/null +++ b/test/monniaux/quicksort/quicksort_run.c @@ -0,0 +1,22 @@ +#include +#include +#include +#include "quicksort.h" +#include "../cycles.h" + +int main (void) { + cycle_count_config(); + unsigned len=10000; + data *vec = malloc(sizeof(data) * len); + data_vec_random(vec, len); + cycle_t quicksort_time = get_cycle(); + quicksort(vec, len); + quicksort_time = get_cycle() - quicksort_time; + printf("sorted=%s\n" + "quicksort_time=%" PRIu64 "\n", + data_vec_is_sorted(vec, len)?"true":"false", + quicksort_time); + free(vec); + return 0; +} + -- cgit