commit 2f19e94b0ce78d6ccc9eedbf04b8a3460fd05565
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 29 Apr 2024 21:59:51 +0200
Sort benchmarks
Diffstat:
12 files changed, 269 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+sort-benchmark/*/sort
diff --git a/README.md b/README.md
@@ -0,0 +1,19 @@
+# Taming C++
+
+Experiments with C++ and comparisons with C.
+
+## sort-benchmark
+
+Inspired by [Bert's post](https://berthub.eu/articles/posts/c++-1).
+
+Sorting an array of integers is a simple task, so C and C++ should perform
+similarly, right? Wrong!
+
+```
+C time for 100000000 numbers: 9.886314s
+C++ time for 100000000 numbers: 4.92299s
+C++ time for 100000000 numbers (parallel): 0.495435s
+```
+
+A similar benchmark is provided for sorting an arrays of pairs in a
+non-standard way.
diff --git a/sort-benchmark/integers/Makefile b/sort-benchmark/integers/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/integers/notes.txt b/sort-benchmark/integers/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/integers/sort.c b/sort-benchmark/integers/sort.c
@@ -0,0 +1,29 @@
+#define _POSIX_C_SOURCE 200809L /* Required to use clock_gettime */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+int a[ARRAYSIZE];
+
+int compar(const void *x, const void *y) { return *(int *)x - *(int *)y; }
+
+int main() {
+ srand(time(NULL));
+ for (int i = 0; i < ARRAYSIZE; i++) a[i] = rand() % 1000000000;
+
+ struct timespec begin;
+ clock_gettime(CLOCK_MONOTONIC, &begin);
+
+ qsort(a, ARRAYSIZE, sizeof(int), 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 numbers: %lfs\n",
+ a[ARRAYSIZE/2], ARRAYSIZE, time);
+
+ return 0;
+}
diff --git a/sort-benchmark/integers/sort.cpp b/sort-benchmark/integers/sort.cpp
@@ -0,0 +1,25 @@
+#include <algorithm>
+#include <cstdlib>
+#include <ctime>
+#include <iostream>
+
+int a[ARRAYSIZE];
+
+int main(void) {
+ srand(time(NULL));
+ for (auto &x : a) x = rand() % 1000000000;
+
+ struct timespec begin;
+ clock_gettime(CLOCK_MONOTONIC, &begin);
+
+ std::sort(a, a+ARRAYSIZE,
+ [](const int &x, const int &y) { return x < y; });
+
+ 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] << ") C++ time for " << ARRAYSIZE
+ << " numbers: " << time << "s\n";
+}
diff --git a/sort-benchmark/integers/sort_parallel.cpp b/sort-benchmark/integers/sort_parallel.cpp
@@ -0,0 +1,28 @@
+/* Requires Thread Building Blocks (libtbb-dev on Debian) */
+
+#include <algorithm>
+#include <cstdlib>
+#include <ctime>
+#include <execution>
+#include <iostream>
+
+int a[ARRAYSIZE];
+
+int main(void) {
+ srand(time(NULL));
+ for (auto &x : a) x = rand() % 1000000000;
+
+ struct timespec begin;
+ clock_gettime(CLOCK_MONOTONIC, &begin);
+
+ std::sort(std::execution::par, a, a+ARRAYSIZE,
+ [](const int &x, const int &y) { return x < y; });
+
+ 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] << ") C++ time for " << ARRAYSIZE
+ << " numbers (parallel): " << time << "s\n";
+}
diff --git a/sort-benchmark/pairs/Makefile 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
@@ -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
@@ -0,0 +1,38 @@
+#define _POSIX_C_SOURCE 200809L /* Required to use clock_gettime */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+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
@@ -0,0 +1,32 @@
+#include <algorithm>
+#include <cstdlib>
+#include <ctime>
+#include <iostream>
+
+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
@@ -0,0 +1,35 @@
+/* Requires Thread Building Blocks (libtbb-dev on Debian) */
+
+#include <algorithm>
+#include <cstdlib>
+#include <ctime>
+#include <execution>
+#include <iostream>
+
+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";
+}
