Skip to content

Instantly share code, notes, and snippets.

@lhog

lhog/cpp Secret

Created September 15, 2023 23:52
Show Gist options
  • Save lhog/fd82bf5e36cea94ef50b1701a2c7ba53 to your computer and use it in GitHub Desktop.
Save lhog/fd82bf5e36cea94ef50b1701a2c7ba53 to your computer and use it in GitHub Desktop.
taskflow compilation error
#include <iostream>
#include <vector>
#include <array>
#include <thread>
#include <future>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstdint>
#include <taskflow/taskflow.hpp>
#include <taskflow/algorithm/sort.hpp>
static constexpr size_t NOPAR_RANGE = 4096;
template<typename RandomIt, typename Pred>
void parallelQuicksort(RandomIt first, RandomIt last, uint32_t numThreads, Pred pred)
{
if (first == last)
return;
if (numThreads <= 1 || std::distance(first, last) <= NOPAR_RANGE) {
// If there's only one thread or the range is small, use standard std::sort
std::sort(first, last, pred);
return;
}
auto pivot = *std::next(first, std::distance(first, last) / 2);
auto middle1 = std::partition(first, last, [pivot, pred](const auto& em) {
return pred(em, pivot);
});
auto middle2 = std::partition(middle1, last, [pivot, pred](const auto& em) {
return !pred(pivot, em);
});
std::array futures {
std::async(std::launch::async, parallelQuicksort<RandomIt, Pred>, first, middle1, numThreads >> 1, pred),
std::async(std::launch::async, parallelQuicksort<RandomIt, Pred>, middle2, last, numThreads >> 1, pred)
};
for (auto& future : futures)
future.get();
}
template<typename RandomIt, typename Pred>
void parallelQuicksort(RandomIt first, RandomIt last, Pred pred = std::less{}) {
const int numThreads = std::thread::hardware_concurrency(); // Number of available CPU cores
parallelQuicksort(first, last, numThreads, pred);
}
// Function to generate a random vector of a given size
std::vector<int> generateRandomVector(int size) {
std::vector<int> vec;
vec.reserve(size);
std::srand(static_cast<unsigned int>(std::time(nullptr)));
for (int i = 0; i < size; ++i) {
vec.push_back(std::rand());
}
return vec;
}
int main() {
const int REP = 200;
const int numElements = 80000; // Number of elements in the vector
// Generate a random vector
std::vector<int> data = generateRandomVector(numElements);
std::vector<int> data1;
std::vector<int> data2;
std::vector<int> data3;
// Time and run parallelQuicksort
std::cout << "Sorting with parallelQuicksort..." << std::endl;
std::clock_t start_time = std::clock();
for (int i = 0; i < REP; ++i) {
data1 = data;
parallelQuicksort(data1.begin(), data1.end(), std::less{});
}
std::clock_t end_time = std::clock();
double elapsed_time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
std::cout << "parallelQuicksort took " << elapsed_time << " seconds." << std::endl;
// Time and run tf::sort()
tf::Taskflow taskflow;
tf::Executor executor;
std::cout << "Sorting with tf::sort()..." << std::endl;
start_time = std::clock();
for (int i = 0; i < REP; ++i) {
data2 = data;
taskflow.sort(data2.begin(), data2.end(), std::less{});
executor.run(taskflow).wait();
}
end_time = std::clock();
elapsed_time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
std::cout << "tf::sort() took " << elapsed_time << " seconds." << std::endl;
// Time and run std::sort()
std::cout << "Sorting with std::sort()..." << std::endl;
start_time = std::clock();
for (int i = 0; i < REP; ++i) {
data3 = data;
std::sort(data3.begin(), data3.end(), std::less{});
}
end_time = std::clock();
elapsed_time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
std::cout << "std::sort() took " << elapsed_time << " seconds." << std::endl;
// Verify that parallel algos and std::sort produced the same result
{
bool sortingCorrect = (data1 == data3);
std::cout << "Sorting correctness: " << (sortingCorrect ? "Correct" : "Incorrect") << std::endl;
}
{
bool sortingCorrect = (data2 == data3);
std::cout << "Sorting correctness: " << (sortingCorrect ? "Correct" : "Incorrect") << std::endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment