From 2f19e94b0ce78d6ccc9eedbf04b8a3460fd05565 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 29 Apr 2024 21:59:51 +0200 Subject: Sort benchmarks --- sort-benchmark/pairs/Makefile | 20 ++++++++++++++++++ sort-benchmark/pairs/notes.txt | 11 ++++++++++ sort-benchmark/pairs/sort.c | 38 ++++++++++++++++++++++++++++++++++ sort-benchmark/pairs/sort.cpp | 32 ++++++++++++++++++++++++++++ sort-benchmark/pairs/sort_parallel.cpp | 35 +++++++++++++++++++++++++++++++ 5 files changed, 136 insertions(+) create mode 100644 sort-benchmark/pairs/Makefile create mode 100644 sort-benchmark/pairs/notes.txt create mode 100644 sort-benchmark/pairs/sort.c create mode 100644 sort-benchmark/pairs/sort.cpp create mode 100644 sort-benchmark/pairs/sort_parallel.cpp (limited to 'sort-benchmark/pairs') diff --git a/sort-benchmark/pairs/Makefile b/sort-benchmark/pairs/Makefile new file mode 100644 index 0000000..56a37ee --- /dev/null +++ b/sort-benchmark/pairs/Makefile @@ -0,0 +1,20 @@ +CC = gcc +CPP = g++ +OPT = -O3 +VAR = -DARRAYSIZE=100000000 + +all: sort_c sort_cpp sort_parallel_cpp + +sort_c: + ${CC} ${OPT} ${VAR} -std=c11 -o sort sort.c + ./sort + +sort_cpp: + ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort.cpp + ./sort + +sort_parallel_cpp: + ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort_parallel.cpp -ltbb + ./sort + +.PHONY: sort_c sort_cpp sort_parallel_cpp diff --git a/sort-benchmark/pairs/notes.txt b/sort-benchmark/pairs/notes.txt new file mode 100644 index 0000000..7984803 --- /dev/null +++ b/sort-benchmark/pairs/notes.txt @@ -0,0 +1,11 @@ +- Getting the parallel version to work was a pain. Two major gotchas: + (1) -ltbb had to be added *at the end* of the command line + (2) clang requires a libstdc++ option to make this work + of course everything was terrible to decipher with C++ compile errors + being the mess they are. +- For measuring time I could also use + clock_t begin = clock(); + ... + clock_t end = clock(); + double time = (dobule)(end - begin) / CLOCKS_PER_SEC; + but it does not work with the parallel version (it meausres CPU clocks). diff --git a/sort-benchmark/pairs/sort.c b/sort-benchmark/pairs/sort.c new file mode 100644 index 0000000..826a684 --- /dev/null +++ b/sort-benchmark/pairs/sort.c @@ -0,0 +1,38 @@ +#define _POSIX_C_SOURCE 200809L /* Required to use clock_gettime */ + +#include +#include +#include + +typedef struct { int a, b; } pair_t; +pair_t a[ARRAYSIZE]; + +int compar(const void *x, const void *y) { + pair_t *p = (pair_t *)x; + pair_t *q = (pair_t *)y; + int d = p->a - q->a; + return d > 0 ? 1 : (d < 0 ? -1 : (q->b - p->b)); +} + +int main() { + srand(time(NULL)); + for (int i = 0; i < ARRAYSIZE; i++) { + a[i].a = rand() % 1000000; + a[i].b = rand() % 1000000; + } + + struct timespec begin; + clock_gettime(CLOCK_MONOTONIC, &begin); + + qsort(a, ARRAYSIZE, sizeof(pair_t), compar); + + struct timespec end; + clock_gettime(CLOCK_MONOTONIC, &end); + double time = end.tv_sec - begin.tv_sec + + (end.tv_nsec - begin.tv_nsec) / 1000000000.0; + + printf("(%d) C time for %d pairs: %lfs\n", + a[ARRAYSIZE/2].a, ARRAYSIZE, time); + + return 0; +} diff --git a/sort-benchmark/pairs/sort.cpp b/sort-benchmark/pairs/sort.cpp new file mode 100644 index 0000000..77ab5f0 --- /dev/null +++ b/sort-benchmark/pairs/sort.cpp @@ -0,0 +1,32 @@ +#include +#include +#include +#include + +typedef struct { int a, b; } pair_t; +pair_t a[ARRAYSIZE]; + +int main(void) { + srand(time(NULL)); + for (auto &x : a) { + x.a = rand() % 1000000; + x.b = rand() % 1000000; + } + + struct timespec begin; + clock_gettime(CLOCK_MONOTONIC, &begin); + + std::sort(a, a+ARRAYSIZE, + [](const pair_t &x, const pair_t &y) { + int d = x.a - y.a; + return d < 0 || (d == 0 && x.b > y.b); + }); + + struct timespec end; + clock_gettime(CLOCK_MONOTONIC, &end); + double time = end.tv_sec - begin.tv_sec + + (end.tv_nsec - begin.tv_nsec) / 1000000000.0; + + std::cout << "(" << a[ARRAYSIZE/2].a << ") C++ time for " << ARRAYSIZE + << " pairs: " << time << "s\n"; +} diff --git a/sort-benchmark/pairs/sort_parallel.cpp b/sort-benchmark/pairs/sort_parallel.cpp new file mode 100644 index 0000000..ef9ee05 --- /dev/null +++ b/sort-benchmark/pairs/sort_parallel.cpp @@ -0,0 +1,35 @@ +/* Requires Thread Building Blocks (libtbb-dev on Debian) */ + +#include +#include +#include +#include +#include + +typedef struct { int a, b; } pair_t; +pair_t a[ARRAYSIZE]; + +int main(void) { + srand(time(NULL)); + for (auto &x : a) { + x.a = rand() % 1000000; + x.b = rand() % 1000000; + } + + struct timespec begin; + clock_gettime(CLOCK_MONOTONIC, &begin); + + std::sort(std::execution::par, a, a+ARRAYSIZE, + [](const pair_t &x, const pair_t &y) { + int d = x.a - y.a; + return d < 0 || (d == 0 && x.b > y.b); + }); + + struct timespec end; + clock_gettime(CLOCK_MONOTONIC, &end); + double time = end.tv_sec - begin.tv_sec + + (end.tv_nsec - begin.tv_nsec) / 1000000000.0; + + std::cout << "(" << a[ARRAYSIZE/2].a << ") C++ time for " << ARRAYSIZE + << " pairs (parallel): " << time << "s\n"; +} -- cgit v1.3