aboutsummaryrefslogtreecommitdiff
path: root/sort-benchmark
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--sort-benchmark/integers/Makefile20
-rw-r--r--sort-benchmark/integers/notes.txt11
-rw-r--r--sort-benchmark/integers/sort.c29
-rw-r--r--sort-benchmark/integers/sort.cpp25
-rw-r--r--sort-benchmark/integers/sort_parallel.cpp28
-rw-r--r--sort-benchmark/pairs/Makefile20
-rw-r--r--sort-benchmark/pairs/notes.txt11
-rw-r--r--sort-benchmark/pairs/sort.c38
-rw-r--r--sort-benchmark/pairs/sort.cpp32
-rw-r--r--sort-benchmark/pairs/sort_parallel.cpp35
10 files changed, 249 insertions, 0 deletions
diff --git a/sort-benchmark/integers/Makefile b/sort-benchmark/integers/Makefile
new file mode 100644
index 0000000..56a37ee
--- /dev/null
+++ b/sort-benchmark/integers/Makefile
@@ -0,0 +1,20 @@
1CC = gcc
2CPP = g++
3OPT = -O3
4VAR = -DARRAYSIZE=100000000
5
6all: sort_c sort_cpp sort_parallel_cpp
7
8sort_c:
9 ${CC} ${OPT} ${VAR} -std=c11 -o sort sort.c
10 ./sort
11
12sort_cpp:
13 ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort.cpp
14 ./sort
15
16sort_parallel_cpp:
17 ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort_parallel.cpp -ltbb
18 ./sort
19
20.PHONY: sort_c sort_cpp sort_parallel_cpp
diff --git a/sort-benchmark/integers/notes.txt b/sort-benchmark/integers/notes.txt
new file mode 100644
index 0000000..7984803
--- /dev/null
+++ b/sort-benchmark/integers/notes.txt
@@ -0,0 +1,11 @@
1- Getting the parallel version to work was a pain. Two major gotchas:
2 (1) -ltbb had to be added *at the end* of the command line
3 (2) clang requires a libstdc++ option to make this work
4 of course everything was terrible to decipher with C++ compile errors
5 being the mess they are.
6- For measuring time I could also use
7 clock_t begin = clock();
8 ...
9 clock_t end = clock();
10 double time = (dobule)(end - begin) / CLOCKS_PER_SEC;
11 but it does not work with the parallel version (it meausres CPU clocks).
diff --git a/sort-benchmark/integers/sort.c b/sort-benchmark/integers/sort.c
new file mode 100644
index 0000000..2a23d9d
--- /dev/null
+++ b/sort-benchmark/integers/sort.c
@@ -0,0 +1,29 @@
1#define _POSIX_C_SOURCE 200809L /* Required to use clock_gettime */
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <time.h>
6
7int a[ARRAYSIZE];
8
9int compar(const void *x, const void *y) { return *(int *)x - *(int *)y; }
10
11int main() {
12 srand(time(NULL));
13 for (int i = 0; i < ARRAYSIZE; i++) a[i] = rand() % 1000000000;
14
15 struct timespec begin;
16 clock_gettime(CLOCK_MONOTONIC, &begin);
17
18 qsort(a, ARRAYSIZE, sizeof(int), compar);
19
20 struct timespec end;
21 clock_gettime(CLOCK_MONOTONIC, &end);
22 double time = end.tv_sec - begin.tv_sec +
23 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
24
25 printf("(%d) C time for %d numbers: %lfs\n",
26 a[ARRAYSIZE/2], ARRAYSIZE, time);
27
28 return 0;
29}
diff --git a/sort-benchmark/integers/sort.cpp b/sort-benchmark/integers/sort.cpp
new file mode 100644
index 0000000..3434d7f
--- /dev/null
+++ b/sort-benchmark/integers/sort.cpp
@@ -0,0 +1,25 @@
1#include <algorithm>
2#include <cstdlib>
3#include <ctime>
4#include <iostream>
5
6int a[ARRAYSIZE];
7
8int main(void) {
9 srand(time(NULL));
10 for (auto &x : a) x = rand() % 1000000000;
11
12 struct timespec begin;
13 clock_gettime(CLOCK_MONOTONIC, &begin);
14
15 std::sort(a, a+ARRAYSIZE,
16 [](const int &x, const int &y) { return x < y; });
17
18 struct timespec end;
19 clock_gettime(CLOCK_MONOTONIC, &end);
20 double time = end.tv_sec - begin.tv_sec +
21 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
22
23 std::cout << "(" << a[ARRAYSIZE/2] << ") C++ time for " << ARRAYSIZE
24 << " numbers: " << time << "s\n";
25}
diff --git a/sort-benchmark/integers/sort_parallel.cpp b/sort-benchmark/integers/sort_parallel.cpp
new file mode 100644
index 0000000..5de4158
--- /dev/null
+++ b/sort-benchmark/integers/sort_parallel.cpp
@@ -0,0 +1,28 @@
1/* Requires Thread Building Blocks (libtbb-dev on Debian) */
2
3#include <algorithm>
4#include <cstdlib>
5#include <ctime>
6#include <execution>
7#include <iostream>
8
9int a[ARRAYSIZE];
10
11int main(void) {
12 srand(time(NULL));
13 for (auto &x : a) x = rand() % 1000000000;
14
15 struct timespec begin;
16 clock_gettime(CLOCK_MONOTONIC, &begin);
17
18 std::sort(std::execution::par, a, a+ARRAYSIZE,
19 [](const int &x, const int &y) { return x < y; });
20
21 struct timespec end;
22 clock_gettime(CLOCK_MONOTONIC, &end);
23 double time = end.tv_sec - begin.tv_sec +
24 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
25
26 std::cout << "(" << a[ARRAYSIZE/2] << ") C++ time for " << ARRAYSIZE
27 << " numbers (parallel): " << time << "s\n";
28}
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 @@
1CC = gcc
2CPP = g++
3OPT = -O3
4VAR = -DARRAYSIZE=100000000
5
6all: sort_c sort_cpp sort_parallel_cpp
7
8sort_c:
9 ${CC} ${OPT} ${VAR} -std=c11 -o sort sort.c
10 ./sort
11
12sort_cpp:
13 ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort.cpp
14 ./sort
15
16sort_parallel_cpp:
17 ${CPP} ${OPT} ${VAR} -std=c++20 -o sort sort_parallel.cpp -ltbb
18 ./sort
19
20.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 @@
1- Getting the parallel version to work was a pain. Two major gotchas:
2 (1) -ltbb had to be added *at the end* of the command line
3 (2) clang requires a libstdc++ option to make this work
4 of course everything was terrible to decipher with C++ compile errors
5 being the mess they are.
6- For measuring time I could also use
7 clock_t begin = clock();
8 ...
9 clock_t end = clock();
10 double time = (dobule)(end - begin) / CLOCKS_PER_SEC;
11 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 @@
1#define _POSIX_C_SOURCE 200809L /* Required to use clock_gettime */
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <time.h>
6
7typedef struct { int a, b; } pair_t;
8pair_t a[ARRAYSIZE];
9
10int compar(const void *x, const void *y) {
11 pair_t *p = (pair_t *)x;
12 pair_t *q = (pair_t *)y;
13 int d = p->a - q->a;
14 return d > 0 ? 1 : (d < 0 ? -1 : (q->b - p->b));
15}
16
17int main() {
18 srand(time(NULL));
19 for (int i = 0; i < ARRAYSIZE; i++) {
20 a[i].a = rand() % 1000000;
21 a[i].b = rand() % 1000000;
22 }
23
24 struct timespec begin;
25 clock_gettime(CLOCK_MONOTONIC, &begin);
26
27 qsort(a, ARRAYSIZE, sizeof(pair_t), compar);
28
29 struct timespec end;
30 clock_gettime(CLOCK_MONOTONIC, &end);
31 double time = end.tv_sec - begin.tv_sec +
32 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
33
34 printf("(%d) C time for %d pairs: %lfs\n",
35 a[ARRAYSIZE/2].a, ARRAYSIZE, time);
36
37 return 0;
38}
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 @@
1#include <algorithm>
2#include <cstdlib>
3#include <ctime>
4#include <iostream>
5
6typedef struct { int a, b; } pair_t;
7pair_t a[ARRAYSIZE];
8
9int main(void) {
10 srand(time(NULL));
11 for (auto &x : a) {
12 x.a = rand() % 1000000;
13 x.b = rand() % 1000000;
14 }
15
16 struct timespec begin;
17 clock_gettime(CLOCK_MONOTONIC, &begin);
18
19 std::sort(a, a+ARRAYSIZE,
20 [](const pair_t &x, const pair_t &y) {
21 int d = x.a - y.a;
22 return d < 0 || (d == 0 && x.b > y.b);
23 });
24
25 struct timespec end;
26 clock_gettime(CLOCK_MONOTONIC, &end);
27 double time = end.tv_sec - begin.tv_sec +
28 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
29
30 std::cout << "(" << a[ARRAYSIZE/2].a << ") C++ time for " << ARRAYSIZE
31 << " pairs: " << time << "s\n";
32}
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 @@
1/* Requires Thread Building Blocks (libtbb-dev on Debian) */
2
3#include <algorithm>
4#include <cstdlib>
5#include <ctime>
6#include <execution>
7#include <iostream>
8
9typedef struct { int a, b; } pair_t;
10pair_t a[ARRAYSIZE];
11
12int main(void) {
13 srand(time(NULL));
14 for (auto &x : a) {
15 x.a = rand() % 1000000;
16 x.b = rand() % 1000000;
17 }
18
19 struct timespec begin;
20 clock_gettime(CLOCK_MONOTONIC, &begin);
21
22 std::sort(std::execution::par, a, a+ARRAYSIZE,
23 [](const pair_t &x, const pair_t &y) {
24 int d = x.a - y.a;
25 return d < 0 || (d == 0 && x.b > y.b);
26 });
27
28 struct timespec end;
29 clock_gettime(CLOCK_MONOTONIC, &end);
30 double time = end.tv_sec - begin.tv_sec +
31 (end.tv_nsec - begin.tv_nsec) / 1000000000.0;
32
33 std::cout << "(" << a[ARRAYSIZE/2].a << ") C++ time for " << ARRAYSIZE
34 << " pairs (parallel): " << time << "s\n";
35}

Generated with cgit - Back to sebastiano.tronto.net