Skip to content

Instantly share code, notes, and snippets.

@PanagiotisPtr
Last active January 25, 2019 00:34
Show Gist options
  • Save PanagiotisPtr/dcfd83577e383a8c6000132eff2e3f0d to your computer and use it in GitHub Desktop.
Save PanagiotisPtr/dcfd83577e383a8c6000132eff2e3f0d to your computer and use it in GitHub Desktop.
Simple examples of parallel and serialized algorithms in C++
#ifndef PPA_H
#define PPA_H
#include "ppa_impl.h"
namespace ppa {
template<
typename RandomIt,
typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type average(RandomIt first, RandomIt last, exec_policy policy = exec_policy::sequenced){
if(policy == exec_policy::parallel)
return parallel_average(first, last);
else
return sequenced_average(first, last);
}
template<
typename RandomIt,
typename Function
>
void for_each(RandomIt first, RandomIt last, Function func,
exec_policy policy = exec_policy::sequenced){
if(policy == exec_policy::parallel)
parallel_for_each(first, last, func);
else
sequenced_for_each(first, last, func);
}
}
#endif
#ifndef PPA_IMPL_H
#define PPA_IMPL_H
#include <algorithm>
#include <list>
#include <iterator>
#include <future>
#include <atomic>
namespace ppa {
static const size_t CHUNK_SIZE = 100000;
static const size_t num_threads = std::thread::hardware_concurrency();
enum class exec_policy {
parallel,
sequenced
};
template<
typename RandomIt,
typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type sequenced_average(RandomIt first, RandomIt last){
value_type sum = 0;
value_type num_elements = std::distance(first, last);
while(first != last)
sum += *first++;
return num_elements == 0 ? 0 : sum / num_elements;
}
template<
typename RandomIt,
typename value_type = typename std::iterator_traits<RandomIt>::value_type
>
value_type parallel_average(RandomIt first, RandomIt last){
size_t chunk_size = std::distance(first, last)/(num_threads);
chunk_size = chunk_size == 0 ? std::distance(first, last) : chunk_size;
std::list<std::future<value_type> > tasks;
for(size_t i = 0; i < num_threads-1; i++){
RandomIt next = first;
std::advance(next, chunk_size);
tasks.push_back(async(sequenced_average<RandomIt, value_type>, first, next));
first = next;
}
value_type result = sequenced_average(first, last);
for(std::future<value_type>& f : tasks)
result += f.get();
return result / num_threads;
}
/*
TO-DO:
For all bellow algorithms change them to iterative versions(more cache effecient)
like the average algorithm and add execution polity
*/
class Finder {
public:
Finder() : done(false) {}
template<typename RandomIt, typename T>
RandomIt parallel_find(RandomIt first, RandomIt last, T value){
done = false;
RandomIt res = parallel_find_impl(first, last, value);
done = true;
return res;
}
private:
std::atomic<bool> done;
template<typename RandomIt, typename T>
RandomIt parallel_find_impl(RandomIt first, RandomIt last, T value){
if(std::distance(first, last) <= CHUNK_SIZE)
return parallel_find_with_flag(first, last, value);
RandomIt mid = first;
std::advance(mid, std::distance(first, last)/2);
std::future<RandomIt> right(
std::async(&parallel_find_impl<RandomIt, T>, this, mid, last, value)
);
RandomIt res = parallel_find_impl(first, mid, value);
return (res == mid ? right.get() : res);
}
template<typename RandomIt, typename T>
RandomIt parallel_find_with_flag(RandomIt first, RandomIt last, T value){
while(first != last && !done.load()){
if(*first == value){
done = true;
return first;
}
first++;
}
return last;
}
};
template<typename RandomIt, typename T>
RandomIt parallel_find(RandomIt first, RandomIt last, T value){
Finder f;
return f.parallel_find(first, last, value);
}
template<
typename RandomIt,
typename Function
>
void sequenced_for_each(RandomIt first, RandomIt last, Function func){
std::for_each(first, last, func);
}
// Function func needs to be void
template<
typename RandomIt,
typename Function
>
void parallel_for_each(RandomIt first, RandomIt last, Function func){
size_t chunk_size = std::distance(first, last)/(num_threads);
chunk_size = chunk_size == 0 ? std::distance(first, last) : chunk_size;
std::list<std::future<void> > tasks;
for(size_t i = 0; i < num_threads-1; i++){
RandomIt next = first;
std::advance(next, chunk_size);
tasks.push_back(std::async(
sequenced_for_each<RandomIt, Function>, first, next, func)
);
first = next;
}
sequenced_for_each(first, last, func);
for(std::future<void>& f : tasks)
f.get();
}
/*
ppa::parallel_copy does not accept
std::back_insert_iterators because it needs
to have enough space for the vector
(can't use std::advance with back_insert_iterator)
*/
template<
typename InputIt,
typename OutputIt
>
void parallel_copy(InputIt first, InputIt last, OutputIt d_iter){
if(std::distance(first, last) <= CHUNK_SIZE){
std::copy(first, last, d_iter);
return;
}
InputIt mid = first;
OutputIt mid_d_iter = d_iter;
std::advance(mid, std::distance(first, last)/2);
std::advance(mid_d_iter, std::distance(first, last)/2);
std::future<void> right(
std::async(&parallel_copy<InputIt, OutputIt>, mid, last, mid_d_iter)
);
parallel_copy(first, mid, d_iter);
right.get();
}
class Sorter {
public:
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
>
static void parallel_quicksort(RandomIt first, RandomIt last, Compare comp = {}){
if(std::distance(first, last) <= CHUNK_SIZE){
quicksort(first, last, comp);
return;
}
RandomIt pivot = partition(first, last, comp);
std::future<void> left(
std::async(&parallel_quicksort<RandomIt, Compare>, first, pivot, comp)
);
pivot++;
parallel_quicksort(pivot, last, comp);
left.get();
}
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
>
static void quicksort(RandomIt first, RandomIt last, Compare comp = {}){
if(distance(first, last) <= 1)
return;
// partition
RandomIt pivot = partition(first, last, comp);
quicksort(first, pivot, comp);
pivot++;
quicksort(pivot, last, comp);
}
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
>
static void parallel_merge_sort(RandomIt first, RandomIt last, Compare comp = {}){
if(std::distance(first, last) <= CHUNK_SIZE){
merge_sort(first, last, comp);
return;
}
RandomIt mid = first;
std::advance(mid, std::distance(first, last)/2);
std::future<void> left(std::async(&parallel_merge_sort<RandomIt, Compare>, first, mid, comp));
parallel_merge_sort(mid, last, comp);
left.get();
merge(first, mid, last, comp);
}
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
>
static void merge_sort(RandomIt first, RandomIt last, Compare comp = {}){
if(std::distance(first, last) <= 1)
return;
RandomIt mid = first;
std::advance(mid, std::distance(first, last)/2);
merge_sort(first, mid, comp);
merge_sort(mid, last, comp);
merge(first, mid, last, comp);
}
private:
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>
>
static RandomIt partition(RandomIt first, RandomIt last, Compare comp = {}){
RandomIt front = first+1;
RandomIt back = first+1;
for(front; front != last; front++){
if(comp(*front, *first)){
std::swap(*back, *front);
back++;
}
}
back--;
std::swap(*first, *back);
return back;
}
template<
typename RandomIt,
typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>,
typename Container = std::list<typename std::iterator_traits<RandomIt>::value_type>
>
static void merge(RandomIt first, RandomIt mid, RandomIt last, Compare comp = {}){
RandomIt i = first;
RandomIt j = mid;
Container res;
std::back_insert_iterator<Container> it(res);
while(i != mid && j != last){
if(comp(*i, *j))
*it++ = *i++;
else
*it++ = *j++;
}
while(i != mid)
*it++ = *i++;
while(j != last)
*it++ = *j++;
std::copy(std::begin(res), std::end(res), first);
}
};
template<typename RandomIt>
void sort(RandomIt first, RandomIt last){
Sorter::merge_sort(first, last);
}
template<typename RandomIt>
void parallel_sort(RandomIt first, RandomIt last){
Sorter::parallel_merge_sort(first, last);
}
template<typename RandomIt>
void quicksort(RandomIt first, RandomIt last){
Sorter::quicksort(first, last);
}
template<typename RandomIt>
void parallel_quicksort(RandomIt first, RandomIt last){
Sorter::parallel_quicksort(first, last);
}
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment