-
-
Save lhog/fd82bf5e36cea94ef50b1701a2c7ba53 to your computer and use it in GitHub Desktop.
taskflow compilation error
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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